1
$\begingroup$

The Question

enter image description here

My Problem

Part a is straight forward, just $C(35,32)$. I'm having a little difficulty with the restrictions and understanding what they mean. $x_1 > 0$ means we shouldn't have any solutions of the form $(0 + 32)$? If that's the case how would I factor that into my answer? I'm thinking taking the answer to part a and subtracting all the solutions which contain $32+0$ but I don't really know how to count those.

$\endgroup$
  • $\begingroup$ Hint: for $b)$ let $y_i=x_i+1$ $\endgroup$ – Mark Bennet Nov 10 '14 at 19:29
  • $\begingroup$ @MarkBennet interesting, so I could kind of think of this as distributing 32 cookies amongst 4 children, where each child receives at least one cookie? $\endgroup$ – Dunka Nov 10 '14 at 19:32
  • $\begingroup$ Indeed - if that helps you to get the idea. You can translate the others into the same language. $\endgroup$ – Mark Bennet Nov 10 '14 at 19:41
3
$\begingroup$

For part (b), $x_i > 0$ for all $i$, let $y_i = x_i - 1$. Then the problem is equivalent to problem (a), only with a sum of 28 instead of 32 -- the answer is $C(31, 28) == C(31,3)$.

For part (c) let $y_i = x_i-5$ for $i\in \left\{ 1,2 \right\} $ and $y_i = x_i-7 $ otherwise. Then you have problem (a) again, with a sum of 8; the answer is $C(7,3)$.

For part (d) the same reasoning gives $C(3,3) = 1$.

For part (e) let $y_i = x_i +2$ to get $C(39,3)$.

For part (f), you can start with the solution to (b), and subtract the cases where $x_4 > 25$. To get the latter, do $y_4 = x_4 -25$, and find an answer of $C(10,3)$ so the answer to part (f) is $C(35,3) - C(10,3)$.

$\endgroup$
2
$\begingroup$

$\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{\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{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#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}$

With $\ds{S\ >\ 0}$:

\begin{align} &\color{#66f}{\large\sum_{x_{1}\ =\ 0}^{\infty} \sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},S}} \\[5mm]&=\sum_{x_{1}\ =\ 0}^{\infty}\sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{-x_{1} - x_{2} - x_{3} - x_{4} + S + 1}}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{S + 1}} \pars{\sum_{x\ =\ 0}^{\infty}z^{x}}^{4}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{S + 1}\pars{1 - z}^{4}} \,{\dd z \over 2\pi\ic} \\[5mm]&=\sum_{k\ =\ 0}^{\infty}{-4 \choose k}\pars{-1}^{k} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{S - k + 1}}\,{\dd z \over 2\pi\ic} =\pars{-1}^{S}{-4 \choose S} =\pars{-1}^{S}{4 + S - 1 \choose S}\pars{-1}^{S} \\[5mm]&={S + 3 \choose 3} =\color{#66f}{\large{\pars{S + 3}\pars{S + 2}\pars{S + 1} \over 6}} \end{align}

    ${\bf a}$) $\ds{S = 32}$. $$ {35 \times 34 \times 33 \over 6} = \color{#66f}{\large 6545} $$ ${\bf b}$) $\ds{S = 28}$ because \begin{align} &\sum_{x_{1}\ =\ 1}^{\infty} \sum_{x_{2}\ =\ 1}^{\infty}\sum_{x_{3}\ =\ 1}^{\infty} \sum_{x_{4}\ =\ 1}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},32} \\[5mm]&=\sum_{x_{1}\ =\ 0}^{\infty} \sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},28} \end{align} $$ {31 \times 30 \times 29 \over 6} = \color{#66f}{\large 4495} $$ ${\bf c}$) $\ds{S = 8}$ because \begin{align} &\sum_{x_{1}\ =\ 5}^{\infty} \sum_{x_{2}\ =\ 5}^{\infty}\sum_{x_{3}\ =\ 7}^{\infty} \sum_{x_{4}\ =\ 7}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},32} \\[5mm]&=\sum_{x_{1}\ =\ 0}^{\infty} \sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},8} \end{align} $$ {11 \times 10 \times 9 \over 6} = \color{#66f}{\large 165} $$

${\tt\mbox{and so on}}$.

$\endgroup$
1
$\begingroup$

For part f) we can use generating functions. The one that models f is

$$G(x)=\left(x+x^2+x^3+...+\right)^3 \left(x+x^2+...+x^{25}\right)$$

these are useful because they reduce combinatoric problems to computational ones. The above gf can be written:

$$g=\left(\frac{x}{1-x}\right)^3 \cdot \frac{ \left(x-x^{26}\right)}{1-x}$$

Now we just need to get at the coefficient of $x^{32}$. I have done that already for you to keep the post small. The term of interest is $4475x^{32}$. So the answer is 4475.

$\endgroup$
  • $\begingroup$ Thanks for the answer! I have no idea what a generating function is (I think they save that for part II of my course). The answer is useful for someone who does though. $\endgroup$ – Dunka Nov 11 '14 at 3:08
  • $\begingroup$ Hi; Did not mean to confuse you with too much. Just keep it in mind when you get to part II and good luck. $\endgroup$ – bobbym Nov 11 '14 at 10:30

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.