Skip to main content
replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link

As Brendan McKay commented, this looks like inclusion-exclusion. I just happened to write up such an inclusion-exclusionsuch an inclusion-exclusion.

Suppose we want to count the number of ways to roll a total of $t$ on $n$ $r$-sided dice (with sides $1, 2, ..., r$). By inclusion-exclusion (or, via generating functions, by using the binomial theorem twice to expand the powers in $[x^t](x^n (x^r-1)^n (x-1)^{-n}$), this is

$$\sum_{m=0}^{[(t-n)/r]} (-1)^m {n \choose m}{t-1 - m r \choose n-1}.$$

Choose $t=nr$. There is just one way to roll a total of $nr$, by getting the maximum $r$ on each of the $n$ dice. So,

$$\sum_{m=0}^{[(n(r-1)/r]} (-1)^m {n \choose m}{(n-m)r-1 \choose n-1}=1.$$

As Brendan McKay commented, this looks like inclusion-exclusion. I just happened to write up such an inclusion-exclusion.

Suppose we want to count the number of ways to roll a total of $t$ on $n$ $r$-sided dice (with sides $1, 2, ..., r$). By inclusion-exclusion (or, via generating functions, by using the binomial theorem twice to expand the powers in $[x^t](x^n (x^r-1)^n (x-1)^{-n}$), this is

$$\sum_{m=0}^{[(t-n)/r]} (-1)^m {n \choose m}{t-1 - m r \choose n-1}.$$

Choose $t=nr$. There is just one way to roll a total of $nr$, by getting the maximum $r$ on each of the $n$ dice. So,

$$\sum_{m=0}^{[(n(r-1)/r]} (-1)^m {n \choose m}{(n-m)r-1 \choose n-1}=1.$$

As Brendan McKay commented, this looks like inclusion-exclusion. I just happened to write up such an inclusion-exclusion.

Suppose we want to count the number of ways to roll a total of $t$ on $n$ $r$-sided dice (with sides $1, 2, ..., r$). By inclusion-exclusion (or, via generating functions, by using the binomial theorem twice to expand the powers in $[x^t](x^n (x^r-1)^n (x-1)^{-n}$), this is

$$\sum_{m=0}^{[(t-n)/r]} (-1)^m {n \choose m}{t-1 - m r \choose n-1}.$$

Choose $t=nr$. There is just one way to roll a total of $nr$, by getting the maximum $r$ on each of the $n$ dice. So,

$$\sum_{m=0}^{[(n(r-1)/r]} (-1)^m {n \choose m}{(n-m)r-1 \choose n-1}=1.$$

Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

As Brendan McKay commented, this looks like inclusion-exclusion. I just happened to write up such an inclusion-exclusion.

Suppose we want to count the number of ways to roll a total of $t$ on $n$ $r$-sided dice (with sides $1, 2, ..., r$). By inclusion-exclusion (or, via generating functions, by using the binomial theorem twice to expand the powers in $[x^t](x^n (x^r-1)^n (x-1)^{-n}$), this is

$$\sum_{m=0}^{[(t-n)/r]} (-1)^m {n \choose m}{t-1 - m r \choose n-1}.$$

Choose $t=nr$. There is just one way to roll a total of $nr$, by getting the maximum $r$ on each of the $n$ dice. So,

$$\sum_{m=0}^{[(n(r-1)/r]} (-1)^m {n \choose m}{(n-m)r-1 \choose n-1}=1.$$