|
| |
|
|
A266213
|
|
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.
|
|
19
|
|
|
|
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, 50, 88, 66, 20, 2, 0, 1, 14, 72, 170, 192, 102, 24, 2, 0, 1, 16, 98, 292, 450, 360, 146, 28, 2, 0, 1, 18, 128, 462, 912, 1002, 608, 198, 32, 2, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
