login
Number A(n,k) of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.
11

%I #16 May 09 2019 18:27:15

%S 1,1,0,1,1,0,1,1,1,0,1,1,2,1,0,1,1,2,3,1,0,1,1,2,6,5,1,0,1,1,2,6,12,8,

%T 1,0,1,1,2,6,24,25,13,1,0,1,1,2,6,24,60,57,21,1,0,1,1,2,6,24,120,150,

%U 124,34,1,0,1,1,2,6,24,120,360,399,268,55,1,0

%N Number A(n,k) of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C The sequence of column k satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.

%H Alois P. Heinz, <a href="/A276837/b276837.txt">Antidiagonals n = 0..30, flattened</a>

%H Alice L. L. Gao, Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019

%F A(n,k+1) - A(n,k) = A263757(n,k) for n>0.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 2, 2, 2, 2, 2, 2, 2, ...

%e 0, 1, 3, 6, 6, 6, 6, 6, 6, ...

%e 0, 1, 5, 12, 24, 24, 24, 24, 24, ...

%e 0, 1, 8, 25, 60, 120, 120, 120, 120, ...

%e 0, 1, 13, 57, 150, 360, 720, 720, 720, ...

%e 0, 1, 21, 124, 399, 1050, 2520, 5040, 5040, ...

%e 0, 1, 34, 268, 1145, 3192, 8400, 20160, 40320, ...

%Y Columns k=0-10 give: A000007, A000012, A000045(n+1), A214663, A276838, A276839, A276840, A276841, A276842, A276843, A276844.

%Y Main diagonal gives A000142.

%Y Cf. A263757, A276719.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Sep 20 2016