A063865 -id:A063865 - cp's OEIS frontend

A063867 Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or +- 1.

1, 2, 2, 2, 2, 6, 10, 8, 14, 46, 80, 70, 124, 442, 794, 722, 1314, 4820, 8882, 8220, 15272, 56920, 106444, 99820, 187692, 707486, 1336546, 1265204, 2399784, 9119656, 17358560, 16547220, 31592878, 120801376, 231266520, 221653776

Offset: 0

N. J. A. Sloane, following a suggestion by J. H. Conway, Aug 27 2001

Ray Chandler, Table of n, a(n) for n = 0..3339 (terms < 10^1000; first 101 terms from T. D. Noe)
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]

Cf. A025591, A063865, A063866.

f[n_, s_] := f[n, s]=Which[n==0, If[s==0, 1, 0], Abs[s]>(n*(n+1))/2, 0, True, f[ n-1, s-n]+f[n-1, s+n]]; a[n_] := f[n, 0]+2f[n, 1]

a(n) = A063865(n) + 2*A063866(n).

More terms from Dean Hickerson and Vladeta Jovovic, Aug 28 2001

A156181 Number of solutions to e(1)1 + e(2)2 + ... + e(n)n = e(-1)1 + e(-2)2 + ... + e(-n)n, where e(j) are from {-1,0,1}, j=-n,...,n.

Original entry on oeis.org

1, 3, 13, 65, 403, 2669, 18759, 136477, 1020373, 7785741, 60395165, 474817833, 3775005799, 30298719855, 245167429681, 1997854542163, 16381233095985, 135050690760831, 1118800428892925, 9308791880014333, 77755512086256649

Offset: 0

Steven Finch, Feb 05 2009

nonn

a(n) = coefficient of x^(n*(n+1)) in the polynomial Product_{k=1..n} (1 + x^k + x^(2*k))^2, and is the maximal such coefficient as well.

Ray Chandler, Table of n, a(n) for n = 0..1052 (terms < 10^1000)
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]

Cf. A007576, A047653, A063865.

Table[Coefficient[Expand[Product[(1 + x^k + x^(2*k))^2, {k, 1, n}]],x, n*(n + 1)], {n, 0, 20}]

a(n) is the constant term in expansion of Product_{k=1..n} (x^k + 1 + 1/x^k)^2. - Ilya Gutkovskiy, Jan 22 2024

A039823 a(n) = ceiling( (n^2 + n + 2)/4 ).

Original entry on oeis.org

1, 2, 4, 6, 8, 11, 15, 19, 23, 28, 34, 40, 46, 53, 61, 69, 77, 86, 96, 106, 116, 127, 139, 151, 163, 176, 190, 204, 218, 233, 249, 265, 281, 298, 316, 334, 352, 371, 391, 411, 431, 452, 474, 496, 518, 541, 565, 589, 613, 638, 664, 690, 716, 743, 771, 799, 827

Offset: 1

Olivier Gérard

Equals the number of different coefficient values in the expansion of Product_{i=1..n} (1 + q^1 + ... + q^i). Proof by Lawrence Sze: The Gaussian polynomial Prod_{k=1..n} Sum_{j=0..k} q^j is the q-version of n! and strictly unimodal with constant term 1. It has degree Sum_{k=1..n} k = n(n+1)/2, and thus n(n+1)/2+1 nonzero terms.
a(n) is equivalently the number of different absolute values obtained when summing the first n integers with all possible 2^n sign combinations. - Olivier Gérard, Mar 22 2010
Numbers in ascending order on the central axes (starting with 1) of Ulam's Spiral. - Bob Selcoe, Sep 25 2015

			Possible absolute values of sums of consecutive integers with any sign combination for n = 4 and n=5 are {0, 2, 4, 6, 8, 10} and {1, 3, 5, 7, 9, 11, 13, 15} respectively. - _Olivier Gérard_, Mar 22 2010

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

Cf. A000125, A004524, A011848, A063865.

[Ceiling((n^2+n+2)/4) : n in [1..80]]; // Wesley Ivan Hurt, Sep 25 2015

I:=[1,2,4,6,8]; [n le 5 select I[n] else 3*Self(n-1)-4*Self(n-2)+4*Self(n-3)-3*Self(n-4)+Self(n-5): n in [1..60]]; // Vincenzo Librandi, Sep 26 2015

A039823:=n->ceil((n^2+n+2)/4): seq(A039823(n), n=1..100); # Wesley Ivan Hurt, Sep 25 2015

Table[Floor[((n*(n+1)+2)/2+1)/2],{n,5!}] (* Vladimir Joseph Stephan Orlovsky, Apr 26 2010 *)
LinearRecurrence[{3, -4, 4, -3, 1}, {1, 2, 4, 6, 8}, 70] (* Vincenzo Librandi, Sep 26 2015 *)

makelist((n*(n+1)+%i^(n*(n+1))+3)/4,n,1,57); /* Bruno Berselli, Jul 25 2012 */

a(n) = ceil((n^2+n+2)/4);
vector(80, n, a(n)) \\ Altug Alkan, Sep 25 2015

a(n) = floor(binomial(n+1, 2)/2) + 1 = A011848(n+1) + 1.
G.f.: x*(x^4-2*x^3+2*x^2-x+1)/((1+x^2)*(1-x)^3).
a(n) = (n*(n+1)+i^(n*(n+1))+3)/4, where i=sqrt(-1). - Bruno Berselli, Jul 25 2012
a(n) = a(n-1) + A004524(n+1). - Bob Selcoe, Sep 25 2015
a(n) = 3*a(n-1)-4*a(n-2)+4*a(n-3)-3*a(n-4)+a(n-5) for n>5. - Wesley Ivan Hurt, Sep 25 2015
a(n) = ceiling( (n^2+n+1)/4 ). - Bob Selcoe, Sep 26 2015

Edited by Ralf Stephan, Nov 15 2004

A069918 Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible.

Original entry on oeis.org

1, 1, 1, 1, 3, 5, 4, 7, 23, 40, 35, 62, 221, 397, 361, 657, 2410, 4441, 4110, 7636, 28460, 53222, 49910, 93846, 353743, 668273, 632602, 1199892, 4559828, 8679280, 8273610, 15796439, 60400688, 115633260, 110826888, 212681976, 817175698, 1571588177, 1512776590

Offset: 1

Robert G. Wilson v, Apr 24 2002

nonn

If n mod 4 = 0 or 3, a(n) is the number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1; if n mod 4 = 1 or 2, a(n) is half this number.

			If the triangular number T_n (see A000217) is even then the two totals must be equal, otherwise the two totals differ by one.
a(6) = 5: T6 = 21 and is odd. There are five sets such that the sum of one side is equal to the other side +/- 1. They are 5+6 = 1+2+3+4, 4+6 = 1+2+3+5, 1+4+6 = 2+3+5, 1+3+6 = 2+4+5 and 2+3+6 = 1+4+5.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
S. R. Finch, Signum equations and extremal coefficients [broken link]
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]
Brian Hayes, The Easiest Hard Problem, American Scientist, Vol. 90, No. 2, March-April 2002, pp. 113-117.
Recreational Mathematics Newsletter, Kolstad, PROBLEM 4: Subset Sums [broken link]
Dave Rusin, More Number Theory [broken link]

Cf. A060005, A058377, A025591, A063865, A063866, A063867, A306443.

b:= proc(n, i) option remember; local m; m:= i*(i+1)/2;
      `if`(n>m, 0, `if`(n=m, 1, b(abs(n-i), i-1) +b(n+i, i-1)))
    end:
a:= n-> `if`(irem(n-1, 4)<2, b(n-1, n-1) +b(n+1, n-1), b(n, n-1)):
seq(a(n), n=1..60);  # Alois P. Heinz, Nov 02 2011

Needs["DiscreteMath`Combinatorica`"]; f[n_] := f[n] = Block[{s = Sort[Plus @@@ Subsets[n]], k = n(n + 1)/2}, If[ EvenQ[k], Count[s, k/2]/2, (Count[s, Floor[k/2]] + Count[s, Ceiling[k/2]]) /2]]; Table[ f[n], {n, 1, 22}]
f[n_, s_] := f[n, s] = Which[n == 0, If[s == 0, 1, 0], Abs[s] > (n*(n + 1))/2, 0, True, f[n - 1, s - n] + f[n - 1, s + n]]; Table[ Which[ Mod[n, 4] == 0 || Mod[n, 4] == 3, f[n, 0]/2, Mod[n, 4] == 1 || Mod[n, 4] == 2, f[n, 1]], {n, 1, 40}]

If n mod 4 = 0 or 3 then the two subsets have the same sum and a(n) = A025591(n); if n mod 4 = 1 or 2 then the two subsets have sums which differ by 1 and a(n) = A025591(n)/2. - Henry Bottomley, May 08 2002

More terms from Henry Bottomley, May 08 2002

Comment corrected by Steven Finch, Feb 01 2009

A326174 Number of subsets of {1..n} containing n whose sum is greater than or equal to the sum of their complement.

Original entry on oeis.org

1, 2, 4, 7, 13, 25, 50, 98, 186, 366, 739, 1457, 2822, 5589, 11258, 22304, 43629, 86658, 174257, 346180, 680955, 1354829, 2721296, 5414787, 10689261, 21290468, 42730228, 85112982, 168430866, 335726276, 673421519, 1342347992, 2661053796, 5307062034, 10640664164

Offset: 1

Gus Wiseman, Jun 11 2019

nonn

			The a(1) = 1 through a(5) = 13 subsets:
  {1}  {2}    {3}      {1,4}      {3,5}
       {1,2}  {1,3}    {2,4}      {4,5}
              {2,3}    {3,4}      {1,2,5}
              {1,2,3}  {1,2,4}    {1,3,5}
                       {1,3,4}    {1,4,5}
                       {2,3,4}    {2,3,5}
                       {1,2,3,4}  {2,4,5}
                                  {3,4,5}
                                  {1,2,3,5}
                                  {1,2,4,5}
                                  {1,3,4,5}
                                  {2,3,4,5}
                                  {1,2,3,4,5}

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..46

Cf. A053632, A057567, A057568, A059529, A063865, A326152, A326173, A326175.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Plus@@#>=Plus@@Complement[Range[n],#]&]],{n,10}]

a(21)-a(42) from Bert Dobbelaere, Jun 22 2019

A060468 Number of fair distributions (equal sum) of the integers {1,..,4n} between A and B = number of solutions to the equation {+-1 +-2 +- 3 ... +-4*n = 0}.

Original entry on oeis.org

1, 2, 14, 124, 1314, 15272, 187692, 2399784, 31592878, 425363952, 5830034720, 81072032060, 1140994231458, 16221323177468, 232615054822964, 3360682669655028, 48870013251334676, 714733339229024336

Offset: 0

Roland Bacher, Mar 15 2001

			a(1)=2: give either the set {1,4} to A and {2,3} to B or give {2,3} to A and {1,4} to B.

Ray Chandler, Table of n, a(n) for n = 0..834 (terms < 10^1000)
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]

Cf. A025591, A060005, A063865, A063867.

a[n_] := Coefficient[Product[q^(-k) + q^k, {k, 1, 4*n}], q, 0]; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Sep 26 2013 *)

a(n) = coefficient of q^0 in Product_{k=1..4*n} (q^(-k) + q^k).

a(n) = A025591(4n) = A063865(4n) = A063867(4n) = 2*A060005(n). Seems to be close to sqrt(3/32Pi)*16^n/sqrt(n^3 + n^2*0.6 + n*0.1385...) and sqrt(n*Pi/2)*A063074(n). - Henry Bottomley, Jul 30 2005

A141000 Numbers k for which there is a solution to the Jumping Grasshopper game.

Original entry on oeis.org

0, 1, 4, 9, 13, 16, 20, 21, 24, 25, 28, 29, 32, 33, 36, 37, 40, 41, 44, 45, 48, 49, 52, 53, 56, 57, 60, 61, 64, 65, 68, 69, 72, 73, 76, 77, 80, 81, 84, 85, 88, 89, 92, 93, 96, 97, 100, 101, 104, 105, 108, 109, 112, 113, 116, 117, 120, 121, 124, 125, 128, 129, 132, 133

Offset: 1

Ivan Moscovich (i.moscovich2(AT)chello.nl), Jul 07 2008

That is, numbers k such that there is a choice of signs s_1, s_2, ..., s_k (each +1 or -1) so that (i) 0 <= Sum_{i = 1..j } i*s_i <= k for all 1 <= j <= k-1 and (ii) Sum_{i = 1..k } i*s_i = k. (This forces s_1 = s_2 = s_k = +1.)
It has been shown by Dick Hess and Benji Fisher that a number k >= 20 is in the sequence iff k == 0 or 1 (mod 4). (For a proof see the Applegate link.) It is easy to see that k == 0 or 1 (mod 4) is a necessary condition.
Further comments from David Applegate and N. J. A. Sloane, Jul 14 2008: (Start)
An obvious greedy algorithm (working backwards) does the following: For j = k, k-1, ..., 1, let target_j = k - Sum_{i = j+1..k} i * s_i and set s_j = +1 if target_j >= j and s_j = -1 otherwise. This works unless we hit one of five exceptions, in which we must set s_j = -1 instead of +1.
The five exceptions are when (j, target_j) is (5,5), (6,9), (7,14), (8,8), or (9,13). The algorithm also works for the more general case when the target total target_k is different from k, with the additional exception of (8,20). (End)

			4 is a member because we can take s_1 = s_2 = s_4 = +1, s_3 = -1. Note in particular that 1 + 2 -3 + 4 = 4. (See the illustration.)

Ivan Moscovich, "MATH - Isn't It Beautiful!", 2009.

David Applegate, Notes on A141000.
Ivan Moscovich, Grasshop Puzzle-Game.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000980, A063865.

{0, 1, 4, 9, 13, 16}~Join~LinearRecurrence[{1, 1, -1}, {20, 21, 24}, 58] (* Jean-François Alcover, Nov 20 2019 *)
LinearRecurrence[{1,1,-1},{0,1,4,9,13,16,20,21,24},70] (* Harvey P. Dale, Mar 22 2025 *)

Tcl
```
# See the notes by D. Applegate above.
```

From Colin Barker, May 19 2013: (Start)
a(n) = (11 - (-1)^n + 4*n)/2 for n > 6.
a(n) = a(n-1) + a(n-2) - a(n-3) for n > 9.
G.f.: -x^2*(x^7+2*x^6+2*x^4-x^3-4*x^2-3*x-1) / ((x-1)^2*(x+1)). (End)

A326173 Number of maximal subsets of {1..n} whose sum is less than or equal to the sum of their complement.

Original entry on oeis.org

1, 1, 1, 2, 4, 5, 8, 16, 24, 44, 77, 133, 240, 429, 772, 1414, 2588, 4742, 8761, 16273, 30255, 56392, 105581, 198352, 373228, 703409, 1329633, 2519927, 4781637, 9084813, 17298255, 33001380, 63023204, 120480659, 230702421, 442423139, 849161669, 1631219288, 3137595779, 6042247855, 11644198080, 22455871375, 43351354727

Offset: 0

Gus Wiseman, Jun 11 2019

nonn

Also the number of minimal subsets of {1..n} whose sum is greater than or equal to the sum of their complement. For example, the a(0) = 1 through a(7) = 16 subsets are:
  {}  {1}  {2}  {3}    {1,4}  {3,5}    {5,6}      {1,6,7}
                {1,2}  {2,3}  {4,5}    {1,4,6}    {2,5,7}
                       {2,4}  {1,2,5}  {2,3,6}    {2,6,7}
                       {3,4}  {1,3,4}  {2,4,5}    {3,4,7}
                              {2,3,4}  {2,4,6}    {3,5,6}
                                       {3,4,5}    {3,5,7}
                                       {3,4,6}    {3,6,7}
                                       {1,2,3,5}  {4,5,6}
                                                  {4,5,7}
                                                  {4,6,7}
                                                  {5,6,7}
                                                  {1,2,4,7}
                                                  {1,2,5,6}
                                                  {1,3,4,6}
                                                  {2,3,4,5}
                                                  {2,3,4,6}

			The a(0) = 1 through a(7) = 16 subsets:
  {}  {}  {1}  {3}    {1,2}  {1,5}    {4,6}      {1,5,7}
               {1,2}  {1,3}  {2,5}    {1,2,5}    {1,6,7}
                      {1,4}  {3,4}    {1,2,6}    {2,5,7}
                      {2,3}  {1,2,3}  {1,3,5}    {3,4,7}
                             {1,2,4}  {1,3,6}    {3,5,6}
                                      {1,4,5}    {1,2,3,4}
                                      {2,3,5}    {1,2,3,5}
                                      {1,2,3,4}  {1,2,3,6}
                                                 {1,2,3,7}
                                                 {1,2,4,5}
                                                 {1,2,4,6}
                                                 {1,2,4,7}
                                                 {1,2,5,6}
                                                 {1,3,4,5}
                                                 {1,3,4,6}
                                                 {2,3,4,5}

The non-maximal case is A059529.

Cf. A053632, A057567, A057568, A063865, A326174, A326175.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],Plus@@Complement[Range[n],#]>=Plus@@#&]]],{n,0,10}]

a(16)-a(42) from Bert Dobbelaere, Jun 22 2019

A326175 Number of minimal subsets of {1..n} containing n whose sum is greater than or equal to the sum of their complement.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 10, 14, 25, 44, 71, 128, 231, 411, 740, 1352, 2481, 4570, 8390, 15550, 29103, 54345, 101312, 190316, 359827, 679051, 1279956, 2426200, 4621174, 8789565, 16701225, 31871629, 61052515, 116818123, 223333533, 428435056, 824395640, 1584833707, 3044562148, 5865073390, 11326741619, 21857561924

Offset: 1

Gus Wiseman, Jun 11 2019

nonn

			The a(1) = 1 through a(8) = 14 subsets:
  {1}  {2}  {3}  {1,4}  {3,5}    {5,6}    {1,6,7}    {3,7,8}
                 {2,4}  {4,5}    {1,4,6}  {2,5,7}    {4,6,8}
                 {3,4}  {1,2,5}  {2,3,6}  {2,6,7}    {4,7,8}
                                 {2,4,6}  {3,4,7}    {5,6,8}
                                 {3,4,6}  {3,5,7}    {5,7,8}
                                          {3,6,7}    {6,7,8}
                                          {4,5,7}    {1,2,7,8}
                                          {4,6,7}    {1,3,6,8}
                                          {5,6,7}    {1,4,5,8}
                                          {1,2,4,7}  {2,3,5,8}
                                                     {2,3,6,8}
                                                     {2,4,5,8}
                                                     {3,4,5,8}
                                                     {1,2,3,4,8}

Cf. A053632, A057567, A057568, A059529, A063865, A326152, A326173, A326174.

fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]&/@Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];
Table[Length[fasmin[Select[Subsets[Range[n]],MemberQ[#,n]&&Plus@@#>=Plus@@Complement[Range[n],#]&]]],{n,10}]

a(15)-a(42) from Bert Dobbelaere, Jun 22 2019

A326441 Number of subsets of {1..n} whose sum is equal to the product of their complement.

Original entry on oeis.org

0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 3, 3, 3, 1, 4, 4, 3, 2, 2, 4, 3, 5, 3, 2, 4, 5, 4, 5, 6, 1, 4, 2, 5, 4, 7, 4, 4, 3, 3, 6, 14, 3, 4, 10, 6, 3, 6, 4, 4, 4, 8, 7, 6, 8, 7, 10, 5, 11, 8, 5, 11, 4, 7, 7, 5, 8, 12, 5, 6, 9, 8, 11, 8, 5, 8, 9, 8, 10, 8

Offset: 0

Gus Wiseman, Jul 07 2019

nonn

Essentially the same as A178830. - R. J. Mathar, Jul 12 2019

			The initial terms count the following subsets:
   1: {1}
   3: {1,2}
   5: {3,5}
   6: {3,4,5}
   7: {2,4,5,7}
   8: {2,4,5,6,7}
   9: {2,3,5,6,7,9}
  10: {4,5,6,8,9,10}
  10: {2,3,5,6,7,8,9}
  10: {1,2,3,4,5,8,9,10}
Also the number of subsets of {1..n} whose product is equal to the sum of their complement. For example, the initial terms count the following subsets:
   1: {}
   3: {3}
   5: {1,2,4}
   6: {1,2,6}
   7: {1,3,6}
   8: {1,3,8}
   9: {1,4,8}
  10: {6,7}
  10: {1,4,10}
  10: {1,2,3,7}

Giovanni Resta, Table of n, a(n) for n = 0..500

Cf. A028422, A053632, A059529, A063865, A178830, A301987, A325044, A325538, A326172, A326173, A326174, A326175, A326179, A326180.

b:= proc(n, s, p)
      `if`(s=p, 1, `if`(n<1, 0, b(n-1, s, p)+
      `if`(s-n b(n, n*(n+1)/2, 1):
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 12 2019

Table[Length[Select[Subsets[Range[n]],Plus@@#==Times@@Complement[Range[n],#]&]],{n,0,10}]

a(21)-a(83) from Giovanni Resta, Jul 08 2019

cp's OEIS Frontend

A063867 Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or +- 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A156181 Number of solutions to e(1)*1 + e(2)*2 + ... + e(n)*n = e(-1)*1 + e(-2)*2 + ... + e(-n)*n, where e(j) are from {-1,0,1}, j=-n,...,n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A039823 a(n) = ceiling( (n^2 + n + 2)/4 ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A069918 Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A326174 Number of subsets of {1..n} containing n whose sum is greater than or equal to the sum of their complement.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A060468 Number of fair distributions (equal sum) of the integers {1,..,4n} between A and B = number of solutions to the equation {+-1 +-2 +- 3 ... +-4*n = 0}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A141000 Numbers k for which there is a solution to the Jumping Grasshopper game.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A156181 Number of solutions to e(1)1 + e(2)2 + ... + e(n)n = e(-1)1 + e(-2)2 + ... + e(-n)n, where e(j) are from {-1,0,1}, j=-n,...,n.