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

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.

• There is a closed formula for the number of different ways to generate a number $k$ from $n$ dice throws (each die has $6$ sides). What is stopping you from directly calculating this formula? Jan 8 at 15:40
• @nirshahar These are not the terms of the question so I guess they did not expect me to use a closed formula Jan 8 at 19:20

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.