login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A268699 Total number of sequences with c_j copies of j and longest increasing subsequence of length k summed over all compositions [c_1, c_2, ..., c_k] of n. 4
1, 1, 2, 6, 22, 95, 471, 2618, 16052, 107313, 775045, 6002106, 49536510, 433485429, 4004680967, 38912323570, 396393445096, 4221367056961, 46878865762185, 541660919690866, 6498811587848690, 80818650742133717, 1040037672241415947, 13829246515918840106 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..60

J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

EXAMPLE

The compositions of 4 are [1,1,1,1], [2,1,1], [1,2,1], [1,1,2], [2,2], [3,1], [1,3], [4] giving the a(4) = 22 sequences: 1234, 1123, 1213, 1231, 1223, 2123, 1232, 1233, 1323, 3123, 1122, 1212, 1221, 2112, 2121, 1112, 1121, 1211, 1222, 2122, 2212, 1111.

MAPLE

c:= l-> f(l)*nops(l)!/(v-> mul(coeff(v, x, j)!,

        j=0..degree(v)))(add(x^i, i=l)):

g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*

      binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]

      -1, l))), j=1..nops(l)-1))(add(i, i=l))

    end:

f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(

         n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):

h:= (n, i, l)-> `if`(n=0 or i=1, c([1$n, l[]]), h(n, i-1, l)+

                `if`(i>n, 0, h(n-i, i, [i, l[]]))):

a:= n-> h(n$2, []):

seq(a(n), n=0..25);

CROSSREFS

Cf. A047909, A268698, A268700, A268701.

Sequence in context: A087959 A292096 A006871 * A253948 A248836 A351919

Adjacent sequences:  A268696 A268697 A268698 * A268700 A268701 A268702

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Feb 11 2016

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 13 20:26 EDT 2022. Contains 356107 sequences. (Running on oeis4.)