TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Basic enumeration

2010-07-10T07:19:06Z

0:0:0:0:0:0:0:1: /* Subsets */

== Counting Problems ==

== Sets and Multisets ==
=== Subsets ===
We want to count the number of subsets of a set.

Let<math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set, or '''<math>n</math>-set''' for short.
Let <math>2^S=\{T\mid T\subset S\}</math> denote the set of all subset of <math>S</math>. <math>2^S</math> is called the '''power set''' of <math>S</math>.

We give a combinatorial proof that <math>|2^S|=2^n</math>. We observe that every subset <math>T\in 2^S</math> corresponds to a unique bit-vector <math>v\in\{0,1\}^S</math>, such that each bit <math>v_i</math> indicates whether <math>x_i\in S</math>. Formally, define a map <math>\phi:2^S\rightarrow\{0,1\}^n</math> by <math>\phi(T)=(v_1,v_2,\ldots,v_n)</math>, where
:<math>
v_i=\begin{cases}
1 & \mbox{if }x_i\in T\\
0 & \mbox{if }x_i\not\in T.
\end{cases}
</math>
The map <math>\phi</math> is a '''bijection''' (a 1-1 correspondence). The proof that <math>\phi</math> is a bijection is left as an exercise.

Since there is a bijection between <math>2^S</math> and <math>\{0,1\}^n</math>, it holds that <math>|2^S|=|\{0,1\}^n|=2^n\,</math>.

Here we apply ''"the rule of bijection"''.
*'''The rule of bijection''': if there exists a bijection between finite sets <math>P</math> and <math>Q</math>, then <math>|P|=|Q|</math>.

How do we know that <math>|\{0,1\}^n|=2^n\,</math>? We use ''"the rule of product"''.
*'''The rule of product''': for any finite sets <math>P</math> and <math>Q</math>, the cardinality of the Cartesian product <math>|P\times Q|=|P|\cdot|Q|</math>.

To count the size of <math>\{0,1\}^n\,</math>, we write <math>\{0,1\}^n=\{0,1\}\times\{0,1\}^{n-1}</math>, thus <math>|\{0,1\}^n|=2|\{0,1\}^{n-1}|\,</math>. Solving the recursion, we have that <math>|\{0,1\}^n|=2^n\,</math>.

There are two elements of the proof:
* Find a 1-1 correspondence between subsets of an <math>n</math>-set and <math>n</math>-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''' <math>U</math> can be represented by an array of <math>|U|</math> bits.
* The rule of bijection: 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 <math>|2^S|=2^n</math>. The proof needs another basic counting rule: ''"the rule of sum"''.
*'''The rule of sum''': for any '''''disjoint''''' finite sets <math>P</math> and <math>Q</math>, the cardinality of the union <math>|P\cup Q|=|P|+|Q|</math>.

Define the function <math>f(n)=|2^{S_n}|</math>, where <math>S_n=\{x_1,x_2,\ldots,x_n\}</math> is an <math>n</math>-set. Our goal is to compute <math>f(n)</math>. We prove the following recursion for <math>f(n)</math>.

{{Theorem|Lemma|
:<math>f(n)=2f(n-1)\,</math>.
}}
{{Proof|
Fix an element <math>x_n</math>, let <math>U</math> be the set of subsets of <math>S_n</math> that contain <math>x_n</math> and let <math>V</math> be the set of subsets of <math>S_n</math> that do not contain <math>x_n</math>. It is obvious that <math>U</math> and <math>V</math> are disjoint (i.e. <math>U\cap V=\emptyset</math>) and <math>2^{S_n}=U\cup V</math>, because any subset of <math>S_n</math> either contains <math>x_n</math> or does not contain <math>x_n</math> but not both.

Applying the rule of sum,
:<math>f(n)=|U\cup V|=|U|+|V|</math>.

The next observation is that <math>|U|=|V|=f(n-1)</math>, because <math>V</math> is exactly the <math>2^{S_{n-1}}</math>, and <math>U</math> is the set resulting from adding <math>x_n</math> to every member of <math>2^{S_{n-1}}</math>. Therefore,
:<math>f(n)=|U|+|V|=f(n-1)+f(n-1)=2f(n-1)\,</math>.
}}
The elementary case <math>f(0)=1</math>, because <math>\emptyset</math> has only one subset <math>\emptyset</math>. Solving the recursion, we have that <math>|2^S|=f(n)=2^n</math>.

=== Subsets of fixed size ===
We then count the number of subsets of fixed size of a set. Again, let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-set. We define <math>{S\choose k}</math> to be the set of all <math>k</math>-elements subsets (or '''<math>k</math>-subsets''') of <math>S</math>. Formally, <math>{S\choose k}=\{T\subseteq S\mid |T|=k\}</math>. The set <math>{S\choose k}</math> is sometimes called the '''<math>k</math>-uniform''' of <math>S</math>.

We denote that <math>{n\choose k}=\left|{S\choose k}\right|</math>. The notation <math>{n\choose k}</math> is read "<math>n</math> choose <math>k</math>".

{{Theorem|Theorem|
:<math>{n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}</math>.
}}
{{Proof|
The number of '''ordered''' <math>k</math>-subsets of an <math>n</math>-set is <math>n(n-1)\cdots(n-k+1)</math>. Every <math>k</math>-subset has <math>k!=k(k-1)\cdots1</math> ways to order it.
}}

;Some notations
* <math>n!</math>, read "<math>n</math> factorial", is defined as that <math>n!=n(n-1)(n-2)\cdots 1</math>, with the convention that <math>0!=1</math>.
* <math>n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}</math> is usually denoted as <math>(n)_k\,</math>, read "<math>n</math> lower factorial <math>k</math>".

The quantity <math>{n\choose k}</math> is called a '''binomial coefficient'''.

{{Theorem|Proposition|
# <math>{n\choose k}={n\choose n-k}</math>;
# <math>\sum_{k=0}^n {n\choose k}=2^n</math>.
}}
{{Proof|
1. We give two proofs for the first equation:
:(1) (numerical proof)
::<math>{n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k}</math>.
:(2) (combinatorial proof)
::Choosing <math>k</math> elements from an <math>n</math>-set is equivalent to choosing the <math>n-k</math> elements to leave out. Formally, every <math>k</math>-subset <math>T\in{S\choose k}</math> is uniquely specified by its complement <math>S\setminus T\in {S\choose n-k}</math>, and the same holds for <math>(n-k)</math>-subsets, thus we have a bijection between <math>{S\choose k}</math> and <math>{S\choose n-k}</math>.
2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. For an <math>n</math>-element set <math>S</math>, it is obvious that we can enumerate all subsets of <math>S</math> by enumerating <math>k</math>-subsets for every possible size <math>k</math>, i.e. it holds that
:<math>
2^S=\bigcup_{k=0}^n{S\choose k}.
</math>
For different <math>k</math>, <math>{S\choose k}</math> are obviously disjoint. By the rule of sum,
:<math>2^n=|2^S|=\left|\bigcup_{k=0}^n{S\choose k}\right|=\sum_{k=0}^n\left|{S\choose k}\right|=\sum_{k=0}^n {n\choose k}</math>.
}}

<math>{n\choose k}</math> 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|Theorem (Binomial theorem)|
:<math>(1+x)^n=\sum_{k=0}^n{n\choose k}x^k</math>.
}}
{{Proof|
Write <math>(1+x)^n</math> as the product of <math>n</math> factors
:<math>(1+x)(1+x)\cdots (1+x)</math>.
The term <math>x^k</math> is obtained by choosing <math>x</math> from <math>k</math> factors and 1 from the rest <math>(n-k)</math> factors. There are <math>{n\choose k}</math> ways of choosing these <math>k</math> factors, so the coefficient of <math>x^k</math> is <math>{n\choose k}</math>.
}}

The following proposition has an easy proof due to the binomial theorem.
{{Theorem| Proposition|
:For <math>n>0</math>, the numbers of subsets of an <math>n</math>-set of even and of odd cardinality are equal.
}}
{{Proof|
Set <math>x=-1</math> in the binomial theorem.
:<math>
0=(1-1)^n=\sum_{k=0}^n{n\choose k}(-1)^k=\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}-\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k},
</math>
therefore
:<math>\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}=\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}.</math>
}}

For counting problems, what we care about are ''numbers''. In the binomial theorem, a formal ''variable'' <math>x</math> 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 <math>n</math> is an expression of <math>n</math> as an ''ordered'' sum of ''positive'' integers. A '''<math>k</math>-composition''' of <math>n</math> is a composition of <math>n</math> with exactly <math>k</math> positive summands.

Formally, a <math>k</math>-composition of <math>n</math> is a <math>k</math>-tuple <math>(a_1,a_2,\ldots,a_k)\in\{1,2,\ldots,n\}^k</math> such that <math>a_1+a_2+\cdots+a_k=n</math>.

Suppose we have <math>n</math> identical balls in a line. A <math>k</math>-composition partitions these <math>n</math> balls into <math>k</math> ''nonempty'' sets, illustrated as follows.
:<math>
\begin{array}{c|cc|c|c|ccc|cc}
\bigcirc \,&\, \bigcirc \,& \bigcirc \,&\, \bigcirc \,&\, \bigcirc \,&\, \bigcirc &\, \bigcirc &\, \bigcirc \,&\, \bigcirc \,& \bigcirc
\end{array}
</math>
So the number of <math>k</math>-compositions of <math>n</math> equals the number of ways we put <math>k-1</math> bars "<math>|</math>" into <math>n-1</math> slots "<math>\sqcup</math>", where each slot has at most one bar (because all the summands <math>a_i>0</math>):
:<math>
\bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc
</math>
which is equal to the number of ways of choosing <math>k-1</math> slots out of <math>n-1</math> slots, which is <math>{n-1\choose k-1}</math>.

This graphic argument can be expressed as a formal proof. We construct a bijection between the set of <math>k</math>-compositions of <math>n</math> and <math>{\{1,2,\ldots,n-1\}\choose k-1}</math> as follows.

Let <math>\phi</math> be a mapping that given a <math>k</math>-composition <math>(a_1,a_2,\ldots,a_k)</math> of <math>n</math>,
:<math>
\begin{align}
\phi((a_1,a_2,\ldots,a_k))
&=\{a_1,\,\,a_1+a_2,\,\,a_1+a_2+a_3,\,\,\ldots,\,\,a_1+a_2+\cdots+a_{k-1}\}\\
&=\left\{\sum_{i=1}^ja_i\,\,\bigg|\,\, 1\le j<k\right\}.
\end{align}
</math>
<math>\phi</math> maps every <math>k</math>-composition to a <math>(k-1)</math>-subset of <math>\{1,2,\ldots,n-1\}</math>. It is easy to verify that <math>\phi</math> is a bijection, thus the number of <math>k</math>-compositions of <math>n</math> is <math>{n-1\choose k-1}</math>.
----
The number of <math>k</math>-compositions of <math>n</math> is equal to the number of ''positive'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. This suggests us to relax the constraint and count the number of ''nonnegative'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. We call such a solution a '''weak <math>k</math>-composition''' of <math>n</math>.

Formally, a weak <math>k</math>-composition of <math>n</math> is a tuple <math>(x_1,x_2,\ldots,x_k)\in[n+1]^k</math> such that <math>x_1+x_2+\cdots+x_k=n</math>.

Given a weak <math>k</math>-composition <math>(x_1,x_2,\ldots,x_k)</math> of <math>n</math>, if we set <math>y_i=x_i+1</math> for every <math>1\le i\le k</math>, then <math>y_i>0</math> and
:<math>
\begin{align}
y_1+y_2+\cdots +y_k
&=(x_1+1)+(x_2+1)+\cdots+(x_k+1)&=n+k,
\end{align}
</math>
i.e., <math>(y_1,y_2,\ldots,y_k)</math> is a <math>k</math>-composition of <math>n+k</math>. It is easy to see that it defines a bijection between weak <math>k</math>-compositions of <math>n</math> and <math>k</math>-compositions of <math>n+k</math>. Therefore, the number of weak <math>k</math>-compositions of <math>n</math> is <math>{n+k-1\choose k-1}</math>.
----
We now count the number of nonnegative integer solutions to <math>x_1+x_2+\cdots+x_k\le n</math>.

Let <math>x_{k+1}=n-(x_1+x_2+\cdots+x_k)</math>. Then <math>x_{k+1}\ge 0</math> and <math>x_1+x_2+\ldots+x_k+x_{k+1}=n</math>.
The problem is transformed to that counting the number of nonnegative integer solutions to the above equation. The answer is <math>{n+k\choose k}</math>.

=== Multisets ===
A <math>k</math>-subset of an <math>n</math>-set <math>S</math> is sometimes called a '''<math>k</math>-combination of <math>S</math> without repetitions'''. This suggests the problem of counting the number of <math>k</math>-combinations of <math>S</math> '''''with repetitions'''''; that is, we choose <math>k</math> elements of <math>S</math>, disregarding order and allowing repeated elements.

;Example
:<math>S=\{1,2,3,4\}</math>. All <math>3</math>-combination without repetitions are
::<math>\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\,</math>.
:Allowing repetitions, we also include the following 3-combinations:
::<math>
\begin{align}
&\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\\
&\{2,2,2\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\\
&\{3,3,3\},\{3,3,4\},\{3,4,4\}\\
&\{4,4,4\}
\end{align}
</math>

Combinations with repetitions can be formally defined as '''multisets'''. A multiset is a set with repeated elements. Formally, a multiset <math>M</math> on a set <math>S</math> is a function <math>m:S\rightarrow \mathbb{N}</math>. For any element <math>x\in S</math>, the integer <math>m(x)\ge 0</math> is the number of repetitions of <math>x</math> in <math>M</math>, called the '''multiplicity''' of <math>x</math>. The sum of multiplicities <math>\sum_{x\in S}m(x)</math> is called the '''cardinality''' of <math>M</math> and is denoted as <math>|M|</math>.

A <math>k</math>-multiset on a set <math>S</math> is a multiset <math>M</math> on <math>S</math> with <math>|M|=k</math>. It is obvious that a <math>k</math>-combination of <math>S</math> with repetition is simply a <math>k</math>-multiset on <math>S</math>.

The set of all <math>k</math>-multisets on <math>S</math> is denoted <math>\left({S\choose k}\right)</math>. Assuming that <math>n=|S|</math>, denote <math>\left({n\choose k}\right)=\left|\left({S\choose k}\right)\right|</math>, which is the number of <math>k</math>-combinations of an <math>n</math>-set with repetitions.

Believe it or not: we have already evaluated the number <math>\left({n\choose k}\right)</math>. If <math>S=\{x_1,x_2,\ldots,x_n\}</math>, let <math>z_i=m(x_i)</math>, then <math>\left({n\choose k}\right)</math> is the number of nonnegative integer solutions to <math>z_1+z_2+\cdots+z_n=k</math>, which is the number of weak <math>n</math>-compositions of <math>k</math>, which we have seen is <math>{n+k-1\choose n-1}={n+k-1\choose k}</math>.

----

There is a direct combinatorial proof that <math>\left({n\choose k}\right)={n+k-1\choose k}</math>.

Given a <math>k</math>-multiset <math>0\le a_0\le a_1\le\cdots\le a_{k-1}\le n-1</math> on <math>[n]</math>, then defining <math>b_i=a_i+i</math>, we see that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-subset of <math>[n+k-1]</math>. Conversely, given a <math>k</math>-subset <math>0\le b_0\le b_1\le\cdots\le b_{k-1}\le n+k-2</math> of <math>[n+k-1]</math>, then defining <math>a_i=b_i-i</math>, we have that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-multiset on <math>[n]</math>. Therefore, we have a bijection between <math>\left({[n]\choose k}\right)</math> and <math>{[n+k-1]\choose k}</math>.

=== Multinomial coefficients ===

== Permutations and Partitions ==

== The twelvfold way ==
We consider a very fundamental counting framework: counting functions <math>f:N\rightarrow M</math>. We can define different counting problems according to the types of mapping (1-1, on-to, arbitrary), and the types of the domain and the range (distinguishable, indistinguishable).
* Distinguishability of set:
* Types of mapping:

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!bgcolor="#A7C1F2" | Elements of <math>N</math>
!bgcolor="#A7C1F2" | Elements of <math>M</math>
!bgcolor="#A7C1F2" | Any <math>f</math>
!bgcolor="#A7C1F2" | Injective (1-1) <math>f</math>
!bgcolor="#A7C1F2" | Surjective (on-to) <math>f</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>m^n\,</math>
|align="center"| <math>\left(m\right)_n</math>
|align="center"| <math>m!S(n, m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>\left({m\choose n}\right)</math>
|align="center"|<math>{m\choose n}</math>
|align="center"|<math>\left({m\choose n-m}\right)</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m S(n,k)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>S(n,m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m p_k(n)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>p_m(n)\,</math>
|}

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!align="center" bgcolor="#A7C1F2" | balls per bin
!align="center" bgcolor="#A7C1F2" | unrestricted
!align="center" bgcolor="#A7C1F2" | ≤ 1
!align="center" bgcolor="#A7C1F2" | ≥ 1
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-tuples of <math>m</math> things
|align="center"| <math>n</math>-permutations of <math>m</math> things
|align="center"| partition of <math>[n]</math> into <math>m</math> ordered parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-combinations of <math>[m]</math> with repetitions
|align="center"| <math>n</math>-combinations of <math>[m]</math> without repetitions
|align="center"| <math>m</math>-compositions of <math>n</math>
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>n</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>n</math> into <math>m</math> parts
|}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 1.

Combinatorics (Fall 2010)/Basic enumeration

2010-07-10T07:18:50Z

0:0:0:0:0:0:0:1: /* Subsets */

== Counting Problems ==

== Sets and Multisets ==
=== Subsets ===
We want to count the number of subsets of a set.

Let<math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set, or '''<math>n</math>-set''' for short.
Let <math>2^S=\{T\mid T\subset S\}</math> denote the set of all subset of <math>S</math>. <math>2^S</math> is called the '''power set''' of <math>S</math>.

We give a combinatorial proof that <math>|2^S|=2^n</math>. We observe that every subset <math>T\in 2^S</math> corresponds to a unique bit-vector <math>v\in\{0,1\}^S</math>, such that each bit <math>v_i</math> indicates whether <math>x_i\in S</math>. Formally, define a map <math>\phi:2^S\rightarrow\{0,1\}^n</math> by <math>\phi(T)=(v_1,v_2,\ldots,v_n)</math>, where
:<math>
v_i=\begin{cases}
1 & \mbox{if }x_i\in T\\
0 & \mbox{if }x_i\not\in T.
\end{cases}
</math>
The map <math>\phi</math> is a '''bijection''' (a 1-1 correspondence). The proof that <math>\phi</math> is a bijection is left as an exercise.

Since there is a bijection between <math>2^S</math> and <math>\{0,1\}^n</math>, it holds that <math>|2^S|=|\{0,1\}^n|=2^n\,</math>.

Here we apply ''"the rule of bijection"''.
*'''The rule of bijection''': if there exists a bijection between finite sets <math>P</math> and <math>Q</math>, then <math>|P|=|Q|</math>.

How do we know that <math>|\{0,1\}^n|=2^n\,</math>? We use ''"the rule of product"''.
*'''The rule of product''': for any finite sets <math>P</math> and <math>Q</math>, the cardinality of the Cartesian product <math>|P\times Q|=|P|\cdot|Q|</math>.

To count the size of <math>\{0,1\}^n\,</math>, we write <math>\{0,1\}^n=\{0,1\}\times\{0,1\}^{n-1}</math>, thus <math>|\{0,1\}^n|=2|\{0,1\}^{n-1}|\,</math>. Solving the recursion, we have that <math>|\{0,1\}^n|=2^n\,</math>.

There are two elements of the proof:
* Find a 1-1 correspondence between subsets of an <math>n</math>-set and <math>n</math>-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''' <math>U</math> can be represented by an array of <math>|U|</math> bits.
* The rule of bijection: 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 <math>|2^S|=2^n</math>. The proof needs another basic counting rule: '''"the rule of sum"'''.
*'''The rule of sum''': for any '''''disjoint''''' finite sets <math>P</math> and <math>Q</math>, the cardinality of the union <math>|P\cup Q|=|P|+|Q|</math>.

Define the function <math>f(n)=|2^{S_n}|</math>, where <math>S_n=\{x_1,x_2,\ldots,x_n\}</math> is an <math>n</math>-set. Our goal is to compute <math>f(n)</math>. We prove the following recursion for <math>f(n)</math>.

{{Theorem|Lemma|
:<math>f(n)=2f(n-1)\,</math>.
}}
{{Proof|
Fix an element <math>x_n</math>, let <math>U</math> be the set of subsets of <math>S_n</math> that contain <math>x_n</math> and let <math>V</math> be the set of subsets of <math>S_n</math> that do not contain <math>x_n</math>. It is obvious that <math>U</math> and <math>V</math> are disjoint (i.e. <math>U\cap V=\emptyset</math>) and <math>2^{S_n}=U\cup V</math>, because any subset of <math>S_n</math> either contains <math>x_n</math> or does not contain <math>x_n</math> but not both.

Applying the rule of sum,
:<math>f(n)=|U\cup V|=|U|+|V|</math>.

The next observation is that <math>|U|=|V|=f(n-1)</math>, because <math>V</math> is exactly the <math>2^{S_{n-1}}</math>, and <math>U</math> is the set resulting from adding <math>x_n</math> to every member of <math>2^{S_{n-1}}</math>. Therefore,
:<math>f(n)=|U|+|V|=f(n-1)+f(n-1)=2f(n-1)\,</math>.
}}
The elementary case <math>f(0)=1</math>, because <math>\emptyset</math> has only one subset <math>\emptyset</math>. Solving the recursion, we have that <math>|2^S|=f(n)=2^n</math>.

=== Subsets of fixed size ===
We then count the number of subsets of fixed size of a set. Again, let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-set. We define <math>{S\choose k}</math> to be the set of all <math>k</math>-elements subsets (or '''<math>k</math>-subsets''') of <math>S</math>. Formally, <math>{S\choose k}=\{T\subseteq S\mid |T|=k\}</math>. The set <math>{S\choose k}</math> is sometimes called the '''<math>k</math>-uniform''' of <math>S</math>.

We denote that <math>{n\choose k}=\left|{S\choose k}\right|</math>. The notation <math>{n\choose k}</math> is read "<math>n</math> choose <math>k</math>".

{{Theorem|Theorem|
:<math>{n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}</math>.
}}
{{Proof|
The number of '''ordered''' <math>k</math>-subsets of an <math>n</math>-set is <math>n(n-1)\cdots(n-k+1)</math>. Every <math>k</math>-subset has <math>k!=k(k-1)\cdots1</math> ways to order it.
}}

;Some notations
* <math>n!</math>, read "<math>n</math> factorial", is defined as that <math>n!=n(n-1)(n-2)\cdots 1</math>, with the convention that <math>0!=1</math>.
* <math>n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}</math> is usually denoted as <math>(n)_k\,</math>, read "<math>n</math> lower factorial <math>k</math>".

The quantity <math>{n\choose k}</math> is called a '''binomial coefficient'''.

{{Theorem|Proposition|
# <math>{n\choose k}={n\choose n-k}</math>;
# <math>\sum_{k=0}^n {n\choose k}=2^n</math>.
}}
{{Proof|
1. We give two proofs for the first equation:
:(1) (numerical proof)
::<math>{n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k}</math>.
:(2) (combinatorial proof)
::Choosing <math>k</math> elements from an <math>n</math>-set is equivalent to choosing the <math>n-k</math> elements to leave out. Formally, every <math>k</math>-subset <math>T\in{S\choose k}</math> is uniquely specified by its complement <math>S\setminus T\in {S\choose n-k}</math>, and the same holds for <math>(n-k)</math>-subsets, thus we have a bijection between <math>{S\choose k}</math> and <math>{S\choose n-k}</math>.
2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. For an <math>n</math>-element set <math>S</math>, it is obvious that we can enumerate all subsets of <math>S</math> by enumerating <math>k</math>-subsets for every possible size <math>k</math>, i.e. it holds that
:<math>
2^S=\bigcup_{k=0}^n{S\choose k}.
</math>
For different <math>k</math>, <math>{S\choose k}</math> are obviously disjoint. By the rule of sum,
:<math>2^n=|2^S|=\left|\bigcup_{k=0}^n{S\choose k}\right|=\sum_{k=0}^n\left|{S\choose k}\right|=\sum_{k=0}^n {n\choose k}</math>.
}}

<math>{n\choose k}</math> 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|Theorem (Binomial theorem)|
:<math>(1+x)^n=\sum_{k=0}^n{n\choose k}x^k</math>.
}}
{{Proof|
Write <math>(1+x)^n</math> as the product of <math>n</math> factors
:<math>(1+x)(1+x)\cdots (1+x)</math>.
The term <math>x^k</math> is obtained by choosing <math>x</math> from <math>k</math> factors and 1 from the rest <math>(n-k)</math> factors. There are <math>{n\choose k}</math> ways of choosing these <math>k</math> factors, so the coefficient of <math>x^k</math> is <math>{n\choose k}</math>.
}}

The following proposition has an easy proof due to the binomial theorem.
{{Theorem| Proposition|
:For <math>n>0</math>, the numbers of subsets of an <math>n</math>-set of even and of odd cardinality are equal.
}}
{{Proof|
Set <math>x=-1</math> in the binomial theorem.
:<math>
0=(1-1)^n=\sum_{k=0}^n{n\choose k}(-1)^k=\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}-\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k},
</math>
therefore
:<math>\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}=\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}.</math>
}}

For counting problems, what we care about are ''numbers''. In the binomial theorem, a formal ''variable'' <math>x</math> 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 <math>n</math> is an expression of <math>n</math> as an ''ordered'' sum of ''positive'' integers. A '''<math>k</math>-composition''' of <math>n</math> is a composition of <math>n</math> with exactly <math>k</math> positive summands.

Formally, a <math>k</math>-composition of <math>n</math> is a <math>k</math>-tuple <math>(a_1,a_2,\ldots,a_k)\in\{1,2,\ldots,n\}^k</math> such that <math>a_1+a_2+\cdots+a_k=n</math>.

Suppose we have <math>n</math> identical balls in a line. A <math>k</math>-composition partitions these <math>n</math> balls into <math>k</math> ''nonempty'' sets, illustrated as follows.
:<math>
\begin{array}{c|cc|c|c|ccc|cc}
\bigcirc \,&\, \bigcirc \,& \bigcirc \,&\, \bigcirc \,&\, \bigcirc \,&\, \bigcirc &\, \bigcirc &\, \bigcirc \,&\, \bigcirc \,& \bigcirc
\end{array}
</math>
So the number of <math>k</math>-compositions of <math>n</math> equals the number of ways we put <math>k-1</math> bars "<math>|</math>" into <math>n-1</math> slots "<math>\sqcup</math>", where each slot has at most one bar (because all the summands <math>a_i>0</math>):
:<math>
\bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc
</math>
which is equal to the number of ways of choosing <math>k-1</math> slots out of <math>n-1</math> slots, which is <math>{n-1\choose k-1}</math>.

This graphic argument can be expressed as a formal proof. We construct a bijection between the set of <math>k</math>-compositions of <math>n</math> and <math>{\{1,2,\ldots,n-1\}\choose k-1}</math> as follows.

Let <math>\phi</math> be a mapping that given a <math>k</math>-composition <math>(a_1,a_2,\ldots,a_k)</math> of <math>n</math>,
:<math>
\begin{align}
\phi((a_1,a_2,\ldots,a_k))
&=\{a_1,\,\,a_1+a_2,\,\,a_1+a_2+a_3,\,\,\ldots,\,\,a_1+a_2+\cdots+a_{k-1}\}\\
&=\left\{\sum_{i=1}^ja_i\,\,\bigg|\,\, 1\le j<k\right\}.
\end{align}
</math>
<math>\phi</math> maps every <math>k</math>-composition to a <math>(k-1)</math>-subset of <math>\{1,2,\ldots,n-1\}</math>. It is easy to verify that <math>\phi</math> is a bijection, thus the number of <math>k</math>-compositions of <math>n</math> is <math>{n-1\choose k-1}</math>.
----
The number of <math>k</math>-compositions of <math>n</math> is equal to the number of ''positive'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. This suggests us to relax the constraint and count the number of ''nonnegative'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. We call such a solution a '''weak <math>k</math>-composition''' of <math>n</math>.

Formally, a weak <math>k</math>-composition of <math>n</math> is a tuple <math>(x_1,x_2,\ldots,x_k)\in[n+1]^k</math> such that <math>x_1+x_2+\cdots+x_k=n</math>.

Given a weak <math>k</math>-composition <math>(x_1,x_2,\ldots,x_k)</math> of <math>n</math>, if we set <math>y_i=x_i+1</math> for every <math>1\le i\le k</math>, then <math>y_i>0</math> and
:<math>
\begin{align}
y_1+y_2+\cdots +y_k
&=(x_1+1)+(x_2+1)+\cdots+(x_k+1)&=n+k,
\end{align}
</math>
i.e., <math>(y_1,y_2,\ldots,y_k)</math> is a <math>k</math>-composition of <math>n+k</math>. It is easy to see that it defines a bijection between weak <math>k</math>-compositions of <math>n</math> and <math>k</math>-compositions of <math>n+k</math>. Therefore, the number of weak <math>k</math>-compositions of <math>n</math> is <math>{n+k-1\choose k-1}</math>.
----
We now count the number of nonnegative integer solutions to <math>x_1+x_2+\cdots+x_k\le n</math>.

Let <math>x_{k+1}=n-(x_1+x_2+\cdots+x_k)</math>. Then <math>x_{k+1}\ge 0</math> and <math>x_1+x_2+\ldots+x_k+x_{k+1}=n</math>.
The problem is transformed to that counting the number of nonnegative integer solutions to the above equation. The answer is <math>{n+k\choose k}</math>.

=== Multisets ===
A <math>k</math>-subset of an <math>n</math>-set <math>S</math> is sometimes called a '''<math>k</math>-combination of <math>S</math> without repetitions'''. This suggests the problem of counting the number of <math>k</math>-combinations of <math>S</math> '''''with repetitions'''''; that is, we choose <math>k</math> elements of <math>S</math>, disregarding order and allowing repeated elements.

;Example
:<math>S=\{1,2,3,4\}</math>. All <math>3</math>-combination without repetitions are
::<math>\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\,</math>.
:Allowing repetitions, we also include the following 3-combinations:
::<math>
\begin{align}
&\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\\
&\{2,2,2\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\\
&\{3,3,3\},\{3,3,4\},\{3,4,4\}\\
&\{4,4,4\}
\end{align}
</math>

Combinations with repetitions can be formally defined as '''multisets'''. A multiset is a set with repeated elements. Formally, a multiset <math>M</math> on a set <math>S</math> is a function <math>m:S\rightarrow \mathbb{N}</math>. For any element <math>x\in S</math>, the integer <math>m(x)\ge 0</math> is the number of repetitions of <math>x</math> in <math>M</math>, called the '''multiplicity''' of <math>x</math>. The sum of multiplicities <math>\sum_{x\in S}m(x)</math> is called the '''cardinality''' of <math>M</math> and is denoted as <math>|M|</math>.

A <math>k</math>-multiset on a set <math>S</math> is a multiset <math>M</math> on <math>S</math> with <math>|M|=k</math>. It is obvious that a <math>k</math>-combination of <math>S</math> with repetition is simply a <math>k</math>-multiset on <math>S</math>.

The set of all <math>k</math>-multisets on <math>S</math> is denoted <math>\left({S\choose k}\right)</math>. Assuming that <math>n=|S|</math>, denote <math>\left({n\choose k}\right)=\left|\left({S\choose k}\right)\right|</math>, which is the number of <math>k</math>-combinations of an <math>n</math>-set with repetitions.

Believe it or not: we have already evaluated the number <math>\left({n\choose k}\right)</math>. If <math>S=\{x_1,x_2,\ldots,x_n\}</math>, let <math>z_i=m(x_i)</math>, then <math>\left({n\choose k}\right)</math> is the number of nonnegative integer solutions to <math>z_1+z_2+\cdots+z_n=k</math>, which is the number of weak <math>n</math>-compositions of <math>k</math>, which we have seen is <math>{n+k-1\choose n-1}={n+k-1\choose k}</math>.

----

There is a direct combinatorial proof that <math>\left({n\choose k}\right)={n+k-1\choose k}</math>.

Given a <math>k</math>-multiset <math>0\le a_0\le a_1\le\cdots\le a_{k-1}\le n-1</math> on <math>[n]</math>, then defining <math>b_i=a_i+i</math>, we see that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-subset of <math>[n+k-1]</math>. Conversely, given a <math>k</math>-subset <math>0\le b_0\le b_1\le\cdots\le b_{k-1}\le n+k-2</math> of <math>[n+k-1]</math>, then defining <math>a_i=b_i-i</math>, we have that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-multiset on <math>[n]</math>. Therefore, we have a bijection between <math>\left({[n]\choose k}\right)</math> and <math>{[n+k-1]\choose k}</math>.

=== Multinomial coefficients ===

== Permutations and Partitions ==

== The twelvfold way ==
We consider a very fundamental counting framework: counting functions <math>f:N\rightarrow M</math>. We can define different counting problems according to the types of mapping (1-1, on-to, arbitrary), and the types of the domain and the range (distinguishable, indistinguishable).
* Distinguishability of set:
* Types of mapping:

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!bgcolor="#A7C1F2" | Elements of <math>N</math>
!bgcolor="#A7C1F2" | Elements of <math>M</math>
!bgcolor="#A7C1F2" | Any <math>f</math>
!bgcolor="#A7C1F2" | Injective (1-1) <math>f</math>
!bgcolor="#A7C1F2" | Surjective (on-to) <math>f</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>m^n\,</math>
|align="center"| <math>\left(m\right)_n</math>
|align="center"| <math>m!S(n, m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>\left({m\choose n}\right)</math>
|align="center"|<math>{m\choose n}</math>
|align="center"|<math>\left({m\choose n-m}\right)</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m S(n,k)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>S(n,m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m p_k(n)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>p_m(n)\,</math>
|}

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!align="center" bgcolor="#A7C1F2" | balls per bin
!align="center" bgcolor="#A7C1F2" | unrestricted
!align="center" bgcolor="#A7C1F2" | ≤ 1
!align="center" bgcolor="#A7C1F2" | ≥ 1
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-tuples of <math>m</math> things
|align="center"| <math>n</math>-permutations of <math>m</math> things
|align="center"| partition of <math>[n]</math> into <math>m</math> ordered parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-combinations of <math>[m]</math> with repetitions
|align="center"| <math>n</math>-combinations of <math>[m]</math> without repetitions
|align="center"| <math>m</math>-compositions of <math>n</math>
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>n</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>n</math> into <math>m</math> parts
|}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 1.

Combinatorics (Fall 2010)/Basic enumeration

2010-07-10T07:18:17Z

0:0:0:0:0:0:0:1: /* Subsets */

== Counting Problems ==

== Sets and Multisets ==
=== Subsets ===
We want to count the number of subsets of a set.

Let<math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set, or '''<math>n</math>-set''' for short.
Let <math>2^S=\{T\mid T\subset S\}</math> denote the set of all subset of <math>S</math>. <math>2^S</math> is called the '''power set''' of <math>S</math>.

We give a combinatorial proof that <math>|2^S|=2^n</math>. We observe that every subset <math>T\in 2^S</math> corresponds to a unique bit-vector <math>v\in\{0,1\}^S</math>, such that each bit <math>v_i</math> indicates whether <math>x_i\in S</math>. Formally, define a map <math>\phi:2^S\rightarrow\{0,1\}^n</math> by <math>\phi(T)=(v_1,v_2,\ldots,v_n)</math>, where
:<math>
v_i=\begin{cases}
1 & \mbox{if }x_i\in T\\
0 & \mbox{if }x_i\not\in T.
\end{cases}
</math>
The map <math>\phi</math> is a '''bijection''' (a 1-1 correspondence). The proof that <math>\phi</math> is a bijection is left as an exercise.

Since there is a bijection between <math>2^S</math> and <math>\{0,1\}^n</math>, it holds that <math>|2^S|=|\{0,1\}^n|=2^n\,</math>.

Here we apply ''"the rule of bijection"''.
*'''The rule of bijection''': if there exists a bijection between finite sets <math>P</math> and <math>Q</math>, then <math>|P|=|Q|</math>.

How do we know that <math>|\{0,1\}^n|=2^n\,</math>? We use ''"the rule of product"''.
*'''The rule of product''': for any finite sets <math>P</math> and <math>Q</math>, the cardinality of the Cartesian product <math>|P\times Q|=|P|\cdot|Q|</math>.

To count the size of <math>\{0,1\}^n\,</math>, we write <math>\{0,1\}^n=\{0,1\}\times\{0,1\}^{n-1}</math>, thus <math>|\{0,1\}^n|=2|\{0,1\}^{n-1}|\,</math>. Solving the recursion, we have that <math>|\{0,1\}^n|=2^n\,</math>.

There are two elements of the proof:
* Find a 1-1 correspondence between subsets of an <math>n</math>-set and <math>n</math>-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''' <math>U</math> can be represented by an array of <math>|U|</math> bits.
* The rule of bijection: 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 <math>|2^S|=2^n</math>. The proof needs another basic counting rule: '''"the rule of sum"'''.
*'''The rule of sum''': for any '''''disjoint''''' finite sets <math>P</math> and <math>Q</math>, the cardinality of the union <math>|P\cup Q|=|P|+|Q|</math>.

Define the function <math>f(n)=|2^{S_n}|</math>, where <math>S_n=\{x_1,x_2,\ldots,x_n\}</math> is an <math>n</math>-set. Our goal is to compute <math>f(n)</math>. We prove the following recursion for <math>f(n)</math>.

{{Theorem|Lemma|
:<math>f(n)=2f(n-1)\,</math>.
}}
{{Proof|
Fix an element <math>x_n</math>, let <math>U</math> be the set of subsets of <math>S_n</math> that contain <math>x_n</math> and let <math>V</math> be the set of subsets of <math>S_n</math> that do not contain <math>x_n</math>. It is obvious that <math>U</math> and <math>V</math> are disjoint (i.e. <math>U\cap V=\emptyset</math>) and <math>2^{S_n}=U\cup V</math>, because any subset of <math>S_n</math> either contains <math>x_n</math> or does not contain <math>x_n</math> but not both.

Applying the rule of sum,
:<math>f(n)=|U\cup V|=|U|+|V|</math>.

The next observation is that <math>|U|=|V|=f(n-1)</math>, because <math>V</math> is exactly the <math>2^{S_{n-1}}</math>, and <math>U</math> is the set resulting from add <math>x_n</math> to every member of <math>2^{S_{n-1}}</math>. Therefore,
:<math>f(n)=|U|+|V|=f(n-1)+f(n-1)=2f(n-1)\,</math>.
}}
The elementary case <math>f(0)=1</math>, because <math>\emptyset</math> has only one subset <math>\emptyset</math>. Solving the recursion, we have that <math>|2^S|=f(n)=2^n</math>.

=== Subsets of fixed size ===
We then count the number of subsets of fixed size of a set. Again, let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-set. We define <math>{S\choose k}</math> to be the set of all <math>k</math>-elements subsets (or '''<math>k</math>-subsets''') of <math>S</math>. Formally, <math>{S\choose k}=\{T\subseteq S\mid |T|=k\}</math>. The set <math>{S\choose k}</math> is sometimes called the '''<math>k</math>-uniform''' of <math>S</math>.

We denote that <math>{n\choose k}=\left|{S\choose k}\right|</math>. The notation <math>{n\choose k}</math> is read "<math>n</math> choose <math>k</math>".

{{Theorem|Theorem|
:<math>{n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}</math>.
}}
{{Proof|
The number of '''ordered''' <math>k</math>-subsets of an <math>n</math>-set is <math>n(n-1)\cdots(n-k+1)</math>. Every <math>k</math>-subset has <math>k!=k(k-1)\cdots1</math> ways to order it.
}}

;Some notations
* <math>n!</math>, read "<math>n</math> factorial", is defined as that <math>n!=n(n-1)(n-2)\cdots 1</math>, with the convention that <math>0!=1</math>.
* <math>n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}</math> is usually denoted as <math>(n)_k\,</math>, read "<math>n</math> lower factorial <math>k</math>".

The quantity <math>{n\choose k}</math> is called a '''binomial coefficient'''.

{{Theorem|Proposition|
# <math>{n\choose k}={n\choose n-k}</math>;
# <math>\sum_{k=0}^n {n\choose k}=2^n</math>.
}}
{{Proof|
1. We give two proofs for the first equation:
:(1) (numerical proof)
::<math>{n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k}</math>.
:(2) (combinatorial proof)
::Choosing <math>k</math> elements from an <math>n</math>-set is equivalent to choosing the <math>n-k</math> elements to leave out. Formally, every <math>k</math>-subset <math>T\in{S\choose k}</math> is uniquely specified by its complement <math>S\setminus T\in {S\choose n-k}</math>, and the same holds for <math>(n-k)</math>-subsets, thus we have a bijection between <math>{S\choose k}</math> and <math>{S\choose n-k}</math>.
2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. For an <math>n</math>-element set <math>S</math>, it is obvious that we can enumerate all subsets of <math>S</math> by enumerating <math>k</math>-subsets for every possible size <math>k</math>, i.e. it holds that
:<math>
2^S=\bigcup_{k=0}^n{S\choose k}.
</math>
For different <math>k</math>, <math>{S\choose k}</math> are obviously disjoint. By the rule of sum,
:<math>2^n=|2^S|=\left|\bigcup_{k=0}^n{S\choose k}\right|=\sum_{k=0}^n\left|{S\choose k}\right|=\sum_{k=0}^n {n\choose k}</math>.
}}

<math>{n\choose k}</math> 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|Theorem (Binomial theorem)|
:<math>(1+x)^n=\sum_{k=0}^n{n\choose k}x^k</math>.
}}
{{Proof|
Write <math>(1+x)^n</math> as the product of <math>n</math> factors
:<math>(1+x)(1+x)\cdots (1+x)</math>.
The term <math>x^k</math> is obtained by choosing <math>x</math> from <math>k</math> factors and 1 from the rest <math>(n-k)</math> factors. There are <math>{n\choose k}</math> ways of choosing these <math>k</math> factors, so the coefficient of <math>x^k</math> is <math>{n\choose k}</math>.
}}

The following proposition has an easy proof due to the binomial theorem.
{{Theorem| Proposition|
:For <math>n>0</math>, the numbers of subsets of an <math>n</math>-set of even and of odd cardinality are equal.
}}
{{Proof|
Set <math>x=-1</math> in the binomial theorem.
:<math>
0=(1-1)^n=\sum_{k=0}^n{n\choose k}(-1)^k=\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}-\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k},
</math>
therefore
:<math>\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}=\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}.</math>
}}

For counting problems, what we care about are ''numbers''. In the binomial theorem, a formal ''variable'' <math>x</math> 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 <math>n</math> is an expression of <math>n</math> as an ''ordered'' sum of ''positive'' integers. A '''<math>k</math>-composition''' of <math>n</math> is a composition of <math>n</math> with exactly <math>k</math> positive summands.

Formally, a <math>k</math>-composition of <math>n</math> is a <math>k</math>-tuple <math>(a_1,a_2,\ldots,a_k)\in\{1,2,\ldots,n\}^k</math> such that <math>a_1+a_2+\cdots+a_k=n</math>.

Suppose we have <math>n</math> identical balls in a line. A <math>k</math>-composition partitions these <math>n</math> balls into <math>k</math> ''nonempty'' sets, illustrated as follows.
:<math>
\begin{array}{c|cc|c|c|ccc|cc}
\bigcirc \,&\, \bigcirc \,& \bigcirc \,&\, \bigcirc \,&\, \bigcirc \,&\, \bigcirc &\, \bigcirc &\, \bigcirc \,&\, \bigcirc \,& \bigcirc
\end{array}
</math>
So the number of <math>k</math>-compositions of <math>n</math> equals the number of ways we put <math>k-1</math> bars "<math>|</math>" into <math>n-1</math> slots "<math>\sqcup</math>", where each slot has at most one bar (because all the summands <math>a_i>0</math>):
:<math>
\bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc
</math>
which is equal to the number of ways of choosing <math>k-1</math> slots out of <math>n-1</math> slots, which is <math>{n-1\choose k-1}</math>.

This graphic argument can be expressed as a formal proof. We construct a bijection between the set of <math>k</math>-compositions of <math>n</math> and <math>{\{1,2,\ldots,n-1\}\choose k-1}</math> as follows.

Let <math>\phi</math> be a mapping that given a <math>k</math>-composition <math>(a_1,a_2,\ldots,a_k)</math> of <math>n</math>,
:<math>
\begin{align}
\phi((a_1,a_2,\ldots,a_k))
&=\{a_1,\,\,a_1+a_2,\,\,a_1+a_2+a_3,\,\,\ldots,\,\,a_1+a_2+\cdots+a_{k-1}\}\\
&=\left\{\sum_{i=1}^ja_i\,\,\bigg|\,\, 1\le j<k\right\}.
\end{align}
</math>
<math>\phi</math> maps every <math>k</math>-composition to a <math>(k-1)</math>-subset of <math>\{1,2,\ldots,n-1\}</math>. It is easy to verify that <math>\phi</math> is a bijection, thus the number of <math>k</math>-compositions of <math>n</math> is <math>{n-1\choose k-1}</math>.
----
The number of <math>k</math>-compositions of <math>n</math> is equal to the number of ''positive'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. This suggests us to relax the constraint and count the number of ''nonnegative'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. We call such a solution a '''weak <math>k</math>-composition''' of <math>n</math>.

Formally, a weak <math>k</math>-composition of <math>n</math> is a tuple <math>(x_1,x_2,\ldots,x_k)\in[n+1]^k</math> such that <math>x_1+x_2+\cdots+x_k=n</math>.

Given a weak <math>k</math>-composition <math>(x_1,x_2,\ldots,x_k)</math> of <math>n</math>, if we set <math>y_i=x_i+1</math> for every <math>1\le i\le k</math>, then <math>y_i>0</math> and
:<math>
\begin{align}
y_1+y_2+\cdots +y_k
&=(x_1+1)+(x_2+1)+\cdots+(x_k+1)&=n+k,
\end{align}
</math>
i.e., <math>(y_1,y_2,\ldots,y_k)</math> is a <math>k</math>-composition of <math>n+k</math>. It is easy to see that it defines a bijection between weak <math>k</math>-compositions of <math>n</math> and <math>k</math>-compositions of <math>n+k</math>. Therefore, the number of weak <math>k</math>-compositions of <math>n</math> is <math>{n+k-1\choose k-1}</math>.
----
We now count the number of nonnegative integer solutions to <math>x_1+x_2+\cdots+x_k\le n</math>.

Let <math>x_{k+1}=n-(x_1+x_2+\cdots+x_k)</math>. Then <math>x_{k+1}\ge 0</math> and <math>x_1+x_2+\ldots+x_k+x_{k+1}=n</math>.
The problem is transformed to that counting the number of nonnegative integer solutions to the above equation. The answer is <math>{n+k\choose k}</math>.

=== Multisets ===
A <math>k</math>-subset of an <math>n</math>-set <math>S</math> is sometimes called a '''<math>k</math>-combination of <math>S</math> without repetitions'''. This suggests the problem of counting the number of <math>k</math>-combinations of <math>S</math> '''''with repetitions'''''; that is, we choose <math>k</math> elements of <math>S</math>, disregarding order and allowing repeated elements.

;Example
:<math>S=\{1,2,3,4\}</math>. All <math>3</math>-combination without repetitions are
::<math>\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\,</math>.
:Allowing repetitions, we also include the following 3-combinations:
::<math>
\begin{align}
&\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\\
&\{2,2,2\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\\
&\{3,3,3\},\{3,3,4\},\{3,4,4\}\\
&\{4,4,4\}
\end{align}
</math>

Combinations with repetitions can be formally defined as '''multisets'''. A multiset is a set with repeated elements. Formally, a multiset <math>M</math> on a set <math>S</math> is a function <math>m:S\rightarrow \mathbb{N}</math>. For any element <math>x\in S</math>, the integer <math>m(x)\ge 0</math> is the number of repetitions of <math>x</math> in <math>M</math>, called the '''multiplicity''' of <math>x</math>. The sum of multiplicities <math>\sum_{x\in S}m(x)</math> is called the '''cardinality''' of <math>M</math> and is denoted as <math>|M|</math>.

A <math>k</math>-multiset on a set <math>S</math> is a multiset <math>M</math> on <math>S</math> with <math>|M|=k</math>. It is obvious that a <math>k</math>-combination of <math>S</math> with repetition is simply a <math>k</math>-multiset on <math>S</math>.

The set of all <math>k</math>-multisets on <math>S</math> is denoted <math>\left({S\choose k}\right)</math>. Assuming that <math>n=|S|</math>, denote <math>\left({n\choose k}\right)=\left|\left({S\choose k}\right)\right|</math>, which is the number of <math>k</math>-combinations of an <math>n</math>-set with repetitions.

Believe it or not: we have already evaluated the number <math>\left({n\choose k}\right)</math>. If <math>S=\{x_1,x_2,\ldots,x_n\}</math>, let <math>z_i=m(x_i)</math>, then <math>\left({n\choose k}\right)</math> is the number of nonnegative integer solutions to <math>z_1+z_2+\cdots+z_n=k</math>, which is the number of weak <math>n</math>-compositions of <math>k</math>, which we have seen is <math>{n+k-1\choose n-1}={n+k-1\choose k}</math>.

----

There is a direct combinatorial proof that <math>\left({n\choose k}\right)={n+k-1\choose k}</math>.

Given a <math>k</math>-multiset <math>0\le a_0\le a_1\le\cdots\le a_{k-1}\le n-1</math> on <math>[n]</math>, then defining <math>b_i=a_i+i</math>, we see that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-subset of <math>[n+k-1]</math>. Conversely, given a <math>k</math>-subset <math>0\le b_0\le b_1\le\cdots\le b_{k-1}\le n+k-2</math> of <math>[n+k-1]</math>, then defining <math>a_i=b_i-i</math>, we have that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-multiset on <math>[n]</math>. Therefore, we have a bijection between <math>\left({[n]\choose k}\right)</math> and <math>{[n+k-1]\choose k}</math>.

=== Multinomial coefficients ===

== Permutations and Partitions ==

== The twelvfold way ==
We consider a very fundamental counting framework: counting functions <math>f:N\rightarrow M</math>. We can define different counting problems according to the types of mapping (1-1, on-to, arbitrary), and the types of the domain and the range (distinguishable, indistinguishable).
* Distinguishability of set:
* Types of mapping:

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!bgcolor="#A7C1F2" | Elements of <math>N</math>
!bgcolor="#A7C1F2" | Elements of <math>M</math>
!bgcolor="#A7C1F2" | Any <math>f</math>
!bgcolor="#A7C1F2" | Injective (1-1) <math>f</math>
!bgcolor="#A7C1F2" | Surjective (on-to) <math>f</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>m^n\,</math>
|align="center"| <math>\left(m\right)_n</math>
|align="center"| <math>m!S(n, m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>\left({m\choose n}\right)</math>
|align="center"|<math>{m\choose n}</math>
|align="center"|<math>\left({m\choose n-m}\right)</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m S(n,k)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>S(n,m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m p_k(n)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>p_m(n)\,</math>
|}

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!align="center" bgcolor="#A7C1F2" | balls per bin
!align="center" bgcolor="#A7C1F2" | unrestricted
!align="center" bgcolor="#A7C1F2" | ≤ 1
!align="center" bgcolor="#A7C1F2" | ≥ 1
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-tuples of <math>m</math> things
|align="center"| <math>n</math>-permutations of <math>m</math> things
|align="center"| partition of <math>[n]</math> into <math>m</math> ordered parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-combinations of <math>[m]</math> with repetitions
|align="center"| <math>n</math>-combinations of <math>[m]</math> without repetitions
|align="center"| <math>m</math>-compositions of <math>n</math>
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>n</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>n</math> into <math>m</math> parts
|}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 1.

Combinatorics (Fall 2010)/Basic enumeration

2010-07-10T07:15:15Z

0:0:0:0:0:0:0:1: /* Subsets */

== Counting Problems ==

== Sets and Multisets ==
=== Subsets ===
We want to count the number of subsets of a set.

Let<math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set, or '''<math>n</math>-set''' for short.
Let <math>2^S=\{T\mid T\subset S\}</math> denote the set of all subset of <math>S</math>. <math>2^S</math> is called the '''power set''' of <math>S</math>.

We give a combinatorial proof that <math>|2^S|=2^n</math>. We observe that every subset <math>T\in 2^S</math> corresponds to a unique bit-vector <math>v\in\{0,1\}^S</math>, such that each bit <math>v_i</math> indicates whether <math>x_i\in S</math>. Formally, define a map <math>\phi:2^S\rightarrow\{0,1\}^n</math> by <math>\phi(T)=(v_1,v_2,\ldots,v_n)</math>, where
:<math>
v_i=\begin{cases}
1 & \mbox{if }x_i\in T\\
0 & \mbox{if }x_i\not\in T.
\end{cases}
</math>
The map <math>\phi</math> is a '''bijection''' (a 1-1 correspondence). The proof that <math>\phi</math> is a bijection is left as an exercise.

Since there is a bijection between <math>2^S</math> and <math>\{0,1\}^n</math>, it holds that <math>|2^S|=|\{0,1\}^n|=2^n\,</math>.

Here we apply ''"the rule of bijection"''.
*'''The rule of bijection''': if there exists a bijection between finite sets <math>P</math> and <math>Q</math>, then <math>|P|=|Q|</math>.

How do we know that <math>|\{0,1\}^n|=2^n\,</math>? We use ''"the rule of product"''.
*'''The rule of product''': for any finite sets <math>P</math> and <math>Q</math>, the cardinality of the Cartesian product <math>|P\times Q|=|P|\cdot|Q|</math>.

To count the size of <math>\{0,1\}^n\,</math>, we write <math>\{0,1\}^n=\{0,1\}\times\{0,1\}^{n-1}</math>, thus <math>|\{0,1\}^n|=2|\{0,1\}^{n-1}|\,</math>. Solving the recursion, we have that <math>|\{0,1\}^n|=2^n\,</math>.

There are two elements of the proof:
* Find a 1-1 correspondence between subsets of an <math>n</math>-set and <math>n</math>-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''' <math>U</math> can be represented by an array of <math>|U|</math> bits.
* The rule of bijection: 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 <math>|2^S|=2^n</math>. Define the function <math>f(n)=|2^{S_n}|</math>, where <math>S_n=\{x_1,x_2,\ldots,x_n\}</math> is an <math>n</math>-set. Our goal is to compute <math>f(n)</math>. We prove the following recursion for <math>f(n)</math>.

{{Theorem|Lemma|
:<math>f(n)=2f(n-1)\,</math>.
}}
{{Proof|
Fix an element <math>x_n</math>, let <math>U</math> be the set of subsets of <math>S_n</math> that contain <math>x_n</math> and let <math>V</math> be the set of subsets of <math>S_n</math> that do not contain <math>x_n</math>. It is obvious that <math>U</math> and <math>V</math> are disjoint (i.e. <math>U\cap V=\emptyset</math>) and <math>2^{S_n}=U\cup V</math>, because any subset of <math>S_n</math> either contains <math>x_n</math> or does not contain <math>x_n</math> but not both.

We apply '''"the rule of sum"''': for any '''''disjoint''''' finite sets <math>P</math> and <math>Q</math>, the cardinality of the union <math>|P\cup Q|=|P|+|Q|</math>.

Therefore,
:<math>f(n)=|U\cup V|=|U|+|V|</math>.

The next observation is that <math>|U|=|V|=f(n-1)</math>, because <math>V</math> is exactly the <math>2^{S_{n-1}}</math>, and <math>U</math> is the set resulting from add <math>x_n</math> to every member of <math>2^{S_{n-1}}</math>. Therefore,
:<math>f(n)=|U|+|V|=f(n-1)+f(n-1)=2f(n-1)\,</math>.
}}
The elementary case <math>f(0)=1</math>, because <math>\emptyset</math> has only one subset <math>\emptyset</math>. Solving the recursion, we have that <math>|2^S|=f(n)=2^n</math>.

=== Subsets of fixed size ===
We then count the number of subsets of fixed size of a set. Again, let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-set. We define <math>{S\choose k}</math> to be the set of all <math>k</math>-elements subsets (or '''<math>k</math>-subsets''') of <math>S</math>. Formally, <math>{S\choose k}=\{T\subseteq S\mid |T|=k\}</math>. The set <math>{S\choose k}</math> is sometimes called the '''<math>k</math>-uniform''' of <math>S</math>.

We denote that <math>{n\choose k}=\left|{S\choose k}\right|</math>. The notation <math>{n\choose k}</math> is read "<math>n</math> choose <math>k</math>".

{{Theorem|Theorem|
:<math>{n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}</math>.
}}
{{Proof|
The number of '''ordered''' <math>k</math>-subsets of an <math>n</math>-set is <math>n(n-1)\cdots(n-k+1)</math>. Every <math>k</math>-subset has <math>k!=k(k-1)\cdots1</math> ways to order it.
}}

;Some notations
* <math>n!</math>, read "<math>n</math> factorial", is defined as that <math>n!=n(n-1)(n-2)\cdots 1</math>, with the convention that <math>0!=1</math>.
* <math>n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}</math> is usually denoted as <math>(n)_k\,</math>, read "<math>n</math> lower factorial <math>k</math>".

The quantity <math>{n\choose k}</math> is called a '''binomial coefficient'''.

{{Theorem|Proposition|
# <math>{n\choose k}={n\choose n-k}</math>;
# <math>\sum_{k=0}^n {n\choose k}=2^n</math>.
}}
{{Proof|
1. We give two proofs for the first equation:
:(1) (numerical proof)
::<math>{n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k}</math>.
:(2) (combinatorial proof)
::Choosing <math>k</math> elements from an <math>n</math>-set is equivalent to choosing the <math>n-k</math> elements to leave out. Formally, every <math>k</math>-subset <math>T\in{S\choose k}</math> is uniquely specified by its complement <math>S\setminus T\in {S\choose n-k}</math>, and the same holds for <math>(n-k)</math>-subsets, thus we have a bijection between <math>{S\choose k}</math> and <math>{S\choose n-k}</math>.
2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. For an <math>n</math>-element set <math>S</math>, it is obvious that we can enumerate all subsets of <math>S</math> by enumerating <math>k</math>-subsets for every possible size <math>k</math>, i.e. it holds that
:<math>
2^S=\bigcup_{k=0}^n{S\choose k}.
</math>
For different <math>k</math>, <math>{S\choose k}</math> are obviously disjoint. By the rule of sum,
:<math>2^n=|2^S|=\left|\bigcup_{k=0}^n{S\choose k}\right|=\sum_{k=0}^n\left|{S\choose k}\right|=\sum_{k=0}^n {n\choose k}</math>.
}}

<math>{n\choose k}</math> 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|Theorem (Binomial theorem)|
:<math>(1+x)^n=\sum_{k=0}^n{n\choose k}x^k</math>.
}}
{{Proof|
Write <math>(1+x)^n</math> as the product of <math>n</math> factors
:<math>(1+x)(1+x)\cdots (1+x)</math>.
The term <math>x^k</math> is obtained by choosing <math>x</math> from <math>k</math> factors and 1 from the rest <math>(n-k)</math> factors. There are <math>{n\choose k}</math> ways of choosing these <math>k</math> factors, so the coefficient of <math>x^k</math> is <math>{n\choose k}</math>.
}}

The following proposition has an easy proof due to the binomial theorem.
{{Theorem| Proposition|
:For <math>n>0</math>, the numbers of subsets of an <math>n</math>-set of even and of odd cardinality are equal.
}}
{{Proof|
Set <math>x=-1</math> in the binomial theorem.
:<math>
0=(1-1)^n=\sum_{k=0}^n{n\choose k}(-1)^k=\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}-\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k},
</math>
therefore
:<math>\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}=\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}.</math>
}}

For counting problems, what we care about are ''numbers''. In the binomial theorem, a formal ''variable'' <math>x</math> 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 <math>n</math> is an expression of <math>n</math> as an ''ordered'' sum of ''positive'' integers. A '''<math>k</math>-composition''' of <math>n</math> is a composition of <math>n</math> with exactly <math>k</math> positive summands.

Formally, a <math>k</math>-composition of <math>n</math> is a <math>k</math>-tuple <math>(a_1,a_2,\ldots,a_k)\in\{1,2,\ldots,n\}^k</math> such that <math>a_1+a_2+\cdots+a_k=n</math>.

Suppose we have <math>n</math> identical balls in a line. A <math>k</math>-composition partitions these <math>n</math> balls into <math>k</math> ''nonempty'' sets, illustrated as follows.
:<math>
\begin{array}{c|cc|c|c|ccc|cc}
\bigcirc \,&\, \bigcirc \,& \bigcirc \,&\, \bigcirc \,&\, \bigcirc \,&\, \bigcirc &\, \bigcirc &\, \bigcirc \,&\, \bigcirc \,& \bigcirc
\end{array}
</math>
So the number of <math>k</math>-compositions of <math>n</math> equals the number of ways we put <math>k-1</math> bars "<math>|</math>" into <math>n-1</math> slots "<math>\sqcup</math>", where each slot has at most one bar (because all the summands <math>a_i>0</math>):
:<math>
\bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc
</math>
which is equal to the number of ways of choosing <math>k-1</math> slots out of <math>n-1</math> slots, which is <math>{n-1\choose k-1}</math>.

This graphic argument can be expressed as a formal proof. We construct a bijection between the set of <math>k</math>-compositions of <math>n</math> and <math>{\{1,2,\ldots,n-1\}\choose k-1}</math> as follows.

Let <math>\phi</math> be a mapping that given a <math>k</math>-composition <math>(a_1,a_2,\ldots,a_k)</math> of <math>n</math>,
:<math>
\begin{align}
\phi((a_1,a_2,\ldots,a_k))
&=\{a_1,\,\,a_1+a_2,\,\,a_1+a_2+a_3,\,\,\ldots,\,\,a_1+a_2+\cdots+a_{k-1}\}\\
&=\left\{\sum_{i=1}^ja_i\,\,\bigg|\,\, 1\le j<k\right\}.
\end{align}
</math>
<math>\phi</math> maps every <math>k</math>-composition to a <math>(k-1)</math>-subset of <math>\{1,2,\ldots,n-1\}</math>. It is easy to verify that <math>\phi</math> is a bijection, thus the number of <math>k</math>-compositions of <math>n</math> is <math>{n-1\choose k-1}</math>.
----
The number of <math>k</math>-compositions of <math>n</math> is equal to the number of ''positive'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. This suggests us to relax the constraint and count the number of ''nonnegative'' integer solutions to <math>x_1+x_2+\cdots+x_k=n</math>. We call such a solution a '''weak <math>k</math>-composition''' of <math>n</math>.

Formally, a weak <math>k</math>-composition of <math>n</math> is a tuple <math>(x_1,x_2,\ldots,x_k)\in[n+1]^k</math> such that <math>x_1+x_2+\cdots+x_k=n</math>.

Given a weak <math>k</math>-composition <math>(x_1,x_2,\ldots,x_k)</math> of <math>n</math>, if we set <math>y_i=x_i+1</math> for every <math>1\le i\le k</math>, then <math>y_i>0</math> and
:<math>
\begin{align}
y_1+y_2+\cdots +y_k
&=(x_1+1)+(x_2+1)+\cdots+(x_k+1)&=n+k,
\end{align}
</math>
i.e., <math>(y_1,y_2,\ldots,y_k)</math> is a <math>k</math>-composition of <math>n+k</math>. It is easy to see that it defines a bijection between weak <math>k</math>-compositions of <math>n</math> and <math>k</math>-compositions of <math>n+k</math>. Therefore, the number of weak <math>k</math>-compositions of <math>n</math> is <math>{n+k-1\choose k-1}</math>.
----
We now count the number of nonnegative integer solutions to <math>x_1+x_2+\cdots+x_k\le n</math>.

Let <math>x_{k+1}=n-(x_1+x_2+\cdots+x_k)</math>. Then <math>x_{k+1}\ge 0</math> and <math>x_1+x_2+\ldots+x_k+x_{k+1}=n</math>.
The problem is transformed to that counting the number of nonnegative integer solutions to the above equation. The answer is <math>{n+k\choose k}</math>.

=== Multisets ===
A <math>k</math>-subset of an <math>n</math>-set <math>S</math> is sometimes called a '''<math>k</math>-combination of <math>S</math> without repetitions'''. This suggests the problem of counting the number of <math>k</math>-combinations of <math>S</math> '''''with repetitions'''''; that is, we choose <math>k</math> elements of <math>S</math>, disregarding order and allowing repeated elements.

;Example
:<math>S=\{1,2,3,4\}</math>. All <math>3</math>-combination without repetitions are
::<math>\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\,</math>.
:Allowing repetitions, we also include the following 3-combinations:
::<math>
\begin{align}
&\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\\
&\{2,2,2\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\\
&\{3,3,3\},\{3,3,4\},\{3,4,4\}\\
&\{4,4,4\}
\end{align}
</math>

Combinations with repetitions can be formally defined as '''multisets'''. A multiset is a set with repeated elements. Formally, a multiset <math>M</math> on a set <math>S</math> is a function <math>m:S\rightarrow \mathbb{N}</math>. For any element <math>x\in S</math>, the integer <math>m(x)\ge 0</math> is the number of repetitions of <math>x</math> in <math>M</math>, called the '''multiplicity''' of <math>x</math>. The sum of multiplicities <math>\sum_{x\in S}m(x)</math> is called the '''cardinality''' of <math>M</math> and is denoted as <math>|M|</math>.

A <math>k</math>-multiset on a set <math>S</math> is a multiset <math>M</math> on <math>S</math> with <math>|M|=k</math>. It is obvious that a <math>k</math>-combination of <math>S</math> with repetition is simply a <math>k</math>-multiset on <math>S</math>.

The set of all <math>k</math>-multisets on <math>S</math> is denoted <math>\left({S\choose k}\right)</math>. Assuming that <math>n=|S|</math>, denote <math>\left({n\choose k}\right)=\left|\left({S\choose k}\right)\right|</math>, which is the number of <math>k</math>-combinations of an <math>n</math>-set with repetitions.

Believe it or not: we have already evaluated the number <math>\left({n\choose k}\right)</math>. If <math>S=\{x_1,x_2,\ldots,x_n\}</math>, let <math>z_i=m(x_i)</math>, then <math>\left({n\choose k}\right)</math> is the number of nonnegative integer solutions to <math>z_1+z_2+\cdots+z_n=k</math>, which is the number of weak <math>n</math>-compositions of <math>k</math>, which we have seen is <math>{n+k-1\choose n-1}={n+k-1\choose k}</math>.

----

There is a direct combinatorial proof that <math>\left({n\choose k}\right)={n+k-1\choose k}</math>.

Given a <math>k</math>-multiset <math>0\le a_0\le a_1\le\cdots\le a_{k-1}\le n-1</math> on <math>[n]</math>, then defining <math>b_i=a_i+i</math>, we see that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-subset of <math>[n+k-1]</math>. Conversely, given a <math>k</math>-subset <math>0\le b_0\le b_1\le\cdots\le b_{k-1}\le n+k-2</math> of <math>[n+k-1]</math>, then defining <math>a_i=b_i-i</math>, we have that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-multiset on <math>[n]</math>. Therefore, we have a bijection between <math>\left({[n]\choose k}\right)</math> and <math>{[n+k-1]\choose k}</math>.

=== Multinomial coefficients ===

== Permutations and Partitions ==

== The twelvfold way ==
We consider a very fundamental counting framework: counting functions <math>f:N\rightarrow M</math>. We can define different counting problems according to the types of mapping (1-1, on-to, arbitrary), and the types of the domain and the range (distinguishable, indistinguishable).
* Distinguishability of set:
* Types of mapping:

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!bgcolor="#A7C1F2" | Elements of <math>N</math>
!bgcolor="#A7C1F2" | Elements of <math>M</math>
!bgcolor="#A7C1F2" | Any <math>f</math>
!bgcolor="#A7C1F2" | Injective (1-1) <math>f</math>
!bgcolor="#A7C1F2" | Surjective (on-to) <math>f</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>m^n\,</math>
|align="center"| <math>\left(m\right)_n</math>
|align="center"| <math>m!S(n, m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>\left({m\choose n}\right)</math>
|align="center"|<math>{m\choose n}</math>
|align="center"|<math>\left({m\choose n-m}\right)</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m S(n,k)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>S(n,m)\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m p_k(n)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>p_m(n)\,</math>
|}

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!align="center" bgcolor="#A7C1F2" | balls per bin
!align="center" bgcolor="#A7C1F2" | unrestricted
!align="center" bgcolor="#A7C1F2" | ≤ 1
!align="center" bgcolor="#A7C1F2" | ≥ 1
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-tuples of <math>m</math> things
|align="center"| <math>n</math>-permutations of <math>m</math> things
|align="center"| partition of <math>[n]</math> into <math>m</math> ordered parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> labeled bins
|align="center"| <math>n</math>-combinations of <math>[m]</math> with repetitions
|align="center"| <math>n</math>-combinations of <math>[m]</math> without repetitions
|align="center"| <math>m</math>-compositions of <math>n</math>
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> labeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> unlabeled balls, <math>m</math> unlabeled bins
|align="center"| partitions of <math>n</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>n</math> into <math>m</math> parts
|}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 1.

Randomized Algorithms (Spring 2010)

2009-12-26T15:15:53Z

0:0:0:0:0:0:0:1:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the homepage for ''Randomized Algorithms'' class for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计聪明的算法通常都需要人们对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:15:32Z

0:0:0:0:0:0:0:1:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the homepage for ''Randomized Algorithms'' class for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计聪明的算法通常都需要人们对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论；
推荐：算法设计与分析

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:14:28Z

0:0:0:0:0:0:0:1:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the homepage for ''Randomized Algorithms'' class for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计聪明的算法通常都需要人们对问题本身的数学结构有深刻的认识。

=== 先修课程 ===
必须：离散数学，概率论；
推荐：算法设计与分析

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T13:03:52Z

0:0:0:0:0:0:0:1:

Randomized Algorithms (Spring 2010)

2009-12-26T12:41:57Z

0:0:0:0:0:0:0:1: