0
$\begingroup$

In a flower shop there's: 20 kinds of white flowers, 15 kinds of yellow flowers, 10 kinds of purple flowers, and 10 kinds of orange flowers. How many possible ways are there to choose 7 different kinds of flowers so you end up with at least one flower for each color.

My attempt:

First I picked one of each flower color, which is 4 kinds of flowers total. And now the problem is to choose 3 kinds of flowers from $15+10+10+20=55$ minus $4$ $(51)$ without any conditions so the number of options to choose a subsequence of $3$ out of $51$ is $51\choose 3 $.

Is this correct? Does anybody else have a possible way of solving this problem. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ This problem can be solved with the stars and bars method $\endgroup$ – Jorge Fernández Hidalgo Nov 30 '15 at 18:19
  • $\begingroup$ Would you mind elaborating? i'm not familliar with this method. @dREaM $\endgroup$ – Yves Halimi Nov 30 '15 at 18:21
  • $\begingroup$ I think that $${15\choose 1}\cdot{10\choose 1}\cdot {10\choose 1}\cdot {20\choose 1}\cdot {51\choose 3}$$ $\endgroup$ – AsdrubalBeltran Nov 30 '15 at 18:30
  • $\begingroup$ Because $7$ is small we could break into cases. Probably less work in this case than Inclusion/Exclusion. $\endgroup$ – André Nicolas Nov 30 '15 at 18:52
1
$\begingroup$

We must use inclusion exclusion, to do so we count the subsets of flowers that do not contain at least one flower of each kind, so let $A,B,C,D$ be the collection of sets than do not have a flower of type $1,2,3,4$ respectively.

Then we want to obtain $|A\cup B \cup C \cup D | $.

By the inclusion-exlusion principle this is equal to $x-y+z$

Where:

$x = |A|+|B|+|C|+|D| = \binom{40}{7}+\binom{45}{7}+\binom{45}{7}+\binom{35}{7}$

$y = |A\cap B| + |A\cap C|+ | A\cap D|+ | B\cap c| + | B\cap D|+ | C\cap D| = \binom{30}{7}+\binom{30}{7}+\binom{20}{7}+\binom{35}{7}+\binom{25}{7}+\binom{25}{7}$

$z = |A \cap B \cap C| + |A\cap C \cap D|+ |A\cap B \cap D| + |A\cap B \cap C|=\binom{15}{7}+\binom{10}{7}+\binom{10}{7}+\binom{20}{7}$.

Hence your final answer is:

$\binom{40}{7}+\binom{45}{7}+\binom{45}{7}+\binom{35}{7}-[\binom{30}{7}+\binom{30}{7}+\binom{20}{7}+\binom{35}{7}+\binom{25}{7}+\binom{25}{7}]+\binom{15}{7}+\binom{10}{7}+\binom{10}{7}+\binom{20}{7}$

$\endgroup$
  • $\begingroup$ $A\cup B\cup C\cup D$ is the set of flower arrangements that don't have at least one flower of every color $\endgroup$ – Julian Rosen Dec 1 '15 at 1:42
  • $\begingroup$ Oh yeah, good point he want $\binom{55}{7}$ minus that. $\endgroup$ – Jorge Fernández Hidalgo Dec 1 '15 at 3:30
1
$\begingroup$

Here are some hints:

  • You need one color of each flower. There are three distributions of colors: $A:(4,1,1,1), B:(3,2,1,1), C:(2,2,2,1).$
  • For each one you can enumerate by color by focusing on the differently-sized groupings in each one. For example, if you had four white flowers in grouping $A$, the number of combinations is $_{20}C_4 \cdot 15 \cdot 10 \cdot 10$. It's a similar expression for the other three colors. If you had three whites and two yellows in $B$, the number of combinations is $_{20}C_3 \cdot _{15}C_2 \cdot 10 \cdot 10$. It's a similar expression for the other eleven color combinations for the bigger subgroups. If you had one white in grouping $C$, the number of combinations is $_{20}C_1 \cdot _{15}C_2 \cdot _{10}C_2 \cdot _{10}C_2.$
  • Calculate them all, and then add them up!
$\endgroup$
1
$\begingroup$

Let $C\in\{W, Y, P, O\}$ be a flower color. For $k\geq 1$ an integer, let $N_C(k)$ be the number of ways of selecting $k$ flowers of color $C$, and consider the polynomial generating function $$ f_C(x):=\sum_{k\geq 1} N_C(k) x^k. $$ The number of ways to choose seven flowers, with at least one of each color, is the coefficient of $x^7$ in the product $f(x):=f_W(x)f_Y(x)f_P(x)f_O(x)$. We can compute explicitly $$ f_W(x)=(1+x)^{20}-1,\;\;\;f_Y(x)=(1+x)^{15}-1, $$ $$f_P(x)=(1+x)^{10}-1,\;\;\; f_O(x)=(1+x)^{10}-1, $$ $$ f(x)=(1+x)^{55}-2(1+x)^{45}-(1+x)^{40}+2(1+x)^{30}+2(1+x)^{25}-(1+x)^{15}-2(1+x)^{10}+1. $$ This means the desired number of flower arrangements is $$ {55\choose 7}-2{45\choose 7}-{40\choose 7}+2{30\choose 7}+2{25\choose 7}-{15\choose 7}-2{10\choose 7}. $$ Of course when you write it all down this is just inclusion-exclusion.

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