Fibonacci numbers, 8

I am at the Southeastern Conference this week; I will say more about this later. Now, I simply want to add a post to my sequence on Fibonacci numbers, based on a lovely talk by Bruce Sagan. What I have to say here is a small subset of Bruce’s talk; you can find the slides on his website.

As everybody knows, the factorial function is defined for positive integers n by the rule that n! is the product of the integers from 1 to n. (By convention, 0!, which is an empty product, is taken to be 1.) Then the binomial coefficient, which I will write here as Bin(n,k), is defined for 0 ≤ k ≤  to be n!/k!(nk)!.

In passing, although this is the definition that students prefer (it is compact and doesn’t take up too much space in the brain), I consider it to be a lousy definition, for various reasons, including computational. Try computing Bin(1000,2) on your calculator using this definition!

It is not clear à priori that the value defined in this way is necessarily a positive integer! Bruce pointed out that there are two standard ways to demonstrate this:

  • by proving the recurrence relation Bin(n,0) = Bin(n,n) = 1 and Bin(n,k) = Bin(n−1,k−1)+Bin(n−1,k) for 0 < k < n;
  • by giving an interpretation of the binomial coefficient as counting the size of a finite set (the example I will use here, not the first you would think of, is that Bin(n,k) is the number of lattice paths from the origin to the point (nk,k) using unit steps in either the easterly or the northerly direction). [Exercise: match this up with your preferred interpretation!]

Now we are going to play a game, which involves taking the above definitions, and replacing the positive integer n by a term in some other sequence. The game is to find proofs (if it is true) that the terms in the sequence are positive integers.

First up are the Gaussian or q-binomial coefficients. We replace the positive integer n by the q-integer [n] = 1+q+…+qn−1. Now the q-factorial q-Fact(n) is the product of [1], [2], … [n]; the q-binomial coefficient (or Gaussian coefficient) is given by

q-Bin(n,k) = q-Fact(n)/q-Fact(k)q-Fact(nk).

This is an integer for integral values of k, indeed it is a polynomial of degree k(nk) with positive integer coefficients. Again, this is not immediately obvious. But it can be proved by analogues of the two methods above:

  • by proving the recurrence relation q-Bin(n,0) = q-Bin(n,n) = 1 and q-Bin(n,k) = qk−1q-Bin(n−1,k−1)+q-Bin(n−1,k) for 0 < k < n;
  • by giving a generating function interpretation: each lattice path counted by the binomial coefficient sits inside a n−k-by-k rectangle; weight it with qA, where A is the area above the path.

So far, so well-known (or at least it should be!) But what if we replace n by the Fibonacci number Fn? (We have to worry about the initial conditions of the recurrence, which we take to be F1 = F2 = 1. Other choices, as described here, don’t work!) Now we define the Fibonacci factorial or Fibotorial, by taking FibFact(n) to be the product of the Fibonacci numbers from F1 to Fn; and the Fibonacci binomial or Fibonomial coefficients by

FibBin(n,k) = FibFact(n)/FibFact(k)FibFact(nk).

For example, FibFact(6) = = 240, and FibBin(6,3) = 240/2.2 = 60.

As usual, we have the question, why are the Fibonomial coefficients integers? Again, as usual, there are two approaches.

The recurrence relation is FibBin(n,0) = FibBin(n,n) = 1 and

FibBin(n,k) = Fnk−1FibBin(n−1,k−1)+Fk+1FibBin(n−1,k)

for 1 < k < n. (The proof is a nice exercise in Fibonacci number manipulation.)

The counting interpretation is more obscure. There are three of these, the simplest due to Bruce Sagan and Carla Savage. Take, as before, a lattice path inside the nk-by-k rectangle. We weight this configuration by the number of ways that the rectangle can be tiled according to the following rules:

  • The tiles are monominoes and dominoes, that is, 1-by-1 and 1-by-2 rectangles.
  • In the part of the diagram above the lattice path, all dominoes are horizontal.
  • In the part of the diagram below the lattice path, all dominoes are vertical; and the bottom tile in each column is a domino. (If this condition cannot be satisfied, then the number of tilings is zero.)

Now the theorem is that if we sum the weights of all the configurations inside the nk-by-k rectangle, we obtain FibBin(n,k).

The implicit question here is, what other sequences of integers give integral values for the corresponding binomial coefficients, and can we find counting interpretations of them?



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , . Bookmark the permalink.

3 Responses to Fibonacci numbers, 8

  1. volkan says:

    Is there more information about Fi bocatalan numbers?

  2. Pingback: Weekly links for March 25 | God plays dice

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s