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)](https://codeforces.net/blog/entry/110376), basics.↵
- [Combinatorics (2)](https://codeforces.net/blog/entry/110390), implementations.↵
- [Combinatorics (3)](https://codeforces.net/blog/entry/110799), 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](https://codeforces.net/problemset/problem/632/E)↵
↵
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](https://codeforces.net/problemset/problem/438/E)↵
↵
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. ↵
↵
$$\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 1 & 4 & 2 & 5\end{pmatrix}\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 4 & 2 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 1 & 4 & 2 & 5\end{pmatrix}\begin{pmatrix}3 & 1 & 4 & 2 & 5\\ 1 & 4 & 3 & 2 & 5\end{pmatrix}=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 1 & 4 & 3 & 2 & 5\end{pmatrix}$$↵
↵
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](https://en.wikipedia.org/wiki/15_puzzle) situation, is it reachable from the initial version?↵
↵
For example:↵
↵
$$\begin{bmatrix}15 & 14 & 13 & 12\\ 11 & 10 & 9 & 8 \\ 7 & 6 & 5 & 4\\ 3 & 2 & 1 & 0 \end{bmatrix}$$↵
↵
$0$ is the empty square. Then, all the swaps together, are the same to this permutations:↵
↵
$$\begin{pmatrix}0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15\\ 0 & 15 &14 &13 &12 &11 &10 &9 &8 &7 &6 &5 &4 &3 &2 &1\end{pmatrix}$$↵
↵
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|$:↵
> $$|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^{g}\right|$$↵
↵
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$.↵
↵
$$\displaystyle l=\dfrac{c_1(a_1)+c_1(a_2)+c_1(a_3)+\dots +c_1(a_g)}{|G|}$$↵
↵
**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↵
↵
$$\displaystyle\sum\limits_{i=1}^{g}c_1(a_i)=\sum\limits_{i=1}^{g}\sum\limits_{x=1}^{n} S(a_i,x)=\sum\limits_{x=1}^{n}|Z_x|$$↵
↵
The equivalence classes make $i$ equivalence classes' set $E_{x_1},E_{x_2},\dots,E_{x_l}$, then we have:↵
↵
$$\displaystyle\sum\limits_{x=1}^{n}|Z_x|=\sum_{i=1}^{l}\sum_{x\in E_{x_i}}|Z_x|$$↵
↵
According to **sublemma1**, we have:↵
↵
$$\displaystyle \sum_{i=1}^{l}\sum_{x\in E_{x_i}}|Z_x|=\sum_{i=1}^{l}|E_{x_i}||Z_{x_i}|=\sum_{i=1}^{l}|G|=l|G|$$↵
↵
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:↵
↵
$$\displaystyle l=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
$\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:↵
↵
$$\displaystyle l=\dfrac{1}{|\hat G|}\sum_{k=1}^{g} c_1(\hat a_k)=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
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:↵
↵
$$\displaystyle l=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
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)$:↵
↵
$$\displaystyle P(G)=\dfrac{1}{G}\sum_{i=1}^{g}\prod_{k=1}^{n} s_{k}^{c_k(a_i)}=\dfrac{1}{|G|}$$↵
↵
### Part 8 — using Polya's enumeration theorem to solve problems↵
↵
#### [ABC198F — Cube](https://atcoder.jp/contests/abc198/tasks/abc198_f)↵
↵
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](https://atcoder.jp/contests/abc284/tasks/abc284_h)↵
↵
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:↵
↵
$$|G|=\dfrac{1}{N!}\sum_{k=1}^{g} c_1(\hat a_k)=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
Finally we can do a dp just as what we did in [ABC226F](https://atcoder.jp/contests/abc226/tasks/abc226_f), and we can solve it in polynomial complexity time. ↵
↵
<spoiler summary="Code">↵
~~~~~↵
//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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
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}$.↵
↵
2. $[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$.↵
↵
3. $[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.↵
↵
4. 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.
↵
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)](https://codeforces.net/blog/entry/110376), basics.↵
- [Combinatorics (2)](https://codeforces.net/blog/entry/110390), implementations.↵
- [Combinatorics (3)](https://codeforces.net/blog/entry/110799), 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](https://codeforces.net/problemset/problem/632/E)↵
↵
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 $\
↵
#### [Codeforces 438E — The Child and Binary Tree](https://codeforces.net/problemset/problem/438/E)↵
↵
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. ↵
↵
$$\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 1 & 4 & 2 & 5\end{pmatrix}\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 4 & 2 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 1 & 4 & 2 & 5\end{pmatrix}\begin{pmatrix}3 & 1 & 4 & 2 & 5\\ 1 & 4 & 3 & 2 & 5\end{pmatrix}=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 1 & 4 & 3 & 2 & 5\end{pmatrix}$$↵
↵
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](https://en.wikipedia.org/wiki/15_puzzle) situation, is it reachable from the initial version?↵
↵
For example:↵
↵
$$\begin{bmatrix}15 & 14 & 13 & 12\\ 11 & 10 & 9 & 8 \\ 7 & 6 & 5 & 4\\ 3 & 2 & 1 & 0 \end{bmatrix}$$↵
↵
$0$ is the empty square. Then, all the swaps together, are the same to this permutations:↵
↵
$$\begin{pmatrix}0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15\\ 0 & 15 &14 &13 &12 &11 &10 &9 &8 &7 &6 &5 &4 &3 &2 &1\end{pmatrix}$$↵
↵
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|$:↵
> $$|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^{g}\right|$$↵
↵
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$.↵
↵
$$\displaystyle l=\dfrac{c_1(a_1)+c_1(a_2)+c_1(a_3)+\dots +c_1(a_g)}{|G|}$$↵
↵
**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↵
↵
$$\displaystyle\sum\limits_{i=1}^{g}c_1(a_i)=\sum\limits_{i=1}^{g}\sum\limits_{x=1}^{n} S(a_i,x)=\sum\limits_{x=1}^{n}|Z_x|$$↵
↵
The equivalence classes make $i$ equivalence classes' set $E_{x_1},E_{x_2},\dots,E_{x_l}$, then we have:↵
↵
$$\displaystyle\sum\limits_{x=1}^{n}|Z_x|=\sum_{i=1}^{l}\sum_{x\in E_{x_i}}|Z_x|$$↵
↵
According to **sublemma1**, we have:↵
↵
$$\displaystyle \sum_{i=1}^{l}\sum_{x\in E_{x_i}}|Z_x|=\sum_{i=1}^{l}|E_{x_i}||Z_{x_i}|=\sum_{i=1}^{l}|G|=l|G|$$↵
↵
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:↵
↵
$$\displaystyle l=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
$\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:↵
↵
$$\displaystyle l=\dfrac{1}{|\hat G|}\sum_{k=1}^{g} c_1(\hat a_k)=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
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:↵
↵
$$\displaystyle l=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
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)$:↵
↵
$$\displaystyle P(G)=\dfrac{1}{G}\sum_{i=1}^{g}\prod_{k=1}^{n} s_{k}^{c_k(a_i)}=\dfrac{1}{|G|}$$↵
↵
### Part 8 — using Polya's enumeration theorem to solve problems↵
↵
#### [ABC198F — Cube](https://atcoder.jp/contests/abc198/tasks/abc198_f)↵
↵
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](https://atcoder.jp/contests/abc284/tasks/abc284_h)↵
↵
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:↵
↵
$$|G|=\dfrac{1}{N!}\sum_{k=1}^{g} c_1(\hat a_k)=\dfrac{m^{c(\overline a_1)}+m^{c(\overline a_2)}+m^{c(\overline a_3)}+\dots +m^{c(\overline a_g)}}{|\overline G|}$$↵
↵
Finally we can do a dp just as what we did in [ABC226F](https://atcoder.jp/contests/abc226/tasks/abc226_f), and we can solve it in polynomial complexity time. ↵
↵
<spoiler summary="Code">↵
~~~~~↵
//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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
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}$.↵
↵
2. $[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$.↵
↵
3. $[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.↵
↵
4. 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.
