A391641 Number of integer compositions of n that are not the first sums of any composition with no 1's.

1, 2, 4, 7, 15, 31, 63, 126, 253, 508, 1019, 2041, 4087, 8179, 16368, 32745, 65508, 131032, 262095, 524219, 1048491, 2097034, 4194158, 8388407, 16776967, 33554091, 67108442, 134217152, 268434744, 536869943, 1073740627, 2147482024, 4294965290, 8589931879

Offset

1,2

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 of n whose k-based partial alternating sums are not all > 1 for any integer k. 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

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

Formula

From Christian Sievers, Jan 15 2026: (Start)

a(n) = A011782(n) - A391235(n).

G.f.: x*(1 - 2*x^2 - x^3 + x^4 + 2*x^5 - x^7 + x^9)/((1 - 2*x)*(1 - x^2 - x^4)*(1 - x^2 - x^5)). (End)

Example

The composition (5,4) is the first sums of (3,2,2) so is not counted under a(9).
The a(1) = 1 through a(5) = 15 compositions:
  (1)  (2)    (3)      (1,3)      (1,4)
       (1,1)  (1,2)    (2,2)      (2,3)
              (2,1)    (3,1)      (3,2)
              (1,1,1)  (1,1,2)    (4,1)
                       (1,2,1)    (1,1,3)
                       (2,1,1)    (1,2,2)
                       (1,1,1,1)  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (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]}];
agc[m_]:=Select[Table[pas[m, b], {b, 1, Max[m]}], Min@@#>1&];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], agc[#]=={}&]], {n, 15}]

Prog

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

Crossrefs

For nonnegative sequences see A390747, A391645, A391679.

The complement is counted by A391235, ranks A391626.

The restriction to partitions on the LHS is A391620, ranks A080671.

For multisets on the LHS and partitions on the RHS we get A391629, ranks A390445.

Allowing 1's on the RHS gives A391680, ranks A390677.

A011782 counts compositions.

A357213 counts compositions by sum of first sums.

A390673 ranks compositions with distinct first sums, count A390567.

A390676 ranks compositions that are first sums, union of A390568.

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

A390745 ranks compositions that are uniquely first sums, count A391644.

Cf. A000041, A008965, A070211, A342527, A390432, A390446, A390447, A390448, A390675, A391642, A391981.

Sequence in context: A049885 A129682 A129981 * A358824 A072964 A247291

Adjacent sequences: A391638 A391639 A391640 * A391642 A391643 A391644

Keyword

nonn,easy

Author

Gus Wiseman, Jan 01 2026

Extensions

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

Status

approved