A180186 - OEIS

%I #6 Jul 23 2019 02:03:24

%S 1,1,0,1,1,0,2,3,0,9,8,3,44,45,12,1,265,264,90,8,1854,1855,660,90,2,

%T 14833,14832,5565,880,45,133496,133497,51912,9275,660,9,1334961,

%U 1334960,533988,103824,9275,264,14684570,14684571,6007320,1245972,129780,5565

%N Triangle read by rows: T(n,k) is the number of permutations of [n] starting with 1, having no 3-sequences and having k successions (0 <= k <= floor(n/2)); a succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

%C Row n has 1+floor(n/2) entries.

%C Sum of entries in row n is A165961(n).

%C T(n,0) = d(n-1).

%C Sum_{k>=0} k*T(n,k) = A180187(n).

%C From _Emeric Deutsch_, Sep 07 2010: (Start)

%C T(n,k) is also the number of permutations of [n-1] with k fixed points, no two of them adjacent. Example: T(5,2)=3 because we have 1432, 1324, and 3214.

%C (End)

%F T(n,k) = binomial(n-k,k)*d(n-k-1), where d(j) = A000166(j) are the derangement numbers.

%e T(5,2)=3 because we have 12453, 12534, and 14523.

%e Triangle starts:

%e     1;

%e     1;

%e     0,   1;

%e     1,   0;

%e     2,   3,   0;

%e     9,   8,   3;

%e    44,  45,  12,  1;

%e   265, 264,  90,  8;

%p d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n, k) if n = 0 and k = 0 then 1 elif k <= (1/2)*n then binomial(n-k, k)*d[n-1-k] else 0 end if end proc: for n from 0 to 12 do seq(a(n, k), k = 0 .. (1/2)*n) end do; # yields sequence in triangular form

%Y Cf. A000166, A165961, A180187.

%K nonn,tabf

%O 0,7

%A _Emeric Deutsch_, Sep 06 2010