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. solution to some problems left in the blog

The homework tutorial and homework this time will be posted in another blog, or it'll be TOO long.

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}$$$.

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 $$$\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.

Part 6 — Polya's enumeration theorem

Let $$$\overline G$$$ be the permutation group of $$$n$$$ elements, color the $$$n$$$ elements with $$$m$$$ colors. Let $$$c(a_k)$$$ be the length of the cycle to permute $$$a_k$$$, Then different ways of coloring is:

$$$\overline a_i$$$ are elements of $$$\overline G$$$.

Proof:

Don't be afraid, based upon Burnside's lemma it's easy.

Suppose all ways instead of considering permutations to color, let the set be $$$S$$$ and according to multiplication principle $$$|S|=m^n$$$.

Then we find that every element of $$$\overline G$$$ represents a permutation of $$$n$$$ elements, and also represents permutations of ways to color the elements $$$\hat a_j$$$ and all of $$$\hat a$$$ make a set $$$\hat G$$$. Since the one-to-one correspondence, $$$|\overline G|=|\hat G|$$$, so $$$c_1(\hat a_k)=m^{c(\overline a_k)}$$$. According to Burnside's lemma:

Similar to Burnside, isn't it? Sometimes we do not seperate them.

Part 7 — Polya's enumeration theorem under generating functions

Polya's theorem is used to count the ways to color the elements. But why isn't it called Polya's counting theorem? Because it can be used for enumerate the states.

Still from this formula:

Let $$$m^{c(\overline a_i)}$$$ be $$$\prod_{p=1}^{n}(\sum_{i=1}^{m}b_i^p)^{c_p(a_i)}$$$.

Then define a polynomial $$$P(G)$$$:

Part 8 — using Polya's enumeration theorem to solve problems

ABC198F — Cube

Cube rotates. Rotate it, and label the six numbers, permutation comes.

Since the cube has $$$6$$$ numbers to be written and only $$$6$$$, so the permutation group can be written out easily. (If $$$6$$$ expands to $$$N$$$ then it'll be terrible) With Digit DP and Polya's enumeration theorem, we can solve it.

ABC284Ex — Count Unlabeled Graphs

Something's grasped from the offical editorial.

Writing numbers $$$1\sim K$$$ is to paint them in $$$K$$$ colors. This is Polya's theorem for sure. Let $$$G$$$ be the set of all labeled graphs, $$$\overline G$$$ be the set of unlabeled ones.

Unlabeled Graphs are hard to count, count labeled graphs. Let $$$g$$$ be a graph in $$$G$$$. Then the number of labeled graph in $$$G$$$ that is isomorphic up to labels multiplies the number of permutations $$$p$$$ such that $$$p(g)$$$ is isomorphic (as a labeled graph) to $$$g$$$ is $$$N!$$$. Let the expression be $$$X_g\cdot Y_g=N!$$$.

Then using Polya's enumeration theorem, then $$$N!\cdot |\overline G|=\sum\limits_g\dfrac{N}{X_g}=\sum Y$$$. Then:

Finally we can do a dp just as what we did in ABC226F, and we can solve it in polynomial complexity time.

//Author: falsEHood
#include<bits/stdc++.h>
//----------------------------------------------------------------
#define int long long
using namespace std;
//----------------------------------------------------------------
const int N = 62;
int mod, n, k, tot, f[N];
int Gcd[N][N], dp[N * 2][N * 2], pw[N], ans;
int cnt[N], inv[N], fac[N];
int gcd(int n, int m) {
    if(Gcd[n][m]) return Gcd[n][m];
    Gcd[n][m] = __gcd(n, m);
    return Gcd[n][m];
}
void dfs(int x, int y, int ind) {
	if(!y) ans += ind * dp[k][tot] % mod * fac[tot] % mod, ans %= mod;
    for(int i = x; i <= y; i++) {
		f[++tot] = i;
		int mul = ind * inv[++cnt[i]] % mod * inv[i] % mod * pw[i / 2] % mod;
        for(int j = 1; j < tot; j++) mul = mul * pw[gcd(f[j],i)] % mod;
		dfs(i, y - i, mul); --cnt[i], --tot;
	}
}
void init() {
    fac[0] = inv[1] = pw[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod, pw[i] = pw[i - 1] * 2 % mod;
	for(int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}
void DP() {
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 1, mul = dp[i - 1][j]; k + j <= n; k++) mul = mul * inv[k] % mod, dp[i][j + k] += mul, dp[i][j + k] %= mod;
}
//----------------------------------------------------------------
signed main() {
    cin >> n >> k >> mod;
    init(); DP();
	dfs(1, n, 1);
    cout << ans << endl;
	return 0;
}

Explaination: $$$\text{gcd}[\bf n][m]$$$ is memorized because of the recalculate may lead to TLE. (I've not tried on Atcoder yet, but I've met a similar problem that will be mentioned in the homework which made me TLE without doing GCD like this)

Part 9 — solution to some problems left in the blog

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]$$$?

1. $$$[1,0,1,0,1,0,\dots]$$$

Not very difficult. Generating function: $$$1+x^2+x^4+x^6+\dots$$$ and what's this? Interesting! Replace $$$x$$$ with $$$x$$$ in $$$1+x+x^2+x^3+\dots$$$ and you will find these two the same. Then since $$$1+x+x^2+x^3+\dots=\dfrac{1}{1-x^2}$$$.

1. $$$[1,2,3,4\dots]$$$

A little bit difficult. You can do derivation, but here we just give out the solution: $$$\dfrac{1}{(1-x)^2}$$$. Why? Try to multiply two $$$1+x+x^2+x^3+\dots$$$ together, then you'll find the two ways to express the generating function $$$1+x+x^2+x^3+\dots$$$ is changed into the generating function of $$$[1,2,3,4\dots]$$$ and it's equal to $$$\Big(\dfrac{1}{1-x}\Big)^2$$$.

1. $$$[1,3,6,10,\dots]$$$

The same, do derivation. But too complicated. Multiplpy $$$1+x+x^2+x^3+\dots$$$ for $$$3$$$ times. Then what will you get? You will get $$$1+3x+6x^2+10x^3+\dots$$$, try it by yourself. Then it's $$$\dfrac{1}{(1-x)^3}$$$ remains non difficulty to be proved.

1. What generates $$$\dfrac{1}{(1-x)^k}$$$?

With the 2 problems discussed above, then it's not hard to get that $$$\sum_{i}^{\infty} C_{i+k-1}^{k-1} x^{i}$$$, or to say $$$[\binom{k-1}{k-1},\binom{k}{k-1},\binom{k+1}{k-1},\dots]$$$ generated it. Just multiply $$$1+x+x^2+x^3+\dots$$$ for $$$k$$$ times. And for each coefficient, it means choosing $$$k-1$$$ elements from $$$i+k-1$$$. There's no doubt that the answer is $$$\sum_{i}^{\infty} C_{i+k-1}^{k-1} x^{i}$$$.

$$$\dfrac{1}{1-x^k}$$$ and $$$\dfrac{1}{(1-x)^k}$$$ are two important generating functions. Try to do some problems for homework.