A035607 Table a(d,m) of number of points of L1 norm m in cubic lattice Z^d, read by antidiagonals (d >= 1, m >= 0).
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, 14, 72, 170, 192, 102, 24, 2, 1, 16, 98, 292, 450, 360, 146, 28, 2, 1, 18, 128, 462, 912, 1002, 608, 198, 32, 2, 1, 20, 162, 688, 1666, 2364, 1970, 952, 258, 36, 2, 1, 22, 200, 978, 2816
Offset: 0
Examples
From _Clark Kimberling_, Oct 24 2014: (Start) As a triangle of coefficients in polynomials v(n,x) in Comments, the first 6 rows are 1 1 2 1 4 2 1 6 8 2 1 8 18 12 2 1 10 32 38 16 2 ... (End) From _Shel Kaphan_, Mar 04 2023: (Start) For d=3, m=4: There are binomial(3,1)*2^1 = 6 facets (vertices) of binomial(4+1-1,1-1) = 1 point with <= one nonzero coordinate. There are binomial(3,2)*2^2 = 12 facets (edges) of binomial(4+2-1,2-1) = 5 points with <= two nonzero coordinates. There are binomial(3,3)*2^3 = 8 facets (faces) of binomial(4+3-1,3-1) = 15 points with <= three nonzero coordinates. a(3,4) = 8*15 - 12*5 + 6*1 = 120 - 60 + 6 = 66. (End)
Links
- Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
- Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
- J. H. Conway and N. J. A. Sloane, Low-Dimensional Lattices VII: Coordination Sequences, Proc. Royal Soc. London, A453 (1997), 2369-2389 (pdf).
- M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 13 2013
- Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 392.
- R. J. Mathar, Bivariate Generating Functions for Non-attacking Wazirs on Rectangular Boards (2024), Table 2.
- Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.
- Joan Serra-Sagrista, Enumeration of lattice points in l_1 norm, Inf. Proc. Lett. 76 (1-2) (2000) 39-44.
- J. Siehler, Adjacency-free selections from a 2xN grid (Mathematica notebook) [broken link]
- Jacob A. Siehler, Selections Without Adjacency on a Rectangular Grid, arXiv:1409.3869 [math.CO], 2014.
- Eric Weisstein's World of Mathematics, Independence Polynomial
- Eric Weisstein's World of Mathematics, Ladder Graph
Crossrefs
Programs
-
Haskell
a035607 n k = a035607_tabl !! n !! k a035607_row n = a035607_tabl !! n a035607_tabl = map fst $ iterate (\(us, vs) -> (vs, zipWith (+) ([0] ++ us ++ [0]) $ zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [1, 2]) -- Reinhard Zumkeller, Jul 20 2013 -
Maple
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
-
Mathematica
u[1, x_] := 1; v[1, x_] := 1; z = 16; u[n_, x_] := x*u[n - 1, x] + v[n - 1, x]; v[n_, x_] := 2 x*u[n - 1, x] + v[n - 1, x]; Table[Expand[u[n, x]], {n, 1, z/2}] Table[Expand[v[n, x]], {n, 1, z/2}] cu = Table[CoefficientList[u[n, x], x], {n, 1, z}]; TableForm[cu] Flatten[%] (* A008288 *) Table[Expand[v[n, x]], {n, 1, z}] cv = Table[CoefficientList[v[n, x], x], {n, 1, z}]; TableForm[cv] Flatten[%] (* A035607 *) (* Clark Kimberling, Mar 09 2012 *) 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 *) -
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))); tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n, k), ", ")); print); \\ as a triangle; Michel Marcus, Feb 27 2018
-
Sage
def A035607_row(n): @cached_function def prec(n, k): if k==n: return 1 if k==0: return 0 return prec(n-1,k-1)+2*sum(prec(n-i,k-1) for i in (2..n-k+1)) return [prec(n, n-k) for k in (0..n-1)] for n in (1..10): print(A035607_row(n)) # Peter Luschny, Mar 16 2016
Formula
From Johannes W. Meijer, Aug 05 2011: (Start)
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(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)
From Roger Cuculière, Apr 10 2006: (Start)
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).
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).
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)
G.f.: (1+x)/(1-x-x*y-x^2*y). - Vladeta Jovovic, Apr 02 2002 (But see previous lines!)
T(2*n,n) = A050146(n+1). - Reinhard Zumkeller, Jul 20 2013
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
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
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
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
Extensions
More terms from David W. Wilson
Maple program corrected and information added by Johannes W. Meijer, Aug 05 2011
Comments