A211318 Triangle read by rows: number of permutations of 1..n by length l of longest run (n >= 1, 1 <= l <= n).

1, 0, 2, 0, 4, 2, 0, 10, 12, 2, 0, 32, 70, 16, 2, 0, 122, 442, 134, 20, 2, 0, 544, 3108, 1164, 198, 24, 2, 0, 2770, 24216, 10982, 2048, 274, 28, 2, 0, 15872, 208586, 112354, 22468, 3204, 362, 32, 2, 0, 101042, 1972904, 1245676, 264538, 39420, 4720, 462, 36, 2, 0

Offset

1,3

References

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262. (Contains errors for n >= 13.)

Sean A. Irvine, Posting to Sequence Fans Mailing List, May 02 2012

Links

Alois P. Heinz, Rows n = 1..70, flattened (rows n = 1..16 from Wouter Meeussen)

Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv:1205.4581 [math.CO], 2012-2013. [From N. J. A. Sloane, Oct 23 2012]

Example

Triangle begins:
n l=1, l=2, l=3, etc...
1 [1]
2 [0, 2]
3 [0, 4, 2]
4 [0, 10, 12, 2]
5 [0, 32, 70, 16, 2]
6 [0, 122, 442, 134, 20, 2]
7 [0, 544, 3108, 1164, 198, 24, 2]
8 [0, 2770, 24216, 10982, 2048, 274, 28, 2]
9 [0, 15872, 208586, 112354, 22468, 3204, 362, 32, 2]
10 [0, 101042, 1972904, 1245676, 264538, 39420, 4720, 462, 36, 2]
11 [0, 707584, 20373338, 14909340, 3340962, 514296, 64020, 6644, 574, 40, 2]
12 [0, 5405530, 228346522, 191916532, 45173518, 7137818, 913440, 98472, 9024, 698, 44, 2]
13 [0, 44736512, 2763212980, 2646100822, 652209564, 105318770, 13760472, 1523808, 145080, 11908, 834, 48, 2]
14 [0, 398721962, 35926266244, 38932850396, 10024669626, 1649355338, 219040274, 24744720, 2419872, 206388, 15344, 982, 52, 2]
15 [0, 3807514624, 499676669254, 609137502242, 163546399460, 27356466626, 3681354658, 422335056, 42129360, 3690960, 285180, 19380, 1142, 56, 2],
...
More rows than usual are shown, in order to correct errors in David, Kendall and Barton.

Mathematica

<<DiscreteMath`Combinatorica`; permruns[perm_List] := Max[Length /@ Split[Sign[Rest[perm] - Drop[perm, -1]]/2 + 1/2]];
Table[CoefficientList[Tr[Apply[Times, Map[(it=Tr[NumberOfTableaux[#]z^#& /@ (permruns[TableauxToPermutation[#, #]]& /@ Tableaux[#])])&, Union[{Length[#], First[#]}& /@ (Union[{#, TransposePartition[#]}]& /@ Partitions[n])], {-2}], {1}]], z], {n, 2, 6}] (* Wouter Meeussen, May 09 2012 *)
T[n_, length_] := Module[{g, b},
g[u_, o_, t_] := g[u, o, t] = If[u+o == 0, 1, Sum[g[o + j - 1, u - j, 2], {j, 1, u}] + If[t<length, Sum[g[u + j - 1, o - j, t+1], {j, 1, o}], 0]];
b[u_, o_, t_] := b[u, o, t] = If[t == length, g[u, o, t], Sum[b[o + j - 1, u - j, 2], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]]; Sum[b[j - 1, n - j, 1], {j, 1, n}]
];
T[n_ /; n>1, 1] = 0;
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 18 2018, after Alois P. Heinz *)

Crossrefs

Mirror image of triangle in A010026.

Columns l=2-10 give: A001250, A001251, A001252, A001253, A230129, A230130, A230131, A230132, A230133.

Sequence in context: A144289 A293815 A339941 * A324239 A274706 A037035

Adjacent sequences: A211315 A211316 A211317 * A211319 A211320 A211321

Keyword

nonn,tabl

Author

N. J. A. Sloane, May 02 2012, based on computations by Sean A. Irvine.

Status

approved