Given a n = n square divided into n smaller squares i.e., a n = n . chessboard , how many k = k squares does it contain, where 1
The answer itself turns out to be a square, namely, n q 1 y k . Thus, the total number of squares contained in the n = n square is the sum of the squares: 1 2 q 2 2 q ะธะธะธ qn 2 .
In the square problem we are essentially counting subsets that have the same structure as the original set but are smaller in size. Intuitively, we can think of this as self-similarity on a discrete scale. The concept of self-similarity has been extensively studied from an analytic perspective w x since Mandlebrot's original work on fractals 22 . Many variants of the concept have been defined including strict self-similarity, fractal self-similarity, self-affinity, and statistical self-similarity. The underlying idea involves the study of sets containing subsets closely resembling the whole but smaller in size. Self-similarity in fractals such as the Mandlebrot set, the Cantor set, and the Sierpinski triangle, reveals how the global and local structures are nearly identical except for scale. Also, each of these fractals contains an infinite number of self-similar subsets, that is, scaled down versions of the original fractal. In this article we will explore the combinatorics of a discrete analogue of self-similarity where scaled down is replaced by same finite structure, smaller size. In particular, we consider the following generalization of the square problem: Giยจen a finite set S of size n