From page-79 of generating functionology,
And the following proof,
The first paragraph is understandable for me, but I don't get how from it he concluded that summation. Here are the parts I understand:
- The weight of hands in $h$ and the number of hands in $h'$ must add upto $n$
- The number of cards in $h$ and the number of cards in $h'$ must add upto $k$
The part I don't get is how the binomial coefficent came and multiplication of two terms came.
$\newcommand{\h}{\mathcal{H}}$ $\newcommand{\f}{\mathcal F}$We start with the expression $$h(n,k) = \sum_{n' \leq n,k'\ leq k} \binom{n}{n'}h'(n',k')h''(n-n',k-k') $$
and how it comes from what's been explained previously. I will then explain the rest. It is possible that you already know some of what I write, but to be complete I will still write it.
So $h(n,k)$ counts the number of hands with weight $n$, comprised of $k$ cards coming from $\f$, the exponential family associated to $\h$. Now, the set of cards in $\f$, is by definition the (disjoint) union of the set of cards of $\f'$ and the set of cards of $\f''$.
Therefore, a hand which would be counted under $h(n,k)$, would be formed uniquely as follows :
Pick an $n' \leq n$ and $k' \leq k$. (Therefore the summation)
Pick , a hand of weight $n'$ and size $k'$ from $\h'$. (Therefore, $h'(n',k')$ and $h''(n-n',k-k')$).
Now, contrary to expectation, we aren't done yet. This is because a hand counted under $h(n,k)$ needs to be a collection of cards whose labels are a disjoint decomposition of $[n]$.
Now, a hand ,say $H'$, counted in $h'(n',k')$ has total weight $n'$, and all label sets of this hand put together make exactly $[n']$. On the other hand (double meaning intended!) $H''$ counted in $h''(n-n',k-k')$, all the label sets put together give $[n-n']$. So now, we must recombine the $[n']$ and $[n-n']$, to give us $[n]$. How is this done?
The answer is simple : instead of $[n']$, we choose any subset of $[n]$ of size $n'$,which we use to change all the labels of hand $H'$. Then, the complement of that subset is a subset of size $n-n'$, which we use to label $H''$. The choice of that subset is independent of the choices of $H'$ and $H''$, because by relabelling the number of hands is not going to change if I change which set the labels have to be a superset of, as long as the size of the superset is retained.
I must give an example, to keep the sanity of my clientele. Let's say we are creating a hand of weight $n=7$, with $k=4$ cards.
I pick hand $H'$ , which has total weight $n'=3$ and $k'=2$ cards, from $F'$. Then I pick $H''$ which has total weight $4 = n-n'$ and $k-k' = 2$ cards.
Now, let's take an example : $H'$ has cards with labels $\{1,3\}$ and $\{2\}$ (so they form a decomposition of $[n'] = [3]$), while $H''$ has cards with labels $\{1,4\}$ and $\{2,3\}$, say, so they form a decomposition of $[n-n'] = [4]$. (The pictures don't matter in our situation, we keep them out of context).
Now, putting them together to get a decomposition of $[n] = [7]$, how do I do that? I decide on a subset of $[n] = [7]$ of size $n' = 3$, which I will use to relabel the first part. The remaining I use to relabel the second part. Let's use the subset given by $\{2,5,7\}$.
Now, I create a mapping like so : $\{1,2,3\} \leftrightarrow \{2,5,7\}$. Then, the cards in $H'$ get relabelled like $\{1,3\} \to\{2,5\}$ and $\{2\} \to \{7\}$.
Then for $H''$ I get the mapping $\{1,2,3,4\} \leftrightarrow \{1,3,4,6\}$ (the complement of $\{2,5,7\}$). This gives the relabelled cards of $\{1,4\} \to \{1,6\}$ and $\{2,3\} \to \{3,4\}$.
Now, we can put the relabelled cards together, and that gives us a hand.
It is clear that for each subset of $[n]$ of size $n'$ the relabelling can be done, and is independent of hand choice. It follows that the number of subsets of such type i.e. $\binom{n}{n'}$ is to be multiplied with the earlier expression, leading to the expression for $h(n,k)$ stated at the starting of the answer.
The last line
Let us write down $\h'(x,y)\h''(x,y)$ , multiply term-by-term, and then do a little rewrite using $\frac{1}{s!t!} = \frac{\binom {s+t}s}{(s+t)!}$ : $$ \h'(x,y)\h''(x,y) = \left(\sum_{n',k' \geq 0} h'(n',k')\frac{x^{n'}}{n'!}y^{k'} \right) \left(\sum_{n'',k'' \geq 0} h''(n'',k'')\frac{x^{n''}}{n''!}y^{k''} \right) \\ = \sum_{n',n'',k',k'' \geq 0} h'(n',k')h''(n'',k'') \frac{x^{n'+n''}}{n'!n''!} y^{k'+k''} \\ = \sum_{n',n'',k',k'' \geq 0} h'(n',k')h''(n'',k'') \binom{n'+n''}{n'}\frac{x^{n'+n''}}{(n' + n'')!} y^{k'+k''} $$
Now, what is the coefficient of $\frac{x^n}{n!}y^k$? Well, note that all we require $n' + n'' = n$ and $k'+k'' = k$ i.e. $n'' = n- n'$ and $k'' = k' - k$. Therefore, we can choose any $n'\leq n, k' \leq k$ and take $n'',k''$ as above. Furthermore, it is clear that this covers all terms containing $\frac{x^n}{n!}y^k$. Combining all such terms the answer is: $$ \sum_{n' \leq n, k' \leq k} h'(n',k')h''(n-n',k-k') \binom{n}{n'} \color{green}{ = h(n,k)} $$
Therefore, $\h'(x,y)\h''(x,y) = \sum_{n,k} h(n,k)\frac{x^n}{n!}y^k = \h(x,y)$, as desired.