[Educational] Combinatorics Study Notes (4)

Revision en4, by Black_Fate, 2023-01-05 17:23:42

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

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 to reach $$$\mathcal O(n\log n)$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English Black_Fate 2023-01-08 04:42:59 9
en9 English Black_Fate 2023-01-07 19:15:11 1 (published)
en8 English Black_Fate 2023-01-07 19:14:46 1856
en7 English Black_Fate 2023-01-07 18:49:03 5231
en6 English Black_Fate 2023-01-06 18:06:01 3200
en5 English Black_Fate 2023-01-06 05:47:26 4769
en4 English Black_Fate 2023-01-05 17:23:42 7107
en3 English Black_Fate 2023-01-03 17:30:58 3143
en2 English Black_Fate 2023-01-03 09:06:08 1397
en1 English Black_Fate 2023-01-01 16:30:56 154 Initial revision (saved to drafts)