How many Combination-Schemes?
(Part II)

Well, I expect you've worked out a likely story for the sequence:

a_n = (2n-3) × a_n-1 .

In particular,

a₁ = (-1) × a₀ ,

causing a₀ to be -1. Another way of putting it: a_n is the product of the first n-1 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₆ we look at 2a₆:

\[ \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_{6-i} \]

(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.(n-1).(n-2) \ldots (n-m+1)}{m!} = \dfrac{n!}{m!(n-m)!} \]

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₀ = -1; then we may write

\[ \dpi{130}0 = -a_6 + \sum _{i=1}^{5} \begin{pmatrix} 6 \\ i \end{pmatrix}a_{i}a_{6-i} - a_6 \\* = \;\;\;\;\;\;\sum _{i=0}^{6} \begin{pmatrix} 6 \\ i \end{pmatrix}a_{i}a_{6-i} \]

\[ \dpi{130} = \sum _{i=0}^{6} \frac{6!}{i!(6-i)!} a_{i}a_{6-i} = 6! \sum _{i=0}^{6} \frac{a_{i}}{i!} \frac{a_{6-i}}{(6-i)!} \]

(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⁶ in the power series that determines (g(t))². We could get t⁶ by picking out the t⁰ term in the first factor, and pairing it with the t⁶ term in the second; or by picking out the t¹ term in the first factor, and pairing it with the t⁵ term in the second; or by picking out the t² term in the first factor, and pairing it with the t⁴ term in the second; and so on, up to the t⁶ term in the first factor, with the t⁰ term in the second. Altogether, we get that the t⁶ term in the square would be

\[ \dpi{130} \sum _{i=0}^{6} \frac{a_{i}}{i!} \frac{a_{6-i}}{(6-i)!} \]

But this sum we expect to be zero: giving us the somewhat disconcerting result that the t⁶ 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))² 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))²:

\[ \dpi{130} \left( g(t) \right)^{2} = 1 - 2t + 0t^{2} + 0t^{3} + \dots = 1 -2t \]

It appears that the coefficient of tⁿ 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} = - (1-2t)^{\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ⁿ 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{-(2n-3)}{2}}{n!}\]

which simplifies to

\[ \dpi{130} \frac{ 1.3.5. \dots (2n-3)}{n!} \]

Equating this expression with a_n/n! we obtain

\[ \dpi{130} a_{n} = 1.3.5. \dots (2n-3) \]

What a beautiful result!

See Sloane's On-Line 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 Combination-schemes? (Part I)

home | Table of Contents