How many CombinationSchemes?
(Part II)
Well, I expect you've worked out a likely story for the sequence:
a_{n} = (2n3) × a_{n1} .
In particular,
a_{1} = (1) × a_{0} ,
causing a_{0} to be 1. Another way of putting it: a_{n} is the product of the first n1 odd numbers  at least, that's what it looks like! Now we have to prove it.
Getting back to our calculations, we note that the (rather awkward) factor of ½ will come up whenever n is even; we can get rid of it by the following stratagem: instead of a_{6} we look at 2a_{6}:
\[ \dpi{130} 2a_6 = 6\, a_1.a_5 + \frac{6.5}{1.2}\, a_2.a_4 + \frac{6.5.4}{1.2.3}\, a_3.a_3 + \frac{6.5}{1.2} \,a_4.a_2 + 6\,a_5.a_1 \]
\[ \dpi{130} = \begin{pmatrix} 6 \\ 1 \end{pmatrix}\, a_1.a_5 + \begin{pmatrix} 6 \\ 2 \end{pmatrix}\, a_2.a_4 + \begin{pmatrix} 6 \\ 3 \end{pmatrix}\, a_3.a_3 + \begin{pmatrix} 6 \\ 4 \end{pmatrix} \,a_4.a_2 + \begin{pmatrix} 6 \\ 5 \end{pmatrix}\,a_5.a_1 \]
\[ \dpi{130} =\sum _{i=1}^{5} \begin{pmatrix} 6 \\ i \end{pmatrix}a_{i}a_{6i} \]
(and this will work for any a_{n}, n>2). Here we have made use of the notation
\[ \dpi{130} \begin{pmatrix} n \\ m \end{pmatrix} = \frac{n.(n1).(n2) \ldots (nm+1)}{m!} = \dfrac{n!}{m!(nm)!} \]
for the number of ways of selecting m objects out of a set of n.
In fact, we may take this rewriting even further. Suppose we define a_{0} = 1; then we may write
\[ \dpi{130}0 = a_6 + \sum _{i=1}^{5} \begin{pmatrix} 6 \\ i \end{pmatrix}a_{i}a_{6i}  a_6 \\* = \;\;\;\;\;\;\sum _{i=0}^{6} \begin{pmatrix} 6 \\ i \end{pmatrix}a_{i}a_{6i} \]
\[ \dpi{130} = \sum _{i=0}^{6} \frac{6!}{i!(6i)!} a_{i}a_{6i} = 6! \sum _{i=0}^{6} \frac{a_{i}}{i!} \frac{a_{6i}}{(6i)!} \]
(and again this will work for any n>2).
Now, apart from the factor 6!, this last sum may be interpreted as follows. Let g(t) be the 'generating function' determined by the infinite power series
\[ \dpi{130} g(t) = \sum _{n=0}^{\infty} \frac { a_{n}}{n!}\; t^{n} = a_0 + \frac{a_1}{1!}t + \frac{a_2}{2!}t^2 + \frac{a_3}{3!}t^3 + \ldots \]
(so if you knew all the a_{n}, you would be able to work out the exact value of g(t), for t not too large).
Then the square of g(t) could be found by writing down the power series twice and multiplying the two series together, term by term. Now, consider the coefficient of t^{6} in the power series that determines (g(t))^{2}. We could get t^{6} by picking out the t^{0} term in the first factor, and pairing it with the t^{6} term in the second; or by picking out the t^{1} term in the first factor, and pairing it with the t^{5} term in the second; or by picking out the t^{2} term in the first factor, and pairing it with the t^{4} term in the second; and so on, up to the t^{6} term in the first factor, with the t^{0} term in the second. Altogether, we get that the t^{6} term in the square would be
\[ \dpi{130} \sum _{i=0}^{6} \frac{a_{i}}{i!} \frac{a_{6i}}{(6i)!} \]
But this sum we expect to be zero: giving us the somewhat disconcerting result that the t^{6} term in the square of g(t) must be zero. But there is nothing special about the number 6: this should work for any integer n — suggesting, at first glance that (g(t))^{2} must be zero as a whole, presumably implying that g(t) must be zero too! But this can't be right. Let's look at what g(t) actually is, given the information we already have:
\[ \dpi{130} g(t) = 1 + t + \frac{t^{2}}{2} + \frac{t^{3}}{2} + \frac{5t^{4}}{8} + \dots \]
Now let's look at (g(t))^{2}:
\[ \dpi{130} \left( g(t) \right)^{2} = 1  2t + 0t^{2} + 0t^{3} + \dots = 1 2t \]
It appears that the coefficient of t^{n} is indeed zero for all n≥2, but not for n=0 and n=1. Indeed, looking back, we see that our argument for it being zero does indeed break down when n=0 or n=1. So
\[ \dpi{130} g(t) =  \sqrt{1  2t} =  (12t)^{\frac{1}{2}} , \]
an expression that may be expanded into a power series using the
binomial formula for
fractional exponents. According to that formula, the coefficient of t^{n} in this power series will be
\[\dpi{130} (2)^{n} \; \frac{ \frac{1}{2} . \frac{1}{2} . \frac{3}{2} . \frac{5}{2} \ldots \frac{(2n3)}{2}}{n!}\]
which simplifies to
\[ \dpi{130} \frac{ 1.3.5. \dots (2n3)}{n!} \]
Equating this expression with a_{n}/n! we obtain
\[ \dpi{130} a_{n} = 1.3.5. \dots (2n3) \]
What a beautiful result!
See Sloane's OnLine Encyclopedia of Integer Sequences, sequence number A001147. A couple of the 'comments' describe the problem we have just solved.
And with grateful acknowledgement to CodeCogs for their handy solution to the problem of incorporating mathematical notation
into a webpage.
back to Boolean Algebras
back to How Many Combinationschemes? (Part I)
home 
Table of Contents
