login
Number of permutations p of [n] such that for each distance d in [n-1] there is at least one index i in [n-d] with p(i)>p(i+d).
2

%I #24 Feb 22 2024 20:00:21

%S 1,1,1,3,11,55,319,2233,17641,158769,1578667,17365337,207865289,

%T 2702248757,37786779669,566801695035,9063808803203,154084749654451

%N Number of permutations p of [n] such that for each distance d in [n-1] there is at least one index i in [n-d] with p(i)>p(i+d).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/K-sorted_sequence">K-sorted sequence</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%F a(n) = A370507(n,n).

%F a(n) = A370506(n,1) for n>=1.

%e a(0) = 1: the empty permutation.

%e a(1) = 1: 1.

%e a(2) = 1: 21.

%e a(3) = 3: 231, 312, 321.

%e a(4) = 11: 2341, 2431, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

%e a(5) = 55: 23451, 23541, 24351, 24531, ..., 54213, 54231, 54312, 54321.

%e a(6) = 319: 234561, 234651, 235461, 235641, ..., 654213, 654231, 654312, 654321.

%Y Main diagonal of A370507.

%Y Column k=1 of A370506 (for n>=1).

%Y Cf. A008302.

%K nonn,more

%O 0,4

%A _Alois P. Heinz_, Feb 20 2024

%E a(14)-a(16) from _Martin Ehrenstein_, Feb 22 2024

%E a(17) from _Alois P. Heinz_, Feb 22 2024