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 third 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)
• Combinatorics (2)

Content

1. Homework Tutorial
2. Catalan Sequence
3. Stirling Number
4. Derangement
5. Linear constant coefficient homogeneous recurrence relation
6. homework

Part 0 — Pre-knowledge

In order not to make this blog too long (it's already very long now xD), I won't explain these things anymore. You can find them on wikis or google them.

• What Combinatorics (1)(2) mentioned.
• CP basics.
• Reading simple C++ code.

Part 1 — Homework Tutorial

Task A

The first task of it can be solved with two quick powers in $$$\mathcal O(\log{(n+k)})$$$ time.

The second task can be solved with combination initiation, $$$inv[i]$$$ initiation mentioned in Task C in $$$\mathcal O(n)$$$ time.

Task B

Let's define $$$z$$$ the number of the $$$0$$$s in the array, $$$p$$$ the number of the positive elements in the array, $$$m$$$ the number of the negative elements in the array.

When the product is $$$0$$$, we have to choose at least one $$$0$$$. You may find it difficult to solve it directly, let's reduce the invalid subsets' count, which contains no $$$0$$$. So the count is $$$2^{n-z}$$$. The whole count is $$$2^n$$$, the answer is $$$2^n-2^{n-z}$$$ which can be solved in $$$\mathcal O(\log n)$$$ time.

When the product is positive, we have to choose $$$2i$$$ negative numbers. So we can enumerate the count of the negative numbers and calculate the answer. Notice that $$$2i\in[0,n]$$$. First, we can choose any subset of the set of positive numbers. So the answer is:

When the product is negative, we have to choose $$$2i+1$$$ negative numbers. So we can enumerate the count of the negative numbers and calculate the answer. Notice that $$$2i+1\in[0,n]$$$. First, we can choose any subset of the set of positive numbers. So the answer is:

All above can be solved in $$$\mathcal O(n)$$$ time.

const int mod = 1000000007, N = 20005;
int pw(int a,int b,int p=mod){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
int fac[N], ifac[N];
void init() {
	ifac[0] = fac[0] = 1;
	for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
	ifac[N - 1] = pw(fac[N - 1], mod - 2);
	for(int i = N - 2; i; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
int binom(int n, int m) {
	if(n < 0 || n < m || m < 0) return 0;
	return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
 
int solve() {
	int n = getInt();
	init();
	vector<int> a(n);
	int po = 0, ze = 0, ne = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		po += (a[i] > 0);
		ze += (a[i] == 0);
		ne += (a[i] < 0);
	}
	int x = -1;
	for(int i = 0; i <= ne; i += 2) {
		x = (x + binom(ne, i) * pw(2, po) % mod) % mod;
	}
	cout << (x + mod) % mod << ' ';
	x = 0;
	for(int i = 1; i <= ne; i += 2) {
		x = (x + binom(ne, i) * pw(2, po) % mod) % mod;
	}
	cout << x << ' ';
	cout << (pw(2, n) - pw(2, n - ze) + mod) % mod << endl;
	return 0;
}

Task C

There are two ways.

The first way: After the prework of $$$fac[]$$$ and $$$ifac[]$$$, $$$inv[i]=fac[i-1]\times ifac[i]$$$. The proof is simple: $$$\frac{(i-1)!}{i!}=\frac{1}{i}$$$.

The second way: First show you the code:

void init() {
	inv[0] = inv[1] = 1;
	for(int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

So:

Proof:

Since $$$a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b$$$, so:

Then:

Since $$$pi\equiv 0\pmod p$$$, we've got proved.

This takes $$$\mathcal O(n)$$$ time too, but less memory.

Task D

This is Catalan sequence, so let's go to the second part first and discuss it later.

Part 2 — Catalan Sequence

First Task D can be solved with dp, we define $$$f_{n}$$$ as the answer. Then:

This can be solved in $$$\mathcal O(n^2)$$$ time. But it's too slow, let's optimize it:

Proof:

Since $$$f_2=1$$$, then:

Then we let $$$f'_{n+1}=nf_{n+1}$$$

Then

So

Since $$$f'_2=f_2=1$$$

Then

Reduce of the fraction, then $$$f'_{n+1}=\dbinom{2n-2}{n-1}$$$

So

At last, $$$f_n=\dfrac{1}{n+1}\dbinom{2n}{n}$$$

This can be solved in $$$\mathcal O(2n)=\mathcal O(n)$$$ time, maybe a little bit slow.

Also we have another formula, and can be initiated in $$$\mathcal O(n)$$$ time:

Since the combination can be solved in $$$\mathcal O(n)$$$ time, and $$$\frac{1}{n+1}$$$ is exactly $$$inv[n+1]$$$ which can be initiated in $$$\mathcal O(n)$$$ time too.

This sequence $$$f$$$ is noted as Catalan sequence. Usually $$$H_n$$$ or $$$C_n$$$ denoted to it.

There are many more problems with can be solved with Catalan sequence, and it'll be put in the homework part.

Part 3 — Stirling Number

We note $$$S(n,k)$$$ as the different ways to cut $$$n$$$ different elements into $$$k$$$ undifferentiated non-empty subsets. For example, $$$S(5,3)$$$ denotes to:

So $$$S(5,3)=25$$$. Why isn't $$$[5,3][1][4,2]$$$ counted? Because it's the same as $$$[1][2,4][3,5]$$$.

Then we can find it expressed by a dp way:

Here we give out another way to express it without proof, since it is in need of binomial inversion:

$$$S(n,k)=\sum_{i=0}^{k} \frac{(-1)^{k-i} i^{n}}{i !(k-i) !}$$$

If you are interested in it, maybe you can start with the inclusion-exclusion principle.

Part 4 — Derangement

How many permutations $$$p$$$ of $$$1,2,3,\dots,n$$$ are there fits $$$\forall p_{i}\not=i$$$?

For example when $$$n=3$$$ the answer is $$$2$$$, since $$$[2,3,1][3,1,2]$$$ are valid, no $$$p_i=i$$$ occurs.

This problem can be also solved with dp, we define $$$D_n$$$ the answer.

Then there are two conditions:

• $$$p_{1...n-1}$$$ is already a derangement. Then if $$$p_n=n$$$, it's bad. So we can swap $$$p_n$$$ and any $$$i$$$ which fits $$$1\leq i\leq n-1$$$. Then it's trivial that $$$p$$$ is a derangement. There are $$$(n-1)\times D_{n-1}$$$ ways.
• $$$p_{1...n-1}$$$ has only one $$$i$$$ which fits $$$p_i=i$$$, then swap $$$p_n$$$ and $$$p_i$$$. Since this $$$i$$$ can be between $$$1$$$ and $$$n-1$$$, so there are $$$(n-1)\times D_{n-2}$$$ ways.

There are no more conditions to decide $$$d_n$$$ in strictly one operation to make $$$p$$$ a derangement.

So we have $$$D_n=(n-1)\times (D_{n-1}+D_{n-2})$$$.

Part 5 — Linear constant coefficient homogeneous recurrence relation

Defination:

If $$$c_1,c_2,\dots,c_k,d_1,d_2,\dots,d_k$$$ are constants, we call $$$(*)$$$ a linear constant coefficient homogeneous recurrence relation.

And we can always solve it to get the general term formula. Proof is in the homework, and I'll prove it in the next blog (or the blog will be too long). Let's go to some examples when $$$k=2$$$. ($$$k\leq 1$$$ is too easy for us to discuss)

For example:

The fibonacci array $$$F_n$$$:

How to easilize it?

Characteristic equation: $$$x^2-x-1=0$$$, Solution: $$$\alpha = \dfrac{1+\sqrt5}{2},\beta = \dfrac{1-\sqrt5}{2}$$$

$$$P(x)$$$ is a linear polynomial. Let it be $$$ax+b$$$.

We can grasp $$$2$$$ special value of the array.

$$$F_0=A+B=0,F_1=A\alpha+B\beta=1.$$$

So

$$$\begin{cases}A+B=0\ A-B=\dfrac{2}{\sqrt5}\end{cases}$$$

Solution: $$$(A,B)=(\dfrac{1}{\sqrt5},-\dfrac{1}{\sqrt5})$$$.

So $$$F_n=\dfrac{\alpha^n-\beta^n}{\sqrt5}$$$.

What if the Characteristic equation turns out to have same solutions?

The array: $$$a_n-4a_{n-1}+4a_{n-2}=0,a_0=1,a_1=4$$$.

Characteristic equation: $$$(x-2)^2=0$$$, Solution $$$x_1=x_2=2$$$.

So:

We can grasp $$$2$$$ special value of the array.

$$$a_0=C=1,a_1=2(1+B)=4.$$$

So $$$B=1$$$.

Solution: $$$a_n=(1+n)2^n$$$.

What if the characteristic equation turns out to have imaginary solutions?

$$$a_n=a_{n-1}-a_{n-2},a_1=a_0=1$$$.

Since $$$a_n-a_{n-1}+a_{n-2}=0$$$, characteristic equation: $$$x^2-x+1=0$$$.

Solution: $$$\alpha=\dfrac 12+\dfrac{\sqrt3i}{2},\beta=\dfrac 12-\dfrac{\sqrt3i}{2}$$$.

We can grasp $$$2$$$ special value of the array.

$$$a_0=A+B=1,a_1=A\alpha+B\beta=1.$$$

So $$$\begin{cases}A+B=1\ A-B=-\dfrac{i}{\sqrt3}\end{cases}$$$.

Then $$$(A,B)=(\dfrac{1-\frac{i}{\sqrt3}}{2},\dfrac{1+\frac{i}{\sqrt3}}{2})$$$

Or more specifically,

Since $$$e^{ix}=\cos x+i\sin x$$$

Then $$$a_n=\cos \dfrac{n\pi}{3}+\dfrac{1}{\sqrt 3}\sin \dfrac{n\pi}{3}$$$.

Part 6 — Homework

Task 1

Solve $$$a_{n}=233 a_{n-1}+666 a_{n-2}, a_{0}=0, a_{1}=1$$$ modulus $$$10^9+7$$$ with $$$T$$$ queries of $$$n$$$.

$$$1\leq n\leq10^9, 1\leq T\leq 5\cdot 10^7$$$.

Task 2

Prove: We can always solve a linear constant coefficient homogeneous recurrence relation to get the general term formula.

Task 3

Solve $$$a_n=2a_{n-1}+1, a_1=1$$$.

Task 4

Solve $$$a_n-6a_{n-1}+8a_{n-2}=0, a_0=x,a_1=y$$$.

Task 5

Solve $$$a_n=9a_{n-2}, a_0=x,a_1=y$$$.

Task 6

Solve $$$a_n+14_a{n-1}+49a_{n-2}=0,a_0=x,a_1=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\leq k\leq n\leq 10^6$$$.

Task 8

We have a regular $$$n$$$-sided polygon with vertex $$$1,2,3\dots,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\leq n\leq 10^7$$$.

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\leq n\leq 10^7$$$.

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\leq n\leq 10^7$$$.

At last

The third blog is completed, it discussed the sequences and recurrence relations. Next blog we will discuss things about recurrence relations and generating functions. If you are puzzled with something in the text, you can comment under the blog!

It really takes time, please, give your valuable comments and advise!

Thanks for reading! This series will be written on.

Last but not least: Happy new year!

Also, thanks to the book Combinatorics (Fifth version, Tsinghua University publishing house co., ltd).