0
$\begingroup$

If I have 10 BALLS and 3 boxes, how many possible number of solutions are there with a maximum number of 9 and minimum number of 1? numbers cannot be repeated.

Mathematically, we are finding the number of solutions of $x_1+x_2+x_3=10$ where $1\leq x_1,x_2,x_3\leq9$ and $x_1,x_2,x_3$ are integers.

$\endgroup$
  • $\begingroup$ 2,5,3? Those add up to ten and match your condition. Forgive me if I didnt understand your question right. $\endgroup$ – Karim O. Jan 2 '14 at 7:53
  • $\begingroup$ Never Mind. What we actually need is the number of possibilities that adds up to 10. $\endgroup$ – suzy ong Jan 2 '14 at 7:59
  • $\begingroup$ I guess [7,2,1] and [6,1,3] also work, not much combinations to work with $\endgroup$ – Karim O. Jan 2 '14 at 8:10
1
$\begingroup$

Straight enumeration is the way to go here, but you can simplify a little I think. Since you don't allow repeats, this is the same as $6$ times the number of ways to write $x_1 + x_2 + x_3 = 10$ with $x_i$ strictly increasing and greater than or equal to $1$. Subtracting $i$ from $x_i$, we see that's the same as counting the number of $x_1 + x_2 + x_3 = 4$ with the $x_i$ weakly increasing and greater than $0$. It's pretty quick to enumerate these, there are only $4$ of them, $(0,0,4),(0,1,3),(0,2,2),(1,1,2)$. So, there are $24$ ways to allocate the balls in your problem.

$\endgroup$
1
$\begingroup$

Assume for the moment that we want $x_1<x_2<x_3$. The we necessarily have $$\eqalign{x_1&=1+y_1,\cr x_2&=(x_1+1)+y_2=2+y_1+y_2,\cr x_3&=(x_2+1)+y_3=3+y_1+y_2+y_3\cr}$$ with $y_k\geq0$ $\>(1\leq k\leq 3)$. The condition $x_1+x_2+x_3=10$ then implies $$3y_1+2y_2+y_3=4\ ,\tag{1}$$ which automatically enforces $y_1+y_2+y_3\leq 6$, or $x_3\leq9$.

The nonnegative solutions of $(1)$ can be found by inspection: We obtain the triples $(0,0,4)$, $(0,1,2)$ and $(0,2,0)$ with $y_1=0$ and the single triple $(1,0,1)$ with $y_1=1$.

So there are $4$ solutions when the $x_k$ are in increasing order, or $24$ solutions when they can be in any order.

$\endgroup$
-3
$\begingroup$

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} ?&=\sum_{x_{1} = 1}^{9}\sum_{x_{2} = 1}^{9}\sum_{x_{3} = 1}^{9} \delta_{x_{1} + x_{2} + x_{3}, 10} =\sum_{x_{1} = 1}^{9}\sum_{x_{2} = 1}^{9}\sum_{x_{3} = 1}^{9}\int_{\verts{z} = 1} {1 \over z^{11 - x_{1} - x_{2} - x_{3}}}\,{\dd z \over 2\pi\ic} \\[3mm]&= \int_{\verts{z} = 1}\pars{\sum_{x = 1}^{9}z^{x}}^{3}{1 \over z^{11}} \,{\dd z \over 2\pi\ic} = \int_{\verts{z} = 1}\bracks{z\pars{z^{9} - 1} \over z - 1}^{3}{1 \over z^{11}} \,{\dd z \over 2\pi\ic} = \int_{\verts{z} = 1}{\pars{1 - z^{9}}^{3} \over \pars{1 - z}^{3}}{1 \over z^{8}} \,{\dd z \over 2\pi\ic} \\[3mm]&= \int_{\verts{z} = 1}\sum_{\ell = 0}^{3}{3 \choose \ell} \pars{-z^{9}}^{\ell}\sum_{\ell' = 0}^{\infty}{\ell' + 2 \choose 2}z^{\ell'}\, {1 \over z^{8}} \,{\dd z \over 2\pi\ic} \\[3mm]&= \sum_{\ell = 0}^{3}\sum_{\ell' = 0}^{\infty}\pars{-1}^{\ell}{3 \choose \ell} {\ell' + 2 \choose 2}\delta_{9\ell + \ell',7} = \sum_{\ell = 0}^{3}\pars{-1}^{\ell}{3 \choose \ell} \sum_{\ell' = 0}^{\infty}{\ell' + 2 \choose 2}\delta_{\ell',7 - 9\ell} \\[3mm]&= \sum_{\ell\ =\ 0 \atop {\vphantom{\LARGE A}\ell\ \leq\ 7/9}}^{3}\pars{-1}^{\ell} {3 \choose \ell}{9 - 9\ell \choose 2} = {9 \choose 2} = \color{#0000ff}{\Large 36} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.