A391644 Number of integer compositions of n that are the first sums of a unique composition.

0, 1, 0, 1, 2, 3, 4, 8, 10, 19, 24, 43, 56, 96, 126, 211, 278, 457, 604, 978, 1296, 2073, 2752, 4359, 5794, 9104, 12112, 18905, 25168, 39065, 52032, 80384, 107104, 164807, 219646, 336837, 449002, 686568, 915314, 1396117, 1861442, 2833135, 3777666, 5738972

Offset

1,5

Comments

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

Also the number of integer compositions c of n with a unique integer k such that the k-based partial alternating sums of c are all positive. 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. This is a signed version of the partial sums transformation, inverse to the "first sums" transformation.

Compositions whose first sums are not achieved by any other composition are those that have at least one 1 at both the odd and the even positions. - Christian Sievers, Jan 09 2026

Links

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

Index entries for linear recurrences with constant coefficients, signature (0,4,1,-4,-3,-1,1,2,2).

Formula

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

Example

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

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, k], {k, 0, Max[m]}], Min@@#>0&];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[cga[#]]==1&]], {n, 15}]

Prog

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

Crossrefs

The compositions are ranked by A390745.

For more than one choice we have a restriction of A391628, ranks A022340 /\ A391627.

For nonnegative sequences we have A391643, ranks A391622.

For no choices we have A391680, ranks A390677.

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.

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

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

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

A391642 counts compositions with standard first sums.

Cf. A008965, A070211, A390446, A390675, A390676, A391235, A391621, A391641, A391645, A391681, A391683, A391983.

Sequence in context: A295296 A186417 A207644 * A114854 A127279 A106131

Adjacent sequences: A391641 A391642 A391643 * A391645 A391646 A391647

Keyword

nonn,easy

Author

Gus Wiseman, Jan 06 2026

Extensions

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

Status

approved