Distinguishable telephone poles being painted

Question

Each of n (distinguishable) telephone poles is painted red, white, blue or yellow. An odd number are painted blue and an even number yellow. In how many ways can this be done?

Can some give me a hint how to approach this problem?

Answer 1

Proposition$^{[1]}$ Fix $k\in\mathbb{P}$ and functions $f_1,f_2,\dots,f_k:\mathbb{N}\to K$. Define a new function $h:\mathbb{N}\to K$ by

$$h(\#S)=\sum f_1(\#T_1)\ f_2(\#T_2)\dots f_k(\#T_k),$$

where $(T_1,\dots,T_k)$ ranges over all weak ordered partitions of $S$ into $k$ blocks, i.e., $T_1,\dots,T_k$ are subsets of $S$ satisfying:

(i) $T_i\cap T_j=\emptyset\ \text{if}\ i\neq j$, and

(ii) $T_1\cup \dots\cup t_k=S$

Then: $$E_h(x)=\prod^k_{i=1}e_{f_i}(x)$$

Solution Using this proposition, now we let $h(n)$ be the desired number.

\begin{align} E_h(x)&=(\sum_{n\geq0}\frac{x^n}{n!})^2(\sum_{n\geq0}\frac{x^{2n+1}}{(2n+1)!})(\sum_{n\geq0}\frac{x^{2n}}{(2n)!}) \\ \\ &=e^{2x}(\frac{e^x+e^{-x}}{2})(\frac{e^x-e^{-x}}{2}) \\ \\ &=\frac{1}{4}(e^{4x}-1) \\ \\ &=\sum_{n\geq 1}4^{n-1}\frac{x^n}{n!} \end{align}

Thus, $\boxed{h(n)=4^{n-1}}$.

$[1]:\ \ \ \ \ $Stanley, Richard. Enumerative Combinatorics: Volume 2. 1st ed. Cambridge, United Kingdom: Cambridge University Press, 2011. 3. Print.

Answer 2

Consider the generating function given by

$( R + W + B + Y )^n$

Without restriction, the sum of all coefficients would give the number of ways to paint the distinguishable posts in any of the 4 colors. We substitute $R=W=B=Y = 1$ to find this sum, and it is (unsurprisingly) $4^n$.

Since there are no restrictions on $R$ and $W$, we may replace them with $1$, and still consider the coefficients.

If we have the restriction that we are only interested in cases where the degree of $B$ is odd (ignore $Y$ for now), then since

$ \frac{1^k - (-1)^k}{2} = \begin{cases} 1 & k \equiv 1 \pmod{2} \\ 0 & k \equiv 0 \pmod{2} \\ \end{cases}$

the sum of the coefficients when the degree of $B$ is odd, is just the sum of the coefficients of $ \frac{ (R + W + 1 + Y) ^n - ( R + W + (-1) + Y) ^n} { 2} $.

Substituting in $R=W=Y=1$, we get that the number of ways is

$$ \frac{ (1 + 1 + 1 + 1)^n - (1 + 1 + (-1) +1)^n}{2} = \frac {4^n - 2^n} {2}$$

Now, how do we add in the restriction that the degree of $Y$ is even? Observe that since

$ \frac{1^k + (-1)^k}{2} = \begin{cases} 1 & k \equiv 0 \pmod{2} \\ 0 & k \equiv 1 \pmod{2} \\ \end{cases}$

the sum of the coefficients when the degree of $B$ is odd and Y is even, is just the sum of the coefficients of $$ \frac{ \frac{ (R + W + 1 + 1) ^n - ( R + W + (-1) + 1) ^n} { 2} + \frac{ (R + W + 1 + (-1)) ^n - ( R + W + (-1) + (-1)) ^n} { 2} } { 2} $$

Now substituting in $R=W=1$, we get $\frac{ 4^n - 2 ^n + 2^n - 0^n } { 4} = 4^{n-1}$

Answer 3

The exponential generating function (EGF) for the number of red or white poles is $$1 + z + \frac{1}{2!}z^2 + \frac{1}{3!}z^3 + \dots = e^z$$ The EGF for the number of blue poles is $$z + \frac{1}{3!}z^3 + \frac{1}{5!}z^5 + \dots = \frac{1}{2}(e^z-e^{-z})$$ The EGF for the number of yellow poles is $$1 + \frac{1}{2!}z^2 + \frac{1}{4!}z^4 + \dots = \frac{1}{2}(e^z + e^{-z})$$ So the EGF for the number of acceptable permutations of red, white, blue and yellow poles is $$f(z) = (e^z)^2 \cdot \frac{1}{2}(e^z-e^{-z}) \cdot \frac{1}{2}(e^z + e^{-z}) = \frac{1}{4}(e^{4z}-1)$$ The number of acceptable permutations of $n$ poles is the coefficient of $\frac{1}{n!}z^n$ in $f(z)$, which by inspection is $4^{n-1}$ for $n > 0$.