Tuesday, December 22, 2009

the Lucas Number Triangle

Polygonal numbers have been a recurring topic on this blog (starting with the first post) and although they might eventually exhaust me, I've realized that I'll never exhaust their recreational possibilities.

One interesting way to look at polygonal numbers is to arrange them into number triangles - for a particular \(k \geq 3 \) you can do this by arranging the k-polygonal numbers in diagonals by dimension. If you do this with the triangular numbers, you get Pascal's Triangle. Said another way, the diagonals of Pascal's triangle list  the various dimensional extensions of triangular numbers: the 3rd diagonal gives the usual 'triangular numbers', the 4th diagonal gives the tetrahedrals (now to be referred to as the 'days of Christmas numbers'), the 5th diagonal gives the triangulo-triangular numbers, etc. Each diagonal lists the finite differences of the diagonal below it, so the second diagonal of Pascal's triangle gives what we could call the 'one dimensional triangulars' or the Naturals, and the first diagonal gives us 'zero dimensional triangulars' - the constant sequence of 1s.

The symmetry of Pascal's Triangle allows you to see the various dimensions of the triangular numbers in both the diagonals that slope downward from left to right, and those that slope downward from right to left. However, when you do the same sort of construction with \(k \geq 4 \) you loose this symmetry, and have to pick a direction. When I tried this (described here and here), I chose to make my generalized k-polygonal Pascal Triangles 'left handed', so that the k-polygonal numbers appear in the diagonals sloping downward from right to left. The diagrams below show the left-handed triangles for the square (k = 4) and pentagonal numbers (k = 5).

Using \( \left[\begin{array}{c}n\\r\end{array}\right]^{\mathcal{L}}_{k} \) to denote the entry in the nth row of the rth diagonal column of the left-handed k-polygonal number triangle, we can express this construction recursively in a way that is very similar to the usual Pascal Triangle definition:

We can express the terms directly using the binomial coefficients:

Instead of making the triangles left-handed, we could instead make them right-handed like these:

Where now all the k-polygonal numbers appear as diagonals sloping downward from left to right. These are almost mirror images of the left-handed variety, and to be honest, I am not sure what the correct value is for the topmost entry. In these formulations, for both the left-handed and right-handed variety, the topmost entry is determined by the value in the far-right column.

Using \( \left[\begin{array}{c}n\\r\end{array}\right]^{\mathcal{R}}_{k} \) to denote the entry in the nth row of the rth diagonal column of the right-handed k-polygonal number triangle, we can express the construction recursively:

And, just as with the left-handed variety, we can express the terms using binomial coefficients:

For the case where k=3, it is easy to see that both our left-handed and right-handed k-polygonal Pascal Triangles are equal to the usual Pascal Triangle.

It turns out that for the right-handed k = 4 case ('square' polygonals) gives a well-known number triangle called the Lucas Number Triangle.

In the Lucas Number Triangle you find the square numbers, the square-based pyrimidal numbers, and all of the higher-dimensional versions of the same, just as you find the triangular, pyrimidal, and higher-triangular numbers in Pascal's Triangle

In the same way that you can find the Fibonacci numbers by summing left-to-right upward sloping diagonals in the regular Pascal's Triangle, you can find Lucas numbers (see also Wikipedia) by summing  left-to-right upward sloping diagonals in the Lucas Number Triangle. Lucas numbers are a generalization of the Fibonacci sequence - the Fibonacci sequence starts with the numbers \( f_0 = 0 \), \( f_1=1 \), and proceeds according to the rule \( f_n = f_{n-1} + f_{n-2} \); the Lucas sequence starts with the numbers \( f_0 = 2 \), \( f_1=1\), and follows the same generating rule as the Fibonacci sequence.

Just as the entries in Pascal's Triangle can be interpreted as coefficients in the expansion of the binomial \( (a+b)^n \), the entries in the Lucas triangle can be seen to be coefficients in the expansion of the binomial \( (a+2b)(a+b)^{n-1} \) for \( n \geq 1 \).

In general, right handed k-polygonal Triangles give generalized "Gibonacci Numbers" - number sequences that follow the usual Fibonacci rule but with different first terms, in this case, \( G_0=k-2 \) and \( G_1=1 \). These Gibbonacci Number Triangles have entries whose rows give the coefficients of \( (a+ (k-2)b)(a+b)^{n-1} \) for \( n \geq 1\).

A nice overview of the Lucas and Gibonacci Triangles and an interesting combinatorial interpretation of their entries is given in Arthur Benjamin's The Lucas Triangle Recounted.

Friday, December 18, 2009

mathematical nature and nurture

Like so many things these days, this post was inspired by a celebrity (well, math celebrity) tweet. This one pointed to a letter published in the October issue of Nature.

The Nature article that du Sautoy referenced is here, and several other related papers by the same group of researchers are here and here. At some point soon I hope to write a bit more about this research, but for now I want to go back to the important issue that I think is raised by du Sauytoy's provocative tweet.

On its most essential level, the question posed by du Sautoy asks if some are born with better mathematical ability than others. This is going perhaps a step further than what was actually asked, but this is a step that many are likely to take, given that a positive answer to this question fits closely with many people's assumptions about mathematics.

Genetic gifts certainly play a role in how our lives turn out, and our ability to do certain kinds of math are not exempt from this. Temperament, attention-span, the gene responsible for holding a pencil properly, and other geneticly influenced factors may equip some more than others for mathematical activiites.

However, belief in the stronger version of this idea, that some are born with math ability while others are not, is one that has plagued the teaching and learning of mathematics for a long time, and may be responsible for excluding vast numbers of people from feeling mathematically competent.

What I believe, and will likely continue to believe until that belief is falsified by convincing evidence, is that mathematics is part of our shared cultural heritage, and is something that we can all lay claim to. Certainly there is much mathematics that I will never understand, but the basics, the fundamentals, and even the spirit that guides the most arcane mathematical research, is available to everyone.

Unfortunately, many feel excluded from the common heritage of mathematics, and part of the reason behind this are beliefs about the nature of mathematics. One belief that causes many to be excluded is precisely the one that states that some are born with the ability to do mathematics and some are not, an assertion that in many cases becomes self-fulfilling prophesy.

Many have written about harmful beliefs about the nature of mathematics - the most harmful being the idea that some are excluded from doing math at birth. Alan H. Schoenfeld has written about how metacognitive concepts like this influence our ability to learn and to teach mathematics. John Mighton has written about the question of math ability being hard-wired in his book The Myth of Ability. In the afterword to his book (online here), Mighton writes how his experience with JUMP tutoring has made him hopeful about challenging these commonly held beliefs - in his Elements of Humanity interview, he calls the belief that only some are born with mathematical ability to be an absurd illusion.

Although the study mentioned by du Sautoy was about measuring individual differences, it is useful to keep in mind how results like these are often misapplied to whole groups of people. In the classic book on group differences and intelligence testing, The Mismeasure of Man, Stephen Jay Gould cautions us:

We pass through this world but once. Few tragedies can be more extensive than the stunting of life, few injustices deeper than the denial of an opportunity to strive or even to hope, by a limit imposed from without, but falsely identified as lying within.

Tuesday, December 15, 2009

a Catalan number triangle fractal

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845...
                                                     the Catalan Numbers, OEIS: A000108

Catalan numbers occur in a surprising number of counting scenarios, such as counting the ways convex polygons can be cut into triangles, or counting how many ways you can write down a  legal list of brackets (a legal list of brackets is something like this: {{}{}}). In The Book of Numbers, Conway and Guy present at least eight different scenarios that the Catalans count, and Richard Stanley has listed 173 combinatorial interpretations for them (see the chapter and addendum on his Enumerative Combinatorics website). What unites these seemingly different scenarios is their recursive character (polygons contain smaller polygons, and lists of brackets contain smaller lists).

The Catalan numbers can be found in Pascal's Triangle  in a few ways. If you take each 'middle' element and subtract its adjacent entry, you get a Catalan number. Also, if you take a middle element and divide it by its position in the list of middle terms (e.g. divide the 5th middle term by 5), you will get a Catalan number. But Catalans have their very own number triangle too.

Starting, as with Pascal's Triangle, with a 1, the Catalan Triangle is generated using the rule that each element is equal to the one above (in this picture, above on the right slanting diagonal) plus the one to its left (where 'missing' numbers are zero).  The Catalan numbers show up both as row sums and as the last entry in each row.

The rule for creating the Catalan Triangle sounds like a 'slanted' version of the generating rule for the Pascal Triangle (where to produce a number you take the sum of the two above its position), and if you look at the fractal that is created by looking at the Catalan Triangle's values mod 2 (so that even numbers are replaced with 0 and odd numbers are replaced with 1), you get a slanted version of the Sierpinski fractal that you get from doing the same with Pascal's Triangle.

The fractals that sometimes arise from looking at modular values in a number triangle provide a visual clue to the divisibility properties of the numbers in the triangle, and also illustrate some aspects of the generating rule that is used to create the triangle. The Catalan fractal above was made with this Tinkerplots file using this data. The Pascal Traiangle was drawn with Tinkerplots using this file as described here.

Thursday, December 10, 2009

unfolding surprises

Here are two videos of some surprising unfoldings.

The first is from New Scientist, posted as part of this article. This shows some unfoldings of a polyhedron with a large number of sides (enough sides so that the polyhedron resembles a sphere).

The second (which may fail to show up in your reader) is from Erik Demain's site. This shows several unfoldings (and refoldings) of a cube.

Tuesday, December 8, 2009

more folds

PBS has launched a new Between the Folds website - the online quiz where you have to match the crease pattern to a finished model is neat.

I've mentioned Between the Folds in previous posts (here and here) - if you haven't seen it yet and you get PBS, you really should check it out.

A lot of the origami models featured in the film can also be seen in Origami USA's gallery. If you are looking for something to fold after watching the film, you should check out the diagrams from Origami USA as well.

Monday, December 7, 2009

philosophical transactions

TierneyLab at the NYT has a post about a really nice online exhibit celebrating 350 years of the Royal Society.

The exhibit, Trailblazing, is presented as a timeline with links to some key scientific papers that were presented in The Philosophical Transactions of the Royal Society. Mathematics plays a big role in many of the interesting primary sources presented in the exhibit.

Here are a few of the more overtly math-related papers in the exhibit:

Isaac Newton's letter on his theory on light and colours from 1672.

John Hadley's paper describing a new instrument for measuring angles from 1731.

Bayes's posthumus essay on chance and proability of 1763.

Davies Gilbert's paper on the mathematical theory of suspension bridges from 1826.

Wednesday, December 2, 2009

a curious population model

Dave Richeson of Division by Zero has recently posted a very nice GeoGebra applet for the interesting discrete logistic equation.

\[p(n + 1) = Mp(n)(1 - p(n))\]
The discrete logistic equation is a simple model of population growth within a closed environment. p(n) is a decimal between 0 and 1 representing the fraction of the maximum population that has been reached (initial seed value of p(0) = 0.001), and M is the "Malthus factor" a multiplier that represents the fertility of the population (value between 1 and 4). Different values of M determine whether the population dies out, achieves a stable level, or fluctuates.

This simple discrete dynamical system is also easy to implement and explore in Fathom. You only need a slider (for the M value) and a couple attributes (you may want to add others as you explore).

1. In a new Fathom document, create a slider M
2. Add a new Collection, and create an attribute generation, and an attribute population.
3. Provide this formula for generation: caseIndex - 1
4. Provide this formula for population: if (generation=1){0.001, M*prev(population)*(1-prev(population))
5. Add cases in to represent the generations of the population (say 20 or so)
6. Create a graph with population as the y attribute and generations as the x attribute
7. Explore how the graph changes as M varies between 0 and 4.

An example Fathom file is here.

When the population is stable, you have a nice curve like one below.

When the Malthus factor is higher, the population becomes less stable - overcrowding and then dying back.

This population model is mentioned in Mark Haddon's, The Curious Incident of the Dog in the Night-time, whose protagonist is a young mathematician with some behavioural difficulties. See the MAA online review of the book here, which includes pointers to other places to learn about the logistic equation.