login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I

%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): 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. E.f.g. for column n: (x^(n+1)((n^2+3n+1)x-2(n^2+2n)))/((n+2)!(x-1)^2) (End)

%D Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, http://www-stat.stanford.edu/~cgates/PERSI/papers/Riffle.pdf, p.4.

%D C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131.

%H Alois P. Heinz, <a href="/A122843/b122843.txt">Rows n = 1..141, flattened</a>

%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 Triangle begins:

%e 1

%e 2 1

%e 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)

%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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 00:18 EDT 2017. Contains 283983 sequences.