A391628 - OEIS

A391628

Number of integer compositions of n that are the first sums of more than one composition.

%I #20 Jan 12 2026 04:32:53

%S 0,0,1,1,1,2,3,4,6,8,12,16,23,31,44,59,83,111,155,207,287,383,528,704,

%T 966,1287,1759,2342,3190,4245,5765,7668,10387,13810,18665,24807,33462,

%U 44459,59866,79518,106909,141968,190608,253058,339341,450431,603345,800718

%N Number of integer compositions of n that are the first sums of more than one composition.

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

%C Also the number of compositions c of n such that there is more than one integer b such that the b-based partial alternating sums of c are all positive. Here, the b-based partial alternating sums of a finite sequence q are given by pas(q,b)_j = (-1)^j * b + 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.

%C Are all these compositions free of 2?

%C From _Christian Sievers_, Jan 09 2026: (Start)

%C The terms in these compositions are all at least 3: for a different composition to have the same first sums as (a, b, c, d, e, ...) has, it has to be of the form (a+k, b-k, c+k, d-k, e+k, ...) for some nonzero integer k. For a first sum to be 2, it has to come from two adjacent 1 terms. But then the second composition giving the same first sums would have a term 1-|k| < 1, which is not allowed.

%C Equivalently, number of compositions of n that are the first sums of a composition with terms that are at least 2 at every other position. (End)

%H Christian Sievers, <a href="/A391628/b391628.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (0,2,1,0,-1,-1,-1).

%F G.f.: (x^3+x^4-x^5-x^6)/(1-2*x^2-x^3+x^5+x^6+x^7). - _Christian Sievers_, Jan 11 2026

%e The composition (2,4,3) is not the first sums of any composition, so (2,4,3) is not counted under a(9).

%e The composition (3,4,3) is the first sums of (1,2,2,1) only, so (3,4,3) is not counted under a(10).

%e The composition (3,3,5) is the first sums of (1,2,1,4) and (2,1,2,3), so (3,3,5) is counted under a(11).

%e The a(3) = 1 through a(11) = 12 compositions are:

%e (3) (4) (5) (6) (7) (8) (9) (10) (11)

%e (3,3) (3,4) (3,5) (3,6) (3,7) (3,8)

%e (4,3) (4,4) (4,5) (4,6) (4,7)

%e (5,3) (5,4) (5,5) (5,6)

%e (6,3) (6,4) (6,5)

%e (3,3,3) (7,3) (7,4)

%e (3,3,4) (8,3)

%e (4,3,3) (3,3,5)

%e (3,4,4)

%e (4,3,4)

%e (4,4,3)

%e (5,3,3)

%t pas[y_,k_]:=Table[(-1)^j*k+Sum[(-1)^(i+j)*y[[i]],{i,j}],{j,0,Length[y]}];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Select[Table[pas[#,b],{b,0,Max[#]}], Min@@#>=1&]]>1&]],{n,1,10}]

%o (PARI) a(n)=polcoef((x^3+x^4-x^5-x^6)/(1-2*x^2-x^3+x^5+x^6+x^7)+O(x*x^n),n) \\ _Christian Sievers_, Jan 11 2026

%Y The compositions are ranked by A391627.

%Y For a unique choice we have A391644, ranks A390745.

%Y For no choices we have A391680, ranks A390677.

%Y For nonnegative sequences we have A391682, ranks A391623.

%Y For at least one choice we have A391683, ranks A390676 (union of A390568).

%Y A011782 counts compositions.

%Y A357213 counts compositions by sum of first sums.

%Y A390432 lists first sums of standard compositions.

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

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

%Y A391621 counts nonnegative sequences with standard first sums.

%Y A391642 counts compositions with standard first sums.

%Y Cf. A008965, A022340, A342527, A066099, A070211, A390446, A390675, A391235, A391983.

%K nonn,easy

%O 1,6

%A _Gus Wiseman_, Jan 07 2026

%E a(21) onward from _Christian Sievers_, Jan 11 2026