A391645 Number of integer compositions of n that are not the first sums of any finite nonnegative sequence.

0, 0, 0, 0, 1, 3, 11, 28, 76, 178, 429, 957, 2167, 4686, 10220, 21640, 46057, 96091, 201123, 415164, 858748, 1758834, 3607109, 7344997, 14969263, 30348574, 61563612, 124403736, 251481889, 506914707, 1022049083, 2056268764, 4137710764, 8312765362, 16702396701

Offset

1,6

Comments

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

Also the number of compositions c of n with no integer k such that the k-based partial alternating sums of c are nonnegative. Here, the k-based partial alternating sums of a sequence q are given by pas(q,k)_j = (-1)^j * k + Sum_{i=1..j} (-1)^(i+j) * q_i.

Links

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

Formula

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

Example

The composition (4,2,5,3) is the first sums of (4,0,2,3,0) so is not counted under a(14).
The k-based partial alternating sums of (2,5,2) are (k, 2-k, 3+k, -1-k), which is not nonnegative for any k, so (2,5,2) is counted under a(9).
The a(1) = 0 through a(7) = 11 compositions:
  .  .  .  .  (131)  (141)   (142)
                     (1131)  (151)
                     (1311)  (241)
                             (1141)
                             (1312)
                             (1411)
                             (2131)
                             (11131)
                             (11311)
                             (12121)
                             (13111)

Mathematica

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

Prog

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

Crossrefs

These compositions are ranked by A390747.

For a unique choice we have A391643, ranks A391622.

The case of all parts > 1 is A391679.

For more than one choice we have A391682, ranks A391623.

For compositions instead of nonnegative sequences we have:

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

- no choices: A391680, ranks A390677

- unique choice: A391644, ranks A390745

- more than one choice: A391628, ranks A391627

A011782 counts compositions.

A357213 counts compositions by sum of first sums.

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

A390678 ranks compositions with no 1's that are not first sums.

A391621 counts nonnegative sequences with standard first sums.

A391642 counts compositions with standard first sums.

Cf. A008965, A070211, A342527, A390307, A390445, A390447, A390675, A391235, A391629, A391641, A391983.

Sequence in context: A163696 A092781 A332669 * A302509 A335899 A018743

Adjacent sequences: A391642 A391643 A391644 * A391646 A391647 A391648

Keyword

nonn,easy

Author

Gus Wiseman, Jan 05 2026

Extensions

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

Status

approved