Combinatorics of $n$-Labelled Object with Certain Constraints

83 Views Asked by At

Let $c_n$ be the number of ways to color a set of n labelled balls using red, white and green where an even number of balls are to be colored red and odd number of balls are to be colored green.


Let's define $r,g,w \in \Bbb Z$ as the number

Then we can formalize given constraints as:

$$r+g+w = n\tag 1$$ where $r$ is even, $g$ is odd and w could be any integer.

However, actually $w$ depends on $n$. Since $r+g$ gives always $odd$, if n is odd $w$ is even and vice versa.

So if $n$ is $odd$, first we can think of every possible $w$ which is $even$ then for each case of $w$ we can count each possible pair of $r$ and $g$.

For example, if $n =3$ and $w =0$ then $(r,g) =(2,1)$ or $(0,3)$

ortherefore $c_3 = \binom{3}{2}+\binom{3}{0}$

Thus, for given $n$, we can get $c_{n=2k} = \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+...\binom{n}{2k}$ and $c_{n=2k+1} = \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+...\binom{n}{2k-1}$


1) Is this approach correct?

2) Additionally, the textbook says to derive exponential generating function from it, but I can't undertstand how could I reformulate above $c_n$ into $\sum_{n=0}^\infty c_n x^n/n!$ in a closed format since I had approached in two separate cases.

1

There are 1 best solutions below

3
On

Your approach is incorrect. The balls are labeled, so it's not enough to just summarize how many there are of each color to determine which balls are colored. With no restrictions you should get that the answer is $3^n$ ($3$ possible choices for each ball), with EGF

$$e^{3x} = e^x e^x e^x$$

(one copy for each color; this identity expresses conceptually that a 3-colored set consists of 3 sets); make sure you understand this case first.

With the given restrictions you still get a product of three EGFs but it's a little different. The EGF for the red balls is

$$\sum_{n \ge 0} \frac{x^{2n}}{(2n)!} = \frac{e^x + e^{-x}}{2} = \cosh x$$

and the EGF for the green balls is

$$\sum_{n \ge 0} \frac{x^{2n+1}}{(2n+1)!} = \frac{e^x - e^{-x}}{2} = \sinh x$$

and so the desired EGF for $c_n$ is

$$\boxed{ \sum_{n \ge 0} c_n \frac{x^n}{n!} = e^x \cosh x \sinh x = e^x \frac{e^{2x} - e^{-2x}}{4} = \frac{e^{3x} - e^{-x}}{4} }$$

and extracting the coefficient of $\frac{x^n}{n!}$ on both sides gives

$$\boxed{ c_n = \frac{3^n - (-1)^n}{4} }.$$

The basic principle being used here is surprisingly difficult to state rigorously, but loosely it's the following: if $A(x)$ is the EGF for "$A$-structures" on a set of size $n$, and $B(x)$ is the EGF for "$B$-structures" on a set of size $n$, then $A(x) B(x)$ is the EGF for ways to decompose a set of size $n$ into two subsets, one of which is given an $A$-structure and one of which is given a $B$-structure. For $e^x$ the structure is "being a set," for $\cosh x$ the structure is "being a set of even cardinality," and for $\sinh x$ the structure is "being a set of odd cardinality."


Here's an alternate solution using ordinary rather than exponential generating functions. If $r + g + w = n$ and we ask how many ways there are to do this with $r$ red balls, $g$ green balls, and $w$ white balls, it's not hard to see that the answer is the multinomial coefficient

$${n \choose r, g, w} = \frac{n!}{r! g! w!}.$$

So the number we're trying to find is

$$c_n = \sum_{r + g + w = n, r \text{ even}, g \text{ odd}} {n \choose r, g, w}.$$

We can understand this sum by first looking at the relevant generating function for multinomial coefficients, namely

$$(x + y + z)^n = \sum_{r + g + w = n} {n \choose r, g, w} x^r y^g z^w.$$

We now want to isolate first the terms in which $x$ appears with an even exponent and second the terms in which $y$ appears with an odd exponent. As in the previous solution this involves expressions of the form $\frac{f(x) \pm f(-x)}{2}$; isolating the even exponents in $x$ gives

$$\frac{(x + y + z)^n + (-x + y + z)^n}{2} = \sum_{r + g + w = n, r \text{ even}} {n \choose r, g, w} x^r y^g z^w.$$

Next, isolating the odd exponents in $y$ gives

$$\frac{(x + y + z)^n + (-x + y + z)^n - (x - y + z)^n - (-x - y + z)^n}{4} = \sum_{r + g + w = n, r \text{ even}, g \text{ odd}} {n \choose r, g, w} x^r y^g z^w.$$

Now we get the same answer as before by setting $x = y = z = 1$. These solutions are secretly the same but this one's a little easier to understand; the relationship is given by looking at the EGF $e^{xt} \cosh (yt) \sinh (zt)$.