How many Combination-Schemes?
(Part II)

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

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

In particular,

a1 = (-1) × a0 ,

causing a0 to be -1. Another way of putting it: an 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 a6 we look at 2a6:

\[ \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 an, 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 a0 = -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 an, 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 t6 in the power series that determines (g(t))2. We could get t6 by picking out the t0 term in the first factor, and pairing it with the t6 term in the second; or by picking out the t1 term in the first factor, and pairing it with the t5 term in the second; or by picking out the t2 term in the first factor, and pairing it with the t4 term in the second; and so on, up to the t6 term in the first factor, with the t0 term in the second. Altogether, we get that the t6 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 t6 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 tn 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 tn 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 an/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.