login
Triangle read by rows: number of permutations of 1..n by length of longest run.
16

%I #36 Aug 18 2018 07:24:11

%S 2,2,4,2,12,10,2,16,70,32,2,20,134,442,122,2,24,198,1164,3108,544,2,

%T 28,274,2048,10982,24216,2770,2,32,362,3204,22468,112354,208586,15872,

%U 2,36,462,4720,39420,264538,1245676,1972904,101042

%N Triangle read by rows: number of permutations of 1..n by length of longest run.

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

%H Alois P. Heinz, <a href="/A010026/b010026.txt">Rows n = 2..70, flattened</a>

%e Triangle begins:

%e 2,

%e 2, 4,

%e 2, 12, 10,

%e 2, 16, 70, 32,

%e 2, 20, 134, 442, 122,

%e 2, 24, 198, 1164, 3108, 544,

%e 2, 28, 274, 2048, 10982, 24216, 2770,

%e 2, 32, 362, 3204, 22468, 112354, 208586, 15872, ...

%e The row "2, 12, 10" for example means that there are two permutations of [1..4] in which the longest run up or down has length 4, 12 in which the longest run has length 3, and 10 in which the longest run has length 2.

%e The following table, computed by _Sean A. Irvine_, May 02, 2012, gives an extended version of the triangle, oriented the right way round (cf. A211318), and corrects errors in David Kendall and Barton:

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

%e ----------------------------

%e 1 [0, 1]

%e 2 [0, 0, 2]

%e 3 [0, 0, 4, 2]

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

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

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

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

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

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

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

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

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

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

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

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

%t (* This program is unsuited for a large number of terms *) f[p_List] := Max[Length /@ Split[Differences[p], #1*#2 > 0 &]] + 1; row[n_] := Sort[Tally[f /@ Permutations[Range[n]]], First[#1] > First[#2] &][[All, 2]]; Table[rn = row[n]; Print["n = ", n, " ", rn]; rn, {n, 2, 10}] // Flatten (* _Jean-François Alcover_, Mar 12 2014 *)

%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 Table[T[n, n-lg+1], {n, 2, 10}, {lg, 1, n-1}] // Flatten (* _Jean-François Alcover_, Aug 18 2018, after _Alois P. Heinz_ *)

%Y Cf. A211318. Diagonals give: A001250, A001251, A001252, A001253, A230129, A230130, A230131, A230132, A230133.

%K nonn,tabl,nice

%O 2,1

%A _N. J. A. Sloane_

%E Edited by _N. J. A. Sloane_, May 02 2012