A391641 - OEIS

%I #19 Jan 15 2026 20:37:22

%S 1,2,4,7,15,31,63,126,253,508,1019,2041,4087,8179,16368,32745,65508,

%T 131032,262095,524219,1048491,2097034,4194158,8388407,16776967,

%U 33554091,67108442,134217152,268434744,536869943,1073740627,2147482024,4294965290,8589931879

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

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

%C 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.

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

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

%F From _Christian Sievers_, Jan 15 2026: (Start)

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

%F 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)

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

%e The a(1) = 1 through a(5) = 15 compositions:

%e   (1)  (2)    (3)      (1,3)      (1,4)

%e        (1,1)  (1,2)    (2,2)      (2,3)

%e               (2,1)    (3,1)      (3,2)

%e               (1,1,1)  (1,1,2)    (4,1)

%e                        (1,2,1)    (1,1,3)

%e                        (2,1,1)    (1,2,2)

%e                        (1,1,1,1)  (1,3,1)

%e                                   (2,1,2)

%e                                   (2,2,1)

%e                                   (3,1,1)

%e                                   (1,1,1,2)

%e                                   (1,1,2,1)

%e                                   (1,2,1,1)

%e                                   (2,1,1,1)

%e                                   (1,1,1,1,1)

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

%t agc[m_]:=Select[Table[pas[m,b],{b,1,Max[m]}],Min@@#>1&];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],agc[#]=={}&]],{n,15}]

%o (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

%Y For nonnegative sequences see A390747, A391645, A391679.

%Y The complement is counted by A391235, ranks A391626.

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

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

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

%Y A011782 counts compositions.

%Y A357213 counts compositions by sum of first sums.

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

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

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

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

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

%K nonn,easy

%O 1,2

%A _Gus Wiseman_, Jan 01 2026

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