What is the number of ways in which a fence can be colored if it consists of 45 pickets and there are 5 colors?

Question

You are to paint a fence consisting of 45 fence pickets, and have 5 colors to choose from. Each picket is to be colored in precisely one color, but different pickets can be of different colors.

1. In how many ways can the fence be colored if the order of the pickets does not matter?
2. What is the minimum and maximum number of ways in which the fence pickets can be arranged if the order of the colored pickets is taken into account?
3. Write an expression for the number of ways in which the fence pickets can be arranged if the order of the colored pickets is taken into account.

Note: The pickets can only be distinguished by color. In other words, all pickets of color 1 are equivalent, so are all pickets of color 2, and so on.

Problem 1: To solve the first problem, I use the stars and bars method to determine the number of ways in which the 45 pickets can be colored using 5 colors:

$$C(\text{picket colors}) = {45 + 4 \choose 4} = {49 \choose 4} = 211,876$$

I believe this answer is correct.

Problem 2: To solve problem 2 we need to determine the minimum number of ways in which the pickets can be arranged and the maximum number of ways in which the pickets can be arranged. The reason the number of ways in which the pickets can be ordered is not a fixed value is because we do not know how many pickets of each color there are.

I believe that a general formula for the number of possible arrangements, given that the number of pickets of color one is $\text{I}$, the number of pickets of color two is $\text{II}$, ..., and the number of pickets of color five is $\text{V}$, is:

$$N(\text{arrangements}) = N(\text{distributions of pickets/color)}) \times P(\text{distribution of pickets/color})$$

$$N(\text{distributions of pickets/color}) = C(\text{color 1}) \times C(\text{color 2, all pickets of color 1 are arranged}) \times ... \times C(\text{color 5, all pickets of colors 1,2,3,4 are arranged}) = $$

$$={45 \choose \text{I}} {45 - \text{I} \choose \text{II}}...{45 - \text{I} - \text{II} - \text{III} - \text{IV} \choose \text{V}}$$

$$P(\text{distribution of pickets/color}) = 5!$$

Example: Let there by $a$ pickets of color one, $b$ pickets of color two, $c$ pickets of color three, $d$ pickets of color four, and $e$ pickets of color five. This is one possible way of distributing the pickets "among" the 5 colors. However, the same pickets/color ratio could be maintained while distributing the pickets differently. For instance, there could be $b$ pickets of color one, $a$ pickets of color two, $c$ pickets of color three, $d$ pickets of color four, and $e$ pickets of color five. The "pickets/color ratios" are the same, namely a,b,c,d,e, but the distribution is different. The rule of product gives us that there are $5!$ ways of distributing the pickets "among" the colors for a specific set of "picket/color ratios".

The minimum number of ways in which the pickets can be arranged occurs when all pickets are of the same color, as then there is only 1 possible arrangement as ${45 \choose 45} = 1$, therefore, yielding $N_{min}(\text{arrangements}) = 5!$

The maximum number of ways in which the pickets can be arranged is, well, I'm not sure. My intuition tells me that the maximum number of picket arrangements are possible when there are equally many pickets of each color; in other words, 9 pickets of each of the 5 colors. This would result in the maximum number of arrangements being:

$$N_{max}(\text{arrangements}) = {45 \choose 9}{36 \choose 9}{27 \choose 9}{18 \choose 9}{9 \choose 9} \times 5! \approx 2.281 \times 10^{30}$$

A few simple test in which I vary the number of pickets of each color seem to confirm my intuition, but I cannot figure out how to prove that my intuition is correct.

Question Regarding "Problem 2":

1. Does anyone know how to prove/disprove my intuition (view text for "Problem 2")
2. Do you believe that my answer to "Problem 2" is correct?

Does anyone have any ideas how to prove this? Do you believe that my answer to "Problem 2" is correct?

Problem 3: To solve "Problem 3" I believe that one should write an expression for the sum of all numbers of arrangements for each of the 211,876 ways of coloring the 45 fence pickets using the 5 colors. However, I have no idea how to convert this expression into mathematical symbols.

Questions Regarding "Problem 3":

1. Is my proposed expression for "Problem 3" is correct?
2. How does one convert the proposed expression into mathematical symbols?

Answer 1

Your solution to Problem (1) is correct.

For the Problem (2), the number of each color be $a, b, c, d, e$. Then as you have reasoned, the number of ways would be $$\begin{align} \binom{45}{a}\binom{45-a}{b}...\binom{45-a-b-c-d}{e} &= \frac{45!}{a!(45-a)!}\frac{(45-a)!}{b!(45-a-b)!}...\frac{(45-a-b-c-d)!}{e!(45-a-b-c-d-e)!} \\ &= \frac{45!}{a!b!c!d!e!} \end{align}$$

Note that $a + b + c + d + e = 45$. Now, we need to show that this expression is maximized when they are equally distributed. For this to happen, we need to minimize the denominator.

This can be done by "smoothing". We shall assume that the optimal answer has $a > b + 1$. If not, we can rearrange the terms such that this is the case. But $(a-1)(b+1) = ab - b + a - 1 > ab$. This gives us a smaller denominator, contradicting the assumption of optimality. Thus, the expected maximum occurs when all the terms are "almost equal", matching your intuition.

If both the orders and colors matter. First we arrange them in a row. Then, each picket can be chosen for any color. Hence the number of total ways is just $5^{45}$.