A092594 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.

1, 0, 2, 0, 2, 4, 0, 8, 8, 8, 0, 40, 40, 24, 16, 0, 240, 240, 144, 64, 32, 0, 1680, 1680, 1008, 448, 160, 64, 0, 13440, 13440, 8064, 3584, 1280, 384, 128, 0, 120960, 120960, 72576, 32256, 11520, 3456, 896, 256, 0, 1209600, 1209600, 725760, 322560, 115200, 34560

Offset

1,3

Comments

Row sums are the factorial numbers (A000142).

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

Links

Table of n, a(n) for n=1..52.

E. Deutsch and W. P. Johnson, Create your own permutation statistics, Math. Mag., 77, 130-134, 2004.

R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985.

Formula

T(n, k) = (k-1)*n!*2^(k-1)*/(k+1)! for k<n; T(n, n)=2^(n-1).

Example

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).
Triangle starts:
1;
0,2;
0,2,4;
0,8,8,8;
0,40,40,24,16;
0,240,240,144,64,32;
0,1680,1680,1008,448,160,64;

Crossrefs

Cf. A000142, A002301.

Sequence in context: A172040 A317327 A120557 * A092741 A347223 A338227

Adjacent sequences: A092591 A092592 A092593 * A092595 A092596 A092597

Keyword

nonn,tabl

Author

Emeric Deutsch and Warren P. Johnson (wjohnson(AT)bates.edu), Apr 10 2004

Status

approved