

A122843


Triangle read by rows: T(n,k) = the number of ascending runs of length k in the permutations of [n] for k <= n.


17



1, 2, 1, 7, 4, 1, 32, 21, 6, 1, 180, 130, 41, 8, 1, 1200, 930, 312, 67, 10, 1, 9240, 7560, 2646, 602, 99, 12, 1, 80640, 68880, 24864, 5880, 1024, 137, 14, 1, 786240, 695520, 257040, 62496, 11304, 1602, 181, 16, 1, 8467200, 7711200, 2903040, 720720, 133920, 19710, 2360, 231, 18, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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
Further comments and formulae from Harlan J. Brothers, Jul 23 2008 (Start): The nth row sums to (n+1)!/2, consistent with total count implied by the nth row in the table of Eulerians, A008292.
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.
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.
As a table of diagonals d[i]:
d[1][n]=1
d[2][n]=2n
d[3][n]=3n^2+5n1
d[4][n]=4n^3+18n^2+16n6
d[5][n]=5n^4+42n^3+106n^2+63n36
d[6][n]=6n^5+80n^4+374n^3+688n^2+292n240
T[n,k]= n!(n(k^2+k1)k(k^24)+1)/(k+2)!+Floor[k/n](1/(k(k+3)+2)), 0<k<=n. E.f.g. for column n: (x^(n+1)((n^2+3n+1)x2(n^2+2n)))/((n+2)!(x1)^2) (End)


REFERENCES

Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, http://wwwstat.stanford.edu/~cgates/PERSI/papers/Riffle.pdf, p.4.
C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120131.


LINKS

Alois P. Heinz, Rows n = 1..141, flattened
Francis Edward Su, Rising Sequences in Card Shuffling


FORMULA

T(n,k) = n![(n(k(k+1)1)  k(k2)(k+2) + 1]/(k+2)! for 0<k<n; T(n,n) = 1; T(n,k) = A122844(n,k)  A122844(n,k+1).
T(n,k) = A008304(n,k) for k > n/2.  Alois P. Heinz, Oct 17 2013


EXAMPLE

Triangle begins:
1
2 1
7 4 1 (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. T(3,2) = 4)
32,21,6,1,
180,130,41,8,1
...


MAPLE

T:= (n, k)> `if`(n=k, 1, n!/(k+1)!*(k*(nk+1)+1
((k+1)*(nk)+1)/(k+2))):
seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Sep 11 2013


MATHEMATICA

Table[n!((n(k(k+1)1)k(k2)(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


CROSSREFS

Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710.
Cf. A122844, A001710, A006157, A005460.
T(2n+j,n+j) for j=010 gives: A230382, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.
Sequence in context: A177011 A092276 A011274 * A167196 A241881 A107865
Adjacent sequences: A122840 A122841 A122842 * A122844 A122845 A122846


KEYWORD

easy,nonn,tabl


AUTHOR

David Scambler, Sep 13 2006


STATUS

approved



