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 second 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. 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 — 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.

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