Counting using products.

Today I proved the binomial theorem for my class. I did an informal proof showing them how, if we consider the set containing the alphabet: S = \{ a,b ,c, d, ..., z \} and the following product.

\displaystyle \prod_{s \in S} (1+s_i) = (1+a)(1+b)(1+c)\cdots (1+z)

expanding this produces a sum with every combination of the letter a-z:

\displaystyle \prod_{s \in S} (1+s_i) = 1 + a + b + \cdots + z + ab + ac + ad + \cdots + az + bd + be + \cdots + bz + \cdots + abc + abd + \cdots + abcd + \cdots + abcdefghijklmnopqrstuvwxyz

if we count all of the terms in this sum with, say three elements, we have the number combinations of 26 items taken 3 at a time or 26 \choose 3. Next, we make every letter x:

(1+x)^{26} = 1 + x + x + \cdots + x + xx + xx + xx + \cdots + xx + xx + xx + \cdots + xx + \cdots + xxx + xxx + \cdots + xxxx + \cdots + xxxxxxxxxxxxxxxxxxxxxxxxx

(Pretty silly looking I know!) But, now we can see that the coefficients of the terms in the expansion are given by the same formula used to count combinations in probability.

That was today's lesson. What I've noticed is that this manner of counting is the same basic idea as what I've been looking at with integer partitions. (There we use a different product and coefficents to count.)

I wonder if this type of process has a name, or if it is further formalized in any contexts?

Counting integer partitions

My close friend Owen introduced me to generating functions last year. I was not impressed at first since they seemed cumbersome... but now I see how powerful they are for counting partitions. So, I will share my understanding of this matter. This post is based on my readings of The Theory of Partitions, by George Andrews.

The generating function for a sequence a0, a1, a2... is the power series whose coefficients are the a_I. That is: f(q)= \sum_{i \geq}^{\infty} a_iq^i.

p(n) is used to represent the number partitions on an integer n. Extending this idea, given a set H. (eg. H={1, 3, 7} or H= \mathbb{N}) p( "H" , n) will represent the number of partitions of n, using only elements in H. So, we can see that p(n) = p("\mathbb{N}" , n). If H={1, 3, 7} then p( "H" , 10)= 6 because we have:

1+1+1+1+1+1+1+1+1+1 = 10
3+1+1+1+1+1+1+1 = 10
7+1+1+1 = 10
3+3+1+1+1+1 = 10
3+3+3+1 = 10
3+7 = 10

Clearly, if H is even a moderately large set or if n is bigger than, say, 10 the question becomes very complex very quickly. (I would love to see a 3D bar graph the showed z = p("H_y", x) with H_y = {1,2, 3 ... y } I say bar graph because the partition function works on the integers, is there an analytic continuation of p? I should look in to that!)

Note, H represents the set and "H" represents the set of partitions with elements in H. If
H={1, 3, 7} then "H" is a very large set! Now I'll introduce a few more characters to this scene:

"H_{0}" = \mathcal{O} The set of partitions in to odd parts.

"H"_{\leq d} Partitions where no part in H appears more than d times.

\mathcal{D} Set of partitions with distinct parts.

Next I'll connect all of this to the idea if generating functions. Let

f(q) = \sum_{n \geq} p("H", n)q^n and
f_d(q) = \sum_{n \geq} p("H"_{\leq d}, n)q^n

These are generating functions for the sequence of partitions of n with parts in H and the sequence of partitions of n with distinct parts in H.

Then for |q| <1

f(q)=\prod_{n \in H} (1-q^n)^{-1}
 f_d(q)=\prod_{n \in H} (1+ q^n +q^{2n} + \cdots + q^{dn}) or another way we could say
f_d(q)=\prod_{n \in H} \frac{1-q^{dn+n}}{1-q^n}

The proof is very lovely. The main idea is that the exponents of q will contain a linear combination of elements in H, hence the when we group together terms with the same exponent it is the same thing as counting the linear combinations of elements in H that add up to some integer... That means the coefficients in the power series are the number of partitions!

Very neat.

An enjoyable lecture on Partitions for beginners.

I just found this on iTunes U. (Click 'New Theories Revel the Natural Numbers') It outlines the basic theory and major questions in Partition Theory. Enjoy it!