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

1, 1, 1, 3, 6, 13, 21, 48, 89, 180, 355, 707, 1382, 2758, 5448, 10786, 21391, 42476, 84291, 167516, 333036, 662153, 1317687, 2622706, 5221951, 10400350, 20720877, 41288823, 82294979, 164052035, 327088649, 652238016, 1300788712, 2594486045, 5175378128, 10324522020

Offset: 0

Author

Gus Wiseman, Nov 20 2019

Keywords

• nonn

Comments

A composition of n is a finite sequence of positive integers with sum n.

Examples

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)  (3)    (4)      (5)
                (1,2)  (1,3)    (1,4)
                (2,1)  (3,1)    (2,3)
                       (1,1,2)  (3,2)
                       (1,2,1)  (4,1)
                       (2,1,1)  (1,1,3)
                                (1,2,2)
                                (1,3,1)
                                (2,1,2)
                                (2,2,1)
                                (3,1,1)
                                (1,1,2,1)
                                (1,2,1,1)
		

Crossrefs

Looking at multiplicities instead of run-lengths gives A329741.

The complete case is A329749.

Complete compositions are A107429.

Cf. A000740, A008965, A242882, A244164, A274174, A329738, A329739, A329740, A329744, A329748.

Programs

Mathematica

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

Extensions

a(21)-a(26) from Giovanni Resta, Nov 22 2019

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