Tyler and Foxy's Scientific and Mathematical Adventure Land: You've Probably Wondered, But Were Afraid to Ask

As well you should've been, by the looks of things.

This is likely to be a long post, touching on a couple of interesting topics and coming to head in an interesting result. Hopefully : ) Warning - past a certain point, it's going to get kind of intense.

So, there's this thing called Pascal's Triangle. It looks something like

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...

The rows are numbered starting at 0 and going down, and the elements of each row are numbered starting at 0 and going across. The nth row has n + 1 elements.

Just straight up, the most obvious pattern is the method of construction. Each number is the sum of the two numbers above it.

There is an actual formula to it, namely that the kth number of the nth row is given by

$\frac{n!}{(n-k)!k!}$

Now, this thing has a lot of nice properties to it. Pascal actually came up with it in reference to probability. The idea is, given a coin and flipping it, say 3 times, there is (1) way of getting 3 heads, (3) ways of getting 2 heads and a tail, (3) ways of getting a head and 2 tails, and (1) way of getting 3 tails. 1 - 3 - 3 - 1. The other rows give similar results all down the rows. Notice that flipping a coin three times, there are 2³ many ways it can happen. 1 + 3 + 3 + 1 = 8. In general, the sum across the nth row is 2ⁿ.

Now, the question we would like to address is how /long/ is a given row of Pascal's triangle. Clearly a given row has n + 1 many elements, but what I'm interested in is, if you were to write out the nth row, literally how many characters would it take. The reason this is interesting to me, at the very least, is that I've always found it incredibly difficult to write out Pascal's triangle, because the length of the rows grows so fast it's difficult to keep the spacing nice and orderly and triangle like.

Look, for example, at the first 16 rows.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1

Look how fast that grows. That's quite fast.

The question is then, exactly how fast.

But how to calculate the length of a row? We have the formula for each element of the row. If we can calculate the length of an element, and sum across the elements of the row and that gives the total length of the row.

But what is the length of the number? In general, the number of digits it takes to write a number n is Floor[log₁₀(n)] + 1, where Floor[x] rounds x down to the nearest integer. A few examples.

Floor[log₁₀(13)] + 1 = Floor[1.1139] + 1 = 1 + 1 = 2

Floor[log₁₀(10000)] + 1 = Floor[4] + 1 = 4 + 1 = 5

Floor[log₁₀(999)] + = Floor[2.99957] + 1 = 2 + 1 = 3

log₁₀x gives you the exponent on 10 needed to calculate x. By rounding it down, you're effectively calculating the exponent on 10 needed to calculate the largest power of 10 smaller than x. (13 gives you 10, 10000 gives you 10000, and 999 gives you 100). And the number of digits in 10ⁿ is n + 1.

So then, using the formula for the k'th element of the n'th row, the number of characters (excluding spaces) needed to write out that row is

$\sum_{k = 0}^n Floor[{ log_{10} \frac{n!}{(n-k)!k!} }] + 1$

However, that is a very uncomfortable looking function. It's going to be very hard to get that in terms of anything sensible, due to all the rounding that must occur, and the inanities involved with taking the log base 10 of things. A closed form expression for that summation is almost out of the question. However, we can still get some good approximations on it, which will tell us how fast the function grows with n.

Now, with a really cool exercise, you can show that the function grows with order less than or equal to n². What this means is that whatever the function actually turns out to be, for large n, the function behaves like, or less than, a*n²ⁿ. We know this to be true, since the sum of all the elements of the row is 2ⁿ. As there are n + 1 many elements in the row then, the number of digits it takes to write out the whole row is less than the number of digits it takes to write out 2ⁿ, n + 1 many times. So we can do the following. Notice that, for any x, Floor[x] is less than or equal to x.

$\sum_{k = 0}^n Floor[log_{10} \frac{n!}{(n-k)!k!} ] + 1 \leq (n + 1)({ Floor[log_{10} 2^n ] + 1})$

Bounding that bound,

$(n + 1)({ Floor[log_{10} 2^n ] + 1}) \leq (n + 1)(log_{10}(2^n) + 1)$

And simplifying,

$... = (n + 1)log_{10}(2^n) + n + 1$

$... = (n + 1)(n)log_{10}(2) + n + 1$

$... = log_{10}(2) n^2 + (log_{10}(2) + 1) n + 1$

We get the final result, bounding the function in question by a quadratic

$\sum_{k = 0}^n Floor[log_{10} \frac{n!}{(n-k)!k!} ] + 1 \leq log_{10}(2) n^2 + (log_{10}(2) + 1) n + 1$

From that now, we know that the function is bound from above by a quadratic function of n, since $log_{10}2$ is a constant. So we know that, whatever the exact form of the summation is, it grows with order of less than or equal to n² Which is very interesting.

But, the actual growth rate of the function could still be something silly like n*log(n), or n^1.5, both of which of are order less than n². How can we figure it out precisely?

Unfortunately I haven't found an equally cool trick to bounding it from below. So what we must do is return to the definition of the function itself, and play with it as best we can.

Notice, due to the definition of Floor, we have the following inequality.

$x - 1 < Floor[x] \leq x$

Making use of this, we can bound the summation as follows

$\sum_{k = 0}^n log_{10} \frac{n!}{(n-k)!k!} < \sum_{k = 0}^n Floor[log_{10} \frac{n!}{(n-k)!k!} ] + 1 \leq \sum_{k = 0}^n log_{10}\frac{n!}{(n-k)!k!} + 1$

Just looking at that, it's clear that getting a grip on

$\sum_{k = 0}^n log_{10} \frac{n!}{(n-k)!k!}$

Would be pretty useful. Note that, following the rules of summations and logarithms, we can do the following.

$\sum_{k = 0}^n log_{10} \frac{n!}{(n-k)!k!} = \sum_{k = 0}^n \frac{log \frac{n!}{(n-k)!k!}}{log 10}$

$\sum_{k = 0}^n log_{10} \frac{n!}{(n-k)!k!} = \frac{1}{log 10} \sum_{k = 0}^n log \frac{n!}{(n-k)!k!}$

So, all we really need to think about is

$\sum_{k = 0}^n log \frac{n!}{(n-k)!k!}$

Which is convenient for me, since I don't want to write out all those 10's. This next part takes some finagling, but it comes out very nicely.

Now, following the rules of logarithms, log(a) + log(b) = log(a*b). Applying that to the summation above, we get that the sum of the logarithms equals the logarithm of the products of the terms.

$\sum_{k = 0}^n log \frac{n!}{(n-k)!k!} = log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} })$

But, expanding out that product, it has a rather nice form.

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = log({ \frac{n!n!n!...n!}{0!n!1!(n-1)!....(n-1)!1!n!0!} })$

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = log({ \frac{ {(n!)}^{n+1} }{ {(0!1!2!....(n-1)!n!)}^2 })$

Then, using the rules of logarithms again, like log(a/b) = log(a) - log(b), and log(aⁿ) = n*log(a), we can simplify that further...

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = log({ {(n!)}^{n+1} }) - log({ {(0!1!2!....(n-1)!n!)}^2 })$

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = (n + 1)log(n!) - 2 log(0!1!2!....(n-1)!n!)$

It becomes convenient to note though, that 0! = 1, and can hence be dropped to give

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = (n + 1)log(n!) - 2 log(1!2!....(n-1)!n!)$

Now :) The expression 1!2!3!....n! is actually very interesting. Because it can be factored very nicely. Remember that j! = 1*2*3*...*j. So, writing out the product...

1!2!3!....n! = (1)*(1*2)*(1*2*3)*...*(1*2*3*...*(n-1)*n)

1!2!3!....n! = 1ⁿ*2^n-1*3^n-2*...*n¹

In general, what you get is that

$1!2!3!...n! = \prod_{k = 1}^n k^{n - k + 1}$

Substituting that in, we now have

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = (n + 1)log(n!) - 2 log( \prod_{k = 1}^n k^{n - k + 1} )$

Then, using logarithms again, we can use the substitutions

$log(n!) = \sum_{k = 1}^n log(k)$

$log( \prod_{k = 1}^n k^{n - k + 1} ) = \sum_{k = 1}^n log(k^{n - k + 1}) = \sum_{k = 1}^n (n - k + 1) log(k)$

And it becomes...

$log({ \prod_{k = 0}^n \frac{n!}{(n-k)!k!} }) = (n + 1)({\sum_{k = 1}^n log k}) - 2 ({\sum_{k = 1}^n (n - k + 1) log k})$

Which we can simplify, grouping the summations, to a rather neat

$\sum_{k = 1}^n (2k - n - 1) log k$

To summarize then, plugging that back in as above, what we've established is that

$\frac{1}{log 10} \sum_{k = 1}^n (2k - n - 1) log(k) < \sum_{k = 0}^n Floor[log_{10} \frac{n!}{(n-k)!k!} ] + 1$

This lower bound is really nice because it looks exceedingly well behaved. We have no factorials to deal with, no crazy functions defined in terms of god knows what ... it seems relatively normal.

But it is still difficult to calculate, and doesn't give us a good, usable bound on the function we're looking for. So what we're going to do is approximate the summation by integrals.

At this point, I've been writing out the mechanics of the work pretty explicitly, because I thought that it involved a couple of neat mechanizations and substitutions. It really gets rather dry from here on, so I'm going to gloss over the worst of the details.

So, we want to approximate the sum by integrals. This is quite reasonable. Indeed, integrals were originally approximated by sums, and we're just doing the reverse, since things can be nicer to integrate than to sum explicitly.

First, we break the function up like so,

$\sum_{k = 1}^n (2k - n - 1) log(k) = 2 \sum_{k = 1}^n k log(k) - (n + 1) \sum_{k = 1}^n log(k)$

We want to approximate the summation from below, so as to produce a lower bound on our lower bound. Through a judicious use of integration, we have that

$\sum_{k = 1}^n log(k) \leq \int_1^{n+1} log(x) dx$

$\sum_{k = 1}^n k log(k) \geq \int_0^n x log(x) dx$

Applying these, we have

$\sum_{k = 1}^n (2k - n - 1) log(k) \geq 2\int_0^n x log(x) dx - (n + 1) \int_1^{n+1} log(x) dx$

$\sum_{k = 1}^n (2k - n - 1) log(k) \geq n + \frac{n^2}{2} + n^2 log(\frac{n}{1 + n}) - (1 + 2n)log(1 + n)$

So, if DL(n) is the length of the nth row (I'm naming this function now because I don't want to have to keep typing out the stupid summation), we've now produced the bounds

$(n + \frac{n^2}{2} + n^2 log(\frac{n}{n + 1}) - (1 + 2n)log(1 + n))\frac{1}{log 10} < DL(n) \leq log_{10}(2) n^2 + (1 + log_{10}(2))n + 1$

Note though that the upper bound was very crudely arrived at, and is no where close to the accuracy of the lower bound. But I'd like to return to a moment to the discussion of order. From the upper bound, we determined that the function DL(n) grew with order of at most n². Looking at the lower bound now, there are a couple of terms to consider. Remember that the order of a function is going to be the term that grows the fastest as n increases. Looking at the terms of the lower bound, the one that stands out first and foremost is n². But there is also this curious n²log(n/(n+1)). What to make of that, though? Note however that as n increases, n/(n+1) becomes very close to 1. As it approaches 1, log(n/(n+1)) actually approaches 0, and that term is effectively canceled. So as n becomes very large, the main contributing term of the lower bound is the n² term. As DL(n) is bound from above and below by functions of order n², DL(n) must be of order n².

So, as you write out more and more of the triangle, the sides are going to grow outwards in roughly parabolic fashion, moreso as you get further and further down.

For fun, here's a plot of the upper and lower bounds, and the actual function.

That's all I've got : ) Anyway, moving on.

Monday, December 17, 2007

You've Probably Wondered, But Were Afraid to Ask

Other Places to See Us

LaTeX Credit

Math + Comp Sci + Physics

Generic Pro-Science

Atheism + Rationalism

Anti-Crankery

Politics

Crap

Blog Archive

Contributors

Creative Commons License