Dmitry Zaitsev - cp's OEIS frontend

User: Dmitry Zaitsev

Dmitry Zaitsev has authored 2 sequences.

A265014 Triangle read by rows: T(n,k) = number of neighbors in n-dimensional lattice for generalized neighborhood given with parameter k.

2, 4, 8, 6, 18, 26, 8, 32, 64, 80, 10, 50, 130, 210, 242, 12, 72, 232, 472, 664, 728, 14, 98, 378, 938, 1610, 2058, 2186, 16, 128, 576, 1696, 3488, 5280, 6304, 6560, 18, 162, 834, 2850, 6882, 12258, 16866, 19170, 19682, 20, 200, 1160, 4520, 12584, 26024, 41384, 52904, 58024, 59048

Offset: 1

Dmitry Zaitsev, Nov 30 2015

In an n-dimensional hypercube lattice, the sequence gives the number of nodes situated at a Chebyshev distance of 1 combined with Manhattan distance not greater than k, 1<=k<=n. In terms of cellular automata, it gives the number of neighbors in a generalized neighborhood given with parameter k: at k=1, we obtain von Neumann's neighborhood with 2n neighbors (A005843), and at k=n, we obtain Moore's neighborhood with 3^n-1 neighbors (A024023). It represents partial sums of A013609 rows, first element of each row (equal to 1) excluded.

			Triangle:
n\k   1    2    3    4    5    6    7    8
--------------------------------------------
1     2
2     4    8
3     6   18   26
4     8   32   64   80
5    10   50  130  210  242
6    12   72  232  472  664  728
7    14   98  378  938 1610 2058 2186
8    16  128  576 1696 3488 5280 6304 6560
...
For instance, for n=3, in a cube:
k=1 corresponds to von Neumann's neighborhood with 6 neighbors situated on facets and given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1)};
k=2 corresponds to 18 neighbors situated on facets and sides and given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1),(-1,-1,0),(-1,0,-1),(0,-1,-1),(-1,0,1),(-1,1,0),(0,-1,1),(0,1,-1),(1,0,-1),(1,-1,0),(1,1,0),(1,0,1),(0,1,1)};
k=3 corresponds to Moore's neighborhood with 26 neighbors situated on facets, sides and corners given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1),(-1,-1,0),(-1,0,-1),(0,-1,-1),(-1,0,1),(-1,1,0),(0,-1,1),(0,1,-1),(1,0,-1),(1,-1,0),(1,1,0),(1,0,1),(0,1,1),(-1,-1,-1),(1,-1,-1),(-1,1,-1),(1,1,-1),(-1,-1,1),(1,-1,1),(-1,1,1),(1,1,1)}.

D. A. Zaitsev, Generator of lattices
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.

First column equals to A005843.
Diagonal equals to A024023.
Partial row sums of A013609, first element of each row excluded.

T[n_, k_] := 3^n - 2^(k+1) Binomial[n, k+1] Hypergeometric2F1[1, k-n+1, k+2, -2] - 1;
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 26 2018 *)

tabl(nn) = {for (n=1, nn, for (k=1, n, print1(sum(r=1, k, 2^r*binomial(n,r)), ", ");); print(););} \\ Michel Marcus, Dec 16 2015

T(n,k) = Sum_{r=1..k} 2^r*binomial(n,r).

Recurrence: T(n,k) = T(n-1,k-1)-2T(n-1,k-2)+T(n-1,k)+T(n,k-1), T(n,1) = 2n, T(n,n) = 3^n-1.

More terms from Michel Marcus, Dec 16 2015

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.

Original entry on oeis.org

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

Offset: 0

Dmitry Zaitsev, Dec 24 2015

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
For n >= 2, the term A(n,r) gives the number of polyominoes of bounding box 2 x (r+n-1) of area (r + 2(n-1)). Let A'(n,k) be the table A(n,k) without the first two rows. The sum of the terms in the i-th anti-diagonal of A'(n,k) gives the i-th term of A034182. - Louis Marin, Dec 11 2024

			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

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.

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

# 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

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 *)

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

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

cp's OEIS Frontend

User: Dmitry Zaitsev

A265014 Triangle read by rows: T(n,k) = number of neighbors in n-dimensional lattice for generalized neighborhood given with parameter k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

cp's OEIS Frontend

User: Dmitry Zaitsev

A265014 Triangle read by rows: T(n,k) = number of neighbors in n-dimensional lattice for generalized neighborhood given with parameter k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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.