The combinatorics of discrete self-similarity
type: Item
instance of: scholarly article
title: The combinatorics of discrete self-similarity
zbMATH Open document ID: 0885.05013
author: John Konvalina
published in: Advances in Applied Mathematics
publication date: 1997-12-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1089809
zbMATH Keywords: discrete self-similarity
zbMATH Keywords: hypercube
zbMATH Keywords: combinatorical numbers
zbMATH Keywords: generalized Möbius inversion
zbMATH Keywords: problems
reviewed by: D. V. Chopra
MaRDI profile type: Publication
full work available at URL: aama.1997.0556
OpenAlex ID: W1998320060
cites work: Q4146776
cites work: Q4101884
cites work: On the Applications of Mobius Inversion in Combinatorial Analysis
cites work: Q5598073
cites work: Q5331549
cites work: Q3335786
cites work: Eulerian Numbers and Polynomials
cites work: Combinatorial extreme value distributions
cites work: Sums of powers of integers: a little of the history
cites work: Théorie géométrique des polynômes eulériens
cites work: Q4927338
cites work: Q5592270
cites work: On the Foundations of Combinatorial Theory IV Finite Vector Spaces and Eulerian Generating Functions
cites work: Q4040797
cites work: Q3715120
cites work: Q3856819
cites work: Q3999066
cites work: Q5535148
cites work: Q5585020
cites work: Q3765876
cites work: Q3934898
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Q4840174
cites work: The Number of Partitions of a Set
cites work: Q3748279
cites work: Q4002255
cites work: Q4324964
DOI: 10.1006/AAMA.1997.0556
description: scientific article; zbMATH DE number 1089809