login
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 both the 132- and the 231-pattern is equal to k.
0

%I #11 Sep 18 2017 13:06:47

%S 1,0,2,0,2,4,0,8,8,8,0,40,40,24,16,0,240,240,144,64,32,0,1680,1680,

%T 1008,448,160,64,0,13440,13440,8064,3584,1280,384,128,0,120960,120960,

%U 72576,32256,11520,3456,896,256,0,1209600,1209600,725760,322560,115200,34560

%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 both the 132- and the 231-pattern is equal to k.

%C Row sums are the factorial numbers (A000142).

%C T(n,2)=n!/3 for n>=3 and T(n,3)=n!/3 for n>=4 (A002301).

%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) = (k-1)*n!*2^(k-1)*/(k+1)! for k<n; T(n, n)=2^(n-1).

%e T(4,3)=8 because 1243, 1342, 2143, 2341, 3142, 3241, 4132 and 4231 are the only permutations of [4] in which the length of the longest initial segment avoiding both the 132- and the 231-pattern is equal to 3 (i.e. the first three entries contain neither the 132- nor the 231-pattern but all four of them contain at least one of these two patterns).

%e Triangle starts:

%e 1;

%e 0,2;

%e 0,2,4;

%e 0,8,8,8;

%e 0,40,40,24,16;

%e 0,240,240,144,64,32;

%e 0,1680,1680,1008,448,160,64;

%Y Cf. A000142, A002301.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_ and Warren P. Johnson (wjohnson(AT)bates.edu), Apr 10 2004