3
$\begingroup$

Through using brute force, I have got 15 triplets of solutions. Have I reached the right answer, and how can I not use brute force?

$\endgroup$
  • 1
    $\begingroup$ Hint: Use inclusion-exclusion, and also stars and bars to help determine $|A|$, $|B|$, $|C|$ and so on. $\endgroup$ – Toby Mak Nov 11 '17 at 0:29
  • $\begingroup$ @TobyMak I don't think stars and bars would strictly work would it? There would be quite a bit of overlapping numbers. $\endgroup$ – Gerard L. Nov 11 '17 at 0:29
  • $\begingroup$ It, in conjunction with inclusion-exclusion, absolutely will work. See a recent answer of mine here which deals with a rephrasing of the question and gives the general solution at the bottom. $\endgroup$ – JMoravitz Nov 11 '17 at 0:46
  • $\begingroup$ @JMoravitz So my problem would translate to 3 combinations, but I don't know how to split 14 into different parts to fit into your answer? $\endgroup$ – Gerard L. Nov 11 '17 at 0:52
  • $\begingroup$ @Gerard L: Not possible you change your data later than acceptable. $$x=0,1,2,3,4,5\\y=0,1,2,3,4,5\\z=0,1,2,3,4,5,6$$ $x=0,1,2$ is clearly impossible. $$x=3\Rightarrow y+z=11\Rightarrow (y,z)=(5,6)\\x=4\Rightarrow y+z=10\Rightarrow (y,z)=(4,6),(5,5)\\x=5\Rightarrow y+z=9\Rightarrow (y,z)=(5,4),(3,6)$$ Thus $$(x,y,z)=(3,5,6),(4,4,6),(4,5,5),(5,5,4),(5,4,5),(5,3,6)$$ $\endgroup$ – Piquito Nov 11 '17 at 1:23
4
$\begingroup$

For the given conditions, the maximum values of x, y and z are: $$\begin{align} x={} & 5 \\ y= {} & 6\\ z = {} & 7 \\ \sup(x+y+z) = {} & 18 \end{align}$$

Hence we must subtract 4 from $x$, $y$ and $z$ collectively such that $x+y+z=14$.

Of the 5 partitions of 4, all except 1+1+1+1 are possible allocations.

  • 4+0+0 - ${3\choose1}=3$ ways of allocating.
  • 3+1+0 - $3!=6$ ways of allocating.
  • 2+2+0- ${3\choose1}=3$ ways of allocating.
  • 1+1+2- ${3\choose1}=3$ ways of allocating.

Thus, as you calculated, $3+6+3+3=15$ integer solutions.

$\endgroup$
  • $\begingroup$ I have made an embarrassing typo that would change your answer by a couple more triplets. $\endgroup$ – Gerard L. Nov 11 '17 at 0:38
3
$\begingroup$

Here is another way to solve the problem.

Since, $x \leq 5, y \leq 6$ and $z \leq 7$, we can define $x_1, x_2, x_3$ as $5-x,6-y$ and $7-z$ respectively. Clearly, $x_1, x_2$ and $x_3$ are all non-negative integers. The original equation can thus be rewritten as

$$x_1 + x_2 + x_3 = 4$$

This has $\binom{4+2}{2} = 15$ solutions.

$\endgroup$
  • $\begingroup$ How do you get 6 choose 2? I don't follow. $\endgroup$ – Gerard L. Nov 11 '17 at 1:59
  • 1
    $\begingroup$ @GerardL. Using the metaphor of choosing a 14-element submultiset from $\{6\cdot x, 7\cdot y, 8\cdot z\}$ like I used below, rather than choosing the $14$ elements to be used by the sub-multiset, iamwhoiam is instead choosing the four elements to be not used by the sub-multiset. $\endgroup$ – JMoravitz Nov 11 '17 at 2:02
  • $\begingroup$ @GerardL, the number of non-negative integer solutions to $x_1 + x_2 .. + x_k = n$ is given by $\binom{n + k -1}{k - 1}$ $\endgroup$ – iamwhoiam Nov 11 '17 at 2:02
  • 1
    $\begingroup$ As an aside, this is the same observation and simplification to the problem that user213305 made, but user213305 used brute force casework to describe each type of partition. Iamwhoiam instead was able to directly use stars-and-bars to give the number of solutions to the simplified problem in one line. $\endgroup$ – JMoravitz Nov 11 '17 at 2:07
  • $\begingroup$ I was about to say that this was stars and bars so I could find the derivation of the formula. Thanks! $\endgroup$ – Gerard L. Nov 11 '17 at 2:08
1
$\begingroup$

Using generating functions, like in this example $$x_1+x_2+x_3=14$$ $$0\leq x_1 \leq5$$ $$0\leq x_2 \leq6$$ $$0\leq x_3 \leq7$$ the generating function is $$(1+x+...+x^5)(1+x+...+x^6)(1+x+...+x^7)$$ and the coefficient near $x^{14}$ term is the answer, which is 15.

$\endgroup$
  • $\begingroup$ how do we calculate the coefficient of $x^{14}$ ? (: $\endgroup$ – gilly Nov 11 '17 at 8:26
  • $\begingroup$ @gilly did you just down-vote me? Without looking at the link I posted? Which contains a reference to a book explaining this material (it's a standard combinatorics!)? ... answer to your question, by expanding the product of polynomials, it's a mechanical calculation. $\endgroup$ – rtybase Nov 11 '17 at 8:30
  • $\begingroup$ i did not down vote you! to prove i will upvote you . I was saying that it is no different from counting cases brute forcefully! No difference $\endgroup$ – gilly Nov 11 '17 at 9:07
  • $\begingroup$ donot put false accusation on me i am good. $\endgroup$ – gilly Nov 11 '17 at 9:11
  • 1
    $\begingroup$ You just proved that method of generating functions works :) ... It's easier to group terms under the same powers, even a computer can do that, with a polynomial complexity, rather that nearly exponential. $\endgroup$ – rtybase Nov 11 '17 at 9:22
0
$\begingroup$

To explain my comment above, which you seem to have not understood, your question is essentially the same as that of finding how many 14-element sub-multisets exist of the set $\{x,x,x,x,x,y,y,y,y,y,y,z,z,z,z,z,z,z\}$ which is discussed here.

Borrowing from the other post, given $n$ distinct letters available, wishing to take a $k$-element submultiset, and having $c_1,c_2,\dots,c_n$ of each respective letter available respectively, the general solution will be $$\sum\limits_{i=0}^n\left((-1)^i\sum\limits_{\Delta\subseteq [n]~:~|\Delta|=i}\binom{n+k-1-\sum\limits_{j\in\Delta}(c_j+1)}{n-1}\right)$$

In your specific case we have $n=3,k=14,c_1=5,c_2=6,c_3=7$;

$$\binom{16}{2} - \binom{10}{2}-\binom{9}{2}-\binom{8}{2}+\binom{3}{2}+\binom{2}{2}+0-0=15$$

This method comes from a combination of stars and bars and inclusion-exclusion, running inclusion-exclusion on the events that some $x_i$ violated it's respective upper bound condition.

$\endgroup$
  • $\begingroup$ Could you simplify the sigma notation down to something I could understand? I have trouble reading it. $\endgroup$ – Gerard L. Nov 11 '17 at 1:34
  • $\begingroup$ For a broad generalization, I can not without requiring ten times the space, but what it is is exactly the same as in the other question. We have our events $S,A_1,A_2,A_3$ (and possibly more in the generalization) where $S$ is the set of solutions if we ignore all upper bounds and $A_1$ is the set of solutions if we violate the upper bound on $x_1$, etc... we have our total number which violated none of the upper bounds as $|S|-|A_1|-|A_2|-|A_3|+|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|-|A_1\cap A_2\cap A_3|$ which using stars and bars to calculate each arrives at $\binom{16}{2}-\cdots$ $\endgroup$ – JMoravitz Nov 11 '17 at 1:39
  • $\begingroup$ If you have a specific question about the sigma notation, the outermost summation runs with index $i$ starting from $0$ and going on up to $n$ hitting each natural number along the way. The second summation notation ranges over all $i$-element subsets of $\{1,2,3,\dots,n\}$, and the innermost summation ranges over all elements in the specific $i$-element subset we had selected for that iteration. $\endgroup$ – JMoravitz Nov 11 '17 at 1:41
  • $\begingroup$ Wouldn't using this for larger amounts of $A_n$ be time consuming as I have to calculate each intersection? I am trying to apply this to $x+y+z+w=14$ with $x<=5, y<=6, z<=7, w<=8$. $\endgroup$ – Gerard L. Nov 11 '17 at 1:56
  • $\begingroup$ "as I have to calculate each intersection?" Considering that each intersection's size has an easy closed form and eventually becomes zero, and the final closed form can be used without much thought process and avoids the brute force approaches above, I would definitely use this approach over any other for the general problem. You can sometimes save time by looking at the problem from the other direction like iamwhoiam did in the other answer, but with other conditions it might be more time consuming to do it that way instead (e.g. if you were choosing 4-element submultisets instead of 14) $\endgroup$ – JMoravitz Nov 11 '17 at 2:05

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.