A391682 Number of integer compositions of n that are the first sums of more than one nonnegative sequence.

1, 2, 4, 7, 13, 22, 39, 65, 112, 185, 313, 514, 859, 1405, 2328, 3797, 6253, 10178, 16687, 27121, 44320, 71953, 117297, 190274, 309619, 501941, 815656, 1321693, 2145541, 3475426, 5637351, 9129161, 14799280, 23961209, 38826025, 62852770, 101809867, 164793709

Offset

1,2

Comments

The first sums of a nonempty sequence (a, b, c, d, ...) are (a+b, b+c, c+d, ...).

A nonnegative sequence is not unique in having its first sums iff every other of its terms is at least 1. - Christian Sievers, Jan 09 2026

Links

Christian Sievers, Table of n, a(n) for n = 1..1000

Formula

G.f.: (x+x^2-x^3-x^4)/(1-x-3*x^2+2*x^3+2*x^4). - Christian Sievers, Jan 11 2026

Example

The composition (1,2,1) is the first sums of (0,1,1,0) only, so (1,2,1) is not counted under a(4).
The composition (2,1,2) is the first sums of both (1,1,0,2) and (2,0,1,1), so (2,1,2) is counted under a(5).
The a(1) = 1 through a(5) = 13 compositions:
  (1)  (2)    (3)      (4)        (5)
       (1,1)  (1,2)    (1,3)      (1,4)
              (2,1)    (2,2)      (2,3)
              (1,1,1)  (3,1)      (3,2)
                       (1,1,2)    (4,1)
                       (2,1,1)    (1,1,3)
                       (1,1,1,1)  (1,2,2)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (2,1,1,1)
                                  (1,1,1,1,1)

Mathematica

pas[y_, k_]:=Table[(-1)^j*k+Sum[(-1)^(i+j)*y[[i]], {i, j}], {j, 0, Length[y]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Select[Table[pas[#, b], {b, 0, Max[#]}], Min@@#>=0&]]>1&]], {n, 1, 10}]

Prog

(PARI) a(n)=polcoef((x+x^2-x^3-x^4)/(1-x-3*x^2+2*x^3+2*x^4)+O(x*x^n), n) \\ Christian Sievers, Jan 11 2026

Crossrefs

These compositions are ranked by A391623.

For a unique choice we have A391643, ranks A391622.

For no choices we have A391645 (for all parts > 1 A391679), ranks A390747.

For compositions we have:

- more than one choice: A391628, ranks A391627

- unique choice: A391644, ranks A390745

- no choices: A391680, ranks A390677

- at least one choice: A391683, ranks A390676 (union of A390568)

A011782 counts compositions.

A357213 counts compositions by sum of first sums.

A390432 lists first sums of standard compositions.

A390673 ranks compositions with distinct first sums, counted by A390567.

A391621 counts nonnegative sequences with standard first sums.

Cf. A008965, A070211, A342527, A390448, A390675, A390678, A391235, A391641, A391642, A391983.

Sequence in context: A319111 A128768 A395489 * A235607 A254007 A372782

Adjacent sequences: A391679 A391680 A391681 * A391683 A391684 A391685

Keyword

nonn,easy

Author

Gus Wiseman, Jan 08 2026

Extensions

a(21) onward from Christian Sievers, Jan 11 2026

Status

approved