2

Apologies if I am missing something obvious. I am an undergraduate Physics major just messing around with numbers in my free time. For fun, I was trying to see if there was a way to explicitly calculate the probability of rolling a particular sum on a series of dice (ie n, s sides dice). I ended up boiling part of the problem down into the following:

$$ \sum_{j=1}^n\sum_{k=1}^ma_jb_kx^{(j+k)}=\sum_{i=1}^{n+m}c_ix^i $$

At this point I do not think my mathematical knowledge is sufficient to figure it out, so I was wondering if anybody could either help explain to me, or set me on the right path (or just tell me if it is even possible) to find some explicit way of describing $c_i$ in terms of $a_j$ and $b_k$.

I have tried googling and looking around quite a bit, but have been unable to find anything (within my knowledge level/capability of understanding) that is related to this enough to provide me a solution.

Thank you!

Curious Cube
  • 23
  • Formulas $(2)$ through $(10)$ are similar here – Тyma Gaidash Nov 29 '22 at 17:22
  • Well, note that $$\sum_{j=1}^n\sum_{k=1}^ma_jb_kx^{(j+k)} = \left(\sum_{j=1}^na_j x^j\right) \left(\sum_{k=1}^m b_kx^{k}\right).$$ Not much more you can do after that. If you're interested in the fastest computation time for $c_i$, you may compute them using FFT. – Jair Taylor Nov 29 '22 at 17:31
  • @JairTaylor so to clarify, are you saying that there isn't any closed form solution for describing c in terms of a and b, and that it would have to be done computationally? – Curious Cube Nov 29 '22 at 18:29
  • Hmm, well I'm not sure what a closed form would mean in this case. Any solution would have to involve all of $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$. So no fixed-length formula will work. It will have to have some kind of sigma notation or similar notation. If you want a particular $c_i$, you could write $$c_i = \sum_{j=1}^{i-1} a_j b_{i-j}.$$ Is that what you want? – Jair Taylor Nov 29 '22 at 18:48
  • Maybe, I am not sure, since when I tested this manually with a=b=[1,1,1], I got something like c=[0,1,2,3,2,1], which doesn't match the explicit value for $c_i$ you gave? – Curious Cube Nov 29 '22 at 19:17
  • It works. $$c_4 = \sum_{j=1}^{4-1} a_j b_{i-j} = a_1 a_{4-1} + a_2 b_{4-2} + a_3 b_{4-3} = 1 + 1 + 1 = 3$$ which matches $c_4 = 3$ in $[c_1,c_2,c_3,c_4,c_5,c_6] = [0,1,2,3,2,1]$. – Jair Taylor Nov 29 '22 at 19:29
  • Ah, ok, that makes sense then, thank you! – Curious Cube Nov 29 '22 at 19:30

1 Answers1

1

There's an explicit formula for $c_i$:

$$c_i = \sum_{j=1}^{i-1} a_j b_{i-j}.$$

This is equivalent to expanding out the term of $x^i$ in $$(a_1 x^1 + \cdots + a_nx^n)(b_1x^1 + \cdots + b_mx^m).$$ You sum all the pairs of terms $a_jx^j b_k x^k$ with $j+k = i$.

If you want to generate all the $c_i$, the fastest way is probably to use FFT. e.g. in Python

import scipy.signal
import numpy as np 
np.round(scipy.signal.fftconvolve([0,1,1,1], [0,1,1,1]))

gives

array([0., 0., 1., 2., 3., 2., 1.])

(Note that this is $0-$ indexed rather than 1-indexed in your examples, ie., it starts with $c_0 = 0$.)

Jair Taylor
  • 16,852