Possible number combinations within a range of sums

Question

I have a range of sums between $50$ and $100$

I need to determine how many possible combinations of $5$ unique selections between $1$ and $69$ will add up to a number this range.

So, for instance, let's say one possible combination would be: $1+17+20+25+30 = 93$ or $1+2+3+4+45 = 55$

How would I determine the $5$ unique selections to generate a sum within an acceptable range of between $50$ and $100$?

I know I've learned some of this before, but I can't find the right nomenclature for my searches so I can relearn it.

Answer 1

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $$ \left\{\begin{array}{rll} \ds{\left. 1\right)} & \mbox{Choose any}\ \ds{5}\ \mbox{numbers}\ \in\ \mathbb{N}_{\ 1\ \leq\ ?\ \leq\ 69}\ \mbox{such that their sum is}\ \ds{s}: & \ds{\sum_{n_{1} = 1}^{69}\ldots\sum_{n_{5} = 1}^{69} \bracks{\sum_{i = 1}^{5}n_{i} = s}} \\ &\ds{\bracks{\cdots}}\ \mbox{is the}\ Iverson\ Bracket:\ \ds{\bracks{P} = 1}\ \mbox{whenever}\ \ds{P}\ \mbox{is}\ true \\ &\mbox{and}\ \ds{0}\ otherwise.& \\[5mm] \ds{\left. 2\right)} & \mbox{Sum the above expression over all the values of} \\ &\ds{s = 50,51,\ldots,99,100.}& \end{array}\right. $$

Then, the answer is given by

\begin{align} &\bbox[10px,#ffd]{\ds{\sum_{s = 50}^{100}\braces{% \sum_{n_{1} = 1}^{69}\ldots\sum_{n_{5} = 1}^{69} \bracks{\sum_{i = 1}^{5}n_{i} = s}}}} = \sum_{s = 50}^{100}\braces{\sum_{n_{1} = 1}^{69}\ldots \sum_{n_{5} = 1}^{69}\bracks{z^{s}}z^{\sum_{i = 1}^{5}n_{i}}} \\[5mm] = &\ \sum_{s = 50}^{100}\bracks{z^{s}}\pars{\sum_{n = 1}^{69}z^{n}}^{5} = \sum_{s = 50}^{100}\bracks{z^{s}}\pars{z\,{z^{69} - 1 \over z - 1}}^{5} = \sum_{s = 45}^{95}\bracks{z^{s}}{\pars{1 - z^{69}}^{5} \over \pars{1 - z}^{5}} \\[5mm] = &\ \sum_{s = 45}^{95}\bracks{z^{s}}{1 - 5z^{69} \over \pars{1 - z}^{5}} = \sum_{s = 45}^{95}\bracks{z^{s}}\pars{1 - z}^{-5} - 5\sum_{s = 45}^{95}\bracks{z^{s}}z^{69}\pars{1 - z}^{-5} \\[5mm] = &\ \sum_{s = 45}^{95}\bracks{z^{s}}\sum_{k = 0}^{\infty}{-5 \choose k}\pars{-z}^{k} - 5\sum_{s = 45}^{95}\bracks{z^{s}}z^{69} \sum_{k = 0}^{\infty}{-5 \choose k}\pars{-z}^{k} \\[5mm] = &\ \sum_{s = 45}^{95}{-5 \choose s}\pars{-1}^{s} - 5\sum_{s = 45}^{95}\bracks{s \geq 69}{-5 \choose s - 69}\pars{-1}^{s - 69} = \sum_{s = 45}^{95}{s + 4 \choose 4} - 5\sum_{s = 69}^{95}{s - 65 \choose 4} \\[5mm] & = \sum_{s = 0}^{50}{s + 49 \choose 4} - 5\sum_{s = 0}^{26}{s + 4 \choose 4} \end{align}

The binomial arguments are polynomials, in $\ds{s}$, of grade four.

Then, $$ \bbx{\bbox[10px,#ffd]{\ds{\sum_{s = 50}^{100}\braces{% \sum_{n_{1} = 1}^{69}\ldots\sum_{n_{5} = 1}^{69} \bracks{\sum_{i = 1}^{5}n_{i} = s}}}} = 72\ 531\ 081} $$

Answer 2

By unique selection, I assume you mean the 5 numbers selected are distinct. Furthermore, I will assume the order of selection doesn't matter. i.e. selections like $1+17+20+25+30 = 93$ and $30+17+20+25+1 = 93$ will be treated as same selection.

By brute force (i.e the most time consuming version of looping through everything), the number of combinations is $467711$.

Following is another way to derive the number mathematically (through we still need an CAS to complete some of the steps).

---

For any formal power series $\sum_{(i,j) \in \mathbb{N}^2} f_{ij} t^i x^j$ in $t$ and $x$. We will use the notation $[t^i x^j] (\cdots)$ to refer to the coefficient $f_{ij}$ in front of $t^i x^j$.

Let $A$ be any finite subset of positive integers. For any $m, n\in \mathbb{Z}_{+}$, the number of subsets of $A$ with $m$ elements whose element sum to $n$ is given by the formula

$$\mathcal{N} \stackrel{def}{=} \# \left\{ B \subset A : \# B = m \land \sum_{k\in B} k = n \right\} = [t^m x^n ] \prod_{k\in A}( 1 + t x^k )$$

For the problem at hand, $m = 5$ and $A = \{ 1, \ldots, 69 \}$. We have

$$\mathcal{N} = \sum_{n=50}^{100} [t^5 x^n] \prod_{k=1}^{69} (1 + tx^k) = [t^5 x^{100} ] \sum_{\ell=0}^{50} x^\ell \prod_{k=1}^{69} (1 + tx^k) = [t^5 x^{100} ] \left(\frac{1-x^{51}}{1-x}\right)\prod_{k=1}^{69} (1 + tx^k) $$ Expand the product into a polynomial in $t$. $$\prod_{k=1}^{69}(1+tx^k) = 1 + \sum_{\ell=1}^{69} e_\ell(x) t^\ell \quad\text{ where }\quad e_\ell(x) = \sum_{1\le k_1 \le \ldots \le k_\ell \le 69} x^{k_1 + \cdots + k_\ell}$$ The coefficient $e_\ell(x)$ is the $\ell^{th}$ elementary symmetric polynomial associated with the set $A' = \{ x^1, \ldots, x^{69} \}$. In terms of $e_\ell(x)$, we have

$$\mathcal{N} = [x^{100}]\left(\frac{1-x^{51}}{1-x}\right)e_5(x)$$

Let $p_\ell(x)$ be the power sum symmetric polynomial associated with $A'$.

$$p_\ell(x) = \sum_{z \in A'} z^\ell = \sum_{k=1}^{69} x^{k\ell} = q_\ell(x)(1 - x^{69\ell}) \quad\text{ where }\quad q_\ell(x) = \frac{x^\ell}{1-x^\ell}$$ They are related to $e_\ell(x)$ through the Newton–Girard formulae. In particular, we have

$$e_5(x) = \frac{1}{5!} \left|\begin{matrix} p_1(x) & 1 & 0 & 0 & 0\\ p_2(x) & p_1(x) & 2 & 0 & 0\\ p_3(x) & p_2(x) & p_1(x) & 3 & 0\\ p_4(x) & p_3(x) & p_2(x) & p_1(x) & 4\\ p_5(x) & p_4(x) & p_3(x) & p_2(x) & p_1(x) \end{matrix}\right|$$ Substitute $p_\ell(x) = q_\ell(x)(1-x^{69\ell})$ into this and throw away terms which don't contribute to $[x^{100}]$, we obtain ($q_\ell(x)$ abbreviated as $q_\ell$):

$$e_5(x) = \frac{1}{5!} \underbrace{\left|\begin{matrix} q_1 & 1 & 0 & 0 & 0\\ q_2 & q_1 & 2 & 0 & 0\\ q_3 & q_2 & q_1 & 3 & 0\\ q_4 & q_3 & q_2 & q_1 & 4\\ q_5 & q_4 & q_3 & q_2 & q_1 \end{matrix}\right|}_{ \Delta_5} - \frac{x^{69}q_1}{4!} \underbrace{\left|\begin{matrix} q_1 & 1 & 0 & 0\\ q_2 & q_1 & 2 & 0\\ q_3 & q_2 & q_1 & 3\\ q_4 & q_3 & q_2 & q_1\\ \end{matrix}\right|}_{\Delta_4} + o(x^{100})\\ {\Large\Downarrow}\\ \mathcal{N} = [x^{100}]\left( \frac{1-x^{51}}{5!(1-x)} \Delta_5 - \frac{x^{70}}{4!(1-x)^2}\Delta_4 \right)$$ With help on a CAS, this simplifies to $$\mathcal{N} = [x^{100}] \frac{P(x)}{Q(x)}\quad\text{ where }\quad \begin{cases} P(x) &= x^{15}(1 - x^{51} - x^{65} - x^{66} - x^{67} - x^{68} - x^{69})\\ Q(x) &= (1-x)^2(1-x^2)(1-x^3)(1-x^4)(1-x^5)\\ &= 1- 2x + x^3 + x^5 - 2x^8 + x^{11} + x^{13} - 2x^{15} + x^{16} \end{cases} $$ Expand $\frac{1}{Q(x)}$ as a power series in $x$, $\displaystyle\;\frac{1}{Q(x)} = s_0 + s_1 x + s_2 x^2 + \cdots$. The coefficients $s_k$ can be computed using following recurrence relation: $$ \begin{cases} n < 0, & s_n = 0,\\ n = 0, & s_n = 1,\\ n > 0, & s_n - 2s_{n-1} + s_{n-3} + s_{n-5} - 2s_{n-8} + s_{n-11} + s_{n-13} - 2s_{n-15} + s_{n-16} = 0 \end{cases} $$ The end result is $$\begin{align}\frac{1}{Q(x)} = &\;\; 1+2x+4x^2 +7x^3 + \cdots \\ & + 509x^{16}+628x^{17}+769x^{18}+933x^{19}+1125x^{20} + \cdots\\ & + 8837x^{34} + \cdots\\ & + 480512x^{85} + \cdots \end{align}$$

In terms of $s_k$, we find $$\begin{align} \mathcal{N} &= [x^{100}] \frac{x^{15}(1 - x^{51} - x^{65} - x^{66} - x^{67} - x^{68} - x^{69})}{Q(x)}\\ &= \left([x^{85}] - [x^{34}] - [x^{20}] - [x^{19}] - [x^{18}] - [x^{17}] - [x^{16}]\right)\frac{1}{Q(x)}\\ &= s_{85} - s_{34} - s_{20} - s_{19} - s_{18} - s_{17} - s_{16}\\ &= 480512 - 8837 - 1125 - 933 - 769 - 628 - 509\\ &= 467711 \end{align} $$

Reproducing what we have obtained by brute force.