Frequency Distribution of Multiple Dice Rolls

Question

Given two positive integers a and b, output the frequency distribution of rolling a b-sided die a times and summing the results.

A frequency distribution lists the frequency of each possible sum if each possible sequence of dice rolls occurs once. Thus, the frequencies are integers whose sum equals b**a.

Rules

• The frequencies must be listed in increasing order of the sum to which the frequency corresponds.
• Labeling the frequencies with the corresponding sums is allowed, but not required (since the sums can be inferred from the required order).
• You do not have to handle inputs where the output exceeds the representable range of integers for your language.
• Leading or trailing zeroes are not permitted. Only positive frequencies should appear in the output.

Test Cases

Format: a b: output

1 6: [1, 1, 1, 1, 1, 1]
2 6: [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
3 6: [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]
5 2: [1, 5, 10, 10, 5, 1]
6 4: [1, 6, 21, 56, 120, 216, 336, 456, 546, 580, 546, 456, 336, 216, 120, 56, 21, 6, 1]
10 10: [1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92368, 167860, 293380, 495220, 810040, 1287484, 1992925, 3010150, 4443725, 6420700, 9091270, 12628000, 17223250, 23084500, 30427375, 39466306, 50402935, 63412580, 78629320, 96130540, 115921972, 137924380, 161963065, 187761310, 214938745, 243015388, 271421810, 299515480, 326602870, 351966340, 374894389, 394713550, 410820025, 422709100, 430000450, 432457640, 430000450, 422709100, 410820025, 394713550, 374894389, 351966340, 326602870, 299515480, 271421810, 243015388, 214938745, 187761310, 161963065, 137924380, 115921972, 96130540, 78629320, 63412580, 50402935, 39466306, 30427375, 23084500, 17223250, 12628000, 9091270, 6420700, 4443725, 3010150, 1992925, 1287484, 810040, 495220, 293380, 167860, 92368, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10, 1]
5 50: [1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316246, 341030, 367215, 394835, 423920, 454496, 486585, 520205, 555370, 592090, 630371, 670215, 711620, 754580, 799085, 845121, 892670, 941710, 992215, 1044155, 1097496, 1152200, 1208225, 1265525, 1324050, 1383746, 1444555, 1506415, 1569260, 1633020, 1697621, 1762985, 1829030, 1895670, 1962815, 2030371, 2098240, 2166320, 2234505, 2302685, 2370746, 2438570, 2506035, 2573015, 2639380, 2704996, 2769725, 2833425, 2895950, 2957150, 3016881, 3075005, 3131390, 3185910, 3238445, 3288881, 3337110, 3383030, 3426545, 3467565, 3506006, 3541790, 3574845, 3605105, 3632510, 3657006, 3678545, 3697085, 3712590, 3725030, 3734381, 3740625, 3743750, 3743750, 3740625, 3734381, 3725030, 3712590, 3697085, 3678545, 3657006, 3632510, 3605105, 3574845, 3541790, 3506006, 3467565, 3426545, 3383030, 3337110, 3288881, 3238445, 3185910, 3131390, 3075005, 3016881, 2957150, 2895950, 2833425, 2769725, 2704996, 2639380, 2573015, 2506035, 2438570, 2370746, 2302685, 2234505, 2166320, 2098240, 2030371, 1962815, 1895670, 1829030, 1762985, 1697621, 1633020, 1569260, 1506415, 1444555, 1383746, 1324050, 1265525, 1208225, 1152200, 1097496, 1044155, 992215, 941710, 892670, 845121, 799085, 754580, 711620, 670215, 630371, 592090, 555370, 520205, 486585, 454496, 423920, 394835, 367215, 341030, 316246, 292825, 270725, 249900, 230300, 211876, 194580, 178365, 163185, 148995, 135751, 123410, 111930, 101270, 91390, 82251, 73815, 66045, 58905, 52360, 46376, 40920, 35960, 31465, 27405, 23751, 20475, 17550, 14950, 12650, 10626, 8855, 7315, 5985, 4845, 3876, 3060, 2380, 1820, 1365, 1001, 715, 495, 330, 210, 126, 70, 35, 15, 5, 1]

Answer 1

Octave, 38 bytes

@(a,b)round(ifft(fft((a:a*b<a+b)).^a))

Try it online!

Explanation

Adding independent random variables corresponds to convolving their probability mass functions (PMF), or multiplying their characteristic functions (CF). Thus the CF of the sum of a independent, identically distributed variables is given by that of a single variable raised to the power of a.

The CF is essentially the Fourier transform of the PMF, and can thus be computed via a FFT. The PMF of a single b-sided die is uniform on 1, 2, ..., b. However, two modifications are required:

• 1 is used instead of the actual probability values (1/b). This way the result will be de-normalized and will contain integers as required.
• Padding with zeros is needed so that the FFT output has the appropriate size (a*b-a+1) and the implicit periodic behaviour assumed by the FFT doesn't affect the results.

Once the characteristic function of the sum has been obtained, an inverse FFT is used to compute the final result, and rounding is applied to correct for floating-point inaccuracies.

Example

Consider inputs a=2, b=6. The code a:a*b<a+b builds a vector with b=6 ones, zero-padded to size a*b-a+1:

[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

Then fft(...) gives

[36, -11.8-3.48i, 0.228+0.147i, -0.949-1.09i, 0.147+0.321i, -0.083-0.577i, -0.083+0.577i, 0.147-0.321i, -0.949+1.09i, 0.228-0.147i, -11.8+3.48i]

One can almost recognize the sinc function here (Fourier transform of a rectangular pulse).

(...).^a raises each entry to a and then ifft(...) takes the inverse FFT, which gives

[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Although the results in this case are exactly integers, in general there may be relative errors of the order of 1e-16, which is why round(...) is needed.

Answer 2

Mathematica, 29 bytes

Tally[Tr/@Range@#2~Tuples~#]&

Just generates all possible dice rolls, takes their totals, then counts. Each frequency comes labeled with its value.

Mathematica, 38 bytes

CoefficientList[((x^#2-1)/(x-1))^#,x]&

Expands (1+x+x^2+...+x^(a-1))^b and takes the coefficients of x. Since 1+x+x^2+...+x^(a-1) is the generating function for a single die roll and products correspond to convolutions - adding values of dice - the result gives the frequency distribution.

Answer 3

Haskell, 90 79 77 75 bytes

Thanks to Lynn for the Cartesian product trick. -11 bytes thanks to many Haskell tricks from Funky Computer Man, -2 bytes from naming, -2 bytes thanks to Laikoni. Golfing suggestions are welcome! Try it online!

import Data.List
g x=[1..x]
a!b=map length$group$sort$map sum$mapM g$b<$g a

Ungolfed

import Data.List
rangeX x = [1..x]
-- sums of all the rolls of b a-sided dice
diceRolls a b = [sum y | y <- mapM rangeX $ fmap (const b) [1..a]]
-- our dice distribution
distrib a b = [length x | x <- group(sort(diceRolls a b))]

Answer 4

Pyth - 10 bytes

Just takes all possible dice combinations by taking the cartesian product of [1, b], a times, summing, and getting the length of each sum group.

lM.gksM^SE

Test Suite.

Answer 5

05AB1E, 8 bytes

LIãO{γ€g

Try it online!

How?

LIãO{γ€g  - Full program.

L         - Range [1 ... input #1]
 I        - Input #2.
  ã       - Cartesian Power.
   O      - Map with sum.
    {     - Sort.
     γ    - Group consecutive equal elements.
      €g  - Get the length of each

Answer 6

R, 58 bytes

function(a,b)table(rowSums(expand.grid(rep(list(1:b),a))))

Try it online!

Answer 7

R, 52 bytes

function(a,b)Re(fft(fft(a:(a*b)<a+b)^a,T)/(a*b-a+1))

Try it online!

A port of @Luis Mendo's Octave solution, fft(z, inverse=T) unfortunately returns the unnormalized inverse FFT, so we have to divide by the length, and it returns a complex vector, so we take only the real part.

Answer 8

Jelly, 5 bytes

ṗS€ĠẈ

Try it online!

Note that this takes the arguments in reverse order.

How?

ṗS€ĠL€   - Full program (dyadic) | Example: 6, 2

ṗ        - Cartesian Power (with implicit range) | [[1, 1], [1, 2], ... , [6, 6]]
 S€      - Sum each | [2, 3, 4, ... , 12]
   Ġ     - Group indices by values | [[1], [2, 7], [3, 8, 13], ... , [36]]
    L€   - Length of each group | [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

---

Alternative solutions:

ṗZSĠL€
ṗZSµLƙ
ṗS€µLƙ

Answer 9

SageMath, 40 bytes

lambda a,b:reduce(convolution,[[1]*b]*a)

Try it online

convolution computes the discrete convolution of two lists. reduce does what it says on the tin. [1]*b is a list of b 1s, the frequency distribution of 1db. [[1]*b]*a makes a nested list of a copies of b 1s.

---

Python 2 + NumPy, 56 bytes

lambda a,b:reduce(numpy.convolve,[[1]*b]*a)
import numpy

Try it online!

I've included this solution with the above one, since they're essentially equivalent. Note that this function returns a NumPy array and not a Python list, so the output looks a bit different if you print it.

numpy.ones((a,b)) is the "correct" way to make an array for use with NumPy, and thus it could be used in place of [[1]*b]*a, but it's unfortunately longer.

Answer 10

Python 2, 102 91 bytes

lambda b,a:map(map(sum,product(*[range(a)]*b)).count,range(b*~-a+1))
from itertools import*

Try it online!

Answer 11

Pari/GP, 28 bytes

a->b->Vec(((x^b-1)/(x-1))^a)

Try it online!

Answer 12

Haskell, 61 bytes

g x=[1..x]
a#b=[sum[1|m<-mapM g$b<$g a,sum m==n]|n<-[a..a*b]]

Try it online! Use as a#b.

Partly based on Sherlock9's Haskell answer.

Answer 13

MATL, 9 bytes

:Z^!Xs8#u

Same approach as Maltysen's Pyth answer.

Inputs are in reverse order. Try it online!

Answer 14

Perl 5, 53 bytes

$g=join',',1..<>;map$r[eval]++,glob"+{$g}"x<>;say"@r"

Try it online!

Input format:

b
a

Answer 15

J, 25 24 21 20 bytes

3 :'#/.~,+//y$i.{:y'

Try it online!

Initially I incremented the [0..n-1] list to get [1..n] but apparently it’s not necessary.

Answer 16

Actually, 13 12 bytes

-1 byte thanks to Mr. Xcoder. Try it online!

R∙♂Σ;╗╔⌠╜c⌡M

Ungolfed

                Implicit input: b, a
R∙              ath Cartesian power of [1..b]
  ♂Σ            Get all the sums of the rolls, call them dice_rolls
    ;╗          Duplicate dice_rolls and save to register 0
      ╔         Push uniquify(dice_rolls)
       ⌠  ⌡M    Map over uniquify(dice_rolls), call the variable i
        ╜         Push dice_rolls from register 0
         c        dice_rolls.count(i)
                Implict return

Answer 17

JavaScript (ES6), 94 bytes

f=(n,m,a=[1],b=[])=>n?[...Array(m)].map((_,i)=>a.map((e,j)=>b[j+=i]=(b[j]|0)+e))&&f(n-1,m,b):a

<div oninput=o.textContent=f(+n.value,+m.value).join`\n`><input id=n type=number min=0 value=0><input id=m type=number min=1 value=1><pre id=o>1

Limited by 32-bit integer overflow, but floats could be used instead at a cost of 1 byte.

Answer 18

Javascript (ES6), 89 bytes

b=>g=a=>a?(l=[..."0".repeat(b-1),...g(a-1)]).map((_,i)=>eval(l.slice(i,i+b).join`+`)):[1]

Takes input in currying syntax in reverse order f(b)(a)

f=b=>g=a=>a>0?(l=[..."0".repeat(b-1),...g(a-1)]).map((_,i)=>eval(l.slice(i,i+b).join`+`)):[1]
r=_=>{o.innerText=f(+inb.value)(+ina.value)}

<input id=ina type=number min=0 onchange="r()" value=0>
<input id=inb type=number min=1 onchange="r()" value=1>
<pre id=o></pre>

Answer 19

AWK, 191 bytes

Outputs frequencies as a vertical column.

func p(z){for(m in z)S[z[m]]++
for(i=$1;i<=$1*$2;i++)print S[i]}func t(a,b,z,s){if(a){if(R++)for(n in z)for(i=0;i++<b;)s[n,i]=z[n]+i
else for(i=0;i++<b;)s[i]=i
t(--a,b,s)}else p(z)}{t($1,$2)}

Try it online!

Adding 6 more bytes allows for multiple sets of inputs.

func p(z,S){for(m in z)S[z[m]]++
for(i=$1;i<=$1*$2;i++)print S[i]}func t(a,b,z,s){if(a){if(R++)for(n in z)for(i=0;i++<b;)s[n,i]=z[n]+i
else for(i=0;i++<b;)s[i]=i
t(--a,b,s)}else p(z)}{R=0;t($1,$2)}

Try it online!

Answer 20

Clojure, 86 bytes

#(sort-by key(frequencies(reduce(fn[r i](for[y(range %2)x r](+ x y 1)))[0](range %))))

An example:

(def f #(...))
(f 5 4)

([5 1] [6 5] [7 15] [8 35] [9 65] [10 101] [11 135] [12 155] [13 155] [14 135] [15 101] [16 65] [17 35] [18 15] [19 5] [20 1])

Answer 21

C (gcc), 142 bytes

i,j,k;int*f(a,b){int*r=malloc(sizeof(int)*(1+a*~-b));r[0]=1;for(i=1;i<=a;i++)for(j=i*~-b;j>=0;j--)for(k=1;k<b&k<=j;k++)r[j]+=r[j-k];return r;}

Try it online!

Answer 22

Julia, 43 bytes

f(n,d)=reduce(conv,repmat([ones(Int,d)],n))

Try it online!