A309807 - OEIS

A309807

Number of permutations sigma of [n] such that sigma(k)/k > sigma(k+1)/(k+1) for 1 <= k <= n-1.

1, 1, 1, 2, 3, 6, 9, 19, 30, 60, 108, 222, 388, 874, 1601, 3244, 6437, 14056, 26545, 57326, 109333, 232751, 481137, 1002039, 1911740, 4261276, 8678424, 17734328, 36186279, 77402058, 154454851, 340848002, 691228119, 1460761640

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

a(n+1) is equal to the number of permutations sigma of [n] such that sigma(k)/k >= sigma(k+1)/(k+1) for 1 <= k <= n-1.

LINKS

Table of n, a(n) for n=0..33.

Mathematics.StackExchange, Why are the numbers of two different permutations the same?, Mar 07 2020.

EXAMPLE

In case of n = 3.

----+----------

1 | [2, 3, 1]

2 | [3, 2, 1]

In case of n = 4.

----+-------------

1 | [2, 3, 4, 1]

2 | [3, 4, 2, 1]

3 | [4, 3, 2, 1]

PROG

(Ruby)

def A(n)

(1..n).to_a.permutation.select{|i| (1..n - 1).all?{|j| i[j - 1] * (j + 1) > i[j] * j}}.size

end

def A309807(n)

(0..n).map{|i| A(i)}

end

p A309807(10)

CROSSREFS

Row sums of A333310.

Cf. A330432, A332954.

Sequence in context: A060172 A193196 A319755 * A003243 A320160 A055873

Adjacent sequences: A309804 A309805 A309806 * A309808 A309809 A309810

KEYWORD

nonn,more

AUTHOR

Seiichi Manyama, Mar 03 2020

EXTENSIONS

a(19)-a(22) from Alois P. Heinz, Mar 03 2020

a(23)-a(25) from Giovanni Resta, Mar 04 2020

a(26)-a(33) from Bert Dobbelaere, Mar 15 2020

STATUS

approved