Hello Codeforces!

Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing an important role in both Codeforces and CP (short for competitive programming).

However, combinatorics is such a great subject that made that impossible for me to write it all in one blog. So, this is just the fourth blog, which is friendly to beginners. If you are interested, please, pay attention to this account and I'll give posts as series for a long term.

If you have found some mistakes in the text, or if you have some questions about the topic, please, leave a comment, and I'll check it weekly and reply. Also, if you find some grammar mistakes, a kind comment will be also welcomed.

Previous Blogs

• Combinatorics (1), basics.
• Combinatorics (2), implementations.
• Combinatorics (3), arrays and recurrence relations.

Content

1. generating function
2. using generating function to solve problems
3. group theory
4. permutation group
5. Burnside's lemma
6. Polya's enumeration theorem
7. Polya's enumeration theorem under generating functions
8. using Polya's enumeration theorem to solve problems
9. Homework

The homework tutorial will be posted in another blog.

Part 1 — Generating function

How to represent an array $$$a_0,a_1,\dots, a_{n-1}$$$ with a function? Maybe we can use Berlekamp-Massey algorithm to calculate the recurrence relation out.

But it's too complicated. Maybe to be more easy, we can generating a function $$$f(x)=a_0+a_1x^2+\dots+a_{n-1} x^n=\sum_{i=1}^{n}a_{i-1}x^i$$$. For example $$$[1,2,3]$$$'s generating function is $$$3x^2+2x+1$$$.

Wtf? This is really naive isn't it? But you may find that it is meaningless to calculate the value of the function with any possible $$$x$$$.

Don't worry. Here is a task for you:

There are many red and blue tickets. You can choose at most $$$K$$$ red tickets and $$$M$$$ blue tickets only if $$$M$$$ is even. You want to get $$$N$$$ tickets in total. How many different ways are there to do the problem?

We can construct a generating function $$$R(x)$$$ generated with $$$r=[\underbrace{1,1,1,\dots 1}_{\text{n+1 ones}}]$$$, when $$$r_i=1$$$ means you can get $$$i$$$ red tickets.

Also, we can construct a generating function $$$B(x)$$$ generated with $$$b=[1,0,1,0,\dots]$$$, when $$$b_i=1$$$ means you can get $$$i$$$ blue tickets.

Then you can make $$$F(x)=R(x)\times B(x)=\sum\limits_{i=0}^{M}f_ix^i$$$. And $$$f_M$$$ is the answer. Proof is trivial when you do the convolution by yourself, it is same as brute force with $$$\mathcal O(n^2)$$$ complexity.

Under FFT, the time complexity is $$$\mathcal O(n\log n)$$$.

But this is not all what generating functions can do. We have another important property of it: $$$x$$$'s detailed value is useless, so we can give a proper range to it.

What is the generating function of $$$[1,1,1,\dots]$$$?

Answer: $$$\frac{1}{1-x}$$$.

Why??? OK, I have to say $$$1+x+x^2+\dots$$$ is also correct. But why these two are the same? Are you kidding the readers? Actually, we can give the range $$$(-1,1)$$$ to it. Then since $$$1+x+x^2+\dots +x^n=\frac{1-x^n}{1-x}$$$, when $$$x\to \infty$$$, $$$x^n\to 0$$$. Then $$$1-x^n=1$$$, so the answer is $$$\frac{1}{1-x}$$$.

Practice: what is the generating function of $$$[1,0,1,0,1,0,\dots]$$$? What about $$$[1,0,0,1,0,0,\dots]$$$, $$$[1,2,3,4,\dots]$$$ and $$$[1,1+2,1+2+3,1+2+3+4,\dots]$$$?

Try to use special binomial theorem to explain some of and, even more than them. For example what generates $$$\frac{1}{(1-x)^k}$$$. This is homework, proof next time.

Part 2 — using generating function to solve problems

If you want to implement them, you should learn the polynomial theory first.

Codeforces 632E — Thief in a Shop

This is a backpack-dp problem, but can you optimize it?

Construct a generating function $$$f(x)=\sum\limits_{i=1}^{n}x^{a_i}$$$, this is what you can get when you can choose one thing.

Then expand one to $$$\textbf{\textit{k}}$$$，you only need to calculate $$$f^k(x)$$$. Use FFT to reach $$$\mathcal O(n\log n)$$$.

Codeforces 438E — The Child and Binary Tree

Catalan is discussed before, now we construct the generating function for the weights of a single node $$$W(x)=\sum_{i=1}^{n}x^{c_i}$$$.

Additionally, the generating function of Catalan sequence is $$$C=xC^2+1$$$, then we get $$$F^2W-F+1=0$$$. Solve it, we get $$$\dfrac{2}{1-\sqrt{1-4W}}$$$.

Use Newton's method (calculate the square root and inversion) to reach $$$\mathcal O(n\log n)$$$.

Part 3 — Group Theory

What is a group? A group is composed of a set $$$\mathcal S$$$ and a dyadic operation $$$*$$$. A group needs to meet these four rules below:

• Closure: $$$\forall a,b\in\mathcal S,a*b\in\mathcal S$$$.
• Combination: $$$\forall a,b,c\in\mathcal S,(a*b)*c=a*(b*c)$$$.
• identity element occurs: $$$\exists e\in \mathcal S$$$, we have $$$\forall a\in \mathcal S, a*e=a$$$.
• inversion element occurs: $$$\forall a\in\mathcal S, \exists b\in\mathcal S$$$, we have $$$a*b=b*a=e$$$.

Practice: Prove that when $$$\mathcal S={0,1,2\dots,n-1}$$$, $$$*$$$ is addition modulus $$$n$$$.

• Closure: Since $$$a,b\in \mathcal S$$$, we have $$$a,b\in\mathbb N$$$, then $$$(a+b)\bmod n\in\mathcal S$$$.
• Combination: trivial.
• identity element: $$$0$$$.
• inversion element: for all $$$x$$$, since $$$-x\equiv n-x\pmod n$$$, then $$$n-x$$$ is the inversion element of it.

This is simple. You can try to make more examples and prove them.

Part 4 — permutation group

What is a permutation here? It's the similar, but not the same.

We define $$$\begin{pmatrix}1 & 2 & 3 & \dots & n\ p_1 & p_2 & p_3 & \dots & p_n\end{pmatrix}$$$ a permutation when $$$p$$$ is a permutation of $$$1,2,3\dots, n$$$. How does the permutation work? It replaces $$$i$$$ to $$$p_i$$$. For example, $$$(2,1,3,5,4)$$$ will become $$$(1,3,4,2,5)$$$ with $$$\begin{pmatrix}1 & 2 & 3 & 4 & 5\ 3 & 1 & 4 & 2 & 5\end{pmatrix}$$$.

But permuations can be multipled too. Permutations multiply and turn out to be new permutations.

What does it mean? It means doing $$$p_1$$$ and then $$$p_2$$$ on the left is the same to doing the one permutation on the right.

Here pay attention that $$$p_1p_2\not=p_2p_1$$$, but combination exists.

All permutations of length $$$n$$$ obviously make a group $$$\mathcal P_n$$$. This can be easily proved.

• Closure: Any multiplication gets a permutation and it's in $$$\mathcal P_n$$$.
• Combination: trivial.
• identity element: $$$\begin{pmatrix}1 & 2 & 3 & \dots & n\ 1 & 2 & 3 & \dots & n\end{pmatrix}$$$.
• inversion element: $$$\begin{pmatrix}1 & 2 & 3 & \dots & n\ p_1 & p_2 & p_3 & \dots & p_n\end{pmatrix}^{-1}=\begin{pmatrix}p_1 & p_2 & p_3 & \dots & p_n\ 1 & 2 & 3 & \dots & n\end{pmatrix}$$$. Easilize it and you'll get a permutation.

Note that we usually put $$$1\ 2\ 3\ \dots\ n$$$ on the first line, but if you really need to, it doesn't matter if you put another permutaion on the first line. Then it means that $$$a_i$$$ will be changed into $$$b_i$$$, after sorting $$$a$$$ it's actually the same.

Now we define a new way to write out a permutation:

$$$(a_1a_2a_3\dots a_n)=\begin{pmatrix}a_1 & a_2 & a_3 & \dots & a_{n-1} & a_n\ a_2 & a_3 & a_4 & \dots & a_n & a_1\end{pmatrix}$$$

What does it means? From the element $$$a_i$$$, do permutaion for $$$n$$$ times and $$$a_i$$$ will remain the same. This makes a cycle, we can note the cycle. Note that $$$a_n$$$ may not be the completed permutation, because the cycle's size $$$|C|$$$ can be any one in $$$[1,n]\cap \mathbb N$$$. Many cycles make a permutation.

$$$\begin{pmatrix}1 & 2 & 3 & 4 & 5\ 5 & 2 & 3 & 1 & 4\end{pmatrix}=\begin{pmatrix}1 & 5 & 4\end{pmatrix}\big(2\big)\big(3\big)$$$.

$$$(1\ 5\ 4)$$$ cannot be turned into $$$(1\ 4\ 5)$$$ but it can also be $$$(4\ 1\ 5)$$$.

You may find that it's similar to contructing a graph when $$$a_i$$$ and $$$b_i$$$ has an edge when the permutation is $$$\dbinom{a}{b}$$$.

What is this way of expressing permutation used for? Have a look at the problem below:

You have a $15$-puzzle situation, is it reachable from the initial version?

For example:

$$$0$$$ is the empty square. Then, all the swaps together, are the same to this permutations:

And express it with the cycles: $$$\text{(0)(1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8)}$$$

There are $$$9$$$ cycles, while for each swap you do, it always makes even cycles. (Even cycles never multiplies to make an odd-cycles-permutation)

Finally, we can prove that there does not exist a way to reach it.

If you expand $$$4$$$ to $$$n$$$, then we can solve the task in $$$\mathcal O(n^2\alpha(n^2))$$$, while $$$\alpha(n^2)$$$ is the time complexity of DSU, because you can use it to count the cycles.

Part 5 — Burnside's lemma

What's Burnside's lemma? Let's go to wikipedia.

In the following, let $$$G$$$ be a finite group that acts on a set $$$X$$$. For each $$$g$$$ in $$$G$$$ let $$$X_g$$$ denote the set of elements in $$$X$$$ that are fixed by $$$g$$$ (also said to be left invariant by $$$g$$$), i.e. $$$X_g = \lbrace x \in X | g.x = x \rbrace$$$. Burnside's lemma asserts the following formula for the number of orbits (or the cycles), denoted $$$|X/G|$$$:

Formalized lemmas do no help to solving problems. Let's go further.

Warning: many more definitions below, if you've forgotten it, try to find the definitions back.

Note $$$G$$$ as the permutation group we are going to discuss.

In a permutation $$$g\in G$$$, sometimes there exists fixed elements. For example $$$\begin{pmatrix}1 & 2 & 3\ 3 & 2 & 1\end{pmatrix}$$$ has a fixed element $$$2$$$.

Count of the fixed elements in $$$g$$$ are noted as $$$c_1(g)$$$.

For a specific integer $$$k$$$ in $$$[1,n]$$$, then do $$$\forall g\in G$$$ on $$$k$$$. There must exist $$$k$$$ itself, formally $$$g(k)=k$$$. Let the valid $$$g$$$-s make a set $$$Z_k$$$. It is a subset of $$$G$$$. $$$Z_k$$$ is a group too, easily proved.

For a specific integer $$$k$$$ in $$$[1,n]$$$, then let all the permutations act on $$$k$$$. Then we have $$$|G|$$$ answers, let them make a set $$$E_k$$$.

Sublemma: $$$|G|=|Z_k|\cdot |E_k|$$$.

Proof: Let $$$Z_k=\lbrace z_1,z_2,\dots z_{|Z_k|}\rbrace$$$, $$$E_k=\lbrace k_1,k_2,\dots, k_{|E_k|}\rbrace$$$, $$$p=|Z_k|,q=|E_k|$$$.

For a specific $$$k_1\not= k$$$ in $$$E_k$$$, then since there is always $$$g\in G$$$ that meets $$$g(k)=k_1$$$, then $$$g\not\in Z_k$$$.

Let this $$$g$$$ generate a new set $$$Z_{k,k_1}={gz_i,gz_2,\dots,gz_p}$$$. Note that $$$z_ig$$$ may be incorrect, $$$z_ig=gz_i$$$ does not always fits. According to the definition, $$$Z_{k,k_1}\cap Z_{k}=\phi$$$, and $$$|Z_{k,k_1}|=p$$$.

Good. If you are clever enough, you may guess that all $$$g\in G$$$ which fits $$$g(k)=k_1$$$ is in $$$Z_{k,k_1}$$$. Suppose that $$$\exists \hat g\in G$$$ which fits $$$\hat g(k)=k_1$$$, then $$$(g^{-1}\hat g)(k)=(g^{-1}g)(k)=k$$$.

So $$$g^{-1}\hat g\in Z_k$$$. Then let $$$g^{-1}\hat g=z_x$$$, therefore $$$\hat g=gz_i$$$, so $$$\hat g\in Z_{k,k_1}$$$.

Let $$$\mathbb Z_k=\bigcup\limits_{i = 1}^{q - 1} Z_{k,k_i}$$$. Then $$$G=Z_k\cup \mathbb Z$$$. And since no one of them have common elements, just add them together and the answer is $$$pq=|E_k|\cdot|Z_k|$$$.

Burnside Lemma:

Let numbers of different equivalence classes be $$$l$$$.

Proof:

Let $$$\forall g\in G,x\in[1,n]\cap \mathbb N,S(g,x)=\begin{cases}1 & g(x)=x\ 0 & g(x)\not= x\end{cases}$$$.

Then

The equivalence classes make $$$i$$$ equivalence classes' set $$$E_{x_1},E_{x_2},\dots,E_{x_l}$$$, then we have:

According to sublemma1, we have:

Then:

$$$l|G|=c_1(a_1)+c_1(a_2)+c_1(a_3)+\dots +c_1(a_g)$$$

Finally, WE GOT PROVED.