Combinatorics (Fall 2010)/Basic enumeration
Contents
Counting Problems
Basic Enumeration
The three basic rules for enumeration are:
- The sum rule: for any disjoint finite sets and , the cardinality of the union .
- The product rule: for any finite sets and , the cardinality of the Cartesian product .
- The bijection rule: if there exists a bijection between finite sets and , then .
Now we apply these rules to solve some basic enumeration problems.
Tuples
We count the number of -tuples of . Formally, we count the number of elements of . (Remember that .)
It is not very hard to see that this number is . That is, .
To prove this rigorously, we use "the product rule".
- The product rule: for any finite sets and , the cardinality of the Cartesian product .
To count the size of , we write , thus . Solving the recursion, we have that .
Functions
Consider the problem of counting the number of functions mapping from to , i.e. we count the number of functions in the form .
We claim that this is the same as counting the number of -tuples of . To see this, for any , we define a tuple by letting for every . It is easy to verify that defines a bijection (a 1-1 correspondence) between and . (Consider this as an exercise.)
Now we summon the "the bijection rule".
- The bijection rule: if there exists a bijection between finite sets and , then .
Applying this rule, we have that the number of functions from to equals the number of tuples in , which is as we proved previously.
Subsets
We count the number of subsets of a set.
Let be an -element set, or -set for short. Let denote the set of all subset of . is called the power set of .
We give a combinatorial proof that . We observe that every subset corresponds to a unique bit-vector , such that each bit indicates whether . Formally, define a map by , where
The map is a bijection. The proof that is a bijection is left as an exercise.
Since there is a bijection between and , it holds that .
There are two elements of the proof:
- Find a 1-1 correspondence between subsets of an -set and -bit vectors.
- An application of this in Computer Science is that we can use bit-array as a data structure for sets: any set defined over a universe can be represented by an array of bits.
- The bijection rule: if there is a 1-1 correspondence between two sets, then their cardinalities are the same.
Many counting problems are solved by establishing a bijection between the set to be counted and some easy-to-count set. This kind of proofs are usually called (non-rigorously) combinatorial proofs.
We give an alternative proof that . The proof needs another basic counting rule: "the sum rule".
- The sum rule: for any disjoint finite sets and , the cardinality of the union .
Define the function , where is an -set. Our goal is to compute . We prove the following recursion for .
Lemma - .
Proof. Fix an element , let be the set of subsets of that contain and let be the set of subsets of that do not contain . It is obvious that and are disjoint (i.e. ) and , because any subset of either contains or does not contain but not both.
Applying the sum rule,
- .
The next observation is that , because is exactly the , and is the set resulting from adding to every member of . Therefore,
- .
The elementary case , because has only one subset . Solving the recursion, we have that .
Subsets of fixed size
We then count the number of subsets of fixed size of a set. Again, let be an -set. We define to be the set of all -elements subsets (or -subsets) of . Formally, . The set is sometimes called the -uniform of .
We denote that . The notation is read " choose ".
Theorem - .
Proof. The number of ordered -subsets of an -set is . Every -subset has ways to order it.
- Some notations
- , read " factorial", is defined as that , with the convention that .
- is usually denoted as , read " lower factorial ".
Binomial coefficient
The quantity is called a binomial coefficient.
Proposition - ;
- .
Proof. 1. We give two proofs for the first equation:
- (1) (numerical proof)
- .
- (2) (combinatorial proof)
- Choosing elements from an -set is equivalent to choosing the elements to leave out. Formally, every -subset is uniquely specified by its complement , and the same holds for -subsets, thus we have a bijection between and .
2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. For an -element set , it is obvious that we can enumerate all subsets of by enumerating -subsets for every possible size , i.e. it holds that
For different , are obviously disjoint. By the sum rule,
- .
- (1) (numerical proof)
is called binomial coefficient for a reason. A binomial is a polynomial with two terms ("poly-" means many, and "bi-" means two, like in "binary", "bipartite", etc). The following celebrated Binomial Theorem states that if a power of a binomial is expanded, the coefficients in the resulting polynomial are the binomial coefficients.
Theorem (Binomial theorem) - .
Proof. Write as the product of factors
- .
The term is obtained by choosing from factors and 1 from the rest factors. There are ways of choosing these factors, so the coefficient of is .
The following proposition has an easy proof due to the binomial theorem.
Proposition - For , the numbers of subsets of an -set of even and of odd cardinality are equal.
Proof. Set in the binomial theorem.
therefore
For counting problems, what we care about are numbers. In the binomial theorem, a formal variable is introduced. It looks having nothing to do with our problem, but turns out to be very useful. This idea of introducing a formal variable is the basic idea of some advanced counting techniques, which will be discussed in future classes.
Compositions of an integer
A composition of is an expression of as an ordered sum of positive integers. A -composition of is a composition of with exactly positive summands.
Formally, a -composition of is a -tuple such that .
Suppose we have identical balls in a line. A -composition partitions these balls into nonempty sets, illustrated as follows.
So the number of -compositions of equals the number of ways we put bars "" into slots "", where each slot has at most one bar (because all the summands ):
which is equal to the number of ways of choosing slots out of slots, which is .
This graphic argument can be expressed as a formal proof. We construct a bijection between the set of -compositions of and as follows.
Let be a mapping that given a -composition of ,
maps every -composition to a -subset of . It is easy to verify that is a bijection, thus the number of -compositions of is .
The number of -compositions of is equal to the number of solutions to in positive integers. This suggests us to relax the constraint and count the number of solutions to in nonnegative integers. We call such a solution a weak -composition of .
Formally, a weak -composition of is a tuple such that .
Given a weak -composition of , if we set for every , then and
i.e., is a -composition of . It is easy to see that it defines a bijection between weak -compositions of and -compositions of . Therefore, the number of weak -compositions of is .
We now count the number of solutions to in nonnegative integers.
Let . Then and . The problem is transformed to that counting the number of solutions to the above equation in nonnegative integers. The answer is .
Multisets
A -subset of an -set is sometimes called a -combination of without repetitions. This suggests the problem of counting the number of -combinations of with repetitions; that is, we choose elements of , disregarding order and allowing repeated elements.
- Example
- . All -combination without repetitions are
- .
- Allowing repetitions, we also include the following 3-combinations:
Combinations with repetitions can be formally defined as multisets. A multiset is a set with repeated elements. Formally, a multiset on a set is a function . For any element , the integer is the number of repetitions of in , called the multiplicity of . The sum of multiplicities is called the cardinality of and is denoted as .
A -multiset on a set is a multiset on with . It is obvious that a -combination of with repetition is simply a -multiset on .
The set of all -multisets on is denoted . Assuming that , denote , which is the number of -combinations of an -set with repetitions.
Believe it or not: we have already evaluated the number . If , let , then is the number of solutions to in nonnegative integers, which is the number of weak -compositions of , which we have seen is .
There is a direct combinatorial proof that .
Given a -multiset on , then defining , we see that is a -subset of . Conversely, given a -subset of , then defining , we have that is a -multiset on . Therefore, we have a bijection between and .
Multinomial coefficients
The binomial coefficient may be interpreted as follows. Each element of an -set is placed into two groups, with elements in Group 1 and elements in Group 2. The binomial coefficient counts the number of such placements.
This suggests a generalization allowing more than two groups. Let be a tuple of nonnegative integers summing to . Let denote the number of ways of assigning each element of an -set to one of groups so that exactly elements are assigned to .
The binomial coefficient is just the case when there are two groups, and . The number is called a multinomial coefficient. We can think of it as that labeled balls are assigned to labeled bins, and is the number of assignments such that the -th bin has balls in it.
The multinomial coefficient can also be interpreted as the number of permutations of multisets. A permutation of an -set can be defined in two equivalent ways:
- a bijection ;
- a tuple such that all are distinct.
There are permutations of an -set .
A permutation of a multiset is a tuple such that every appears in for exactly times, where is the multiplicity of in .
- Example
- We want to enumerate all the ways of reordering the word "multinomial". Note that in this word, the letter "m", "l" and "i" each appears twice. So the problem is to enumerate the permutations of the multiset .
Let be a multiset of distinct elements such that has multiplicity in . A permutation of multiset assigns indices to groups, where each group corresponds to a distinct element , such that is assigned to group if .
Therefore, is also the number of permutations of a multiset with such that has distinct elements whose multiplicities are given by .
Theorem
Proof. There are permutations of objects. Assume that these objects are the elements of an multiset of distinct elements with and multiplicities . Since permutations of object do not change the permutation of the multiset , every permutations of these objects correspond to the same permutation of the multiset . Thus, the number of permutations of is .
We also have the Multinomial Theorem.
Theorem - is the coefficient of in .
Proof. Write
- .
Each of the factors corresponds to a distinct ball, and correspond to groups. The coefficient of equals the number of ways to put distinct balls to distinct groups so that group receives balls, which is exactly our first definition of .
Partitions of a set
A partition of finite set is a collection of subsets of such that:
- for every ;
- if (also called that blocks are pairwise disjoint);
- .
Each is called a block of partition . We call a -partition of if .
Define to be the number of -partitions of an -set. Note that since a partition is a set, the order of blocks is disregarded when counting -partitions.
The number is called a Stirling number of the second kind.
- Stirling number
- Stirling numbers are named after James Stirling.There are two kinds of Stirling numbers. Stirling number of the first kind is related to the number of permutations with fixed number of disjoint cycles. And Stirling number of the second kind counts the number of ways of partitioning a set into fixed number of disjoint blocks. Both numbers arise from important combinatorial problems and have various applications in combinatorics and other branches of Mathematics.
Unlike previous identities, it is very difficult to give a determinant for . But we have the following recurrence:
Theorem - .
Proof. To partition into blocks,
- we can partition into blocks and place into one of the blocks, which gives us ways to do so;
- or we can partition into blocks and let be a block by itself, which gives us ways to do so.
The permutation constructed by these two methods are different, since by the first method, is always in a block of cardinality , and by the second method, is always a block. So the cases are disjoint. And any -partition of an -set must be constructible by one of the two methods, thus by the sum rule,
- .
Let , which gives the total number of partitions of an -set. is called the Bell number.
Partitions of a number
For a positive integer , we define a partition of into parts to be a sequence of positive integers such that and .
A partition of into parts corresponds to a way of representing as a sum of positive integers, disregarding the order of summands. (Note the difference from -composition, for which we care about the order of summands.)
Let be the number of partitions of into parts. We will revisit this number in future.
The twelvfold way
We now introduce a general framework for counting problems, called the twelvefold way. This framework is introduced by the great mathematician and also a great teacher, Gian-Carlo Rota.
Let and be finite sets with and . We count the number of functions subject to different restrictions. There are three restrictions regarding the mapping itself:
- is an arbitrary function;
- is an injection (one-to-one);
- is a surjection (onto).
The elements of and can be regarded as distinguishable or indistinguishable. Think of as a set of balls and as a set of bins. A function is an assignment of the balls into bins. The balls are distinguishable if each ball has a distinct label on it, and the balls are indistinguishable if they are identical. The same also applies to the bins.
Three restrictions on the functions, with two restrictions on each of the domain and the range, together give us twelve counting problems, called the Twelvefold Way.
The following table gives the solutions to the counting problems.
Elements of | Elements of | Any | Injective (1-1) | Surjective (on-to) |
---|---|---|---|---|
distinguishable | distinguishable | |||
indistinguishable | distinguishable | |||
distinguishable | indistinguishable | |||
indistinguishable | indistinguishable |
In the fascicle version of Volume 4 of Don Knuth's TAOCP, the twelvefold way is presented as the problems of counting the ways of assigning balls into bins. The domain corresponds to a set of balls, the range corresponds to a set of bins, and each function corresponds to an assignment of balls into bins. Balls (or bins) are distinguishable if they are distinct and are indistinguishable if they are identical. An injective function corresponds to an assignment with at most one ball in each bin, and a surjective function corresponds to an assignment with at least one ball(s) in each bin.
balls per bin | unrestricted | ≤ 1 | ≥ 1 |
---|---|---|---|
distinct balls, distinct bins |
-tuples of things |
-permutations of things |
partition of into ordered parts |
identical balls, distinct bins |
-combinations of with repetitions |
-combinations of without repetitions |
-compositions of |
distinct balls, identical bins |
partitions of into parts |
pigeons into holes |
partitions of into parts |
identical balls, identical bins |
partitions of into parts |
pigeons into holes |
partitions of into parts |
Reference
- Stanley, Enumerative Combinatorics, Volume 1, Chapter 1.