A141000 -id:A141000 - cp's OEIS frontend

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

1, 0, 0, 2, 2, 0, 0, 8, 14, 0, 0, 70, 124, 0, 0, 722, 1314, 0, 0, 8220, 15272, 0, 0, 99820, 187692, 0, 0, 1265204, 2399784, 0, 0, 16547220, 31592878, 0, 0, 221653776, 425363952, 0, 0, 3025553180, 5830034720, 0, 0, 41931984034, 81072032060, 0, 0

Offset: 0

N. J. A. Sloane, suggested by J. H. Conway, Aug 27 2001

Number of sum partitions of the half of the n-th-triangular number by distinct numbers in the range 1 to n. Example: a(7)=8 since triangular(7)=28 and 14 = 2+3+4+5 = 1+3+4+6 = 1+2+5+6 = 3+5+6 = 7+1+2+4 = 7+3+4 = 7+2+5 = 7+1+6. - Hieronymus Fischer, Oct 20 2010
The asymptotic formula below was stated as a conjecture by Andrica & Tomescu in 2002 and proved by B. D. Sullivan in 2013. See his paper and H.-K. Hwang's review MR 2003j:05005 of the JIS paper. - Jonathan Sondow, Nov 11 2013
a(n) is the number of subsets of {1..n} whose sum is equal to the sum of their complement. See example below. - Gus Wiseman, Jul 04 2019

			From _Gus Wiseman_, Jul 04 2019: (Start)
For example, the a(0) = 1 through a(8) = 14 subsets (empty columns not shown) are:
  {}  {3}    {1,4}  {1,6,7}    {3,7,8}
      {1,2}  {2,3}  {2,5,7}    {4,6,8}
                    {3,4,7}    {5,6,7}
                    {3,5,6}    {1,2,7,8}
                    {1,2,4,7}  {1,3,6,8}
                    {1,2,5,6}  {1,4,5,8}
                    {1,3,4,6}  {1,4,6,7}
                    {2,3,4,5}  {2,3,5,8}
                               {2,3,6,7}
                               {2,4,5,7}
                               {3,4,5,6}
                               {1,2,3,4,8}
                               {1,2,3,5,7}
                               {1,2,4,5,6}
(End)

T. D. Noe, N. J. A. Sloane and Ray Chandler, Table of n, a(n) for n = 0..3339 (terms < 10^1000, first 101 terms from T. D. Noe, next 300 terms from N. J. A. Sloane)
Dorin Andrica and Ovidiu Bagdasar, On k-partitions of multisets with equal sums, The Ramanujan J. (2021) Vol. 55, 421-435.
Dorin Andrica, Ovidiu Bagdasar, and George Cătălin Ţurcaş, The Number of Partitions of a Set and Superelliptic Diophantine Equations, Disc. Math. and Applications, Springer, Cham (2020), 35-55.
D. Andrica and E. J. Ionascu, Variations on a result of Erdős and Surányi, INTEGERS 2013 slides.
D. Andrica and I. Tomescu, On an Integer Sequence Related to a Product of Trigonometric Functions, and Its Combinatorial Relevance, J. Integer Seq., 5 (2002), Article 02.2.4
Ovidiu Bagdasar and Dorin Andrica, New results and conjectures on 2-partitions of multisets, 2017 7th International Conference on Modeling, Simulation, and Applied Optimization (ICMSAO).
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]
B. D. Sullivan, On a Conjecture of Andrica and Tomescu, J. Int. Sequences, 16 (2013), Article 13.3.1.
zbMATH, Review of Andrica and Tomescu

Cf. A000980, A025591, A058377, A063866, A063867, A113036, A113037, A141000.
"Decimations": A060468 = 2*A060005, A123117 = 2*A104456.
Analogous sequences for sums of squares and cubes are A158092, A158118, see also A019568. - Pietro Majer, Mar 15 2009
Cf. A053632, A059529, A326173, A326174, A326175.

M:=400; t1:=1; lprint(0,1); for n from 1 to M do t1:=expand(t1*(x^n+1/x^n)); lprint(n, coeff(t1,x,0)); od: # N. J. A. Sloane, Jul 07 2008

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]
nmax = 50; d = {1}; a1 = {};
Do[
  i = Ceiling[Length[d]/2];
  AppendTo[a1, If[i > Length[d], 0, d[[i]]]];
  d = PadLeft[d, Length[d] + 2 n] + PadRight[d, Length[d] + 2 n];
  , {n, nmax}];
a1 (* Ray Chandler, Mar 13 2014 *)

a(n)=my(x='x); polcoeff(prod(k=1,n,x^k+x^-k)+O(x),0) \\ Charles R Greathouse IV, May 18 2015

a(n)=0^n+floor(prod(k=1,n,2^(n*k)+2^(-n*k)))%(2^n) \\ Tani Akinari, Mar 09 2016

Asymptotic formula: a(n) ~ sqrt(6/Pi)*n^(-3/2)*2^n for n = 0 or 3 (mod 4) as n approaches infinity.
a(n) = 0 unless n == 0 or 3 (mod 4).
a(n) = constant term in expansion of Product_{ k = 1..n } (x^k + 1/x^k). - N. J. A. Sloane, Jul 07 2008
If n = 0 or 3 (mod 4) then a(n) = coefficient of x^(n(n+1)/4) in Product_{k=1..n} (1+x^k). - D. Andrica and I. Tomescu.
a(n) = 2*A058377(n) for any n > 0. - Rémy Sigrist, Oct 11 2017

More terms from Dean Hickerson, Aug 28 2001

Corrected and edited by Steven Finch, Feb 01 2009

A000980 Number of ways of writing 0 as Sum_{k=-n..n} e(k)*k, where e(k) is 0 or 1.

Original entry on oeis.org

2, 4, 8, 20, 52, 152, 472, 1520, 5044, 17112, 59008, 206260, 729096, 2601640, 9358944, 33904324, 123580884, 452902072, 1667837680, 6168510256, 22903260088, 85338450344, 318995297200, 1195901750512, 4495448217544, 16940411201280, 63983233268592

Offset: 0

N. J. A. Sloane

The 4-term sequence 2,4,8,20 is the answer to the "Solitaire Army" problem, or checker-jumping puzzle. It is too short to have its own entry. See Conway et a;., Winning Ways, Vol. 2, pp. 715-717. - N. J. A. Sloane, Mar 01 2018

Number of subsets of {-n..n} with sum 0. Also the number of subsets of {0..2n} that are empty or have mean n. For median instead of mean we have twice A024718. - Gus Wiseman, Apr 23 2023

			From _Gus Wiseman_, Apr 23 2023: (Start)
The a(0) = 2 through a(2) = 8 subsets of {-n..n} with sum 0 are:
  {}   {}        {}
  {0}  {0}       {0}
       {-1,1}    {-1,1}
       {-1,0,1}  {-2,2}
                 {-1,0,1}
                 {-2,0,2}
                 {-2,-1,1,2}
                 {-2,-1,0,1,2}
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 294.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see pp. 715-717.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 0..1668 (terms < 10^1000; terms 0..200 from T. D. Noe, terms 201..400 from Alois P. Heinz)
Eunice Y. S. Chan and R. M. Corless, Narayana, Mandelbrot, and A New Kind of Companion Matrix, arXiv preprint arXiv:1606.09132 [math.CO], 2016.
R. C. Entringer, Representation of m as Sum_{k=-n..n} epsilon_k k, Canad. Math. Bull., 11 (1968), 289-293.
Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]
J. H. van Lint, Representations of 0 as Sum_{k = -N..N} epsilon_k*k, Proc. Amer. Math. Soc., 18 (1967), 182-184.

A047653(n) = a(n)/2.
Bisection of A084239. Cf. A063865, A141000.
A007318 counts subsets by length, A327481 by integer mean.
A327475 counts subsets with integer mean, A000975 integer median.
Cf. A024718, A047997, A070925, A079309, A133406, A212352, A359893, A362046.

a000980 n = length $ filter ((== 0) . sum) $ subsequences [-n..n]

b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
      `if`(i=0, 1, 2*b(n, i-1)+b(n+i, i-1)+b(abs(n-i), i-1)))
    end:
a:=n-> 2*b(0, n):
seq(a(n), n=0..40); # Alois P. Heinz, Mar 10 2014

a[n_] := SeriesCoefficient[ Product[1+x^k, {k, -n, n}], {x, 0, 0}]; a[0] = 2; Table[a[n], {n, 0, 24}](* Jean-François Alcover, Nov 28 2011 *)
nmax = 26; d = {2}; a1 = {};
Do[
  i = Ceiling[Length[d]/2];
  AppendTo[a1, If[i > Length[d], 0, d[[i]]]];
  d = PadLeft[d, Length[d] + 2 n] + PadRight[d, Length[d] + 2 n] +
    2 PadLeft[PadRight[d, Length[d] + n], Length[d] + 2 n];
  , {n, nmax}];
a1 (* Ray Chandler, Mar 15 2014 *)
Table[Length[Select[Subsets[Range[-n,n]],Total[#]==0&]],{n,0,5}] (* Gus Wiseman, Apr 23 2023 *)

PARI
```
a(n)=polcoeff(prod(k=-n,n,1+x^k),0)
```

Constant term of Product_{k=-n..n} (1+x^k).
a(n) = Sum_i A067059(2n+1-i, i) = 2+2*Sum_j A047997(n, j); i.e., sum of alternate antidiagonals of A067059 and two more than twice row sums of A047997. - Henry Bottomley, Aug 11 2002
a(n) = A004171(n) - 2*A181765(n).
Coefficient of x^(n*(n+1)/2) in 2*Product_{k=1..n} (1+x^k)^2. - Sean A. Irvine, Oct 03 2011
From Gus Wiseman, Apr 23 2023: (Start)
a(n) = 2*A047653(n).
a(n) = A070925(2n+1) + 1.
a(n) = 2*A133406(2n+1).
a(n) = 2*(A212352(n) + 1).
a(n) = A222955(2n+1).
a(n) = 2*(A362046(2n) + 1).
(End)

More terms from Michael Somos, Jun 10 2000

A141002 a(n) = total number of different ways a grasshopper can take n hops.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 7, 12, 21, 37, 63, 116, 208, 372, 682, 1255, 2334, 4277, 7951, 14905, 27967, 52334, 98222, 186344, 352621, 666933, 1264406, 2413511, 4604124, 8766995, 16748492, 32124034, 61642942, 118049157, 226709069, 436727197, 841581933, 1619406091

Offset: 0

David Applegate and N. J. A. Sloane, Jul 21 2008

nonn

Consider a grasshopper (cf. A141000) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraint that it must always land on a point x >= 0; sequence gives number of different ways that it can make n hops.

Here, unlike A141000, there is no restriction on how large x can be (of course x <= n(n+1)/2).

			For example, for n=3 the grasshopper can hit 0=1+2-3 or 6=1+2+3; for n=4 it can hit 2=1+2+3-4, 4=1+2-3+4, or 10=1+2+3+4. For n=7 we can reach 8 in two different ways, which explains the first place where this sequence differs from A141001.

David W. Wilson, Table of n, a(n) for n = 0..1000

Cf. A141000, A141001.

A141001 a(n) = number of different landings of a grasshopper after n hops.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 7, 11, 16, 21, 26, 32, 38, 44, 51, 59, 67, 75, 84, 94, 104, 114, 125, 137, 149, 161, 174, 188, 202, 216, 231, 247, 263, 279, 296, 314, 332, 350, 369, 389, 409, 429, 450, 472, 494, 516, 539, 563, 587, 611, 636, 662, 688, 714, 741, 769, 797

Offset: 0

David Applegate and N. J. A. Sloane, Jul 21 2008

Here, unlike A141000, there is no restriction on how large x can be (of course x <= n(n+1)/2).

			For example, for n=3 the grasshopper can hit 0=1+2-3 or 6=1+2+3; for n=4 it can hit 2=1+2+3-4, 4=1+2-3+4, or 10=1+2+3+4.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).

Cf. A141000, A141002.

LinearRecurrence[{3,-4,4,-3,1},{1,1,1,2,3,4,7,11,16,21,26,32,38,44},60] (* Harvey P. Dale, Mar 26 2023 *)

Vec((1 - 2*x + 2*x^2 - x^3 + x^5 + x^6 - x^7 + 2*x^8 - 2*x^9 - x^12 + x^13) / ((1 - x)^3*(1 + x^2)) + O(x^60)) \\ Colin Barker, Aug 06 2017

a(n) = floor(n * (n+1) / 4 - 1) for n >= 9. The induction proof for A141000 shows that for n >= 21, you hit all numbers of the right parity except n(n+1)/2-2 and n(n+1)/2-4. The floor expression handles the various parity cases. - David Applegate.
G.f.: (1 - 2*x + 2*x^2 - x^3 + x^5 + x^6 - x^7 + 2*x^8 - 2*x^9 - x^12 + x^13) / ((1 - x)^3*(1 + x^2)). - Colin Barker, May 21 2013
From Colin Barker, Aug 06 2017: (Start)
a(n) = (1/8+i/8) * ((-5+5*i) + (-i)^(1+n) + i^n + (1-i)*n + (1-i)*n^2) for n>8 where i=sqrt(-1).
a(n) = 3*a(n-1) - 4*a(n-2) + 4*a(n-3) - 3*a(n-4) + a(n-5) for n>9.
(End)

A321535 Number of different ways a grasshopper can take n hops without landing on the same point more than once.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 7, 9, 14, 23, 35, 56, 86, 136, 216, 338, 535, 848, 1374, 2234, 3594, 5750, 9265, 14856, 24019, 39350, 64222, 104878, 170247, 276489, 452138, 739486, 1207429, 1974247, 3234889, 5295560, 8708262, 14276970, 23493811, 38683402, 63773042, 104840427

Offset: 0

Andrew Howroyd, Nov 12 2018

nonn

Consider a grasshopper (cf. A141000, A141002) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraints that it must always land on a point x >= 0 and no point may be visited more than once; sequence gives number of different ways that it can make n hops.

In other words, the number of n step self avoiding walks on a line where the n-th step has length n.

			a(6) = 4 because there are 4 walks with 6 steps:
0 -> 1 -> 3 -> 6 -> 2 -> 7 -> 13,
0 -> 1 -> 3 -> 6 -> 10 -> 5 -> 11,
0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 9,
0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 21.

Cf. A141000, A141002, A175941.

a(n)={local(f=vectorsmall(n*(n+1)/2+1)); my(recurse(p, k)=if(p>0&&!f[p], if(k==n, 1, f[p]=1; k++; my(z=self()(p+k, k) + self()(p-k, k)); f[p]=0; z))); recurse(1, 0)}

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A000980 Number of ways of writing 0 as Sum_{k=-n..n} e(k)*k, where e(k) is 0 or 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A141002 a(n) = total number of different ways a grasshopper can take n hops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A141001 a(n) = number of different landings of a grasshopper after n hops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A321535 Number of different ways a grasshopper can take n hops without landing on the same point more than once.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI