A230445 Triangle read by rows: T(n,m) = 3^m*2^(n-m)-1, the number of neighbors in an n-dimensional cubic array.

0, 1, 2, 3, 5, 8, 7, 11, 17, 26, 15, 23, 35, 53, 80, 31, 47, 71, 107, 161, 242, 63, 95, 143, 215, 323, 485, 728, 127, 191, 287, 431, 647, 971, 1457, 2186, 255, 383, 575, 863, 1295, 1943, 2915, 4373, 6560, 511, 767, 1151, 1727, 2591, 3887, 5831, 8747, 13121

Offset: 0

Author

Ron R. King, Oct 18 2013

Keywords

• nonn
• easy
• tabl

Comments

Let n be the dimension of the cubic array.

Let m be the "placement depth" of the cell within the array. m = (number of horizontal or vertical neighbors)-n. 0 <= m <= n.

Let T(n,m) represent the number of neighbors (horizontally, vertically, or diagonally) a cell has in an n-dimensional cube that has at least 3^n cells.

The sequence forms a triangle structure similar to Pascal’s triangle: T(0,0) in row one, T(1,0), T(1,1) in row two, etc.

The triangle in A094615 is a subtriangle. - Philippe Deléham, Oct 31 2013

In a finite n-dimensional hypercube lattice, the sequence gives the number of nodes situated at a Chebyshev distance of 1 for a node, situated on an m-cube bound, which is not on an (m-1)-cube bound. The number of m-cube bounds for n-cube is given by A013609. In cellular automata theory, the cell surrounding with Chebyshev distance 1 is called Moore's neighborhood. For von Neumann neighborhood (with Manhattan distance 1), an analogous sequence is represented by A051162. - Dmitry Zaitsev, Oct 22 2015

Examples

			Triangle starts:
n \ m  0    1    2    3    4    5     6     7     8     9    10 ...
0:     0
1:     1    2
2:     3    5    8
3:     7   11   17   26
4:    15   23   35   53   80
5:    31   47   71  107  161  242
6:    63   95  143  215  323  485   728
7:   127  191  287  431  647  971  1457  2186
8:   255  383  575  863 1295 1943  2915  4373  6560
9:   511  767 1151 1727 2591 3887  5831  8747 13121 19682
10: 1023 1535 2303 3455 5183 7775 11663 17495 26243 39365 59048
... (reformatted (and extended) by _Wolfdieter Lang_, May 04 2022)
For a 3-d cube, at a corner, the number of horizontal and vertical neighbors is 3, hence m = 3-3 = 0.
Along the edge, the number of horizontal and vertical neighbors is 4, hence m = 4-3 = 1.
In a face, the number of horizontal and vertical neighbors is 5, hence m = 5-3 = 2.
In the interior, the number of horizontal and vertical neighbors is 6, hence m = 6-3 = 3.
T(3,2) = 17 because a cell on the face of a 3-d cube has 17 neighbors.
		

Links

• Dmitry A. Zaitsev, A generalized neighborhood for cellular automata, Theoretical Computer Science, 2016, Volume 666, 1 March 2017, Pages 21-35.

Crossrefs

Cf. A000225, A024023, A051162, A013609.

Sequence numbers are 1 less than A036561.

Cf. A048473, A094615.

Programs

C

void a10(){int p3[10], p2[10], n, m, a; p3[0]=1; p2[0]=1;
for(n=1;n<10;n++){ p2[n]=p2[n-1]*2; p3[n]=p3[n-1]*3;
  for(m=0;m<=d;m++){ a=p3[m]*p2[n-m]-1; printf("%d ",a); }
  printf("\n"); } } /* Dmitry Zaitsev, Oct 23 2015 */

Mathematica

Table[3^m 2^(n - m) - 1, {n, 0, 9}, {m, 0, n}] // Flatten (* Michael De Vlieger, Oct 23 2015 *)

Formula

T(n,m) = 3^m*2^(n-m)-1, 0 <= m <= n.

T(n,0) = 2^n-1. (A000225)

T(n,n) = 3^n-1. (A024023)

T(n,m) = (3*T(n,m-1)+1)/2, first part of the Collatz sequence for the number 2^n-1, for n >= 1.

T(n,m) = (T(n-1,m) + T(n,m+1))/2, 0 <= m <= n-1.

T(n,m) = 1 + T(n-1,m-1) + T(n,m-1), 1 <= m <= n.

m = T2(n,k)-n, where T2(n,k) is A051162.

From Wolfdieter Lang, May 04 2022: (Start)

G.f. for column m: G(m, x) = x^m*(3^m - 1 - (3^m - 2)*x)/((1 - 2*x)*(1 - x)).

G.f. for row polynomials R(n, x) = Sum_{m=1..n} T(n, m)*x^m, for n >= 0: G(z, x) = z*(1 + (2 - 5*z)*x)/((1 - 2*z)*(1 - z)*(1 - 3*x*z)*(1 - x*z)).

(End)