|
%I #51 Mar 22 2021 03:42:33
%S 1,1,0,1,2,0,1,4,2,0,1,6,8,2,0,1,8,18,12,2,0,1,10,32,38,16,2,0,1,12,
%T 50,88,66,20,2,0,1,14,72,170,192,102,24,2,0,1,16,98,292,450,360,146,
%U 28,2,0,1,18,128,462,912,1002,608,198,32,2,0
%N Square array A(n,r), the number of neighbors at a sharp Manhattan distance r in a finite n-hypercube lattice, read by upwards antidiagonals; A(n,r) = Sum_{k=0..min(n,r)} binomial(r-1,k-1)*binomial(n,k)* 2^k.
%C In an n-dimensional hypercube lattice, the array A(n,r) gives the number of nodes situated at a Manhattan distance equal to r, counting the current node. When counting coordinate offsets for neighboring nodes, binomial(n,k) chooses k nonzero coordinates from n coordinates, binomial(r-1,k-1) partitions the number r as the sum of exactly k nonzero numbers, and 2^k counts combinations of signs for coordinate offsets; starting indexing from 0 adds 1, which counts the current node.
%C In cellular automata theory, the cell surrounding with Manhattan distance less than or equal to r is called the von Neumann neighborhood of radius r or the diamond-shaped neighborhood to distinguish it from other generalizations of the von Neumann neighborhood for radius r>1, for instance, as a neighborhood having a difference in the range from -r to r in exactly one coordinate (the "narrow" von Neumann neighborhood of radius r).
%C The square array of partial sums of A(n,r) on rows gives us the Delannoy numbers A008288, which correspond to the number of nodes in the diamond-shaped neighborhood of radius r. - _Dmitry Zaitsev_, Dec 24 2015
%H Vincenzo Librandi, <a href="/A266213/b266213.txt">Table of n, a(n) for n = 0..5150</a>
%H Bela Bajnok, <a href="https://arxiv.org/abs/1705.07444">Additive Combinatorics: A Menu of Research Problems</a>, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
%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 A(n, 0)=1, n>=0, A(0, r)=0, r>0.
%F A(n, r) = A(n, r-1) + A(n-1, r-1) + A(n-1, r).
%F A(n, r) = Sum_{k=0..min(n,r)} binomial(r-1,k-1)*binomial(n,k)*2^k.
%F Triangle T(m, r) = A(m-r, r), n >= 0, 0 <= r <= n, otherwise 0. - _Wolfdieter Lang_, Jan 31 2016
%F A(n, k) = [x^k] ((1 + x)/(1 - x))^n. - _Ilya Gutkovskiy_, May 23 2017
%e The array A(n, k) begins:
%e n \ k 0 1 2 3 4 5 6 7 8 9
%e ---------------------------------------------------------
%e 0: 1 0 0 0 0 0 0 0 0 0
%e 1: 1 2 2 2 2 2 2 2 2 2
%e 2: 1 4 8 12 16 20 24 28 32 36
%e 3: 1 6 18 38 66 102 146 198 258 326
%e 4: 1 8 32 88 192 360 608 952 1408 1992
%e 5: 1 10 50 170 450 1002 1970 3530 5890 9290
%e 6: 1 12 72 292 912 2364 5336 10836 20256 35436
%e 7: 1 14 98 462 1666 4942 12642 28814 59906 115598
%e 8: 1 16 128 688 2816 9424 27008 68464 157184 332688
%e 9: 1 18 162 978 4482 16722 53154 148626 374274 864146
%e ...
%e For instance, in a 5-hypercube lattice there are 170 nodes situated at a Manhattan distance of 3 for a chosen node.
%e The triangle T(m, r) begins:
%e m\r 0 1 2 3 4 5 6 7 8 9 10 ...
%e 0: 1
%e 1: 1 0
%e 2: 1 2 0
%e 3: 1 4 2 0
%e 4: 1 6 8 2 0
%e 5: 1 8 18 12 2 0
%e 6: 1 10 32 38 16 2 0
%e 7: 1 12 50 88 66 20 2 0
%e 8: 1 14 72 170 192 102 24 2 0
%e 9: 1 16 98 292 450 360 146 28 2 0
%e 10: 1 18 128 462 912 1002 608 198 32 2 0
%e ... Formatted by _Wolfdieter Lang_, Jan 31 2016
%p # Prints the array by rows.
%p gf := n -> ((1 + x)/(1 - x))^n: ser := n -> series(gf(n), x, 40):
%p seq(lprint(seq(coeff(ser(n), x, k), k=0..6)), n=0..9); # _Peter Luschny_, Mar 20 2020
%t Table[Sum[Binomial[r - 1, k - 1] Binomial[n - r, k] 2^k, {k, 0, Min[n - r, r]}], {n, 0, 10}, {r, 0, n}] // Flatten (* _Michael De Vlieger_, Dec 24 2015 *)
%o (Python)
%o from sympy import binomial
%o def T(n, r):
%o if r==0: return 1
%o return sum(binomial(r - 1, k - 1) * binomial(n - r, k) * 2**k for k in range(min(n - r, r) + 1))
%o for n in range(11): print([T(n, r) for r in range(n + 1)]) # _Indranil Ghosh_, May 23 2017
%Y Other versions: A035607, A113413, A119800, A122542.
%Y Partial sums on rows of A give A008288.
%Y Cf. A001333 (row sums of T). A057077 (alternating row sums of T). - _Wolfdieter Lang_, Jan 31 2016
%K nonn,tabl
%O 0,5
%A _Dmitry Zaitsev_, Dec 24 2015
|
