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. Homework Tutorial
2. generating function
3. using generating function to solve problems
4. group theory
5. permutation group
6. Burnside's lemma
7. Polya's enumeration theorem
8. Polya's enumeration theorem under generating functions
9. using Polya's enumeration theorem to solve problems
10. Homework

Part 1 — Homework tutorial

Task 1

Solution: $$$a_{n}=\frac{1}{\sqrt{56953}}\left(\left(\frac{233+\sqrt{56953}}{2}\right)^{n}-\left(\frac{233-\sqrt{56953}}{2}\right)^{n}\right)$$$.

Prove it by yourselves, it's simple after reading last blog.

When you modulus $$$10^9+7$$$, $$$\sqrt{56953}\equiv188305837$$$. Proof: $$$188305837\times 188305837 \equiv 56953\pmod {10^9+7}$$$.

Then you can solve it with quick power in $$$\mathcal O(T\log n)$$$, but this is not quick enough. You can make a table of $$$\left(\left(\frac{233+\sqrt{56953}}{2}\right)^{n}-\left(\frac{233-\sqrt{56953}}{2}\right)^{n}\right)$$$, and you'll find that there exists a shorter cycle than $$$10^9+6$$$.

Note: If you are clever enough, then you'll find the Fermat's little theorem tells about $$$[a^1,a^2,a^3,\dots]\pmod {p}$$$ is actually cyclic, but here the cycle is shorter than $$$p-1$$$ and a factor of $$$p-1$$$.

Try yourselves on the length of cycle, I can tell you that it's shorter than $$$10^6$$$ so you can prework it out and for each query, you can do it in $$$\mathcal O(1)$$$ time.

Matrix quick power can be too slow sometimes.

Task 2

We discussed $$$k=2$$$ occation last time, than we let the polynomial $$$F(x)=0$$$ makes the characteristic equation. Then according to the fundamental theorem of algebra, it has $$$k$$$ solutions $$$\alpha_1,\alpha_2,\dots,\alpha_k$$$ which fits $$$\forall \alpha_i \in \mathbb R$$$. Then we can do it just as what we've done in last blog. If you really, really need a stricter proof, I'll try to write it when I'm free.

Task 3

This is not a linear constant coefficient homogeneous recurrence relation, but it's really trivial that it's $$$2^n-1$$$, since it's just the solution to the Hanoi tower.

Task 4

Task 4

Solve an−6an−1+8an−2=0,a0=x,a1=y

.

Task 5

Solve an=9an−2,a0=x,a1=y

.

Task 6

Solve an+14an−1+49an−2=0,a0=x,a1=y

.

Task 7

n men are writing letters to their wives, but the postman's sent it wrongly. Though each wife receives a letter, but only k

of them receives the right one from their husbands. How many possible versions of the derangement are there?

1≤k≤n≤106

.

Task 8

We have a regular n -sided polygon with vertex 1,2,3…,n. Now you will divide in into n−2 triangles after drawing n−3 non-intersected diagonal, how many different ways are there to complete this division? For example, when n=4,ans=2;n=5,ans=5

.

1≤n≤107

.

Task 9

There are 2n dots which are regularly distributed on a circle. Now we divide the 2n dots into n

pairs of dots. In a pair, join the two dots. No segments are intersected inside the circle. How many different ways are there to divide the dots?

1≤n≤107

.

Task 10

2n people are going to watch a film which needs a 5-dollar-ticket. n people take a 5 dollar note, and the others take a 10 dollar note. Now they are going to buy the tickets at the ticket office, however, the ticket office has no change at first. Everyone will pay strictly 5 dollar to watch the film. How many different orders of the 2n people are there to make everyone pay strictly 5

dollar to watch the film?

1≤n≤107 .