OFFSET
0,3
COMMENTS
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..750 (first 101 terms from John Tyler Rascoe)
FORMULA
G.f.: 1 + Sum_{i>0} A(x,i) where A(x,i) = 1/(1-x^i) * (x^i + Sum_{z>0} ( ((x^i)/(1-x^i) * (-1 + Product_{j>i} (1/(1-x^j))))^z )) is the g.f. for compositions of this kind with all leaders equal to i. - John Tyler Rascoe, Jul 25 2024
EXAMPLE
The composition (1,3,1,4,1,2,2,1) has maximal weakly increasing subsequences ((1,3),(1,4),(1,2,2),(1)), with leaders (1,1,1,1), so is counted under a(15).
The a(0) = 1 through a(6) = 19 compositions:
() (1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(111) (22) (23) (24)
(112) (113) (33)
(121) (122) (114)
(1111) (131) (123)
(1112) (141)
(1121) (222)
(1211) (1113)
(11111) (1122)
(1131)
(1212)
(1221)
(1311)
(11112)
(11121)
(11211)
(12111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], SameQ@@First/@Split[#, LessEqual]&]], {n, 0, 15}]
PROG
(PARI)
C_x(N) = {my(x='x+O('x^N), h=1+sum(i=1, N, 1/(1-x^i)*(x^i+sum(z=1, N-i+1, (x^i/(1-x^i)*(-1+(1/prod(j=i+1, N-i, 1-x^j))))^z)))); Vec(h)}
C_x(40) \\ John Tyler Rascoe, Jul 25 2024
CROSSREFS
Types of runs (instead of weakly increasing):
Types of run-leaders (instead of identical):
- For strictly decreasing leaders we appear to have A188920.
- For weakly decreasing leaders we appear to have A189076.
- For strictly increasing leaders we have A374634.
- For weakly increasing leaders we have A374635.
A003242 counts anti-run compositions.
A011782 counts compositions.
A335456 counts patterns matched by compositions.
A374637 counts compositions by sum of leaders of weakly increasing runs.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 23 2024
EXTENSIONS
a(26) onwards from John Tyler Rascoe, Jul 25 2024
STATUS
approved