From mwise@euclid.math.temple.edu Mon Dec 14 21:31:28 1998 Received: (from mwise@localhost) by euclid.math.temple.edu (8.8.5/8.8.5) id VAA17425; Mon, 14 Dec 1998 21:31:27 -0500 (EST) Date: Mon, 14 Dec 1998 21:31:27 -0500 (EST) From: Myra Wise To: Doron Zeilberger cc: Myra Wise Subject: essay Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Length: 6996 Status: RO Myra Wise Bologna December 10, 1998 The Bell Numbers One of the interesting sequences of numbers that was studied in Dr. Zeilberger's Combinatorics class was the Catalan numbers. A sequence which is closely related to the Catalan numbers is the sequence of Bell numbers. The Bell numbers were most extensively explored by Eric Temple Bell. Bell was born in 1883 in Aberdeen, Scotland. He began his studies at the University of London, and eventually came to the United States where he received his Ph.D. from Columbia University in 1912. Dr. Bell went on to teach at several esteemed universities, primarily as a number theorist. He also wrote at least twenty-one books. His writing spanned several genres; from science fiction to numerology to the history of mathematics and mathematicians. The formulation of the Bell numbers requires a little preparatory work. Consider a table on which five plates and five chess pieces sit. How many ways can the five chess pieces be arranged on the five plates? The answer is 5!. There are five different possibilities for the first plate, four for the second, and so on. Now modify the problem and allow any number of chess pieces to be on any plate. In this case, how many ways can the chess pieces be arranged? If there is one piece and one plate then there is only one way that this piece can be placed on this plate. If there are two pieces and two plates, then there are only four ways that these pieces can be arranged. Either there are two pieces on plate A and none on plate B, two on plate B and none on plate A, piece one on plate A and piece 2 on plate B, or vice versa. Now try arranging three pieces on three plates. You should find that there are twenty-seven ways to make this arrangement. Continuing in this way, we have the sequence 1, 4, 27, 256, ... This is the sequence of n raised to the nth power. Therefore, the number of ways that n objects can be arranged on n labelled plates is n to the nth power. Modify the above process again by asking the question: How many ways can n objects be placed on m labelled plates? The answer is m raised to the nth power. To make the problem more difficult, unlabel the plates. In this situation there is only one way to place one piece on one plate. There are two ways to place two pieces on two plates. Either both pieces are on one plate, or one piece is on each plate. Continuing in this way, you will uncover the Bell numbers. These numbers model many situations. For example, we can answer the question of how many ways 2 police officers can handcuff 2 prisoners by using this sequence. Another example would be the number of ways that three nations can form alliances. The first few terms of this sequence are 1, 2, 5, 15, 52, and 203. Bell's interest in this sequence began when he was studying the Maclaurin expansion for e^(e^x). the coefficients of this series are the Bell numbers. When Dr. Bell began studying them, he called them exponential numbers. When John Riordan, a famous combinatorialist, gave the nth such number the name Bn in honor of Bell, these numbers became known as the "Bell nubers." Using the Maclaurin expansion mentioned above, we can find an explicit formula for the nth Bell number. However, there is a much nicer recursive definition. Form a triangle of numbers in the following way: "Start with 1 at the top and 1 below it. Since 1 plus 1 equals 2, place 2 at the end of the second row. Bring the 2 back to start the third row. The sum of 2 and the number above it is 3, and so put 3 to the right of 2. The sum of 3 and the number above it is 5, and so 5 goes to the right of 3. Continue in this manner, observing the following two rules: The last number of each row is the first number of the next row, and all other numbers are obtained by adding the desired number's left neighbor to the number above the neighbor."(Gardner, pg. 29) The triangle looks like this: 1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 ... The nth Bell number is the first number in the (n+1)th row. This triangle can be rotated to get the following difference triangle: 1 2 5 15 52 203 ... 1 3 10 37 151 ... 2 7 27 114 ... 5 20 87 ... 15 67 ... 52 ... . . . This triangle is structured so that the difference of two consecutive entries is the entry below those two entries. This structure is just like that of Pascal's triangle. Here are some of the properties of the "Bell Triangle" in its first form: 1. The sums of the individual rows can be found along the second infinite diagonal. 2. By adding the sum of a row to the Bell number at the end of that row, the next Bell number is obtained. 3. The sum of any three adjacent Bell numbers is always an even number The uses for Bell numbers and the properties of Bell numbers are extensive, and new ones are discovered constantly. For instance, Bell numbers are quite uselful in prime number theory because they tell us how many ways a number with distinct prime factors can be factored. One of the interesting properties of the Bell numbers is that the (n+k)th Bell number is congruent modulo p to the sum of the kth and (k+1)th Bell numbers. The fascinating application of Bell numbers which peaked my interest in studying them is their relationship to poetry. The Bell numbers count the number of possible rhyme schemes for a stanza of poetry. A stanza with one line has one possible rhyming scheme. A stanza with two lines has two possible rhyming schemes. A stanza with three lines has five possible rhyming schemes (aaa, aab, aba, abb, abc), and so on. Diagrams of the possible rhyming schemes were first described by Henry Gould. The method for this diagramming was introduced by the Japanese. Each diagram consists of vertical lines representing the lines of the stanza, and horizontal lines joining the lines that rhyme. References: 1. Gardner, Martin. Fractal Music, Hypercards, and More... W. H. Freeman and Co., New York (1992), pg. 24-37. 2. Newman, James R. The World of Mathematics, Volume 1 "Commentary on Gauss", Tempus Books of Microsoft Press, Redmond, Washington (1988) pg. 289.