The combinatorics of discrete self-similarity
This paper deals with the concept of discrete self-similarity which involves essentially the study of subsets having the same structure as the original set but are smaller in size. It means if we have a finite set \(S\) with \(n\) elements and with structure \(M\), then to find the number of subsets of \(S\) having the same structure \(M\). In particuar, the following result dealing with self-similarity on the hypercube is given: ``Consider the \(m\)-dimensional cube (hypercube) of side length \(n\) divided into \(n^m\) unit size \(m\)-cubes. How many \(m\)-cubes of size \(k\) does the hypercube contain, where \(1\leq k\leq n\)?'' Familiar examples of self-similarity include topics such as group/subgroup, matrix/submatrix, graph/subgraph, tree/subtree, etc. Illustrative examples are given to show how counting the self-similar subsets unifies some of the most important combinatorical numbers (e.g. Bernoulli numbers, Gaussian coefficients, Stirling and Bell numbers, the Eulerian numbers, etc.) in applied mathematics, and how a study of the algebraic structure of these self-similar subsets leads to a powerful method for solving combinatorial problems known as generalized Möbius inversion. The paper ends with some open and unresolved problems in this area.
scientific article; zbMATH DE number 1089809
scientific article