|
%I #7 Sep 18 2017 13:06:34
%S 1,0,2,0,3,3,0,12,7,5,0,60,35,17,8,0,360,210,102,35,13,0,2520,1470,
%T 714,245,70,21,0,20160,11760,5712,1960,560,134,34,0,181440,105840,
%U 51408,17640,5040,1206,251,55,0,1814400,1058400,514080,176400,50400,12060
%N Triangle read by rows: T(n,k) is the number of permutations p of [n] in which the length of the longest initial segment avoiding the 123-, the 132- and the 321-pattern is equal to k.
%C Row sums are the factorial numbers (A000142).
%C Diagonal yields the Fibonacci numbers A000045.
%H E. Deutsch and W. P. Johnson, <a href="http://www.jstor.org/stable/3219101">Create your own permutation statistics</a>, Math. Mag., 77, 130-134, 2004.
%H R. Simion and F. W. Schmidt, <a href="https://doi.org/10.1016/S0195-6698(85)80052-4">Restricted permutations</a>, European J. Combin., 6, 383-406, 1985.
%F T(n, k) = n!*[(k+1)fibonacci(k+1)-fibonacci(k+2)]/(k+1)! for 1<=k<=n-1; T(1, 1)=1; T(n, n)=fibonacci(n+1).
%e T(4,3)=7 because the permutations 4132, 3124, 2413, 4213, 2314 and 3214 do not avoid all three patterns 123, 132 and 213, but their initial segments of length three, namely 413, 312, 241, 421, 231 and 321, do.
%e Triangle begins:
%e 1;
%e 0,2;
%e 0,3,3;
%e 0,12,7,5;
%e 0,60,35,17,8;
%e 0,360,210,102,35,13;
%e 0,2520,1470,714,245,70,21;
%p with(combinat): T:=proc(n,k) if n=1 and k=1 then 1 elif n=1 then 0 elif k=1 then 0 elif k=n then fibonacci(n+1) elif k>0 and k<n then n!*((k+1)*fibonacci(k+1)-fibonacci(k+2))/(k+1)! else 0 fi end: seq(seq(T(n,k),k=1..n),n=1..11);
%Y Cf. A000142, A000045.
%K nonn,tabl
%O 1,3
%A _Emeric Deutsch_, May 31 2004
|
