2

From page-79 of generating functionology,

enter image description here

And the following proof,

enter image description here

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.

tryst with freedom
  • 11,538

1 Answers1

3

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

Sarvesh Ravichandran Iyer
  • 76,105
  • "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. (nn′) is to be multiplied with the earlier expression, leading to the expression for h(n,k) stated at the starting of the answer." how is the number of subset of each type given as $\binom{n}{n'}$ – tryst with freedom Jan 19 '21 at 21:15
  • In the example, I could have used any subset of size $n' = 3$, of the set $n = [7]$. I used ${2,5,7}$ in the example but I could have used ${3,4,6}$ too. The number of subsets of $[m]$ of size $m'$ is equal to $\binom{m}{m'}$, because choosing $m'$ elements and putting them together gives a subset. – Sarvesh Ravichandran Iyer Jan 20 '21 at 05:27
  • Huh. So the binomial coefficents are the ways to choose subset of size m' from m... OH! It's like going to each number from 0 to m and asking a yes or no question whether it wants to be in the ultimate subset or not, Is this interpretation correct? – tryst with freedom Jan 20 '21 at 08:09
  • @Buraian Yes, that is correct, but once you ask each number, and put all those that say yes together, you're not bothered about the order in which you asked them, but only which ones said yes, so that means you are taking a combination of the $m'$ numbers which said yes, out of $m$ numbers. That number is $\binom{m}{m'}$. An alternate definition of $\binom{m}{m'}$ is then : number of subsets of $[m]$ of size $m'$, which one easily finds to be equal to $\frac{m!}{m'!(m-m')!}$ – Sarvesh Ravichandran Iyer Jan 20 '21 at 08:49
  • @Buraian Do you have any other issues with this answer? Would you like me to add something else? If the subset part is not clear to you I will try to direct you somewhere or explain it myself. – Sarvesh Ravichandran Iyer Jan 21 '21 at 06:36
  • I've read your answer a few times and I think the part I'm stuck on is figuring out where if the relabelling part is taken care of by the multiplication of power series. Does the multiplication and reindexing the power series contain the relabelling part as well? – tryst with freedom Jan 21 '21 at 07:00
  • @Buraian The relabeling is not taken care by the multiplication : it is taken care of by the binomial coefficient. The binomial coefficient represents the choice of relabeling i.e. which subset of size $n'$ you are taking from $[n]$. Then, regardless of which subset you take, you can relabel every $\mathcal F'$ hand that you took using that subset, and relabel every $\mathcal F''$ hand that you took using the complement, and then put this together to get a hand from $\mathcal F$. – Sarvesh Ravichandran Iyer Jan 21 '21 at 07:21
  • So : binomial coefficient for choosing the subset for relabeling, $h'(n',k')$ for choosing which hand from $\mathcal F'$ you choose for relabeling with this subset , and $h''(n-n',k-k')$ for choosing which hand from $\mathcal F''$ you choose for relabeling with the complement. These get multiplied because the choices are independent. Then you sum over $n'$ and $k'$. – Sarvesh Ravichandran Iyer Jan 21 '21 at 07:23
  • Wait, but don't you want to do the standard relabelling? so, isn't there only one relabelling you could do – tryst with freedom Jan 21 '21 at 07:27
  • Oh wait nevermind, I got it now. Hand doesn't need standard relabelling. – tryst with freedom Jan 21 '21 at 07:32
  • @Buraian I still wish to clarify this! Let's take my example. I have two hands. One of them has subsets that will be a decomposition of $[3]$. The other hand has subsets that make a decomposition of $[4]$. Now, there's not a single way to combine $[3]$ and $[4]$ to make $[7]$ , because I can replace $[3]$ with any subset of $[7]$ that I want of size $3$, let $[4]$ be the complement, relabel all cards like how I illustrate, then put the cards together. So even though it must come to $[7]$ in the end, the choice comes from which part of $[7]$ I want to associate to each hand. – Sarvesh Ravichandran Iyer Jan 21 '21 at 07:35
  • That choice, is represented by which subset of $[7]$ of size $[3]$ I choose for relabeling the first hand, and the number of subsets of $[7]$ of size $3$ is $\binom{7}{3}$. I hope this explanation is better. – Sarvesh Ravichandran Iyer Jan 21 '21 at 07:36
  • Yes! It makes much sense now @Teresa Libson, You can relabel either hand you took and that is denoted by $\binom{n}{k}= \binom{n}{n-k}$ – tryst with freedom Jan 21 '21 at 08:00
  • Thank you for the confirmation of understanding, @Buraian. If you get more questions on this topic, I will try to get a look in, because I am very interested in the subject you are pursuing. – Sarvesh Ravichandran Iyer Jan 21 '21 at 08:13
  • Let us continue this discussion in chat. – tryst with freedom Jan 21 '21 at 08:16