1

If you have 12 trees with five of one kind, four of another and three of a third kind how many combinations of these trees can be planted in twelve holes?

blue9207
  • 19
  • I'm not sure what the question wants. Do we have to plant all twelve trees? Are the holes distinct? – Asinomás Jun 04 '15 at 23:25
  • There are $\binom{12}{5}$ ways to choose the holes for the Type 1 trees. For every such choice there are $\dots$. (I am assuming that trees of the same type are indistinguishable. If they are distinguishable, the answer is different. – André Nicolas Jun 04 '15 at 23:36

1 Answers1

1

When you have an $n$ element set with all distinct elements, you can arrange the elements of the set into a line in $n!$ ways (i.e. $n\times(n-1)\times(n-2)\times...\times1$). The reason for this is that there are $n$ options for which element is placed in the first spot, then $n-1$ remaining options for which of the remaining elements is placed in the second spot, etc., until you get to the last spot and there is only one element available to choose from.

Imagine that your example involved $12$ trees of all different colors. There would therefore be $12\times11\times10\times...\times1=12!$ (nearly half a billion) ways to arrange those distinct trees in a line of $12$ holes in the ground.

However, your example does not involve $12$ distinct trees. Instead, it involves $3$ distinct types of trees in a total set of $12$ trees. This greatly limits the possible number of meaningfully different linear arrangements, since trees of the same type could exchange spots and nobody would know the difference.

So how do we compensate for overcounting the possible linear arrangements of trees? We do this by dividing out the number of ways we could exchange same-type trees in the line of holes. Let's say $5$ of the trees are spruce. Based on the rule mentioned in the first paragraph, we could independently arrange those trees in $5!$ ways once you already fix $5$ total spots in which to put spruce trees. If you also have $4$ oak trees and $3$ hawthorn trees, you could also independently rearrange those in $4!$ and $3!$ linear ways, respectively.

So we divide out $5!\times4!\times3!$ from our initial permutation of $12!$ arrangements. The result is that there are $\frac{12!}{5!\times4!\times3!}= 27,720$ ways to linearly arrange those three types of trees in twelve holes.

Fred
  • 216