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

%I

%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 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 G.f. of row n: ((1 + x)/(1 - x))^n. - _Ilya Gutkovskiy_, May 23 2017

%e The array A(n, r) begins:

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

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

%o for n in xrange(0, 11): print [T(n, r) for r in xrange(0, 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

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 26 15:16 EDT 2017. Contains 288766 sequences.