A336127 Number of ways to split a composition of n into contiguous subsequences with different sums.

1, 1, 2, 8, 16, 48, 144, 352, 896, 2432, 7168, 16896, 46080, 114688, 303104, 843776, 2080768, 5308416, 13762560, 34865152, 87818240, 241172480, 583008256, 1503657984, 3762290688, 9604956160, 23689428992, 60532195328, 156397207552, 385137770496, 967978254336

Offset

0,3

Comments

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

Links

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

Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

Formula

a(n) = Sum_{k=0..n} 2^(n-k) k! A008289(n,k).

Example

The a(0) = 1 through a(4) = 16 splits:
  ()  (1)  (2)    (3)        (4)
           (1,1)  (1,2)      (1,3)
                  (2,1)      (2,2)
                  (1,1,1)    (3,1)
                  (1),(2)    (1,1,2)
                  (2),(1)    (1,2,1)
                  (1),(1,1)  (1),(3)
                  (1,1),(1)  (2,1,1)
                             (3),(1)
                             (1,1,1,1)
                             (1),(1,2)
                             (1),(2,1)
                             (1,2),(1)
                             (2,1),(1)
                             (1),(1,1,1)
                             (1,1,1),(1)

Mathematica

splits[dom_]:=Append[Join@@Table[Prepend[#, Take[dom, i]]&/@splits[Drop[dom, i]], {i, Length[dom]-1}], {dom}];
Table[Sum[Length[Select[splits[ctn], UnsameQ@@Total/@#&]], {ctn, Join@@Permutations/@IntegerPartitions[n]}], {n, 0, 10}]

Crossrefs

The version with equal instead of different sums is A074854.

Starting with a strict composition gives A336128.

Starting with a partition gives A336131.

Starting with a strict partition gives A336132

Partitions of partitions are A001970.

Partitions of compositions are A075900.

Compositions of compositions are A133494.

Compositions of partitions are A323583.

Cf. A006951, A063834, A279786, A305551, A316245, A317715, A323433, A336130, A336134, A336135.

Sequence in context: A134353 A280229 A360323 * A076508 A162584 A100243

Adjacent sequences: A336124 A336125 A336126 * A336128 A336129 A336130

Keyword

nonn

Author

Gus Wiseman, Jul 09 2020

Status

approved