A265014 Triangle read by rows: T(n,k) = number of neighbors in n-dimensional lattice for generalized neighborhood given with parameter k.

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

Author

Dmitry Zaitsev, Nov 30 2015

Keywords

• nonn
• tabl

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.

Examples

			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)}.
		

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.

Crossrefs

First column equals to A005843.

Diagonal equals to A024023.

Partial row sums of A013609, first element of each row excluded.

Programs

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 *)

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

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.

Extensions

More terms from Michel Marcus, Dec 16 2015