The OEIS is supported by the many generous donors to the OEIS Foundation. 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 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 formulas from Harlan J. Brothers, Jul 23 2008: (Start) 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. 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[n] = 1 d[n] = 2n d[n] = 3n^2 + 5n - 1 d[n] = 4n^3 + 18n^2 + 16n - 6 d[n] = 5n^4 + 42n^3 + 106n^2 + 63n - 36 d[n] = 6n^5 + 80n^4 + 374n^3 + 688n^2 + 292n - 240 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) REFERENCES C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131. 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. LINKS Alois P. Heinz, Rows n = 1..141, flattened Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, p.4. Francis Edward Su, Rising Sequences in Card Shuffling FORMULA 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). T(n,k) = A008304(n,k) for k > n/2. - Alois P. Heinz, Oct 17 2013 EXAMPLE T(3,2) = 4: There are 4 ascending runs of length 2 in the permutations of , namely 13 in 132 and in 213, 23 in 231, 12 in 312. Triangle begins: 1; 2, 1; 7, 4, 1; 32, 21, 6, 1; 180, 130, 41, 8, 1; ... MAPLE T:= (n, k)-> `if`(n=k, 1, n!/(k+1)!*(k*(n-k+1)+1 -((k+1)*(n-k)+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(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 *) CROSSREFS Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710. Cf. A122844, A001710, A006157, A005460. T(2n+j,n+j) for j = 0..10 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 01:03 EST 2023. Contains 367717 sequences. (Running on oeis4.)