2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ honestly, the solution you just kindly provide looks like a magic to me. Which text do you recommend to start to understand the concpet of structure rigorousity? $\endgroup$
    – snapper
    Nov 27, 2017 at 1:51
  • $\begingroup$ Also, I think A structure and B structure is not disjoint but they are coupled in certain constraint like r+g+w =n but when we construct egf, your answer just multiply it without any other manipulation. It's interesting how it's possible $\endgroup$
    – snapper
    Nov 27, 2017 at 1:52
  • 1
    $\begingroup$ The coupling comes from the fact that the set of size $n$ is being decomposed into two disjoint subsets, whose cardinalities have to add up to $n$. You can try looking at the beginning of Analytic Combinatorics by Flajolet and Sedgewick (freely available online) or Combinatorial Species and Tree-like Structures by Bergeron, Labelle, and Leroux. I agree that this solution looks like magic at first! $\endgroup$ Nov 27, 2017 at 1:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .