login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A211318
Triangle read by rows: number of permutations of 1..n by length l of longest run (n >= 1, 1 <= l <= n).
16
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.
Sequence in context: A293815 A373691 A339941 * A324239 A274706 A037035
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, May 02 2012, based on computations by Sean A. Irvine.
STATUS
approved