login
Table a(d,m) of number of points of L1 norm m in cubic lattice Z^d, read by antidiagonals (d >= 1, m >= 0).
28

%I #131 Aug 07 2024 09:18:49

%S 1,1,2,1,4,2,1,6,8,2,1,8,18,12,2,1,10,32,38,16,2,1,12,50,88,66,20,2,1,

%T 14,72,170,192,102,24,2,1,16,98,292,450,360,146,28,2,1,18,128,462,912,

%U 1002,608,198,32,2,1,20,162,688,1666,2364,1970,952,258,36,2,1,22,200,978,2816

%N Table a(d,m) of number of points of L1 norm m in cubic lattice Z^d, read by antidiagonals (d >= 1, m >= 0).

%C Table also gives coordination sequences of same lattices.

%C Rows sums are given by A001333. Rising and falling diagonals are the tribonacci numbers A000213, A001590. - _Paul Barry_, Feb 13 2003

%C a(d,m) also gives the number of ways to choose m squares from a 2 X (d-1) grid so that no two squares in the selection are (horizontally or vertically) adjacent. - _Jacob A. Siehler_, May 13 2006

%C Mirror image of triangle A113413. - _Philippe Deléham_, Oct 15 2006

%C The Ca1 sums lead to A126116 and the Ca2 sums lead to A070550, see A180662 for the definitions of these triangle sums. - _Johannes W. Meijer_, Aug 05 2011

%C A035607 is jointly generated with the Delannoy triangle A008288 as an array of coefficients of polynomials v(n,x): initially, u(1,x) = v(1,x) = 1; for n > 1, u(n,x) = x*u(n-1,x) + v(n-1) and v(n,x) = 2*x*u(n-1,x) + v(n-1,x). See the Mathematica section. - _Clark Kimberling_, Mar 05 2012

%C Also, the polynomial v(n,x) above is x + (x + 1)*f(n-1,x), where f(0,x) = 1. - _Clark Kimberling_, Oct 24 2014

%C Rows also give the coefficients of the independence polynomial of the n-ladder graph. - _Eric W. Weisstein_, Dec 29 2017

%C Considering both sequences as square arrays (offset by one row), the rows of A035607 are the first differences of the rows of A008288, and the rows of A008288 are the partial sums of the rows of A035607. - _Shel Kaphan_, Feb 23 2023

%C Considering only points with nonnegative coordinates, the number of points at L1 distance = m in d dimensions is the same as the number of ways of putting m indistinguishable balls into d distinguishable urns, binomial(m+d-1, d-1). This is one facet of the cross-polytope. Allowing for + and - coordinates, there are binomial(d,i)*2^i facets containing points with up to i nonzero coordinates. Eliminating double counting of points with any coordinates = 0, there are Sum_{i=1..d} (-1)^(d-i)*binomial(m+i-1,i-1)*binomial(d,i)*2^i points at distance m in d dimensions. One may avoid the alternating sum by using binomial(m-1,i-1) to count only the points per facet with exactly i nonzero coordinates, avoiding any double counting, but the result is the same. - _Shel Kaphan_, Mar 04 2023

%H Reinhard Zumkeller, <a href="/A035607/b035607.txt">Rows n = 0..125 of triangle, flattened</a>

%H Bela Bajnok, <a href="https://arxiv.org/abs/1705.07444">Additive Combinatorics: A Menu of Research Problems</a>, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.

%H J. H. Conway and N. J. A. Sloane, Low-Dimensional Lattices VII: Coordination Sequences, Proc. Royal Soc. London, A453 (1997), 2369-2389 (<a href="http://neilsloane.com/doc/Me220.pdf">pdf</a>).

%H M. Janjic and B. Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv preprint arXiv:1301.4550 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 13 2013

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 392.

%H R. J. Mathar, <a href="http://viXra.org/abs/2404.0122">Bivariate Generating Functions for Non-attacking Wazirs on Rectangular Boards</a> (2024), Table 2.

%H Emanuele Munarini, <a href="http://www.emis.de/journals/INTEGERS/papers/j29/j29.Abstract.html">Combinatorial properties of the antichains of a garland</a>, Integers, 9 (2009), 353-374.

%H Joan Serra-Sagrista, <a href="http://dx.doi.org/10.1016/S0020-0190(00)00119-8">Enumeration of lattice points in l_1 norm</a>, Inf. Proc. Lett. 76 (1-2) (2000) 39-44.

%H J. Siehler, <a href="http://home.wlu.edu/~siehlerj/computing/index.html#af">Adjacency-free selections from a 2xN grid</a> (Mathematica notebook) [broken link]

%H Jacob A. Siehler, <a href="http://arxiv.org/abs/1409.3869">Selections Without Adjacency on a Rectangular Grid</a>, arXiv:1409.3869 [math.CO], 2014.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>

%F From _Johannes W. Meijer_, Aug 05 2011: (Start)

%F f(d,m) = Sum_{j=0..d-1} binomial(floor((d-1+j)/2), d-m-1)*binomial(d-m-1, floor((d-1-j)/2)), d >= 1 and 0 <= m <= d-1.

%F f(d,m) = f(d-1,m-1) + f(d-1,m) + f(d-2,m-1) (d >= 3 and 1 <= m <= d-1) with f(d,0) = 1 (d >= 1) and f(d,d-1) = 2 (d>=2). (End)

%F From _Roger Cuculière_, Apr 10 2006: (Start)

%F The generating function G(x,y) of this double sequence is the sum of a(n,p)*x^n*y^p, n=1..oo, p=0..oo, which is G(x,y) = x*(1+y)/(1-x-y-x*y).

%F The horizontal generating function H_n(y), which generates the rows of the table: (1, 2, 2, 2, 2, ...), (1, 4, 8, 12, 16, ...), (1, 6, 18, 38, 66, ...), is the sum of a(n,p)*y^p, p=0..oo, for each fixed n. This is H_n(y) = ((1+y)^n)/((1-y)^n).

%F The vertical generating function V_p(x), which generates the columns of the table: (1, 1, 1, 1, 1, ...), (2, 4, 6, 8, 10, ...), (2, 8, 18, 32, 50, ...), is the sum of a(n,p)*x^n, n=1..oo, for each fixed p. This is V_p(x) = 2*((1+x)^(p-1))/((1-x)^(p+1)) for p >= 1 and V_0(x) = x/(1-x). (End)

%F G.f.: (1+x)/(1-x-x*y-x^2*y). - _Vladeta Jovovic_, Apr 02 2002 (But see previous lines!)

%F T(2*n,n) = A050146(n+1). - _Reinhard Zumkeller_, Jul 20 2013

%F Seen as a triangle read by rows: T(n,0) = 1, for n > 1: T(n,n-1) = 2, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-2,k-1), 0 < k < n. - _Reinhard Zumkeller_, Jul 20 2013

%F Seen as a triangle T(n,k) with 0 <= k < n read by rows: T(n,0)=1 for n > 0 and T(n,k) = Sum_{i=0..k-1} binomial(n-k,i+1)*binomial(k-1,i)*2^(i+1) for k > 0. - _Werner Schulte_, Feb 22 2018

%F With p >= 1 and q >= 0, as a square array a(p,q) = T(p+q-1,q) = 2*p*Hypergeometric2F1[1-p, 1-q, 2, 2] for q >= 1. Consequently, a(p,q) = a(q,p)*p/q. - _Shel Kaphan_, Feb 14 2023

%F For n >= 1, T(2*n,n) = A002003(n), T(3*n,2*n) = A103885(n) and T(4*n,3*n) = A333715(n). - _Peter Bala_, Jun 15 2023

%e From _Clark Kimberling_, Oct 24 2014: (Start)

%e As a triangle of coefficients in polynomials v(n,x) in Comments, the first 6 rows are

%e 1

%e 1 2

%e 1 4 2

%e 1 6 8 2

%e 1 8 18 12 2

%e 1 10 32 38 16 2

%e ... (End)

%e From _Shel Kaphan_, Mar 04 2023: (Start)

%e For d=3, m=4:

%e There are binomial(3,1)*2^1 = 6 facets (vertices) of binomial(4+1-1,1-1) = 1 point with <= one nonzero coordinate.

%e There are binomial(3,2)*2^2 = 12 facets (edges) of binomial(4+2-1,2-1) = 5 points with <= two nonzero coordinates.

%e There are binomial(3,3)*2^3 = 8 facets (faces) of binomial(4+3-1,3-1) = 15 points with <= three nonzero coordinates.

%e a(3,4) = 8*15 - 12*5 + 6*1 = 120 - 60 + 6 = 66. (End)

%p A035607 := proc(d,m) local j: add(binomial(floor((d-1+j)/2),d-m-1)*binomial(d-m-1, floor((d-1-j)/2)),j=0..d-1) end: seq(seq(A035607(d,m),m=0..d-1),d=1..11); # d=dimension, m=norm # _Johannes W. Meijer_, Aug 05 2011

%t u[1, x_] := 1; v[1, x_] := 1; z = 16;

%t u[n_, x_] := x*u[n - 1, x] + v[n - 1, x];

%t v[n_, x_] := 2 x*u[n - 1, x] + v[n - 1, x];

%t Table[Expand[u[n, x]], {n, 1, z/2}]

%t Table[Expand[v[n, x]], {n, 1, z/2}]

%t cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];

%t TableForm[cu]

%t Flatten[%] (* A008288 *)

%t Table[Expand[v[n, x]], {n, 1, z}]

%t cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];

%t TableForm[cv]

%t Flatten[%] (* A035607 *)

%t (* _Clark Kimberling_, Mar 09 2012 *)

%t Reverse /@ CoefficientList[CoefficientList[Series[(1 + x)/(1 - x - x y - x^2 y), {x, 0, 10}], x], y] // Flatten (* _Eric W. Weisstein_, Dec 29 2017 *)

%o (Haskell)

%o a035607 n k = a035607_tabl !! n !! k

%o a035607_row n = a035607_tabl !! n

%o a035607_tabl = map fst $ iterate

%o (\(us, vs) -> (vs, zipWith (+) ([0] ++ us ++ [0]) $

%o zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [1, 2])

%o -- _Reinhard Zumkeller_, Jul 20 2013

%o (Sage)

%o def A035607_row(n):

%o @cached_function

%o def prec(n, k):

%o if k==n: return 1

%o if k==0: return 0

%o return prec(n-1,k-1)+2*sum(prec(n-i,k-1) for i in (2..n-k+1))

%o return [prec(n, n-k) for k in (0..n-1)]

%o for n in (1..10): print(A035607_row(n)) # _Peter Luschny_, Mar 16 2016

%o (PARI) T(n, k) = if (k==0, 1, sum(i=0, k-1, binomial(n-k,i+1)*binomial(k-1,i)*2^(i+1)));

%o tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n, k), ", ")); print); \\ as a triangle; _Michel Marcus_, Feb 27 2018

%Y Other versions: A113413, A119800, A122542, A266213.

%Y Cf. A008288, which has g.f. 1/(1-x-x*y-x^2*y).

%Y Cf. A078057 (row sums), A050146 (central terms).

%Y Cf. A050146.

%K nonn,easy,tabl

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_

%E Maple program corrected and information added by _Johannes W. Meijer_, Aug 05 2011