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

%I #45 Oct 27 2023 22:14:04

%S 1,0,2,0,4,2,0,10,12,2,0,32,70,16,2,0,122,442,134,20,2,0,544,3108,

%T 1164,198,24,2,0,2770,24216,10982,2048,274,28,2,0,15872,208586,112354,

%U 22468,3204,362,32,2,0,101042,1972904,1245676,264538,39420,4720,462,36,2,0

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

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

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

%H Alois P. Heinz, <a href="/A211318/b211318.txt">Rows n = 1..70, flattened</a> (rows n = 1..16 from Wouter Meeussen)

%H Max A. Alekseyev, <a href="http://arxiv.org/abs/1205.4581">On the number of permutations with bounded run lengths</a>, arXiv:1205.4581 [math.CO], 2012-2013. [From _N. J. A. Sloane_, Oct 23 2012]

%e Triangle begins:

%e n l=1, l=2, l=3, etc...

%e 1 [1]

%e 2 [0, 2]

%e 3 [0, 4, 2]

%e 4 [0, 10, 12, 2]

%e 5 [0, 32, 70, 16, 2]

%e 6 [0, 122, 442, 134, 20, 2]

%e 7 [0, 544, 3108, 1164, 198, 24, 2]

%e 8 [0, 2770, 24216, 10982, 2048, 274, 28, 2]

%e 9 [0, 15872, 208586, 112354, 22468, 3204, 362, 32, 2]

%e 10 [0, 101042, 1972904, 1245676, 264538, 39420, 4720, 462, 36, 2]

%e 11 [0, 707584, 20373338, 14909340, 3340962, 514296, 64020, 6644, 574, 40, 2]

%e 12 [0, 5405530, 228346522, 191916532, 45173518, 7137818, 913440, 98472, 9024, 698, 44, 2]

%e 13 [0, 44736512, 2763212980, 2646100822, 652209564, 105318770, 13760472, 1523808, 145080, 11908, 834, 48, 2]

%e 14 [0, 398721962, 35926266244, 38932850396, 10024669626, 1649355338, 219040274, 24744720, 2419872, 206388, 15344, 982, 52, 2]

%e 15 [0, 3807514624, 499676669254, 609137502242, 163546399460, 27356466626, 3681354658, 422335056, 42129360, 3690960, 285180, 19380, 1142, 56, 2],

%e ...

%e More rows than usual are shown, in order to correct errors in David, Kendall and Barton.

%t <<DiscreteMath`Combinatorica`; permruns[perm_List] := Max[Length /@ Split[Sign[Rest[perm] - Drop[perm, -1]]/2 + 1/2]];

%t 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 T[n_, length_] := Module[{g, b},

%t 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]];

%t 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 ];

%t T[n_ /; n>1, 1] = 0;

%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Aug 18 2018, after _Alois P. Heinz_ *)

%Y Mirror image of triangle in A010026.

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

%K nonn,tabl

%O 1,3

%A _N. J. A. Sloane_, May 02 2012, based on computations by _Sean A. Irvine_.