OFFSET
0,5
COMMENTS
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.
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).
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
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..5150
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
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.
FORMULA
A(n, 0)=1, n>=0, A(0, r)=0, r>0.
A(n, r) = A(n, r-1) + A(n-1, r-1) + A(n-1, r).
A(n, r) = Sum_{k=0..min(n,r)} binomial(r-1,k-1)*binomial(n,k)*2^k.
Triangle T(m, r) = A(m-r, r), n >= 0, 0 <= r <= n, otherwise 0. - Wolfdieter Lang, Jan 31 2016
A(n, k) = [x^k] ((1 + x)/(1 - x))^n. - Ilya Gutkovskiy, May 23 2017
EXAMPLE
The array A(n, k) begins:
n \ k 0 1 2 3 4 5 6 7 8 9
---------------------------------------------------------
0: 1 0 0 0 0 0 0 0 0 0
1: 1 2 2 2 2 2 2 2 2 2
2: 1 4 8 12 16 20 24 28 32 36
3: 1 6 18 38 66 102 146 198 258 326
4: 1 8 32 88 192 360 608 952 1408 1992
5: 1 10 50 170 450 1002 1970 3530 5890 9290
6: 1 12 72 292 912 2364 5336 10836 20256 35436
7: 1 14 98 462 1666 4942 12642 28814 59906 115598
8: 1 16 128 688 2816 9424 27008 68464 157184 332688
9: 1 18 162 978 4482 16722 53154 148626 374274 864146
...
For instance, in a 5-hypercube lattice there are 170 nodes situated at a Manhattan distance of 3 for a chosen node.
The triangle T(m, r) begins:
m\r 0 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 1 0
2: 1 2 0
3: 1 4 2 0
4: 1 6 8 2 0
5: 1 8 18 12 2 0
6: 1 10 32 38 16 2 0
7: 1 12 50 88 66 20 2 0
8: 1 14 72 170 192 102 24 2 0
9: 1 16 98 292 450 360 146 28 2 0
10: 1 18 128 462 912 1002 608 198 32 2 0
... Formatted by Wolfdieter Lang, Jan 31 2016
MAPLE
# Prints the array by rows.
gf := n -> ((1 + x)/(1 - x))^n: ser := n -> series(gf(n), x, 40):
seq(lprint(seq(coeff(ser(n), x, k), k=0..6)), n=0..9); # Peter Luschny, Mar 20 2020
MATHEMATICA
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 *)
PROG
(Python)
from sympy import binomial
def T(n, r):
if r==0: return 1
return sum(binomial(r - 1, k - 1) * binomial(n - r, k) * 2**k for k in range(min(n - r, r) + 1))
for n in range(11): print([T(n, r) for r in range(n + 1)]) # Indranil Ghosh, May 23 2017
CROSSREFS
Partial sums on rows of A give A008288.
KEYWORD
nonn,tabl
AUTHOR
Dmitry Zaitsev, Dec 24 2015
STATUS
approved