login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
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

Vincenzo Librandi, Table of n, a(n) for n = 0..5150

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

G.f. of row n: ((1 + x)/(1 - x))^n. - Ilya Gutkovskiy, May 23 2017

EXAMPLE

The array A(n, r) begins:

n \ r  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

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): return sum([binomial(r - 1, k - 1)* binomial(n - r, k)*2**k for k in xrange(min(n - r, r) + 1)])

for n in xrange(0, 11): print [T(n, r) for r in xrange(0, n + 1)] # Indranil Ghosh, May 23 2017

CROSSREFS

Other versions: A035607, A113413, A119800, A122542.

Partial sums on rows of A give A008288.

Cf. A001333 (row sums of T). A057077 (alternating row sums of T). - Wolfdieter Lang, Jan 31 2016

Sequence in context: A228924 A246862 A194686 * A124915 A158239 A159819

Adjacent sequences:  A266210 A266211 A266212 * A266214 A266215 A266216

KEYWORD

nonn,tabl

AUTHOR

Dmitry Zaitsev, Dec 24 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 27 02:59 EDT 2017. Contains 288777 sequences.