# Usage of generating functions in the given enumeration problem

There are $$48$$ flags in a ship that should be sent to the other ships,the flags are white,blue,black,red and for each one of the colors there are $$12$$ flags. We choose $$12$$ of the flags.

• How any messages can be sent assuming an odd number of black flags and an even number of blue flags have been used?

Consider the following exponential generating function:

$$\sum_{k=0}^{n}P(n,k)\frac{x^k}{k!}\tag{I}$$

Where $$P(n,k)=k!\binom{n}{k}=k!C(n,k)$$ is the number of ways to distribute $$k$$ distinct objects into $$n$$ distinct bins such that no bin can contains more than one object.

And so $$[x^k/k!]\sum_{k=0}^{n}P(n,k)\frac{x^k}{k!}=P(n,k)$$

I want to use the same approach to answer the question: We can consider the coefficient of $$x^{12}/(12)!$$ in $$f(x)$$ where:

$$f(x)=\sum_{k=0}^{48}P(n,k)\frac{x^{2k}}{(2k)!}\sum_{k=0}^{48}P(n,k)\frac{x^{2k+1}}{(2k+1)!}\left[\sum_{k=0}^{48}P(n,k)\frac{x^{k}}{k!}\right]^2$$

And I "guess" since we only interested in the coefficients so the convergence is not what we should be worry about,and so I think the answer is given by :

$$[x^{12}/(12)!]\sum_{k \ge 0}^{}P(n,k)\frac{x^{2k}}{(2k)!}\sum_{k \ge 0}^{}P(n,k)\frac{x^{2k+1}}{(2k+1)!}\left[\sum_{k \ge 0}^{}P(n,k)\frac{x^{k}}{k!}\right]^2$$

Since $$P(n,k)=k!C(n,k)[0 \le k \le n]$$,where $$[]$$ is Iverson bracket and so the terms with $$k > n$$ will be equal to $$0$$ (ignoring the convergence ).

But the book I'm working with says that we should be looking for the coefficient of $$x^{12}/{(12)!}$$ in : $$\sum_{k \ge 0}^{}\frac{x^{2k}}{(2k)!}\sum_{k \ge 0}\frac{x^{2k+1}}{(2k+1)!}\left[\sum_{k \ge 0}\frac{x^{k}}{k!}\right]^2$$

But I don't understand why that is,because it looks to me a conflict with $$\text{(I)}$$

## 2 Answers

If we'd multiply

$$\sum_{k \ge 0}{x^{2k}}\sum_{k \ge 0}x^{2k+1}\left[\sum_{k \ge 0}x^k \right]^2$$

out, then each summand of the form $$x^n$$ would correspond to a composition of $$n$$ into 4 parts (i.e. $$x_1+...+x_4=n$$) with the first part ($$x_1$$) being an even number, and the second part ($$x_2$$) being an odd number.

The number of words we can create from (the letters corresponding to) a particular composition $$2x_1+2x_2+1+x_3+x_4=n$$ is $$\binom{n}{2x_1,2x_2+1,x_3,x_4}$$

And the number of words corresponding to some composition of the form $$2x_1+2x_2+1+x_3+x_4=n$$ is:

$$[x^n]\sum_{k_1 \ge 0}\sum_{k_2 \ge 0}\sum_{k_3 \ge 0}\sum_{k_4 \ge 0}\binom{n}{2k_1,2k_2+1,k_3,k_4}x^{(2k_1)+(2k_2+1)+(k_3)+(k_4)}$$

Factoring as much as possible, we obtain: $$[x^n] n!\cdot \sum_{k \ge 0}^{}\frac{x^{2k}}{(2k)!}\sum_{k \ge 0}\frac{x^{2k+1}}{(2k+1)!}\left[\sum_{k \ge 0}\frac{x^{k}}{k!}\right]^2$$ as the quantity we're looking for.

That the bounds don't matter comes from the problem description - there is no summand $$c\cdot x^{12}$$ that uses more flags of a type than there are.

The question remaining is: What does your generating function do?

To each particular composition $$2x_1+2x_2+1+x_3+x_4=n$$ it creates a summand $$\frac{P(n,x_1)P(n,x_2)P(n,x_3)P(n,x_4)}{(2x_1)!(2x_2+1)!(x_3)!(x_4)!}$$

I don't see any concrete thing this could count, especially because of the factor $$\frac{P(n,x_2)}{(2x_2+1)!}$$.

If your generating function were $$f(x)=\sum_{k=0}^{48}P(n,2k)\frac{x^{2k}}{(2k)!}\sum_{k=0}^{48}P(n,2k+1)\frac{x^{2k+1}}{(2k+1)!}\left[\sum_{k=0}^{48}P(n,k)\frac{x^{k}}{k!}\right]^2$$

then to each particular composition $$2x_1+2x_2+1+x_3+x_4=n$$ it'd create a summand $$\frac{P(n,2x_1)P(n,2x_2+1)P(n,x_3)P(n,x_4)}{(2x_1)!(2x_2+1)!(x_3)!(x_4)!}$$

This would count the number of messages of the following scenario:

Each message has 4 parts. Each part has 12 slots. You fill the first part with an even number of blue flags, the second part with an odd number of black flags, the third part with white flags and the fourth with red flags, so that all 4 parts together contain exactly 12 flags.

So the problem of your generating function is that it would create 4 distinct parts, one for each of the factors $$\frac{P(n,2x_1)}{(2x_1)!} ,\frac{P(n,2x_2+1)}{(2x_2+1)!} ,\frac{P(n,x_3)}{(x_3)!} ,\frac{P(n,x_4)}{(x_4)!}$$.

Here is what I think is a correct approach.

First, it will simplify the generating function if we disregard the fact that there are only $$12$$ flags of each type. Since we only need to send a message of length $$12$$, we may regard the number of flags of each type as unlimited.

The EGF for the number of sequences of length $$n$$ of white flags is then $$1 + x + \frac{1}{2!} x^2 + \frac{1}{3!} x^3 + \dots = e^x$$ and the same for red flags.

The EGF for the number of sequences of length $$n$$ of an even number of blue flags is $$1 + \frac{1}{2!} x^2 + \frac{1}{4!} x^4 + \dots = \frac{e^x + e^{-x}}{2}$$

The EGF for the number of sequences of length $$n$$ of an odd number of black flags is $$x + \frac{1}{3!} x^3 + \frac{1}{5!} x^5 + \dots = \frac{e^x - e^{-x}}{2}$$

A sequence of white, blue, black or red flags is the "star product" of the four sequences above, so its EGF is $$f(x) = e^x \cdot e^x \cdot \frac{e^x + e^{-x}}{2} \cdot \frac{e^x - e^{-x}}{2}$$

The answer to the original problem is given by $$12! [x^{12}]f(x)$$, a computation which we leave to the reader.