|
%I #21 Oct 22 2019 04:21:09
%S 1,3,13,62,306,1546,7958
%N Number of two-dimensional burst patterns of size n, i.e., translation inequivalent subsets of the grid Z^2 which can be covered by a connected subset of n elements (in the sense of von Neumann neighborhoods).
%C 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.
%C 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
%H M. Blaum, J. Bruck, A. Vardy, <a href="http://dx.doi.org/10.1109/18.661516">Interleaving schemes for multidimensional cluster errors</a>, IEEE Trans. on Inform. Theory, 44(2):730-743, March 1998.
%H Tuvi Etzion and Alexander Vardy, <a href="http://dx.doi.org/10.1109/18.978765">Two-dimensional interleaving schemes with repetitions: constructions and bounds</a>, IEEE Trans. on Inform. Theory, 48(2):428-457, 2002.
%H Moshe Schwartz and Tuvi Etzion, <a href="http://dx.doi.org/10.1109/ISIT.2004.1365434">Two-dimensional burst-correcting codes</a>, Proceedings, International Symposium on Information Theory, 2004.
%e a(3) = 13 because we have the following burst patterns (the *'s indicate the 1's):
%e 1) *
%e 2) **
%e 3) *.*
%e 4) *
%e ...*
%e 5) *
%e ....
%e ...*
%e 6) *
%e ....*
%e 7) .*
%e ...*
%e 8) ***
%e 9) **
%e ....*
%e 10) *
%e ....**
%e 11) .*
%e ....**
%e 12) **
%e ....*
%e 13) *
%e ....*
%e ....*
%e 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
%Y Cf. A093426, A093427.
%K nonn,more
%O 1,2
%A Tuvi Etzion and Moshe Schwartz (etzion(AT)cs.technion.ac.il), May 11 2004
%E Definition simplified and example corrected by _M. F. Hasler_, Aug 20 2014
|
