login
A265014
Triangle read by rows: T(n,k) = number of neighbors in n-dimensional lattice for generalized neighborhood given with parameter k.
0
2, 4, 8, 6, 18, 26, 8, 32, 64, 80, 10, 50, 130, 210, 242, 12, 72, 232, 472, 664, 728, 14, 98, 378, 938, 1610, 2058, 2186, 16, 128, 576, 1696, 3488, 5280, 6304, 6560, 18, 162, 834, 2850, 6882, 12258, 16866, 19170, 19682, 20, 200, 1160, 4520, 12584, 26024, 41384, 52904, 58024, 59048
OFFSET
1,1
COMMENTS
In an n-dimensional hypercube lattice, the sequence gives the number of nodes situated at a Chebyshev distance of 1 combined with Manhattan distance not greater than k, 1<=k<=n. In terms of cellular automata, it gives the number of neighbors in a generalized neighborhood given with parameter k: at k=1, we obtain von Neumann's neighborhood with 2n neighbors (A005843), and at k=n, we obtain Moore's neighborhood with 3^n-1 neighbors (A024023). It represents partial sums of A013609 rows, first element of each row (equal to 1) excluded.
LINKS
D. A. Zaitsev, Generator of lattices
Dmitry Zaitsev, k-neighborhood for Cellular Automata, arXiv preprint arXiv:1605.08870 [cs.DM], 2016.
D. A. Zaitsev, A generalized neighborhood for cellular automata, Theoretical Computer Science, 666 (2017), 21-35.
FORMULA
T(n,k) = Sum_{r=1..k} 2^r*binomial(n,r).
Recurrence: T(n,k) = T(n-1,k-1)-2T(n-1,k-2)+T(n-1,k)+T(n,k-1), T(n,1) = 2n, T(n,n) = 3^n-1.
EXAMPLE
Triangle:
n\k 1 2 3 4 5 6 7 8
--------------------------------------------
1 2
2 4 8
3 6 18 26
4 8 32 64 80
5 10 50 130 210 242
6 12 72 232 472 664 728
7 14 98 378 938 1610 2058 2186
8 16 128 576 1696 3488 5280 6304 6560
...
For instance, for n=3, in a cube:
k=1 corresponds to von Neumann's neighborhood with 6 neighbors situated on facets and given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1)};
k=2 corresponds to 18 neighbors situated on facets and sides and given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1),(-1,-1,0),(-1,0,-1),(0,-1,-1),(-1,0,1),(-1,1,0),(0,-1,1),(0,1,-1),(1,0,-1),(1,-1,0),(1,1,0),(1,0,1),(0,1,1)};
k=3 corresponds to Moore's neighborhood with 26 neighbors situated on facets, sides and corners given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1),(-1,-1,0),(-1,0,-1),(0,-1,-1),(-1,0,1),(-1,1,0),(0,-1,1),(0,1,-1),(1,0,-1),(1,-1,0),(1,1,0),(1,0,1),(0,1,1),(-1,-1,-1),(1,-1,-1),(-1,1,-1),(1,1,-1),(-1,-1,1),(1,-1,1),(-1,1,1),(1,1,1)}.
MATHEMATICA
T[n_, k_] := 3^n - 2^(k+1) Binomial[n, k+1] Hypergeometric2F1[1, k-n+1, k+2, -2] - 1;
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 26 2018 *)
PROG
(PARI) tabl(nn) = {for (n=1, nn, for (k=1, n, print1(sum(r=1, k, 2^r*binomial(n, r)), ", "); ); print(); ); } \\ Michel Marcus, Dec 16 2015
CROSSREFS
First column equals to A005843.
Diagonal equals to A024023.
Partial row sums of A013609, first element of each row excluded.
Sequence in context: A277331 A124510 A131886 * A262243 A328964 A061284
KEYWORD
nonn,tabl
AUTHOR
Dmitry Zaitsev, Nov 30 2015
EXTENSIONS
More terms from Michel Marcus, Dec 16 2015
STATUS
approved