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

%I #39 Sep 26 2018 16:26:09

%S 2,4,8,6,18,26,8,32,64,80,10,50,130,210,242,12,72,232,472,664,728,14,

%T 98,378,938,1610,2058,2186,16,128,576,1696,3488,5280,6304,6560,18,162,

%U 834,2850,6882,12258,16866,19170,19682,20,200,1160,4520,12584,26024,41384,52904,58024,59048

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

%C 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.

%H D. A. Zaitsev, <a href="https://github.com/dazeorgacm/hmn/">Generator of lattices</a>

%H Dmitry Zaitsev, <a href="https://arxiv.org/abs/1605.08870">k-neighborhood for Cellular Automata</a>, arXiv preprint arXiv:1605.08870 [cs.DM], 2016.

%H D. A. Zaitsev, <a href="https://doi.org/10.1016/j.tcs.2016.11.002">A generalized neighborhood for cellular automata</a>, Theoretical Computer Science, 666 (2017), 21-35.

%F T(n,k) = Sum_{r=1..k} 2^r*binomial(n,r).

%F 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.

%e Triangle:

%e n\k 1 2 3 4 5 6 7 8

%e --------------------------------------------

%e 1 2

%e 2 4 8

%e 3 6 18 26

%e 4 8 32 64 80

%e 5 10 50 130 210 242

%e 6 12 72 232 472 664 728

%e 7 14 98 378 938 1610 2058 2186

%e 8 16 128 576 1696 3488 5280 6304 6560

%e ...

%e For instance, for n=3, in a cube:

%e 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)};

%e 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)};

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

%t T[n_, k_] := 3^n - 2^(k+1) Binomial[n, k+1] Hypergeometric2F1[1, k-n+1, k+2, -2] - 1;

%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 26 2018 *)

%o (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

%Y First column equals to A005843.

%Y Diagonal equals to A024023.

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

%K nonn,tabl

%O 1,1

%A _Dmitry Zaitsev_, Nov 30 2015

%E More terms from _Michel Marcus_, Dec 16 2015