Catalan Numbers

Here is a simple problem to try out. Draw a 4x4 array of dots. Now construct all the paths possible from the bottom left to the upper right corners by moving only upward or to the right, (think of rook moves on a chess board). Go ahead, there are not that many (only 6 choose 3). Now draw the diagonal from the start corner to the stop corner. How many of the paths never cross the line? You can touch it, but not cross. Now generalize the answer, what if the array was nxn. AFTER you have tried this, read on..

Catalan Numbers first appeared in disguise in a problem Euler first proposed to Christian Goldbach in 1751. The problem is now called "Euler's Polygon Division Problem", and asks, in how many ways may
a plane convex polygon of n+2 sides be divided into triangles by diagonals. Euler gave a solution that looked like The numbers in the sequence are now called Catalan Numbers

The numbers in the Catalan sequence also answer questions such as the one at the top of the page. In how many paths can you move from the origin of a coordinate axis to the point (n,n) if each move consists of either an upward move or a move to the right one unit between two lattice points and you cannot cross the line y=x . Another application (or the same application viewed differently) answers the question in how many ways can 2N beans (for an application, think votes) be divided into two containers if one container can never have less than the second?

The sequence of numbers is given by 1,2,5,14,42,132 ... or
in general by the function . It may seem hard to figure out where the 1/(n+1) comes from in the formula. I found a really nice explanation with graphics at this Wikipedia page(go down to the third proof).

The numbers also can be found from Pascal's triangle by taking (2n Choose n) - (2n Choose n+1). These are two adjacent numbers in each even numbered row

The function is named for Eugene Catalan of Belgium (1814-1894).

The Writer's Desk...

In Charlotte, N.C. there is a memorial in front of the ImagiOn Center to a writer named Rolfe Neill called “The Writer’s Desk” ..."Rolfe Neill, was a publisher of The Charlotte Observer and The Charlotte News, Larry Kirkland created whimsical sculptures of granite pencils, rubber stamps, a typewriter keyboard, and a tower of books to celebrate Neill’s passion for truth, the written word and the writing profession. Located on the Plaza of ImaginOn – a children’s learning center and partnership of the Public Library of Charlotte-Mecklenburg County and the Children’s Theatre of Charlotte, the artwork “serves as a place for people to gather, reflect, sit quietly or noisily, or create a spontaneous performance at an outdoor gathering,” said Kirkland. "

I especially loved one quote

In an article by John Brock, another Southern Newsman, I found an interesting quote from Neill..,

"Rolfe Neill, retired publisher of the Charlotte Observer, informed us one day that of the more than 600,000 words in the English language, only 43 words constitute 50 per cent of everything we say or write! This is not limited to Southerners but applies to the rest of Americans as well.

In fact, only nine words make up 25 per cent of all that we communicate. These words are: and, be, have, it, of, the, to, will and you. In this self-centered world, it is surprising that “I” is not in there somewhere.

Check it out. The frequency of the nine words in the following documents is: The Boy Scout oath, 25%; the Marines Hymn, 35.4%; The Miranda rights, 32.1%; the first five verses of St. Paul’s letter to the Galatians, 23.2%. You get the idea."

Triangular Numbers

A friend reminded me that I hadn't explained triangular numbers here or on my web site, so taking care of both in a limited way today...

The triangular numbers are known back to before Pythagoras (500ish BCE). They are simply the sums of the natural or counting numbers 1 + 2 + ... + n is the n^th triangular number, so the sequence of triangular numbers is 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, etc. An explicit formula for the triangular numbers is T_n = n(n+1)/2. For example, T₁₀= (10)(11)/2 = 55.

The triangular numbers appear as the third number in each row of Pascal's triangle.

This means that they are also expressible as (n+1 choose 2)

One of the interesting properties of the triangular numbers is that any two consecutive ones form a square number.... in the image below, T₄ (in red) is added to T₅ in blue, to form S₅, the fifth square number or 25.

It is also known that any even perfect number, and all the ones we know of are even, is a triangular number. The first few are 6, 28, 496.

It is also known that the digit root in base ten of any triangular number is either 1 or 0. That means that all triangular numbers are either divisible by three, or have a remainder of one when divided by three. An easy test of any number to see if it is triangular is to multiply by eight and add one... if the result is a perfect square, then the number is triangular.

It is also interesting that the square of a triangular number T_n is equal to the sum of the cubes of the natural numbers from 1 to n,

....

And one final note on the triangular numbers, the infinite sum of their reciprocals is an integer, ... how sweet, and unexpected, is that? I think you can figure out what it is..but if you get stuck and need a hint, or the answer... just drop a note

More...Things I Learned on the Road

More Things I learned on the Road.... The picture above is for those who have always secretly wondered what I would look like with long flowing locks... Newsflash!! Spanish Moss is NOT Spanish...AND (wait for it.....) it is NOT moss... talk about bad names... The French gave it the "Spanish" name as an insult???? Guess you had to be there. Probably an old Monty Python skit about that, "Your Moss is Spanish and your Mother smells of Elderberries!!!". Ok, and the moss part, NOPE... its an epiphitic (gets its food from the air) bromeliad (cousin of the pineapple). Now you know

I also was reminded that people are really strange. In the middle of the road in Enterprise Alabama, there is a statue to the Boil Weevil . Now if you are really a city child and know nothing of the agricultural history of the south, the weevil wiped out many cotton farmers in the south around the beginning of the 20th century. The idea of a monument to the weevil in Alabama would be like a giant grasshopper in Salt Lake City, Utah.

I also continued my road heroics on Jekyll Island (which used to be called Jeykl Island, but someone thought the extra L would be better ). I saved a Loggerhead Turtle and set him free. Ok, I didn't do it all by myself. The Georgia Sea Turtle association was releasing a ten year old (about 150 pounds) that had been kept in the Georgia Acquarium since its egg-ship. I did happen to be in the crowd watching as Dylan, that was his name, went free. He seemed to need a little encouragement as he turned back to shore several times. Eventually prompted by the workers in the waters urging he swam out to sea. Perhaps he was also encouraged by the shouting on shore as the crowd yelled "DIll - Enn.. Dill Enn... repeatedly, especially if he was as confused as I was at first. I thought I had fallen in with gourmets of the turtle soup variety yelling "Kill him, kill him..' eventually I got it straight, and hope Dylan also knew we were NOT trying to have him for supper.

More stuff I learned, don't explain palindromes while driving through Elba, Alabama. As I came into town the name of the town reminded me of one of the first palindromes I ever leaned (OK, second, the first was Madam I am Adam.. read it backwards if you don't know what a palindrome is); Able was I ere I saw Elba. In math, we call numbers like 121 or 1331 or 14641 (surely you recognize the powers of 11) palindromic numbers. We even refer to a polynomial like 1x²+2x+1 as palindromic (look at the coefficients). As I was making sure my wife understood, I saw flashing lights in the rear view mirror... apparently the speed through town was only 25 mph and I was, as the kind officer explained holding thumb and finger an inch apart, "A little over." It was Sunday Morning, and in the spirit of Christian charity, he let me off with a warning.... Thank goodness I was not in Georgia.. I might still be rotting in Macon County Correctional Institute for Out of state drivers.