imported>Etone |
imported>TCSseminar |
| Line 1: |
Line 1: |
| == Basic Enumeration == | | {{Infobox |
| | |name = Infobox |
| | |bodystyle = |
| | |title = <font size=3>计算复杂性 |
| | <br>Computational Complexity</font> |
| | |titlestyle = |
|
| |
|
| The three basic rules for enumeration are:
| | |image = |
| *'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>.
| | |imagestyle = |
| *'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>.
| | |caption = |
| *'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> and <math>T</math>, then <math>|S|=|T|</math>.
| | |captionstyle = |
| | |headerstyle = background:#ccf; |
| | |labelstyle = background:#ddf; |
| | |datastyle = |
|
| |
|
| Now we apply these rules to solve some basic enumeration problems.
| | |header1 =Instructor |
| | | |label1 = |
| === Tuples === | | |data1 = |
| We count the number of <math>n</math>-tuples of <math>[m]</math>. Formally, we count the number of elements of <math>[m]^n</math>. (Remember that <math>[m]=\{0,1,2,\ldots,m-1\}</math>.)
| | |header2 = |
| | | |label2 = |
| It is not very hard to see that this number is <math>m^n</math>. That is, <math>|[m]^n|=m^n</math>.
| | |data2 = 姚鹏晖 |
| | | |header3 = |
| To prove this rigorously, we use ''"the product rule"''.
| | |label3 = Email |
| *'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>.
| | |data3 = pyao@nju.edu.cn |
| | | |header4 = |
| | | |label4= Office |
| To count the size of <math>[m]^n\,</math>, we write <math>[m]^n=[m]\times[m]^{n-1}</math>, thus <math>|[m]^n|=m\cdot|[m]^{n-1}|\,</math>. Solving the recursion, we have that <math>|[m]^n|=m^n\,</math>.
| | |data4= 计算机系 502 |
| | | |header5 = Class |
| === Functions ===
| | |label5 = |
| Consider the problem of counting the number of functions mapping from <math>[n]</math> to <math>[m]</math>, i.e. we count the number of functions in the form <math>f:[n]\rightarrow [m]</math>.
| | |data5 = |
| | | |header6 = |
| We claim that this is the same as counting the number of <math>n</math>-tuples of <math>[m]</math>. To see this, for any <math>f:[n]\rightarrow [m]</math>, we define a tuple <math>v_f\in[m]^n</math> by letting <math>v_f(i)=f(i-1)</math> for every <math>i=1,2,\ldots,n</math>. It is easy to verify that <math>v</math> defines a '''bijection''' (a 1-1 correspondence) between <math>\{f:[n]\rightarrow [m]\}</math> and <math>[m]^n</math>. (Consider this as an exercise.)
| | |label6 = Class meetings |
| | | |data6 = Thursday, 18:30-20:20 <br> 仙II-214 |
| Now we summon the ''"the bijection rule"''.
| | |header7 = |
| *'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> and <math>T</math>, then <math>|S|=|T|</math>.
| | |label7 = Place |
| | | |data7 = |
| Applying this rule, we have that the number of functions from <math>[n]</math> to <math>[m]</math> equals the number of tuples in <math>[m]^n</math>, which is <math>m^n</math> as we proved previously.
| | |header8 = |
| | | |label8 = Office hours |
| === Subsets ===
| | |data8 = Thursday, 14:00-16:00 <br>计算机系 502 |
| We count the number of subsets of a set.
| | |header9 = Textbooks |
| | | |label9 = |
| 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.
| | |data9 = |
| 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>.
| | |header10 = |
| | | |label10 = |
| 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
| | |data10 = https://image.ibb.co/drYZEp/51_KWx_I1yyy_L.jpg |
| :<math>
| | |header11 = |
| v_i=\begin{cases}
| | |label11 = |
| 1 & \mbox{if }x_i\in T\\
| | |data11 = Arora and Barak. <br>''Computational Complexity: A Modern Approach''.<br> Cambridge Univ Press, 2009. |
| 0 & \mbox{if }x_i\not\in T.
| | |header12 = Teaching Assistant |
| \end{cases}
| | |data13= 刘明谋 |
| </math>
| | |label14=Email |
| The map <math>\phi</math> is a bijection. The proof that <math>\phi</math> is a bijection is left as an exercise.
| | |data14=liu.mingmou@smail.nju.edu.cn |
| | | |label15=Office |
| 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>.
| | |data15=计算机系 410 |
| | | |belowstyle = background:#ddf; |
| | | |below = |
| 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 bijection rule: if there is a 1-1 correspondence between two sets, then their cardinalities are the same.
| |
| | |
| Many counting problems are solved by establishing a bijection between the set to be counted and some easy-to-count set. This kind of proofs are usually called (non-rigorously) '''combinatorial proofs'''.
| |
| | |
| ----
| |
| We give an alternative proof that <math>|2^S|=2^n</math>. The proof needs another basic counting rule: ''"the sum rule"''.
| |
| *'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</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 sum rule,
| |
| :<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>".
| |
| | |
| === Binomial coefficient ===
| |
| 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 sum rule,
| |
| :<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. 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 <font color="red">''ordered''</font> sum of <font color="red">''positive''</font> 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 solutions to <math>x_1+x_2+\cdots+x_k=n</math> in ''positive'' integers. This suggests us to relax the constraint and count the number of solutions to <math>x_1+x_2+\cdots+x_k=n</math> in ''nonnegative'' integers. 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 solutions to <math>x_1+x_2+\cdots+x_k\le n</math> in nonnegative integers.
| |
| | |
| 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 solutions to the above equation in nonnegative integers. 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.\left({\binom{S}{k}}\right)\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 solutions to <math>z_1+z_2+\cdots+z_n=k</math> in nonnegative integers, 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>\{a_0,a_1,\ldots,a_{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 ===
| |
| The binomial coefficient <math>{n\choose k}</math> may be interpreted as follows. Each element of an <math>n</math>-set is placed into two groups, with <math>k</math> elements in Group 1 and <math>n-k</math> elements in Group 2. The binomial coefficient <math>{n\choose k}</math> counts the number of such placements.
| |
| | |
| This suggests a generalization allowing more than two groups. Let <math>(a_1,a_2,\ldots,a_m)</math> be a tuple of nonnegative integers summing to <math>n</math>. Let <math>{n\choose a_1,a_2,\ldots,a_m}</math> denote the number of ways of assigning each element of an <math>n</math>-set to one of <math>m</math> groups <math>G_1,G_2,\ldots,G_m</math> so that exactly <math>a_i</math> elements are assigned to <math>G_i</math>.
| |
| | |
| The binomial coefficient is just the case when there are two groups, and <math>{n\choose k}={n\choose k,n-k}</math>. The number <math>{n\choose a_1,a_2,\ldots,a_m}</math> is called a '''multinomial coefficient'''. We can think of it as that <math>n</math> labeled balls are assigned to <math>m</math> labeled bins, and <math>{n\choose a_1,a_2,\ldots,a_m}</math> is the number of assignments such that the <math>i</math>-th bin has <math>a_i</math> balls in it.
| |
| | |
| The multinomial coefficient can also be interpreted as the number of ''permutations of multisets''. A permutation <math>\pi</math> of an <math>n</math>-set <math>S</math> can be defined in two equivalent ways:
| |
| * a bijection <math>\pi:S\rightarrow S</math>;
| |
| * a tuple <math>\pi=(x_1,x_2,\ldots,x_n)\in S^n</math> such that all <math>x_i</math> are distinct.
| |
| There are <math>n!</math> permutations of an <math>n</math>-set <math>S</math>.
| |
| | |
| A '''permutation of a multiset''' <math>M</math> is a tuple <math>\pi=(x_1,x_2,\ldots,x_n)</math> such that every <math>x_i\in M</math> appears in <math>\pi</math> for exactly <math>m(x_i)</math> times, where <math>m(x_i)</math> is the multiplicity of <math>x_i</math> in <math>M</math>.
| |
| | |
| ;Example
| |
| :We want to enumerate all the ways of reordering the word "multinomial". Note that in this word, the letter "m", "l" and "i" each appears twice. So the problem is to enumerate the permutations of the multiset <math>\{\text{a, i, i, l, l, m, m, n, o, t, u}\}</math>. | |
| | |
| Let <math>M</math> be a multiset of <math>m</math> distinct elements <math>x_1,x_2,\ldots,x_m</math> such that <math>x_i</math> has multiplicity <math>a_i</math> in <math>M</math>. A permutation <math>\pi</math> of multiset <math>M</math> assigns <math>n</math> indices <math>1,2,\ldots,n</math> to <math>m</math> groups, where each group corresponds to a distinct element <math>x_i</math>, such that <math>i</math> is assigned to group <math>j</math> if <math>\pi_i=x_j</math>.
| |
| | |
| Therefore,
| |
| <math>{n\choose a_1,a_2,\ldots,a_m}</math> is also the number of permutations of a multiset <math>M</math> with <math>|M|=n</math> such that <math>M</math> has <math>m</math> distinct elements whose multiplicities are given by <math>a_1,a_2,\ldots,a_m</math>.
| |
| | |
| {{Theorem|Theorem|
| |
| :<math>{n\choose a_1,a_2,\ldots,a_m}=\frac{n!}{a_1!a_2!\cdots a_m!}.</math>
| |
| }}
| |
| {{Proof|
| |
| There are <math>n!</math> permutations of <math>n</math> objects. Assume that these <math>n</math> objects are the elements of an multiset <math>M</math> of <math>m</math> distinct elements with <math>|M|=n</math> and multiplicities <math>a_1,a_2,\ldots,a_m</math>. Since <math>a_i!</math> permutations of object <math>i</math> do not change the permutation of the multiset <math>M</math>, every <math>a_1!a_2!\cdots a_m!</math> permutations of these <math>n</math> objects correspond to the same permutation of the multiset <math>M</math>. Thus, the number of permutations of <math>M</math> is <math>\frac{n!}{a_1!a_2!\cdots a_m!}</math>.
| |
| }}
| |
| | |
| We also have the Multinomial Theorem.
| |
| {{Theorem|Theorem|
| |
| :<math>{n\choose a_1,a_2,\ldots,a_m}</math> is the coefficient of <math>x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}</math> in <math>(x_1+x_2+\cdots +x_m)^n</math>.
| |
| }}
| |
| {{Proof|
| |
| Write
| |
| :<math>(x_1+x_2+\cdots +x_m)^n=(x_1+x_2+\cdots +x_m)\cdots (x_1+x_2+\cdots +x_m)</math>.
| |
| Each of the <math>n</math> factors corresponds to a distinct ball, and <math>x_1,x_2,\ldots,x_m</math> correspond to <math>m</math> groups. The coefficient of <math>x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}</math> equals the number of ways to put <math>n</math>distinct balls to <math>m</math> distinct groups so that group <math>i</math> receives <math>a_i</math> balls, which is exactly our first definition of <math>{n\choose a_1,a_2,\ldots,a_m}</math>.
| |
| }}
| |
| | |
| === Partitions of a set ===
| |
| A '''partition''' of finite set <math>S</math> is a collection <math>P=\{S_1,S_2,\ldots,S_k\}</math> of subsets of <math>S</math> such that:
| |
| * <math>S_i\neq\emptyset</math> for every <math>i</math>;
| |
| * <math>S_i\cap S_j=\emptyset</math> if <math>i\neq j</math> (also called that blocks are pairwise '''disjoint''');
| |
| * <math>S_1\cup S_2\cup\cdots\cup S_k=S</math>.
| |
| Each <math>S_i</math> is called a '''block''' of partition <math>P</math>. We call <math>P</math> a '''<math>k</math>-partition''' of <math>S</math> if <math>|P|=k</math>.
| |
| | |
| Define <math>\left\{{n \atop k}\right\}</math> to be the number of <math>k</math>-partitions of an <math>n</math>-set. Note that since a partition <math>P</math> is a set, the order of blocks <math>S_1,S_2,\ldots,S_k</math> is disregarded when counting <math>k</math>-partitions.
| |
| | |
| The number <math>\left\{{n \atop k}\right\}</math> is called a '''Stirling number of the second kind'''.
| |
| :{|border="1"
| |
| |
| |
| ;Stirling number
| |
| : [http://en.wikipedia.org/wiki/Stirling_number Stirling numbers] are named after James Stirling.There are two kinds of Stirling numbers. [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Stirling number of the first kind] is related to the number of permutations with fixed number of disjoint cycles. And [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind] counts the number of ways of partitioning a set into fixed number of disjoint blocks. Both numbers arise from important combinatorial problems and have various applications in combinatorics and other branches of Mathematics.
| |
| |} | |
| Unlike previous identities, it is very difficult to give a determinant for <math>\left\{{n \atop k}\right\}</math>. But we have the following recurrence:
| |
| {{Theorem|Theorem|
| |
| :<math>\left\{{n \atop k}\right\}=k\left\{{n-1 \atop k}\right\}+\left\{{n-1 \atop k-1}\right\}</math>.
| |
| }}
| |
| {{Proof|
| |
| To partition <math>\{1,2,\ldots,n\}</math> into <math>k</math> blocks,
| |
| * we can partition <math>\{1,2,\ldots,{n-1}\}</math> into <math>k</math> blocks and place <math>n</math> into one of the <math>k</math> blocks, which gives us <math>k\left\{{n-1 \atop k}\right\}</math> ways to do so;
| |
| * or we can partition <math>\{1,2,\ldots,{n-1}\}</math> into <math>k-1</math> blocks and let <math>\{n\}</math> be a block by itself, which gives us <math>\left\{{n-1 \atop k-1}\right\}</math> ways to do so.
| |
| | |
| The partitions constructed by these two methods are different, since by the first method, <math>n</math> is always in a block of cardinality <math>>1</math>, and by the second method, <math>\{n\}</math> is always a block. So the cases are disjoint. And any <math>k</math>-partition of an <math>n</math>-set must be constructible by one of the two methods, thus by the sum rule,
| |
| :<math>\,\left\{{n \atop k}\right\}=k\left\{{n-1 \atop k}\right\}+\left\{{n-1 \atop k-1}\right\}</math>.
| |
| }}
| |
| | |
| Let <math>B_n=\sum_{k=1}^n \left\{{n \atop k}\right\}</math>, which gives the total number of partitions of an <math>n</math>-set. <math>B(n)</math> is called the '''Bell number'''.
| |
| | |
| === Partitions of a number ===
| |
| We count the ways of partitioning <math>n</math> ''identical'' objects into <math>k</math> ''unordered'' groups. This is equivalent to counting the ways partitioning a number <math>n</math> into <math>k</math> unordered parts.
| |
| | |
| A '''<math>k</math>-partition''' of a number <math>n</math> is a multiset <math>\{x_1,x_2,\ldots,x_k\}</math> with <math>x_i\ge 1</math> for every element <math>x_i</math> and <math>x_1+x_2+\cdots+x_k=n</math>.
| |
| | |
| We define <math>p_k(n)</math> as the number of <math>k</math>-partitions of <math>n</math>.
| |
| | |
| For example, number 7 has the following partitions:
| |
| <div class="center"><math>
| |
| \begin{align}
| |
| &\{7\}
| |
| & p_1(7)=1\\
| |
| &\{1,6\},\{2,5\},\{3,4\}
| |
| & p_2(7)=3\\
| |
| &\{1,1,5\}, \{1,2,4\}, \{1,3,3\}, \{2,2,3\}
| |
| & p_3(7)=4\\
| |
| &\{1,1,1,4\},\{1,1,2,3\}, \{1,2,2,2\}
| |
| & p_4(7)=3\\
| |
| &\{1,1,1,1,3\},\{1,1,1,2,2\}
| |
| & p_5(7)=2\\
| |
| &\{1,1,1,1,1,2\}
| |
| & p_6(7)=1\\
| |
| &\{1,1,1,1,1,1,1\}
| |
| & p_7(7)=1
| |
| \end{align}
| |
| </math></div>
| |
| | |
| Equivalently, we can also define that A <math>k</math>-partition of a number <math>n</math> is a <math>k</math>-tuple <math>(x_1,x_2,\ldots,x_k)</math> with:
| |
| * <math>x_1\ge x_2\ge\cdots\ge x_k\ge 1</math>;
| |
| * <math>x_1+x_2+\cdots+x_k=n</math>.
| |
| | |
| <math>p_k(n)</math> the number of integral solutions to the above system.
| |
| | |
| Let <math>p(n)=\sum_{k=1}^n p_k(n)</math> be the total number of partitions of <math>n</math>. The function <math>p(n)</math> is called the '''partition number'''.
| |
| | |
| We now try to determine <math>p_k(n)</math>. Unfortunately, <math>p_k(n)</math> does not have a nice closed form formula. We now give a recurrence for <math>p_k(n)</math>.
| |
| | |
| {{Theorem|Proposition|
| |
| :<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
| |
| }}
| |
| {{Proof|
| |
| Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Note that it must hold that
| |
| :<math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.
| |
| There are two cases: <math>x_k=1</math> or <math>x_k>1</math>.
| |
| ;Case 1.
| |
| :If <math>x_k=1</math>, then <math>(x_1,\cdots,x_{k-1})</math> is a distinct <math>(k-1)</math>-partition of <math>n-1</math>. And every <math>(k-1)</math>-partition of <math>n-1</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k-1}(n-1)</math>.
| |
| ;Case 2.
| |
| :If <math>x_k>1</math>, then <math>(x_1-1,\cdots,x_{k}-1)</math> is a distinct <math>k</math>-partition of <math>n-k</math>. And every <math>k</math>-partition of <math>n-k</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k}(n-k)</math>.
| |
| In conclusion, the number of <math>k</math>-partitions of <math>n</math> is <math>p_{k-1}(n-1)+p_k(n-k)</math>, i.e.
| |
| :<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
| |
| }}
| |
| | |
| Use the above recurrence, we can compute the <math>p_k(n)</math> for some decent <math>n</math> and <math>k</math> by computer simulation.
| |
| | |
| If we are not restricted ourselves to the precise estimation of <math>p_k(n)</math>, the next theorem gives an asymptotic estimation of <math>p_k(n)</math>. Note that it only holds for '''constant''' <math>k</math>, i.e. <math>k</math> does not depend on <math>n</math>.
| |
| | |
| {{Theorem|Theorem|
| |
| For any fixed <math>k</math>,
| |
| :<math>p_k(n)\sim\frac{n^{k-1}}{k!(k-1)!}</math>,
| |
| as <math>n\rightarrow \infty</math>.
| |
| }}
| |
| {{Proof|
| |
| Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Then <math>x_1+x_2+\cdots+x_k=n</math> and <math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.
| |
| | |
| The <math>k!</math> permutations of <math>(x_1,\ldots,x_k)</math> yield at most <math>k!</math> many <math>k</math>-compositions (the ''ordered'' sum of <math>k</math> positive integers). There are <math>{n-1\choose k-1}</math> many <math>k</math>-compositions of <math>n</math>, every one of which can be yielded in this way by permuting a partition. Thus,
| |
| :<math>k!p_k(n)\ge{n-1\choose k-1}</math>.
| |
| | |
| Let <math>y_i=x_i+k-i</math>. That is, <math>y_k=x_k, y_{k-1}=x_{k-1}+1, y_{k-2}=x_{k-2}+2,\ldots, y_{1}=x_{1}+k-1</math>. Then, it holds that
| |
| * <math>y_1>y_2>\cdots>y_k\ge 1</math>; and
| |
| * <math>y_1+y_2+\cdots+y_k=n+\frac{k(k-1)}{2}</math>.
| |
| Each permutation of <math>(y_1,y_2,\ldots,y_k)</math> yields a '''distinct''' <math>k</math>-composition of <math>n+\frac{k(k-1)}{2}</math>, because all <math>y_i</math> are distinct.
| |
| Thus,
| |
| :<math>k!p_k(n)\le {n+\frac{k(k-1)}{2}-1\choose k-1}</math>.
| |
| | |
| Combining the two inequalities, we have
| |
| :<math>\frac{{n-1\choose k-1}}{k!}\le p_k(n)\le \frac{{n+\frac{k(k-1)}{2}-1\choose k-1}}{k!}</math>. | |
| The theorem follows.
| |
| }}
| |
| | |
| === Ferrers diagram ===
| |
| A partition of a number <math>n</math> can be represented as a diagram of dots (or squares), called a '''Ferrers diagram''' (the square version of Ferrers diagram is also called a '''Young diagram''', named after a structured called Young tableaux). | |
| | |
| Let <math>(x_1,x_2,\ldots,x_k)</math> with that <math>x_1\ge x_2\ge \cdots x_k\ge 1</math> be a partition of <math>n</math>. Its Ferrers diagram consists of <math>k</math> rows, where the <math>i</math>-th row contains <math>x_i</math> dots (or squares).
| |
| | |
| <div class="center">
| |
| {|border="0"
| |
| | | |
| {|border="0"
| |
| |[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
| |
| |-
| |
| |[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
| |
| |-
| |
| |[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
| |
| |-
| |
| |[[File:Chess xot45.svg|22px]]
| |
| |}
| |
| |
| |
| [[File:Chess t45.svg|120px]]
| |
| |align=center|
| |
| {|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]
| |
| |}
| |
| |-
| |
| |align=center|Ferrers diagram (''dot version'') of (5,4,2,1)||
| |
| |align=center|Ferrers diagram (''square version'') of (5,4,2,1)
| |
| |}
| |
| </div>
| |
| | |
| ;Conjugate partition
| |
| The partition we get by reading the Ferrers diagram by column instead of rows is called the '''conjugate''' of the original partition.
| |
| <div class="center">
| |
| {|border="0"
| |
| |align=center|
| |
| {|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |- | |
| |[[File:Chess t45.svg|22px]]
| |
| |}
| |
| |
| |
| [[File:Chess t45.svg|120px]]
| |
| |align=center|
| |
| {|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]
| |
| |-
| |
| |[[File:Chess t45.svg|22px]]
| |
| |}
| |
| |-
| |
| |align=center|<math>(6,4,4,2,1)</math>||
| |
| |align=center|conjugate: <math>(5,4,3,3,1,1)</math>
| |
| |}
| |
| </div>
| |
| | |
| Clearly,
| |
| * different partitions cannot have the same conjugate, and
| |
| * every partition of <math>n</math> is the conjugate of some partition of <math>n</math>,
| |
| so the conjugation mapping is a permutation on the set of partitions of <math>n</math>. This fact is very useful in proving theorems for partitions numbers.
| |
| | |
| Some theorems of partitions can be easily proved by representing partitions in Ferrers diagrams.
| |
| | |
| {{Theorem|Proposition|
| |
| # The number of partitions of <math>n</math> which have largest summand <math>k</math>, is <math>p_k(n)</math>.
| |
| # The number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts. Formally,
| |
| ::<math>p_k(n)=\sum_{j=1}^k p_j(n-k)</math>.
| |
| }}
| |
| {{Proof|
| |
| # For every <math>k</math>-partition, the conjugate partition has largest part <math>k</math>. And vice versa.
| |
| # For a <math>k</math>-partition of <math>n</math>, remove the leftmost cell of every row of the Ferrers diagram. Totally <math>k</math> cells are removed and the remaining diagram is a partition of <math>n-k</math> into at most <math>k</math> parts. And for a partition of <math>n-k</math> into at most <math>k</math> parts, add a cell to each of the <math>k</math> rows (including the empty ones). This will give us a <math>k</math>-partition of <math>n</math>. It is easy to see the above mappings are 1-1 correspondences. Thus, the number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts.
| |
| }} | | }} |
|
| |
|
| == The twelvfold way ==
| |
| We now introduce a general framework for counting problems, called the [http://en.wikipedia.org/wiki/Twelvefold_way twelvefold way]. This framework is introduced by the great mathematician and also a great teacher, [http://en.wikipedia.org/wiki/Gian-Carlo_Rota Gian-Carlo Rota].
| |
|
| |
|
| Let <math>N</math> and <math>M</math> be finite sets with <math>|N|=n</math> and <math>|M|=m</math>. We count the number of functions <math>f:N\rightarrow M</math> subject to different restrictions. There are three restrictions regarding the mapping <math>f</math> itself:
| |
| # <math>f</math> is an '''arbitrary''' function;
| |
| # <math>f</math> is an '''injection''' (one-to-one);
| |
| # <math>f</math> is a '''surjection''' (onto).
| |
|
| |
|
| The elements of <math>N</math> and <math>M</math> can be regarded as '''distinguishable''' or '''indistinguishable'''. Think of <math>N</math> as a set of <math>n</math> balls and <math>M</math> as a set of <math>m</math> bins. A function <math>f:N\rightarrow M</math> is an assignment of the <math>n</math> balls into <math>m</math> bins. The balls are ''distinguishable'' if each ball has a distinct label on it, and the balls are ''indistinguishable'' if they are identical. The same also applies to the bins.
| | = Announcement = |
| | * (2019/9/5) 新学期第一堂课。 |
| | * (2019/9/5) 交流及授课反馈群: 854081425 [https://i.ibb.co/cN3ydT6/2019.png QRcode]（助教出差中，有问题可以到qq群问或者邮件询问。qq群仅作讨论用，所有的通知及资料仍在本页面发放） |
| | * (2019/9/17) 第一次作业已发布，9月26日之前交。 |
| | * (2019/9/26) 第二次作业已发布，10月10日上课前交。 |
| | * (2019/9/29) 第二次作业的 3.8 题目有错，详见[[计算复杂性 (Fall 2019)/Assignment 2|作业页面]] |
| | * (2019/10/7) 第一次作业已批阅发回，参考答案及评分标准已发布。 |
| | * (2019/10/11) 第三次作业已发布，10月24日上课前交。 |
| | * (2019/10/13) 第三次作业 4.3 题目有错，详见[[计算复杂性 (Fall 2019)/Assignment 3|作业页面]]。 |
| | * (2019/10/23) 第二次作业已批阅发回，参考答案及评分标准已发布。 |
| | * (2019/10/24) 第四次作业已发布，10月31日上课前交。 |
| | * (2019/10/30) 因姚老师出差，将<strong><font color=red>11月7日晚上的课调整到11月8日晚上。具体地点待通知。</font></strong> |
| | * (2019/10/31) 第五次作业已发布，11月7日前交。 |
| | * (2019/11/2) 第五次作业 6.14, 6.15 题目有错，详见[[计算复杂性 (Fall 2019)/Assignment 5|作业页面]]。 |
| | * (2019/11/6) <strong><font color=red>11月8日晚上在原教室仙II-214上课。</font></strong> |
| | * (2019/11/14) 第六次作业已发布，11月21日前交。 |
| | * (2019/11/14) 第三次作业已批阅发回，参考答案及评分标准已发布。 |
| | * (2019/11/14) 第四次作业已批阅发回，参考答案及评分标准已发布。 |
| | * (2019/12/6) 第五次作业已批阅发回，参考答案及评分标准已发布。 |
| | * (2019/12/6) 第六次作业已批阅发回，参考答案及评分标准已发布。 |
| | * (2019/12/6) 第七次作业已发布，12月12日前交。 |
| | * (2019/12/19) 第七次作业已批阅发回，参考答案及评分标准已发布。 |
|
| |
|
| Three restrictions on the functions, with two restrictions on each of the domain and the range, together give us twelve counting problems, called the '''Twelvefold Way'''.
| | = Course info = |
| | * '''Instructor ''': 姚鹏晖 ([mailto:pyao@nju.edu.cn pyao@nju.edu.cn]) |
| | * '''Teaching assistant''': 刘明谋 ([mailto:liu.mingmou@smail.nju.edu.cn liu.mingmou@smail.nju.edu.cn]) |
| | * '''Class meeting''': Thursday, 18:30-20:20 仙II-214. |
| | * '''Office hour''': Thursday, 14:00-16:00, 计算机系 502. |
|
| |
|
| The following table gives the solutions to the counting problems.
| | = Course materials = |
| {|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| | * [https://www.amazon.com/dp/0521424267 Arora and Barak. Computational Complexity: A Modern Approach. Cambridge Univ Press, 2009.] |
| |-
| | * [https://www.amazon.cn/dp/B007VXH70K/ Arora and Barak. 计算复杂性的现代方法. (英语). 世界图书出版公司. 2012.] |
| !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!\left\{{n\atop m}\right\}\,</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>{n-1\choose m-1}</math>
| |
| |-
| |
| |align="center"| ''distinguishable''
| |
| |align="center"| ''indistinguishable''
| |
| |align="center"| <math>\sum_{k=1}^m \left\{{n\atop k}\right\}</math>
| |
| |align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
| |
| |align="center"| <math>\left\{{n\atop m}\right\}\,</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>
| |
| |}
| |
|
| |
|
| In the Volume 4A of Don Knuth's [http://www-cs-faculty.stanford.edu/~uno/taocp.html TAOCP], the twelvefold way is presented as the problems of counting the ways of assigning <math>n</math> balls into <math>m</math> bins. The domain <math>N</math> corresponds to a set of <math>n</math> balls, the range <math>M</math> corresponds to a set of <math>m</math> bins, and each function corresponds to an assignment of <math>n</math> balls into <math>m</math> bins. Balls (or bins) are distinguishable if they are ''distinct'' and are indistinguishable if they are ''identical''. An injective function corresponds to an assignment with ''at most'' one ball in each bin, and a surjective function corresponds to an assignment with ''at least'' one ball(s) in each bin.
| | 如果在获取教材方面有困难可以联系助教。(仅限英文版) |
|
| |
|
| {|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| | = Assignments = |
| |-
| | 这是一门概念性课程，也是一门理论课程。作为理论课程，证明应该是小心、严谨的。作为概念性课程，同学们需要在作业中证明自己确实、清楚地掌握了这些概念，而不是在试图滥竽充数蒙混过关。所以在作业中请尽量不要偷懒，把每一个步骤和定义都仔细小心地写清楚，以免无意义地失分。 |
| !align="center" bgcolor="#A7C1F2" | balls per bin
| | * [[计算复杂性 (Fall 2019)/Assignment 1|Assignment 1]], due on Sep 25. [[计算复杂性 (Fall 2019)/作业1已提交名单 | 作业1已提交名单]]. |
| !align="center" bgcolor="#A7C1F2" | unrestricted
| | * [https://www.overleaf.com/read/rwcjcjpxqvfn 作业1参考答案及评分标准] |
| !align="center" bgcolor="#A7C1F2" | ≤ 1
| | * [[计算复杂性 (Fall 2019)/Assignment 2|Assignment 2 (updated)]], due on Oct 10. [[计算复杂性 (Fall 2019)/作业2已提交名单 | 当前作业2已提交名单]]. |
| !align="center" bgcolor="#A7C1F2" | ≥ 1
| | * [https://www.overleaf.com/read/dcnfcjxnpqgv 作业2参考答案及评分标准] |
| |- | | * [[计算复杂性 (Fall 2019)/Assignment 3|Assignment 3]], due on Oct 24. [[计算复杂性 (Fall 2019)/作业3已提交名单 | 当前作业3已提交名单]]. |
| !align="center" bgcolor="#A7C1F2" | <math>n</math> distinct balls, <br><math>m</math> distinct bins
| | * [https://www.overleaf.com/read/dnqkmkcgqjtx 作业3参考答案及评分标准] |
| |align="center"| <math>n</math>-tuples <br>of <math>m</math> things | | * [[计算复杂性 (Fall 2019)/Assignment 4|Assignment 4]], due on Oct 31.[[计算复杂性 (Fall 2019)/作业4已提交名单 | 当前作业4已提交名单]]. |
| |align="center"| <math>n</math>-permutations <br>of <math>m</math> things
| | * [https://www.overleaf.com/read/nszxznspcqmp 作业4参考答案及评分标准] |
| |align="center"| partition of <math>[n]</math> <br> into <math>m</math> ordered parts | | * [[计算复杂性 (Fall 2019)/Assignment 5|Assignment 5]], due on Nov 7.[[计算复杂性 (Fall 2019)/作业5已提交名单 | 当前作业5已提交名单]]. |
| |- | | * [https://www.overleaf.com/read/npqfwgtyvkst 作业5参考答案及评分标准] |
| !align="center" bgcolor="#A7C1F2" | <math>n</math> identical balls, <br><math>m</math> distinct bins
| | * [[计算复杂性 (Fall 2019)/Assignment 6|Assignment 6]], due on Nov 21.[[计算复杂性 (Fall 2019)/作业6已提交名单 | 当前作业6已提交名单]]. |
| |align="center"| <math>n</math>-combinations of <math>[m]</math> <br>with repetitions | | * [https://www.overleaf.com/read/twcwcwnmvwcj 作业6参考答案及评分标准] |
| |align="center"| <math>n</math>-combinations of <math>[m]</math> <br> without repetitions
| | * [[计算复杂性 (Fall 2019)/Assignment 7|Assignment 7]], due on Dec 12.[[计算复杂性 (Fall 2019)/作业7已提交名单 | 当前作业7已提交名单]]. |
| |align="center"| <math>m</math>-compositions <br>of <math>n</math>
| | * [https://www.overleaf.com/read/thzypgnhjpgx 作业7参考答案及评分标准] |
| |- | |
| !align="center" bgcolor="#A7C1F2" | <math>n</math> distinct balls, <br><math>m</math> identical bins
| |
| |align="center"| partitions of <math>[n]</math> <br>into <math>\le m</math> parts
| |
| |align="center"| <math>n</math> pigeons <br>into <math>m</math> holes
| |
| |align="center"| partitions of <math>[n]</math> <br>into <math>m</math> parts | |
| |- | |
| !align="center" bgcolor="#A7C1F2" | <math>n</math> identical balls, <br><math>m</math> identical bins
| |
| |align="center"| partitions of <math>n</math> <br>into <math>\le m</math> parts
| |
| |align="center"| <math>n</math> pigeons <br>into <math>m</math> holes | |
| |align="center"| partitions of <math>n</math> <br>into <math>m</math> parts
| |
| |}
| |
|
| |
|
| == Reference == | | = Lecture Notes = |
| * ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 1.
| | 如果有下载课件的问题请及时联系助教。 |
| | # 图灵机、计算复杂性类 P ([http://45.77.25.129:8000/cc_fall19/lec%201.pptx slides]) |
| | # NP 和 NP 完全问题 ([http://45.77.25.129:8000/cc_fall19/lec%202.pptx slides.v2]) |
| | # 对角化方法 ([http://45.77.25.129:8000/cc_fall19/lec%203.pptx slides(updated)]) |
| | # 空间复杂度 ([http://45.77.25.129:8000/cc_fall19/lec%204.1.pptx slides1],[http://45.77.25.129:8000/cc_fall19/lec%204.2.pptx slides2]) |
| | # 多项式谱系 ([http://45.77.25.129:8000/cc_fall19/lec%205.pptx slides]) |
| | # 布尔线路 ([http://45.77.25.129:8000/cc_fall19/lec%206.pptx slides1], [http://45.77.25.129:8000/cc_fall19/lec%207.pptx slides2]) |
| | # 随机计算 ([http://45.77.25.129:8000/cc_fall19/lec%208.pptx slides1], [http://45.77.25.129:8000/cc_fall19/lec%209.pptx slides2]) |
| | # 交互证明 ([http://45.77.25.129:8000/cc_fall19/lec%2010.pptx slides1], [http://45.77.25.129:8000/cc_fall19/lec%2011.pptx slides2]) |
| | # 前沿课题介绍 ([http://45.77.25.129:8000/cc_fall19/lec%2013.pptx 通讯复杂性]) |
