OFFSET
1,2
COMMENTS
Original definition: Number of different two-dimensional burst patterns in the grid graph: The grid graph has Z^2 as vertices and each vertex (x,y) is connected to (x-1,y),(x+1,y),(x,y-1),(x,y+1). A cluster of size t is a set of t points such that each pair of points of the set is on a connected path contained entirely within the set. A burst pattern is a labeling of Z^2 with 0's and 1's. The term a(n) denotes the number of different (up to a translation) burst patterns whose 1's are covered by a cluster of size n.
As shown in the examples 3, 5, 6 and 7 below, the set need not be connected itself. But this is always the case when it has n points; in such a case, it coincides with the covering set. - M. F. Hasler, Aug 28 2014
LINKS
M. Blaum, J. Bruck, A. Vardy, Interleaving schemes for multidimensional cluster errors, IEEE Trans. on Inform. Theory, 44(2):730-743, March 1998.
Tuvi Etzion and Alexander Vardy, Two-dimensional interleaving schemes with repetitions: constructions and bounds, IEEE Trans. on Inform. Theory, 48(2):428-457, 2002.
Moshe Schwartz and Tuvi Etzion, Two-dimensional burst-correcting codes, Proceedings, International Symposium on Information Theory, 2004.
EXAMPLE
a(3) = 13 because we have the following burst patterns (the *'s indicate the 1's):
1) *
2) **
3) *.*
4) *
...*
5) *
....
...*
6) *
....*
7) .*
...*
8) ***
9) **
....*
10) *
....**
11) .*
....**
12) **
....*
13) *
....*
....*
The absence of a V-shaped pattern, which would have a (taxicab) "diameter" of 3 but cannot be covered by a 3-element connected set, illustrates that the latter condition cannot be replaced by the former. - M. F. Hasler, Aug 28 2014
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Tuvi Etzion and Moshe Schwartz (etzion(AT)cs.technion.ac.il), May 11 2004
EXTENSIONS
Definition simplified and example corrected by M. F. Hasler, Aug 20 2014
STATUS
approved