login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047887 Triangle of numbers T(n,k) = number of permutations of n things with longest increasing subsequence of length <=k (1<=k<=n). 5
1, 1, 2, 1, 5, 6, 1, 14, 23, 24, 1, 42, 103, 119, 120, 1, 132, 513, 694, 719, 720, 1, 429, 2761, 4582, 5003, 5039, 5040, 1, 1430, 15767, 33324, 39429, 40270, 40319, 40320, 1, 4862, 94359, 261808, 344837, 361302, 362815, 362879, 362880, 1, 16796 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

LINKS

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

Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.

EXAMPLE

Triangle T(n,k) begins:

1;

1,   2;

1,   5,    6;

1,  14,   23,   24;

1,  42,  103,  119,  120;

1, 132,  513,  694,  719,  720;

1, 429, 2761, 4582, 5003, 5039, 5040;

MATHEMATICA

h[l_] := Module[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];

g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Array[1 &, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Array[i &, j]]], {j, 0, n/i}]]];

T[n_] := Table[g[n - k, Min[n - k, k], {k}], {k, 1, n}] // Accumulate;

Table[T[n], {n, 1, 10}] // Flatten (* Jean-Fran├žois Alcover, Mar 24 2016, after Alois P. Heinz *)

CROSSREFS

Rows are partial sums of A047874. Cf. A047888.

Sequence in context: A260613 A179457 A107783 * A120986 A095801 A128567

Adjacent sequences:  A047884 A047885 A047886 * A047888 A047889 A047890

KEYWORD

nonn,easy,nice,tabl

AUTHOR

Eric Rains (rains(AT)caltech.edu), N. J. A. Sloane

EXTENSIONS

More terms from Naohiro Nomoto, Mar 01 2002

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 25 19:39 EST 2021. Contains 341618 sequences. (Running on oeis4.)