Calculating the number of ways to generate each number in $\left\{ n,\ldots,6n\right\} $ by throwing $n$ dice

Question

Question

The convolution $a*b=\left(c_{0},c_{1},\ldots,c_{n+m-2}\right)$ of two vectors $\left(a_{0},\ldots,a_{n-1}\right)$ and $\left(b_{0},\ldots,b_{m-1}\right)$ is defined as follows: $$ \left(a*b\right)_{i}=c_{i}=\sum_{j=0}^{i}a_{j}b_{i-j} $$

Given that by using the $FFT$ algorithm the convolution can be calculated in $O\left(n\log n\right)$, suggest an algorithm that calculates the number of ways to generate each number in $\left\{ n,\ldots,6n\right\} $ by throwing $n$ dice in $O\left(n\log n\right)$.

---

My Take

I tought on defining the following vectors: $$ V_{A}\left[i\right]=V_{B}\left[i\right]=\begin{cases} 1 & \text{i is a possible result for n dice throws}\\ 0 & \text{else} \end{cases} $$ For example, if n = 2 then: $$ V_{A}=V_{B}=\left[\underbrace{0}_{1},\underbrace{1}_{2},\underbrace{1}_{3},\underbrace{1}_{4},\underbrace{1}_{5},\underbrace{1}_{6},\underbrace{1}_{7},\underbrace{1}_{8},\underbrace{1}_{9},\underbrace{1}_{10},\underbrace{1}_{11},\underbrace{1}_{12}\right] $$ So the convolution would be: $$ c_{i}=\sum_{j=0}^{i}V_{A}\left[j\right]V_{B}\left[i-j\right] $$ when $c_{i}$ contains the possible ways to get $i$ as the sum of $n$ throws.

For example: $$ c_{2}=\underbrace{V_{A}\left[0\right]V_{B}\left[2\right]}_{0}+\underbrace{V_{A}\left[1\right]V_{B}\left[1\right]}_{1}+\underbrace{V_{A}\left[1\right]V_{B}\left[0\right]}_{0}=1 $$ So there is only one way to get 2 as the sum of two dice throws.

Well, I think it works for $n=2$ but it gets complicated for $n>2$, and I don't think it works in $O\left(n\log n\right)$ anymore.

When $n=3$ I will define: $$ V_{A}=V_{B}=\left[\underbrace{0}_{1},\underbrace{0}_{2},\underbrace{1}_{3},\underbrace{1}_{4},\underbrace{1}_{5},\underbrace{1}_{6},\underbrace{1}_{7},\ldots,\underbrace{1}_{23},\underbrace{1}_{24}\right] $$

So for example: $$ c_{8}=\underbrace{V_{A}\left[0\right]V_{B}\left[8\right]}_{0}+\ldots+\underbrace{V_{A}\left[3\right]V_{B}\left[5\right]}_{1}+\underbrace{V_{A}\left[4\right]V_{B}\left[4\right]}_{1}+\underbrace{V_{A}\left[5\right]V_{B}\left[3\right]}_{1}+\ldots+\underbrace{V_{A}\left[8\right]V_{B}\left[0\right]}_{0}=3 $$

That is incorrect, because in this case I need to find the number of possible ways to get 3,4 and 5.

This is where I got stuck. I don't know if my idea is good and if it's possible to use it and stay at $O\left(n\log n\right)$. I think it gets recursive and complicated.

Answer 1

FFT allows you to multiply two degree $d$ polynomials in $O(d\log d)$.

In your case, you want to compute $(x+x^2+x^3+x^4+x^5+x^6)^n$. Using repeated squaring and FFT, you can compute this in $O(n\log n)$. The coefficient of $x^k$ gives you the number of ways to obtain $k$ by throwing $n$ dice.