Combinatorics (Fall 2010)/Basic enumeration: Difference between revisions

Revision as of 06:52, 9 July 2010

Counting Problems

Functions and Tuples

Sets and Multisets

Subsets

We want to count the number of subsets of a set.

Let $S = {x_{1}, x_{2}, \dots, x_{n}}$ be an $n$ -element set, or $n$ -set for short. Let $2^{S} = {T ∣ T \subset S}$ denote the set of all subset of $S$ . $2^{S}$ is called the power set of $S$ .

We give a combinatorial proof that $| 2^{S} | = 2^{n}$ . We observe that every subset $T \in 2^{S}$ corresponds to a unique bit-vector $v \in {0, 1}^{S}$ , such that each bit $v_{i}$ indicates whether $x_{i} \in S$ . Formally, define a map $ϕ : 2^{S} \to {0, 1}^{n}$ by $ϕ (T) = (v_{1}, v_{2}, \dots, v_{n})$ , where

v_{i} = {\begin{cases} 1 & if x_{i} \in T \\ 0 & if x_{i} \notin T . \end{cases}

The map $ϕ$ is a bijection (a 1-1 correspondence). The proof that $ϕ$ is a bijection is left as an exercise.

We know that $| {0, 1}^{n} | = 2^{n}$ . Why is that? We apply "the rule of product": for any finite sets $P$ and $Q$ , the cardinality of the Cartesian product $| P \times Q | = | P | \cdot | Q |$ . We can write ${0, 1}^{n} = {0, 1} \times {0, 1}^{n - 1}$ , thus $| {0, 1}^{n} | = 2 | {0, 1}^{n - 1} |$ , and by induction, $| {0, 1}^{n} | = 2^{n}$ .

Since there is a bijection between $2^{S}$ and ${0, 1}^{n}$ , it holds that $| 2^{S} | = | {0, 1}^{n} | = 2^{n}$ . Here we use "the rule of bijection": if there exists a bijection between finite sets $P$ and $Q$ , then $| P | = | Q |$ .

There are two elements of this proof:

Find a 1-1 correspondence between subsets of an $n$ -set and $n$ -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

U

can be represented by an array of

| U |

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 $| 2^{S} | = 2^{n}$ . Define the function $f (n) = | 2^{S_{n}} |$ , where $S_{n} = {x_{1}, x_{2}, \dots, x_{n}}$ is an $n$ -set. Our goal is to compute $f (n)$ . We prove the following recursion for $f (n)$ .

Lemma

f (n) = 2 f (n - 1)

.

Proof.

Fix an element $x_{n}$ , let $U$ be the set of subsets of $S_{n}$ that contain $x_{n}$ and let $V$ be the set of subsets of $S_{n}$ that do not contain $x_{n}$ . It is obvious that $U$ and $V$ are disjoint (i.e. $U \cap V = \emptyset$ ) and $2^{S_{n}} = U \cup V$ , because any subset of $S_{n}$ either contains $x_{n}$ or does not contain $x_{n}$ but not both.

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

Therefore,

f (n) = | U \cup V | = | U | + | V |

.

The next observation is that $| U | = | V | = f (n - 1)$ , because $V$ is exactly the $2^{S_{n - 1}}$ , and $U$ is the set resulting from add $x_{n}$ to every member of $2^{S_{n - 1}}$ . Therefore,

f (n) = | U | + | V | = f (n - 1) + f (n - 1) = 2 f (n - 1)

.

◻

The elementary case $f (0) = 1$ , because $\emptyset$ has only one subset $\emptyset$ . Solving the recursion, we have that $| 2^{S} | = f (n) = 2^{n}$ .

Subsets of fixed size

We then count the number of subsets of fixed size of a set. Again, let $S = {x_{1}, x_{2}, \dots, x_{n}}$ be an $n$ -set. We define $(\binom{S}{k})$ to be the set of all $k$ -elements subsets (or $k$ -subsets) of $S$ . Formally, $(\binom{S}{k}) = {T \subseteq S ∣ | T | = k}$ . The set $(\binom{S}{k})$ is sometimes called the $k$ -uniform of $S$ .

We denote that $(\binom{n}{k}) = | (\binom{S}{k}) |$ . The notation $(\binom{n}{k})$ is read " $n$ choose $k$ ".

Theorem

(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k (k - 1) \dots 1} = \frac{n!}{k! (n - k)!}

.

Proof.

The number of ordered $k$ -subsets of an $n$ -set is $n (n - 1) \dots (n - k + 1)$ . Every $k$ -subset has $k! = k (k - 1) \dots 1$ ways to order it.

◻

Some notations

$n! = n (n - 1) (n - 2) \dots 1$ , read " $n$ factorial". A convention is that $0! = 1$ .
$n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!}$ is usually denoted as $(n)_{k}$ , read " $n$ lower factorial $k$ ".

Proposition

(\binom{n}{k}) = (\binom{n}{n - k})

.

Proof 1 (numerical proof).

(\binom{n}{k}) = \frac{n!}{k! (n - k)!} = (\binom{n}{n - k})

.

◻

Proof 2 (combinatorial proof).

Choosing

k

elements from an

n

-set is equivalent to choosing the

n - k

elements to leave out. Formally, every

k

-subset

T \in (\binom{S}{k})

is uniquely specified by its complement

S ∖ T \in (\binom{S}{n - k})

, and the same holds for

(n - k)

-subsets, thus we have a bijection between

(\binom{S}{k})

and

(\binom{S}{n - k})

.

◻

Permutations and Partitions

The twelvfold way

$f : N \to M$

Elements of $N$	Elements of $M$	Any $f$	Injective (1-1) $f$	Surjective (on-to) $f$
distinguishable	distinguishable	$m^{n}$	${(m)}_{n}$	$m! S (n, m)$
indistinguishable	distinguishable	$((\binom{m}{n}))$	$(\binom{m}{n})$	$((\binom{m}{n - m}))$
distinguishable	indistinguishable	$\sum_{k = 1}^{m} S (n, k)$	${\begin{cases} 1 & if n \leq m \\ 0 & if n > m \end{cases}$	$S (n, m)$
indistinguishable	indistinguishable	$\sum_{k = 1}^{m} p_{k} (n)$	${\begin{cases} 1 & if n \leq m \\ 0 & if n > m \end{cases}$	$p_{m} (n)$

@@ Line 50: / Line 50: @@
 === Subsets of fixed size ===
-We then count the number of subsets of fixed size of a set.
+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!=n(n-1)(n-2)\cdots 1</math>, read "<math>n</math> factorial". A convention is 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>".
+{{Theorem|Proposition|
+:<math>{n\choose k}={n\choose n-k}</math>.
+}}
+{{Proofbox|
+'''Proof 1 (numerical proof).'''
+:<math>{n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k}</math>.
+}}
+{{Proofbox|
+'''Proof 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>.
+}}
 == Permutations and Partitions ==

Combinatorics (Fall 2010)/Basic enumeration: Difference between revisions

Revision as of 06:52, 9 July 2010

Contents

Counting Problems

Functions and Tuples

Sets and Multisets

Subsets

Subsets of fixed size

Permutations and Partitions

The twelvfold way

Navigation menu

Combinatorics (Fall 2010)/Basic enumeration: Difference between revisions

Revision as of 06:52, 9 July 2010

Counting Problems

Functions and Tuples

Sets and Multisets

Subsets

Subsets of fixed size

Permutations and Partitions

The twelvfold way

Navigation menu

Search