login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #51 Jun 22 2022 23:18:48

%S 0,1,2,3,5,8,7,11,17,26,15,23,35,53,80,31,47,71,107,161,242,63,95,143,

%T 215,323,485,728,127,191,287,431,647,971,1457,2186,255,383,575,863,

%U 1295,1943,2915,4373,6560,511,767,1151,1727,2591,3887,5831,8747,13121

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

%C Let n be the dimension of the cubic array.

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

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

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

%C The triangle in A094615 is a subtriangle. - _Philippe Deléham_, Oct 31 2013

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

%H Dmitry A. Zaitsev, <a href="https://doi.org/10.1016/j.tcs.2016.11.002">A generalized neighborhood for cellular automata</a>, Theoretical Computer Science, 2016, Volume 666, 1 March 2017, Pages 21-35.

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

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

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

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

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

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

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

%F From _Wolfdieter Lang_, May 04 2022: (Start)

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

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

%F (End)

%e Triangle starts:

%e n \ m 0 1 2 3 4 5 6 7 8 9 10 ...

%e 0: 0

%e 1: 1 2

%e 2: 3 5 8

%e 3: 7 11 17 26

%e 4: 15 23 35 53 80

%e 5: 31 47 71 107 161 242

%e 6: 63 95 143 215 323 485 728

%e 7: 127 191 287 431 647 971 1457 2186

%e 8: 255 383 575 863 1295 1943 2915 4373 6560

%e 9: 511 767 1151 1727 2591 3887 5831 8747 13121 19682

%e 10: 1023 1535 2303 3455 5183 7775 11663 17495 26243 39365 59048

%e ... (reformatted (and extended) by _Wolfdieter Lang_, May 04 2022)

%e For a 3-d cube, at a corner, the number of horizontal and vertical neighbors is 3, hence m = 3-3 = 0.

%e Along the edge, the number of horizontal and vertical neighbors is 4, hence m = 4-3 = 1.

%e In a face, the number of horizontal and vertical neighbors is 5, hence m = 5-3 = 2.

%e In the interior, the number of horizontal and vertical neighbors is 6, hence m = 6-3 = 3.

%e T(3,2) = 17 because a cell on the face of a 3-d cube has 17 neighbors.

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

%o (C)

%o void a10(){int p3[10], p2[10], n, m, a; p3[0]=1; p2[0]=1;

%o for(n=1;n<10;n++){ p2[n]=p2[n-1]*2; p3[n]=p3[n-1]*3;

%o for(m=0;m<=d;m++){ a=p3[m]*p2[n-m]-1; printf("%d ",a); }

%o printf("\n"); } } /* _Dmitry Zaitsev_, Oct 23 2015 */

%Y Cf. A000225, A024023, A051162, A013609.

%Y Sequence numbers are 1 less than A036561.

%Y Cf. A048473, A094615.

%K nonn,easy,tabl

%O 0,3

%A _Ron R. King_, Oct 18 2013