Combinatorial Analysis
What is combinatorial analysis
Combinatorial analysis is the area of mathematics that examines how many distinct configurations can be formed from a given collection of objects.
The most familiar types of configurations are permutations, arrangements, and combinations.
The sum rule and the product rule
Combinatorial analysis is built on two foundational counting principles: the sum rule and the product rule.
The sum rule
If A and B are disjoint sets, the cardinality of their union A∪B is equal to the sum of their individual cardinalities. $$ |A∪B|=|A|+|B| $$
This principle extends naturally to any finite collection of pairwise disjoint sets.
Example
Consider a set of three consonants
$$ A = \{ k, m, z \} $$
and a set of two vowels
$$ B = \{ a, e \} $$
The sets are disjoint, so their intersection is empty:
$$ A ⋂ B = Ø $$
Their cardinalities are
$$ |A|=3 \\ |B|=2 $$
The union A ∪ B is
$$ A ∪ B = \{ k, m, z, a, e \} $$
which contains 5 elements
$$ |A ∪ B| = 5 $$
This agrees with the sum of the cardinalities of A and B:
$$ |A ∪ B| = |A|+|B| = 3 + 2 = 5 $$
The product rule
For two sets A and B, the product of their cardinalities |A|*|B| equals the cardinality of their Cartesian product A×B. $$ |A|\cdot|B| = |AxB| $$
This rule applies equally to any finite number of sets.
Example
Suppose I can choose a car type from two models
$$ A = \{ utilitaria, sportiva \} $$
and a color from three available options
$$ B=\{ rossa, verde, gialla \} $$
The cardinalities are
$$ |A|=2 \\ |B|=3 $$
The Cartesian product A×B consists of the ordered pairs
$$ A = \{ \\ (utilitaria, rossa), (utilitaria, verde), (utilitaria, gialla), \\ (sportiva, rossa), (sportiva, verde), (sportiva, gialla) \\ \} $$
The product set contains 6 elements
$$ |AxB|=6 $$
which matches the product of the two cardinalities:
$$ |AxB| = |A| \cdot |B| = 3 \cdot 2 = 6 $$
These principles extend in the same way to more complex situations.
