2

Let's say I have nine colors, and my art teacher asks me to draw pictures using these nine colors. However, I need to use at least five colors for each drawing. Now I know there is only one way to combine nine colors (the order doesn't matter). But I don't know how to determine other combinations (8/9, 7/9, 6/9, 5/9). I imagine that once I figure out each of these possibilities, then I need to add them together to get all possible 5+ color combinations using nine colors.

Appreciate your help.

Wictim
  • 21
  • 1

2 Answers2

1

Label the colors as $1,...,9$.

Let $X=\{1,...,9\}$.

For each subset $S$ of $X$, let $S'=\{x\in X\mid x\notin S\}$.

Let $A$ be the set of subsets of $X$ with at least $5$ elements.

Our goal is to find $|A|$.

Let $B$ be the set of subsets of $X$ with at most $4$ elements.

It's easily seen that the map $S\mapsto S'$ is a bijection from $A$ to $B$, hence $|A|=|B|$.

Let $P(X)$ be the set of subsets of $X$.

From $|X|=9$, we get $|P(X)|=2^9$.

Noting that $P(X)=A\cup B$, and $A\cap B={\large{\varnothing}}$, it follows that $$2^9=|P(X)|=|A|+|B|=2|A|$$ hence $|A|=2^8=256$.

So that's one way to find $|A|$.

As an alternative, more elementary approach, we can use the binomial theorem . . . \begin{align*} 2^9&=(1+1)^9\\[4pt] &={\small{\binom{9}{0}}}+\cdots +{\small{\binom{9}{9}}}\\[4pt] &= \left({\small{\binom{9}{5}}}+{\small{\binom{9}{4}}}\right) + \left({\small{\binom{9}{6}}}+{\small{\binom{9}{3}}}\right) + \left({\small{\binom{9}{7}}}+{\small{\binom{9}{2}}}\right) + \left({\small{\binom{9}{8}}}+{\small{\binom{9}{1}}}\right) + \left({\small{\binom{9}{9}}}+{\small{\binom{9}{0}}}\right)\\[4pt] &=2 \left({\small{\binom{9}{5}}}+\cdots+{\small{\binom{9}{9}}}\right)\\[4pt] &=2|A|\\[4pt] \end{align*} hence $|A|=2^8=256$, the same result as in the first method.

quasi
  • 58,772
  • Thanks for both solutions. If I may ask a subsequent question: For some reason I got 126 when I calculated this before. Is 126 the answer to choosing 5 out of 9 possibilities? That is, if I were asked to use not at least five but ONLY 5 colors for each drawing? – Wictim Oct 25 '18 at 04:49
  • 1
    @Wictim: Yes, for exactly $5$ colors, the count would be $$ \binom{9}{5} = \binom{9}{4} = \frac {9\cdot 8\cdot 7\cdot 6} {4\cdot 3\cdot 2\cdot 1} =126 $$ – quasi Oct 25 '18 at 05:11
0

If you use exactly eight colours, then you're choosing eight colours out of nine, so the number of combinations is given by the binomial coefficient $\binom 98=\binom{9!}{8!1!}=9$. Similar computations are done for seven, six and five colours – $\binom97$ combinations for a seven-colour choice, etc.

Once these cases have been calculated, you are right in that the numbers should be added to arrive at the final result.

Parcly Taxel
  • 103,344