# Combinatorics Problem - Counting.

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.

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

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

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