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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008304 Triangle read by rows: T(n,k) (n>=1; 1<=k<=n) is the number of permutations of [n] in which the longest increasing run has length k. 27
1, 1, 1, 1, 4, 1, 1, 16, 6, 1, 1, 69, 41, 8, 1, 1, 348, 293, 67, 10, 1, 1, 2016, 2309, 602, 99, 12, 1, 1, 13357, 19975, 5811, 1024, 137, 14, 1, 1, 99376, 189524, 60875, 11304, 1602, 181, 16, 1, 1, 822040, 1960041, 690729, 133669, 19710, 2360, 231, 18, 1, 1, 7477161 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Row n has n terms.

REFERENCES

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1.

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581, 2012. - From N. J. A. Sloane, Oct 23 2012

D. W. Wilson, Extended tables for A008304 and A064315

FORMULA

E.g.f. of column k: 1/Sum_{n>=0} ((k+1)*n+1-x)*x^((k+1)*n)/((k+1)*n+1)! - 1/Sum_{n>=0} (k*n+1-x)*x^(k*n)/(k*n+1)!. - Alois P. Heinz, Oct 13 2013

T(n,k) = A122843(n,k) for k > n/2. - Alois P. Heinz, Oct 17 2013

EXAMPLE

1;

1,   1;

1,   4,   1;

1,  16,   6,  1;

1,  69,  41,  8,  1;

1, 348, 293, 67, 10,  1;

...

T(3,2) = 4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround runs of length 2.

MAPLE

b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,

      `if`(max(t, u)+o<k, 0, add(b(u+j-1, o-j, t+1, k), j=1..o)+

      add(b(u-j, o+j-1, 1, k), j=1..u)))

    end:

T:= (n, k)-> b(0, n, 0, k) -b(0, n, 0, k+1):

seq(seq(T(n, k), k=1..n), n=1..15);  # Alois P. Heinz, Oct 16 2013

MATHEMATICA

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u]+o < k, 0, Sum[b[u+j-1, o-j, t+1, k], {j, 1, o}] + Sum[b[u-j, o+j-1, 1, k], {j, 1, u}]]]; T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k+1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-Fran├žois Alcover, Jan 10 2014, translated from Alois P. Heinz's Maple code *) '

(*additional code*)

nn=12; a[r_]:=Apply[Plus, Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i, {i, 1, r}]), {x, 0, nn}]][[n]]/(n+r)!, {n, 1, nn-r}]]/.y->-1; Map[Select[#, #>0&]&, Transpose[Prepend[Table[Drop[Range[0, nn]! CoefficientList[Series[1/(1-x-a[n+1])-1/(1-x-a[n]), {x, 0, nn}], x], 1], {n, 1, 8}], Table[1, {nn}]]]]//Grid (* Geoffrey Critzer, Feb 25 2014 *)

CROSSREFS

Row sums give A000142. Sum_{k=1..n} k*T(n,k) = A064314(n). Cf. A064315.

Columns k=1-10 give: A000012, A000303, A000402, A000434, A000456, A000467, A230055, A230234, A230235, A230236.

T(2n+j,n+j) for j=0-10 gives: A230341, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.

Sequence in context: A155826 A010320 A152571 * A203846 A118185 A176483

Adjacent sequences:  A008301 A008302 A008303 * A008305 A008306 A008307

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from David W. Wilson, Sep 07 2001

Better description from Emeric Deutsch, May 08 2004

STATUS

approved

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 May 23 18:24 EDT 2017. Contains 286926 sequences.