A332836 Number of compositions of n whose run-lengths are weakly increasing.

1, 1, 2, 4, 7, 12, 24, 40, 73, 128, 230, 399, 712, 1241, 2192, 3833, 6746, 11792, 20711, 36230, 63532, 111163, 194782, 340859, 596961, 1044748, 1829241, 3201427, 5604504, 9808976, 17170112, 30051470, 52601074, 92063629, 161140256, 282033124, 493637137, 863982135, 1512197655

Offset

0,3

Comments

A composition of n is a finite sequence of positive integers summing to n.

Also compositions whose run-lengths are weakly decreasing.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Example

The a(0) = 1 through a(5) = 12 compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (13)    (14)
                 (21)   (22)    (23)
                 (111)  (31)    (32)
                        (121)   (41)
                        (211)   (122)
                        (1111)  (131)
                                (212)
                                (311)
                                (1211)
                                (2111)
                                (11111)
For example, the composition (2,3,2,2,1,1,2,2,2) has run-lengths (1,1,2,2,3) so is counted under a(17).

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], LessEqual@@Length/@Split[#]&]], {n, 0, 10}]

Prog

(PARI)
step(M, m)={my(n=matsize(M)[1]); for(p=m+1, n, my(v=vector((p-1)\m, i, M[p-i*m, i]), s=vecsum(v)); M[p, ]+=vector(#M, i, s-if(i<=#v, v[i]))); M}
seq(n)={my(M=matrix(n+1, n, i, j, i==1)); for(m=1, n, M=step(M, m)); M[1, n]=0; vector(n+1, i, vecsum(M[i, ]))/(n-1)} \\ Andrew Howroyd, Dec 31 2020

Crossrefs

The version for the compositions themselves (not run-lengths) is A000041.

The case of partitions is A100883.

The case of unsorted prime signature is A304678, with dual A242031.

Permitting the run-lengths to be weakly decreasing also gives A332835.

The complement is counted by A332871.

Unimodal compositions are A001523.

Compositions that are not unimodal are A115981.

Compositions with equal run-lengths are A329738.

Compositions whose run-lengths are unimodal are A332726.

Cf. A001462, A072704, A072706, A100882, A181819, A329744, A329766, A332641, A332727, A332745, A332833, A332834.

Sequence in context: A357925 A190591 A332338 * A328129 A360890 A309729

Adjacent sequences: A332833 A332834 A332835 * A332837 A332838 A332839

Keyword

nonn

Author

Gus Wiseman, Feb 29 2020

Extensions

Terms a(21) and beyond from Andrew Howroyd, Dec 30 2020

Status

approved