login
Number of solutions to k_1 + 2*k_2 + ... + n*k_n = 0, where k_i are from {-1,0,1}, i=1..n.
(Formerly M2656)
22

%I M2656 #87 Oct 30 2023 00:47:48

%S 1,1,1,3,7,15,35,87,217,547,1417,3735,9911,26513,71581,194681,532481,

%T 1464029,4045117,11225159,31268577,87404465,245101771,689323849,

%U 1943817227,5494808425,15568077235,44200775239,125739619467

%N Number of solutions to k_1 + 2*k_2 + ... + n*k_n = 0, where k_i are from {-1,0,1}, i=1..n.

%C Also, number of maximally stable towers of 2 X 2 LEGO blocks.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D P. J. S. Watson, On "LEGO" towers, J. Rec. Math., 12 (No. 1, 1979-1980), 24-27.

%H Ray Chandler, <a href="/A007576/b007576.txt">Table of n, a(n) for n = 0..2106</a> (terms < 10^1000; first 101 terms from T. D. Noe)

%H D. Andrica and O. Bagdasar, <a href="https://doi.org/10.1016/j.endm.2018.11.001">Some remarks on 3-partitions of multisets</a>, Electron. Notes Discrete Math., TCDM'18 (2018).

%H Dorin Andrica and Ovidiu Bagdasar, <a href="https://doi.org/10.1007/s11139-021-00418-7">On k-partitions of multisets with equal sums</a>, The Ramanujan J. (2021) Vol. 55, 421-435.

%H Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Signum equations and extremal coefficients</a> [Broken link]

%H Steven R. Finch, <a href="/A000980/a000980.pdf">Signum equations and extremal coefficients</a>, February 7, 2009. [Cached copy, with permission of the author]

%H P. J. S. Watson, <a href="/A007575/a007575.pdf">On "LEGO" towers</a>, J. Rec. Math., 12 (No. 1, 1979-1980), 24-27. (Annotated scanned copy)

%H <a href="/wiki/Index_to_OEIS:_Section_Lc#LEGO">Index entry for sequences related to LEGO blocks</a>

%F Coefficient of x^(n*(n+1)/2) in Product_{k=1..n} (1+x^k+x^(2*k)).

%F Equivalently, the coefficient of x^0 in Product_{k=1..n} (1/x^k + 1 + x^k). - _Paul D. Hanna_, Jul 10 2018

%F a(n) ~ 3^(n + 1) / (2 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jul 11 2018

%F a(n) = (1/(2*Pi))*Integral_{t=0..2*Pi} ( Product_{k=1..n} (1+2*cos(k*t)) ) dt. - _Ovidiu Bagdasar_, Aug 08 2018

%e For n=4 there are 7 solutions: (-1,-1,1,0), (-1,0,-1,1), (-1,1,1,-1), (0,0,0,0), (1,-1,-1,1), (1,0,1,-1), (1,1,-1,0).

%t f[0] = 1; f[n_] := Coefficient[Expand@ Product[1 + x^k + x^(2k), {k, n}], x^(n(n + 1)/2)]; Table[f@n, {n, 0, 28}] (* _Robert G. Wilson v_, Nov 10 2006 *)

%o (Maxima) a(n):=coeff(expand(product(1+x^k+x^(2*k),k,1,n)),x,binomial(n+1,2));

%o makelist(a(n),n,0,24);

%Y Cf. A007575, A063865, A039826.

%K easy,nonn

%O 0,4

%A _Simon Plouffe_, _Robert G. Wilson v_ and _Vladeta Jovovic_

%E More terms from _David Wasserman_, Mar 29 2005

%E Edited by _N. J. A. Sloane_, Nov 07 2006. This is a merging of two sequences which, thanks to the work of _Søren Eilers_, we now know are identical.