1
$\begingroup$

I have this problem to complete that wants to know how many combinations of flowers can there be in a bouquet of 25 flowers, such that:

$r+c+d+t=25$ where $r=$roses, $c=$carnations, $d=$daisies and $t=$tulips.

The conditions are:

  • between 1 and 7 daisies
  • between 2 and 11 carnations
  • at least 4 roses
  • at most 6 tulips

The inequalities should look like this, I believe:

  • $1\leq d \leq 7$
  • $2\leq c \leq 11$
  • $4\leq r \leq 25$
  • $0\leq t \leq 6$

I've gotten as far as fixing the bounds, so that the lower bounds are 0 for every flower. I let $r'=r-4$, $c'=c-2$ and $d'=d-1$. If I adjust the equation to follow these new assignments, then I have: $r'+c'+d'+t=18$

This got me to thinking that maybe I can't adjust the roses, since the condition is that there are at least 4 roses in the bouquet. If I adjust the bounds, then I get this:

  • $0\leq d' \leq 6$
  • $0\leq c' \leq 9$
  • $0\leq r' \leq 21$
  • $0\leq t \leq 6$

After adjusting the bounds, I must use this principle:

$$S(d'\leq 6 \cap c'\leq 9 \cap r'\leq 21 \cap t\leq 6) = S_{total}-S(d'\leq 6 \cap c'\leq 9 \cap r'\leq 21 \cap t\leq 6)^c$$

This has an issue in it already, since the new total is 18, so the roses can't be between 0 and 21. There is no way the roses can have 21 roses when there are only 18 positions available to be filled.

Another reason I know this is wrong, is when I get to try using $n-A+k-1 \choose k-1$, I get a negative when I get to $S(r'\leq 21)^c=S(r'\geq 22)$, because $A=22$ and so $18-22+4-1\choose 4-1$ yields a negative on top. So I messed up somewhere.

Am I doing any of this wrong? I don't know how to adjust the roses specifically.

Update*: When I was adjusting the bounds, I forgot that when I adjust the daisies and carnations, I should have taken into account how many flowers were left to subtract from roses. So, the roses could only have $0\leq r' \leq 18$.

$\endgroup$
  • 1
    $\begingroup$ I's OK to adjust the roses. What you are missing is that there can only really be $22$ roses to begin wit, because of the requirements on daisies and carnations. $\endgroup$ – saulspatz Nov 17 '18 at 23:10
  • $\begingroup$ OH!!!! I see what you mean now. I was subtracting incorrectly. I appreciate the help, saul!! $\endgroup$ – ChairMane Nov 17 '18 at 23:21
1
$\begingroup$

I don't know if this method is available to you, but here's a nice way to solve problems like this.

Use generating functions to encode the possible occurrences of flowers in the bouquet. For daisies, it's $d+d^2+d^3+d^4+d^5+d^6+d^7$ (we don't need to make the conversion to $d'$). For carnations, it's $c^2+\cdots+c^{11}$, roses $r^4 + \cdots + r^{25}$ (we do not even need the correct cap on roses as per @saulspatz), and tulips $1+t+\cdots+t^6$ where $1 = t^0$ indicates no tulips.

In multiplying together these four polynomials, there will be terms like $d^5 c^{10} r^5 t^5$ signifying a bouquet with 5 daisies, 10 carnations, 5 roses, and 5 tulips. But that doesn't do much for counting possibilities. Since each flower contributes to the 25, we want to replace each flower variable by $x$ so that $d^5 c^{10} r^5 t^5$ becomes $x^{25}$. Every allowed bouquet will contribute another $x^{25}$, so the total number of possible 25-flower bouquets will be the coefficient of $x^{25}$.

A computer algebra system like Wolfram Alpha can work out the following product (use ``expand''):

\begin{align*} (x+\cdots+x^7)&(x^2+\cdots+x^{11})(x^4 + \cdots + x^{25})(1+x+\cdots+x^6) \\ &= x^7 + 4x^8 + 10x^9 + 20 x^{10} + \cdots + 470x^{24} + 480x^{25} +\cdots \end{align*}

The single $x^7$ means that there's only one way to make a bouquet of 7 flowers: $d^1 c^2 r^4 t^0$ in our system with four variables. The $4x^8$ means there are four ways to make an 8 flower bouquet: $d^2 c^2 r^4 t^0$, $d^1 c^3 r^4 t^0$, $d^1 c^2 r^5 t^0$, $d^1 c^2 r^4 t^1$. The number of 25 flower bouquets is 480, the coefficient of $x^{25}$.

With four types of flowers, one could probably work out this problem with the counting techniques you started. But the generating function technique gives more information (counts for various bouquet sizes) in a much simpler way (once the machinery is set up)---the tricky counting is done in the algebra when the polynomials are multiplied together.

For another example, look at this question about counting possible Scrabble starting positions, which is like having 27 kinds of flowers with various constraints (e.g., at most 2 blank tiles, 6 A tiles) and a 7 flower bouquet. That problem requires generating functions or a brute force computer approach; careful counting arguments would not be feasible.

$\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.