A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.

1, 1, 0, 2, 3, 5, 11, 23, 40, 80, 180, 344, 661, 1321, 2657, 5268, 10481, 20903, 41572, 82734, 164998, 328304, 654510, 1305421, 2598811, 5182174, 10332978, 20594318, 41066611, 81897091, 163309679, 325707492, 649648912, 1295827380, 2584941276, 5156774487

Offset

0,4

Comments

A composition of n is a finite sequence of positive integers with sum n. It is complete if it covers an initial interval of positive integers.

Links

Table of n, a(n) for n=0..35.

Example

The a(0) = 1 through a(6) = 11 compositions (empty column not shown):
  ()  (1)  (1,2)  (1,1,2)  (1,2,2)    (1,2,3)
           (2,1)  (1,2,1)  (2,1,2)    (1,3,2)
                  (2,1,1)  (2,2,1)    (2,1,3)
                           (1,1,2,1)  (2,3,1)
                           (1,2,1,1)  (3,1,2)
                                      (3,2,1)
                                      (1,2,1,2)
                                      (1,2,2,1)
                                      (2,1,1,2)
                                      (2,1,2,1)
                                      (1,1,2,1,1)

Mathematica

normQ[m_]:=Or[m=={}, Union[m]==Range[Max[m]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], normQ[#]&&normQ[Length/@Split[#]]&]], {n, 0, 10}]

Crossrefs

Looking at multiplicities instead of run-lengths gives A329748.

The non-complete version is A329766.

Complete compositions are A107429.

Cf. A000740, A008965, A098504, A244164, A274174, A329738, A329739, A329740, A329741, A329744.

Sequence in context: A038905 A019405 A079848 * A237810 A073434 A109551

Adjacent sequences: A329746 A329747 A329748 * A329750 A329751 A329752

Keyword

nonn

Author

Gus Wiseman, Nov 21 2019

Extensions

a(21)-a(35) from Alois P. Heinz, Jul 06 2020

Status

approved