TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T05:44:16Z

210.28.131.13: /* Subsets */

== Counting Problems ==

== Functions and Tuples ==

== 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.

We know that <math>|\{0,1\}^n|=2^n\,</math>. Why is that? We apply '''"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>. We can write <math>\{0,1\}^n=\{0,1\}\times\{0,1\}^{n-1}</math>, thus <math>|\{0,1\}^n|=2|\{0,1\}^{n-1}|\,</math>, and by induction, <math>|\{0,1\}^n|=2^n\,</math>.

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 use '''"the rule of bijection"''': if there exists a bijection between finite sets <math>P</math> and <math>Q</math>, then <math>|P|=|Q|</math>.

There are two elements of this 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.

== Permutations and Partitions ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Template:Proof

2010-07-09T05:22:45Z

210.28.131.13:

:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|'''Proof.'''
:{|
|{{{1}}}
|}
:<math>\square</math>
|}

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T03:11:44Z

210.28.131.13: /* Subsets */

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T03:07:57Z

210.28.131.13: /* Sets and Multisets */

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T01:58:24Z

210.28.131.13: /* Sets and Multisets */

== Counting Problems ==

== Functions and Tuples ==

== Sets and Multisets ==
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>.

== Permutations and Partitions ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T01:31:02Z

210.28.131.13:

== Counting Problems ==

== Functions and Tuples ==

== Sets and Multisets ==

== Permutations and Partitions ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T01:30:45Z

210.28.131.13: /* Tuples and Permutations */

== Counting Problems ==

== Functions and Tuples ==

== Sets and Multisets ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T01:26:49Z

210.28.131.13: /* Permutations */

== Counting Problems ==

== Tuples and Permutations ==

== Sets and Multisets ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T01:26:22Z

210.28.131.13:

== Counting Problems ==

== Permutations ==

== Sets and Multisets ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Combinatorics (Fall 2010)/Basic enumeration

2010-07-09T01:06:01Z

210.28.131.13: /* The twelvfold way */

== Counting Problems ==

== Sets and Multisets ==

== Permutations ==

== The twelvfold way ==
<math>f:N\rightarrow M</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;"
|-
!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>
|}

Template:Theorem

2010-06-06T12:19:13Z

210.28.131.13:

Template:Theorem

2010-06-06T12:01:53Z

210.28.131.13: Created page with ':{|border="1" |'''{{{1}}}''' {{{2}}} |}'

:{|border="1"
|'''{{{1}}}'''
{{{2}}}
|}