|
%I #36 Jan 22 2020 23:30:58
%S 1,2,1,7,4,1,32,21,6,1,180,130,41,8,1,1200,930,312,67,10,1,9240,7560,
%T 2646,602,99,12,1,80640,68880,24864,5880,1024,137,14,1,786240,695520,
%U 257040,62496,11304,1602,181,16,1,8467200,7711200,2903040,720720,133920,19710,2360,231,18,1
%N Triangle read by rows: T(n,k) = the number of ascending runs of length k in the permutations of [n] for k <= n.
%C Also T(n,k) = number of rising sequences of length k among all permutations. E.g., T(4,3)=6 because in the 24 permutations of n=4, there are 6 rising sequences of length 3: {1,2,3} in {1,2,4,3}, {1,2,3} in {1,4,2,3}, {2,3,4} in {2,1,3,4}, {2,3,4} in {2,3,1,4}, {2,3,4} in {2,3,4,1}, {1,2,3} in {4,1,2,3}. - _Harlan J. Brothers_, Jul 23 2008
%C Further comments and formulas from _Harlan J. Brothers_, Jul 23 2008: (Start)
%C The n-th row sums to (n+1)!/2, consistent with total count implied by the n-th row in the table of Eulerians, A008292.
%C Generating this triangle through use of the diagonal polynomials allows one to produce an arbitrary number of "imaginary" columns corresponding to runs of length 0, -1, -2, etc. These columns match A001286, A001048 and the factorial function respectively.
%C As n->inf, there is a limiting value for the count of each length expressed as a fraction of all rising sequences in the permutations of n. The numerators of the set of limit fractions are given by A028387 and the denominators by A001710.
%C As a table of diagonals d[i]:
%C d[1][n] = 1
%C d[2][n] = 2n
%C d[3][n] = 3n^2 + 5n - 1
%C d[4][n] = 4n^3 + 18n^2 + 16n - 6
%C d[5][n] = 5n^4 + 42n^3 + 106n^2 + 63n - 36
%C d[6][n] = 6n^5 + 80n^4 + 374n^3 + 688n^2 + 292n - 240
%C T[n,k] = n!(n(k^2 + k - 1) - k(k^2 - 4) + 1)/(k+2)! + floor(k/n)(1/(k(k+3)+2)), 0 < k <= n. (End)
%D C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131.
%D Donald E. Knuth. The Art of Computer Programming. Vol. 2. Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms, Third edition, Section 3.3.2, p.67.
%H Alois P. Heinz, <a href="/A122843/b122843.txt">Rows n = 1..141, flattened</a>
%H Persi Diaconis, <a href="http://www-stat.stanford.edu/~cgates/PERSI/papers/Riffle.pdf">Mathematical developments from the analysis of riffle shuffling</a>, p.4.
%H Francis Edward Su, <a href="http://www.math.hmc.edu/funfacts/ffiles/20001.4-6.shtml">Rising Sequences in Card Shuffling</a>
%F T(n,k) = n!(n(k(k+1)-1) - k(k-2)(k+2) + 1)/(k+2)! for 0 < k < n; T(n,n) = 1; T(n,k) = A122844(n,k) - A122844(n,k+1).
%F T(n,k) = A008304(n,k) for k > n/2. - _Alois P. Heinz_, Oct 17 2013
%e T(3,2) = 4: There are 4 ascending runs of length 2 in the permutations of [3], namely 13 in 132 and in 213, 23 in 231, 12 in 312.
%e Triangle begins:
%e 1;
%e 2, 1;
%e 7, 4, 1;
%e 32, 21, 6, 1;
%e 180, 130, 41, 8, 1;
%e ...
%p T:= (n, k)-> `if`(n=k, 1, n!/(k+1)!*(k*(n-k+1)+1
%p -((k+1)*(n-k)+1)/(k+2))):
%p seq(seq(T(n,k), k=1..n), n=1..10); # _Alois P. Heinz_, Sep 11 2013
%t Table[n!((n(k(k+1)-1)-k(k-2)(k+2)+1))/(k+2)!+Floor[k/n]1/(k(k+3)+2),{n,1,10},{k,1,n}]//TableForm (* _Harlan J. Brothers_, Jul 23 2008 *)
%Y Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710.
%Y Cf. A122844, A001710, A006157, A005460.
%Y T(2n+j,n+j) for j = 0..10 gives A230382, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.
%K easy,nonn,tabl
%O 1,2
%A _David Scambler_, Sep 13 2006
|
