Review of Combinatorics （HITSZ）含22年真题

好久没更新博客了，一方面是有其他工作；一方面是假期空闲时间比较想休息，陪陪家人。本次更新主要是关于HITSZ组合数学方面的比较重要的内容，课程老师授课比较用心，值得学习（不过对博主后续研究工作不太有帮助，OK。进入正题。（注：以下PPT内容均来自HITSZ组合数学黄荷娇教授）

1. Pigeonhole Principle

1.1 Conceptions

• The Pigeonhole Principle: If $m+1$ pigeons are put into $m$ pigeonholes, then at least one hole contains two or more pigeons.
• Dirichlet Principle: If $n>m$ pigeons are put into $m$ pigeonholes, there’s a hole with more than one pigeon.
• Generalized Pigeonhole Principle: If $N$ objects are assigned to $k$ places, then at least one place must be assigned at least $\lceil N/k\rceil$ objects.
• Pigeonhole Principle-Strong Form: Let $q_1$,$q_2$, …, $q_n$ be positive integers. If $q_1+q_2+\dots +q_n-n+1$ objects are put into $n$ boxes, then either the first box contains at least $q_1$ objects, or the second box contains at least $q_2$ object, ……, or the $n$th box contains at least $q_n$ objects.

1.2 Examples

1. There are several people in the room. Some are acquaintances, others are not. (Being acquainted is a symmetric non-reflexive relationship.) Show that some two people have the same number of acquaintances.

   Suppose one can know $0$ person, $1$ person, … , $N-1$ persons. Note that $0$ person cannot exist with $N-1$ persons. Thus, $N$ people can have at most $N-1$ cases for acquaintances. According to the pigeonhole principle, there must be some two people have the same number of acquaintances.

2. Given $m$ integers $a_1$,$ a_2$,\dots ,$a_m$, there exists integers $k$ and $l$ with $0\le k<l\le m$ such that $a_{k+1}$ + $a_{k+2}$ + … + $a_l$ is divisible by $m$.

   Consider the $m$ sums $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, …, $a_1+a_2+a_3+\dots +a_m$.

   ① If any of these sums is divisible by $m$, then the conclusion holds.

   ② Otherwise, the reminder has only $m-1$ cases (i.e., 1, …, $m-1$). Thus, two sums have the same reminder, suppose $s_k$ and $s_l$. Thus, $s_l-s_k=a_{k+1}+...+a_l$ can be divisible by $m$.

3. From the integers 1, 2, …, 200, we choose 101 integers. Show that among the integers chosen there are two such that one of them is divisible by the other.

   Any integer can be written in the form $2^k\times a$, where $k\ge 0$ and $a$ is odd. Among 1~200, there are only 100 odd numbers. Thus, there must have two numbers have same $a$ in the chosen 101 integers. Assume they are $2^{k_1}\times a$ and $2^{k_2}\times a$. Therefore, they can be divisible by the other.

4. A bag contains 100 apples, 100 bananas, 100 oranges and 100 pears. How many fruits should be taken out such that we can sure a dozen (12) pieces of them are of the same kind?

According to Pigeonhole Principle-Strong Form, the answer is $N=12+12+12+12-4+1=45$.

5. A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number of pieces of fruits that should be put in the basket in order to guarantee that either there are at least 8 apples or at least 6 bananas or at least 9 oranges?

   According to Pigeonhole Principle-Strong Form, the answer is $N=8+6+9-3+1=21$.

6. There are 100 people at a party. Each people has an even number of acquaintances. Prove that there are three people at the party with the same number of acquaintances. (it is assumed that no one is acquainted with him or herself.)

   Similar to example 1. However, one can only know 2,…, 98 persons (i.e., 49 cases in total). Thus, there are at least $\lceil 100/49\rceil =3$ people at the party with the same number of acquaintances.

1.3 Ramsey

• R(m, n): Either there are $m$, each pair of whom are acquainted, or there are $n$, each pair of whom are unacquainted. The Ramsey number is the smallest integer.

• Proof of R(3,3) = 6

  We argue as follows: Suppose the edges of K6 have been colored red or blue in any way. Consider one of the points p of K6. It meets five edges. Since each of these five edges is colored red or blue, it follows (from the strong form of the pigeonhole principle) that either at least three of them are colored red or at least three of them are colored blue. We suppose that three of the five edges meeting the point p are red. (If three are blue, a similar argument works.) Let the three red edges meeting p join p to points a, b, and c, respectively. Consider the edges which join a, b, c in pairs. If all of these are blue, then a, b, c determine a blue K3. If one of them, say the one joining a and b, is red, then p, a, b determine a red K3. Thus, we are guaranteed either a red K3 or a blue K3.

2. Permutations and combinations

• r-permutation: $P(n,r)$
• r-combinations: $C(n,r)$
• infinite multiset r-combinations (k types): $C(n+k-1,k-1)$
• infinite multiset r-permutations (k types): $k^r$
• finite multiset (repletion) r-combinations: Using IEP.

3. Generating Permutations and Combinations

3.1 Generating Permutations

• Mobile Integer

  Given $\overrightarrow{2}\overrightarrow{6}\overrightarrow{3}\overrightarrow{1}\overrightarrow{5}\overrightarrow{4}$. 6, 3, 5 are mobile integers

• Algorithm
  

• Example
  

3.2 Inversion in Permutations

• Inversion Numbers
  Given 51234. Pairs (5, 1), (5, 2), (5, 3), (5, 4) are inversions. Thus, 1, 1, 1, 1, 0 is the inversion sequence.
• Generating permutations according to inversion sequence.
  • Algorithm 1. Write n, n-1, … 1. (Disadvantage: without location information)
  • Algorithm 2. Write 1, …, n

3.3 Generating Combinations

Base-2 algorithm, i.e., Binary Addition Method.

3.4 Generating r-combinations

• A precedes B: the smallest integer which is in their union A∪B but not in their intersection A ∩ B is in A

• Algorithm

• Example
  

4. The Inclusion-Exclusion Principle and Applications (容斥原理)

4.1 IEP Conceptions

4.2 Derangement

• Definition: the numbers are out of its natural position.

• Equations:
  

4.3 Chessboard Polynomial (棋盘多项式)

• Basics

$$R(C)=xR(C_i)+R(C_e)$$

• Example

5. Recurrence Relations and Generating Functions

• For Combinations: $(1+x+x^2+...)(1+x+x^2+...)(1+x+x^2+...)$
• For Permutations: $(1+x+x^2/n^2+...)(1+x+x^2/n^2+...)(1+x+x^2/n^2+...)$

6. Special Counting Sequences

6.1 Catalan Number

• Catalan Number: $Ca{t}_n=\frac{1}{n+1}{C}_{2n}^n$
• Meanings: The number of sequences $a_1,a_2,\dots ,a_{2n}$ of $2n$ terms that can be formed by using $n$ $+1$’s and $n$ $-1$’s whose partial sums satisfy $a_1+a_2+\dots +a_k\ge 0,(k=1,2,\dots ,2n)$ equals the $n$th Catalan number $Ca{t}_n$.
• Recurrence relation: $\frac{Ca{t}_n}{Ca{t}_{n-1}}=\frac{4n-2}{n+1}$
• Pseudo-Catalan Number: $C_n^{\ast }=n!C_{n-1}$

6.2 Difference sequences and Stirling numbers

6.2.1 Difference Sequences

• $h_n=c_{0}C(n,0)+c_{1}C(n,1)+...+c_{p}C(n,p)$, where $c_i$ is the 0th diagonal of the difference table.
• ${\sum }_{k=0}^n{h}_k=c_{0}C(n+1,1)+c_{1}C(n+1,2)+...+c_{p}C(n+1,p+1)$

6.2.2 Stirling number of the second kind

• Definition: Let $h_n=n^p$, the 0th diagonal of its difference table is $c(p,0)$,$c(p,1)$…$c(p,p)$. Then, $S(p,k)=\frac{c(p,k)}{k!}$
• Recurrence: $S(p,k)=kS(p-1,k)+S(p-1,k-1)$
• The Stirling number of the second kind $S(p,k)$ counts the number of partitions of a set of p elements into k indistinguishable boxes in which no box is empty

6.2.3 Partition Number $S^{sharp}(p,k)$

• $S^{sharp}(s,p)=k!S(p,k)$.
• Similar to 2th Stirling Number but with distinguishable boxes.

6.2.4 Bell Number

• $B_p=S(p,0)+S(p,1)+...+S(p,p)$
• The Bell number $B_p$ is the number of partitions of a set of p elements into non-empty, indistinguishable boxes. (The number of the box is not clarified).

6.2.5 Stirling Number of the first kind

• The Stirling number $s(p,k)$ of the first kind counts the number of arrangements of p objects into k non-empty circular permutations.
• Recurrence: $s(p,k)=(p-1)s(p-1,k)+s(p-1,k-1)$

6.3 Partition Number

• Definition

• Calculation: using generating functions to calculate. Since $\lambda =a_n\ast n+...+a_1\ast 1$. Let $f_1=a_1\ast 1$, … $f_n=a_n\ast n$. Thus, $f_n$ is multiply of $n$. That is to say:
  $$g(x)=(1+x+x^2+...)(1+x^2+x^4+...)...(1+x^n+x^{2n}+...)={\Pi }_{k=1}^n\frac{1}{1-x^k}$$

7. Matchings in bipartite graphs

7.1 Bipartite Graph

• Matching: A matching in a graph G is a set of non-loop edges with no shared endpoints
• Maximal Matching: A maximal matching in a graph is a matching that cannot enlarged by adding an edge.
• Maximum Matching: A maximum-matching is a matching of maximum size among all matchings in the graph.
• M-Saturated Vertices: The vertices incident to the edges of a matching M (匹配M中的点).
• M-Unsaturated Vertices: The vertices which are not saturated by M (匹配M外的点).
• M-Alternating Path: Given a matching M, and an M-Alternating path is a path that alternates between edges in M and edges not in M (M中的边和非M中的边交错).
• M-Augmenting Path: An M-Alternating path whose endpoints are unsaturated by M (交织路径但端点是非饱和点).
• A Matching M is a Max-Matching in G iff G has no M-Augmenting path (最大匹配当且仅当图G中没有增广路径).
• Vertex Cover: A vertex cover of a graph G is a set $S\subseteq V(G)$ that contains at least one endpoint of every edge (点覆盖了所有边).
• Min-Cover: A cover with the smallest number of vertices.
• The number of edges in Max-Matching $\le$ The number of vertices in Min-Cover.
• Max-Matching Algorithm: Scan and Label.

Theorems

• Hall’s Theorem: An $X,Y$-bigraph G has a matching that saturates X iff $|N(S)|>=|S|$ for all $S\subseteq X$

• The Marriage Theorem: An $X,Y$-bigraph G with $|X|=|Y|$ has a perfect matching iff $|N(S)|>=|S|$ for all $S\subseteq X$.

  Perfect matching is a matching M such that all the vertices in G are saturated.

• Konig Theorem: If G is a bipartiite graph, then the maximum size of a matching in G equals to the minimum size of a vertex cover in G (二部图最大匹配与最小顶点覆盖数相同).

7.2 Systems of Distinct Representatives (SDR)

• Definitions

  Choose distinct representatives from given groups.

• How to calculate the largest number of sets of A which can be chosen such that they have an SDR

7.3 Stable Marriages (Deferred acceptance algorithm)

Women-Optimal Stable Marriages is equivalent to Men-Optimal Stable Marriages.

8. Combinatorial designs

8.1 Basics

• Parameters

  $b$	分组块数
  $v$	属性数
  $k$	每个分组中的属性数
  $r$	每个属性存在$r$个分组中
  $\lambda$	每对属性存在$\lambda$个分组中

• BIBD (Balanced Incomplete Block Design)

  • $b\ge v$
  • $r=\lambda (v-1)/(k-1)$
  • $\lambda <r$
  • $bk=vr$

• SBIBD (Symmetry Balanced Incomplete Block Design): $b=v$

8.2 Difference set mod $v$ and Starter Block

8.3 Steiner Triple Systems

• Definition: BIBD with $k=3$.

• Important Theorem: If there are Steiner triple systems of index $\lambda =1$ with $v$ and $w$ varieties, respectively, then there is a Steiner triple system of index $\lambda =1$ with $vw$ varieties.

  • Row. Row elements are in $B_2$.
  • Column. Column elements are in $B_1$.
  • Cross. Cross elements are in both $B_1$ and $B_2$.

• Resolvability Class/Resolvable. The Steiner Triple System is Resolvable while each part is called a resolvability class.

8.4 Latin Squares

8.4.1 Basics

• Definition: Each of the rows and each of the columns of a Latin square is a permutation of the elements of S.

• Partitions

• Properties of Latin Squares (How to judge a Latin Sqaure)

• Orthogonal: In the juxtaposed array $A\times B$ (see above), each of the ordered pairs $(i,j)$ of integers in $Z_n$ occurs exactly once.

• MOLS (Mutually Orthogonal Latin Squares): $A_1,A_2,...,A_k$ are Latin squares of order $n$, each pair $(A_i,A_j)$ is orthogonal.

• The Largest Number of MOLS is denoted as $N(n)$ (where the Latin squares all of order $n$).

• Latin Rectangle: Let $m$ and $n$ be integers with $m\le n$. An $m$-by-$n$ Latin rectangle, based on the integers in $Z_n$, is an $m$-by-$n$ array such that no integers is repeated in any row or in any column.

• Semi-Latin Square: Latin Square with many “holes”.

8.4.2 Constructing Latin squares

• Addition mod n

• Multiplicative Inverse

• Field Arithmetic

8.4.3 Important Theorems

• Let $n$ be a prime number. Then $L_n^1,L_n^2,\dots ,L_n^{n-1}$ are $n-1$ MOLS of order $n$.
• Let $n=p^k$ be an integer and $p$ is a prime number. Then $L_n^{a_1},L_n^{a_2},\dots ,L_n^{a_{n-1}}$ are $n-1$ MOLS of order $n$.

8.4.4 Construction of BIBD with MOLS

• Key Idea: using $n-1$ MOLS of order $n$ with $R_n$, $S_n$ to construct a block design with parameters: ① $v=n^2$ ② $k=n$ ③ $\lambda =1$ ④ $r=n+1$ ⑤ $b=n^2+n$

• Algorithm (① list the table with $v$ items ② find the group by the following array: $R_n,S_n,A_i$)

8.4.6 Completion of Latin Squares

Using Bi-graph and perfect matching to complete Latin Rectangle (Since it is a K-regular graph, perfect matching must exist).

• Latin Rectangle (X is row, Y is missing number)

  

• Semi-Latin Square (X is row, Y is missing column)

9. Ploya Counting

9.1 Group Basics

• Permutation Group

  • Closure under composition (置换加法封闭)
  • Identity (有恒等置换)
  • Closure under inverse (置换都有逆元)

  $G=\{l\}$ is a permutation group.

• Symmetric Group

  • The set $S_n$ of all permutations of $X=\{1,2,\dots ,n\}$ is a permutation group, called the symmetric group of order $n$.

• Dihedral Group (二面体群)

  A Group with order $2n$ consisting of $n$ Rotations and $n$ Reflections.

9.2 Burnside’s Theorem

• Stabilizer: $G(c)=\{f:finG,f\ast c=c\}$, 即所有让染色$c$不变的置换；$C(f)=\{c:cinG,f\ast c=c\}$，即所有在置换$f$下保持不变的染色方案

• Theorem: For each coloring $c$, the stabilizer $G(c)$ of $c$ is a permutation group. Moreover, for any permutations $f$ and $g$ in $G$, $g\ast c=f\ast c$ if and only if $f^{-1}g$ is in $G(c)$.

• Corollary: 所有与c相同的着色方案为$|G|/|G(c)|$个

• Burnside Theorem

  $\sum |C(f)|=\sum |G(c)|$ and using the Corollary

9.3 Polya’s counting formula

• Factorization, see below:

  

• #$(f)$ is the number of cycles in the cycle factorization of a permutation f. In the above example, #$(f)=3$.

• Type of a permutation

  

• Generating Function: $\sum mon(f)=\sum z_1^{e_1}{z}_2^{e_2}...z_n^{e_n}$

• Cycle Index: Generating function divided by $|G|$, i.e.,
  $$P_G(z_1,z_2,...,z_n)=\frac{1}{|G|}\sum z_1^{e_1}{z}_2^{e_2}...z_n^{e_n}$$

• $|N(G,C)|=P_G(k,k,...,k)$

• Playa Counting

  
  

22年真题回顾

第一部分：填空题（无需写出详细过程，30分）

顺序记不太清了，以下不分先后

1. 用1、2、3、4、5组成4个数字的偶数共多少种方法？
2. 非负整数解问题，类似$e1+e2+e3+e4=n$，对$ei$有限制
3. $\{1,2,3,4,5,6\}$排序，逆序数为14的排序数有几个？（最大为15，654321，相邻两两交换即为所求）
4. Forbidden Chessboard问题
5. ${\sum }_{k=0}^n{k}^4=?$（差分序列部分公式Difference Sequence）
6. 填充Latin Rectangle矩阵（二部图匹配）
7. $\{1,2,3,4,5,6\}$找4组合中1356的位置
8. 递归关系问题：类似用三种颜色图1-n的棋盘，然后两个红色不能连续
9. $\{1,2,3,...,3n\}$里选多少个数能够保证一定有两个数的差最多为2（鸽巢原理）
10. $f\ast c$问题

第二部分：问答题（70分，1、2题5分，剩下各10分）

1. 判断数字是否有乘法逆元并求其逆元（GCD(p,n)=1）
2. 鸽巢原理：等边三角形，放入$m$个点，问$m$至少为多少时一定有两个点间距最大为1/2（等分成4个部分，m=5）
3. 证明:
   $$k^n=C(k,1)\ast 1!\ast S(n,1)+C(k,2)\ast 2!\ast S(n,2)+...+C(k,n)\ast n!\ast S(n,n)$$
   （思路：左边是把n个元素放到k个可区分盒子中，盒子可空的方法数；右边是1个盒子不空、2个盒子不空……n个盒子不空的方法数之和，显然二者等价）
4. 根据生成函数求$h_n$:
   $$(x+x^2+...+x^5)(1+x+x^2+...+x^7)(x^4+x^5+...+x^8)(x^2+x^3+...+x^6)$$
5. 1-by-n的棋盘，涂四种颜色，红色为奇数，求$h_n$（指数生成函数套路）
6. 求最大匹配与最小点覆盖
7. 组合设计问题，根据MOLS生成BIBD，n=5
8. 正方体着色问题，利用Playa公式计算