A391683 Number of integer compositions of n that are the first sums of some composition.

0, 1, 1, 2, 3, 5, 7, 12, 16, 27, 36, 59, 79, 127, 170, 270, 361, 568, 759, 1185, 1583, 2456, 3280, 5063, 6760, 10391, 13871, 21247, 28358, 43310, 57797, 88052, 117491, 178617, 238311, 361644, 482464, 731027, 975180, 1475635, 1968351, 2975103, 3968274, 5992030

Offset

1,4

Comments

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

Links

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

Formula

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

Example

The composition (2,4,3) is not the first sums of any composition, so (2,4,3) is not counted under a(9).
The composition (3,4,3) is the first sums of (1,2,2,1), so (3,4,3) is counted under a(10).
The a(2) = 1 through a(9) = 16 compositions:
  (2)  (3)  (4)    (5)    (6)      (7)      (8)        (9)
            (2,2)  (2,3)  (2,4)    (2,5)    (2,6)      (2,7)
                   (3,2)  (3,3)    (3,4)    (3,5)      (3,6)
                          (4,2)    (4,3)    (4,4)      (4,5)
                          (2,2,2)  (5,2)    (5,3)      (5,4)
                                   (2,2,3)  (6,2)      (6,3)
                                   (3,2,2)  (2,2,4)    (7,2)
                                            (2,3,3)    (2,2,5)
                                            (3,2,3)    (2,3,4)
                                            (3,3,2)    (3,2,4)
                                            (4,2,2)    (3,3,3)
                                            (2,2,2,2)  (4,2,3)
                                                       (4,3,2)
                                                       (5,2,2)
                                                       (2,2,2,3)
                                                       (3,2,2,2)

Mathematica

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^2+x^3-x^4-x^5)/(1-3*x^2-x^3+2*x^4+2*x^5)+O(x*x^n), n) \\ Christian Sievers, Jan 11 2026

Crossrefs

This is the union of A390568.

Ranks indicate positive terms in the pre-bisected A390675.

These compositions have ranks A390676.

The unique case is counted by A391644, ranks A390745.

The complement is counted by A391680, ranks A390677.

Ranks for nonnegative sequences are:

- no choices: A390747, counted by A391645.

- a unique choice: A391622, counted by A391643.

- more than one choice: A391623, counted by A391682.

A011782 counts compositions.

A066099 lists all compositions in standard order.

A357213 counts compositions by sum of first sums.

A390432 lists first sums of standard compositions.

A390449 ranks first sums of prime indices, listed by A390307 or A390362.

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

A390674 ranks compositions with equal first sums, counted by A342527.

Cf. A000079, A000120, A001511, A008965, A029837, A029931, A070211, A070939, A389731, A390448, A390678.

Sequence in context: A319635 A179822 A319769 * A326083 A027959 A060730

Adjacent sequences: A391680 A391681 A391682 * A391684 A391685 A391686

Keyword

nonn,easy

Author

Gus Wiseman, Jan 08 2026

Extensions

a(21)-a(44) from Christian Sievers, Jan 10 2026

Status

approved