2
$\begingroup$

In generating functions we can related the coefficients of the generating function with as sequence.

$$f(x) = \sum^{\infty}_{n=0}f_nx^n$$

and the sequence that corresponds to it:

$$( \ f_0 \ , \ f_1 \ , \ f_2 \ , \ ... \ , \ f_n \ , \ ...)$$

and these coefficients might be related to some counting problem and its kind of a way to "organize" the counting of some set.

Now when we consider the product of two generating functions $A(x)B(x)$. The product can be interpreted the following way:

Let $A(x)$ be the generating function for selecting items from set A, and let $B(x)$ be the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from the union $A \cup B$ is the product $A(x) \cdot B(x) = C(x)$.

This is the statement that I am seeking to understand better, either with a proof or an intuitive argument (ideally both).

Recall that if the generating function of the product is $C(x) = A(x) \cdot B(x)$, then the coefficients of $C(x)$ is the convolution:

$$c_n = \sum^{n}_{j=0} a_j b_{n-j}$$

What is incredible for me is that the convolution rule for counting, remains valid for many interpretation of "selection" (selection, as in the paragraph). I want to understand what are the limits of this word "select" and why.

Also for two sets of objects we are interested in counting, say coefficients for$a_n$ and $b_n$, might have different combinatorial interpretations for the word "select", right? If the interpretation of the word select is different, does the product of the generating functions still hold as a valid method for computing mountings of the union of A and B? i.e. when we use the word select for counting things in $a_n$ and $b_n$, if the word select mean different things for $a_n$ and $b_n$, does $c_n$ still count the intended arrangements of objects?

For example, I was told that, we could insist that distinct items be selected or we might allow the same item to be picked a limited number of times or any number of times. However, there are only 2 restrictions for our convolution coefficients to yield correct counting numbers and these are:

  1. the order in which items are selected is disregarded.
  2. restrictions on the selection of items from sets A and B also apply in selecting items from $A \cup B$.

Why do we need those two rules to ensure the correctness that $c_n$ counts the number of ways to select n items from $A \cup B$?

I was told that these two restrictions can be equivalently expressed as follows:

Formally, there must be a bijection between n-element selections from $A \cup B$ and ordered pairs of selections from A and B containing a total of n elements.

I was having trouble understanding how those two statements are related and thus, why the restrictions correspond to that bijection.

Once we have those restrictions and we understand them, as far as I know the following sum gives the desired count. If we let $c_n$ is the number of ways to select n items from $A \cup B$, then (for some reason) we observe that we can select n items by choosing j items from A and n - j items from B, where j is any number from 0 to n. This can be done in $a_j b_{n-j}$ ways. Summing over all the possible values of j gives a total of:

$$c_n = \sum^{n}_{j=0} a_j b_{n-j}$$

ways to select n items from $A \cup B$.

I was unsure why that was the case and how it would break if the conditions that were pre specified would break it. Why does the convolution give indeed the correct count?


Source:

Page 375 from the book (page 21 by chapter) of:

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap12.pdf

$\endgroup$
  • 2
    $\begingroup$ What is your source? The generating function for a combinatorial object formed from the disjoint union of two other combinatorial objects is their $sum$, not their product. The product of generating functions corresponds to the Cartesian product of two combinatorial objects. $\endgroup$ – A.E Nov 7 '14 at 18:56
  • 1
    $\begingroup$ I can prove this, but my source is Analytic Combinatorics by Flajolet and Sedgewick. $\endgroup$ – A.E Nov 7 '14 at 18:57
  • $\begingroup$ @A.E page 375 (or page 21 if your looking at that chapter only) of the following: ocw.mit.edu/courses/electrical-engineering-and-computer-science/… $\endgroup$ – Pinocchio Nov 7 '14 at 23:34
  • $\begingroup$ @A.E I prefer simpler proofs than something to crazy (or too advance), however, if that is the only proof you know and its correct, feel free to share it. It will just take me longer to understand/digest it (because I might have to look up things I don't know as I read the proof and stuff like that). I have a math background of a computer scientist (with inclinations to mathematics) or probably a junior doing maths as a major. However, I prefer proofs or arguments that are not too dumbed down, if I need to rise my level, I will try and do my homework on this side :) $\endgroup$ – Pinocchio Nov 7 '14 at 23:36
  • $\begingroup$ @A.E in fact, I prefer some proof than no proof at all :) $\endgroup$ – Pinocchio Nov 7 '14 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.