## Archive for October 26th, 2008

### One, Two, Three, Four, Six [Again. And then again!]

October 26, 2008

I’m teaching a math course for non-majors, and right now we’re talking about Induction versus Deduction. I have some neat examples of Induction, like the fact that the US presidents elected in 1840, 1860, 1880, 1900, 1920, 1940, and 1960 all died in office, but Ronald Reagan did not. I’ve found, though, that these cultural examples don’t carry as much weight for the students as a mathematical pattern that continues for a while and then stops. Hence my interest in Patterns that Fail.

In this vein, last week I looked at how many necklaces could be made out of N beads, where the beads could be two different colors, and it turns out that the number of necklaces follows the pattern one [for 0 beads], two [for 1 bead], three [for 2 beads], four [for 3 beads], and then six [for 4 beads]. But there’s another setup that gives the same pattern 1, 2, 3, 4 before jumping to 6. This setup involves covering 3xN rectangles with dominoes that are 1×3 or 3×1 (tri-ominoes? But I think those are L-shaped).

If you start with N=2 (to avoid the sequence beginning 1,1,…), there is one way:

If N=3, there are two ways:

If N=4, there are three ways:

If N=5, there are four ways:

But if N=6, suddenlythere are six ways!

After that, the pattern grows in larger steps [following the recursive pattern a(n)=a(n-1)+a(n-3)].

Incidentally, there’s another pattern that starts off 1, 2, 3, 4, 6, ….: the number of ways to make N cents in 1¢, 2¢, 3¢, 5¢, 10¢, 20¢, 25¢, 50¢ and/or 100¢ coins, all of which are or have been valid US coins. For example:

• 1¢ can only be made with a 1¢ coin. [1 way]
• 2¢ can be made with two 1¢ coins or 1 2¢ coin. [2 ways]
• 3¢ can be made with three 1¢ coins, a 1¢ and a 2¢ coin, and a 3¢ coin. [3 ways]
• 4¢ can be made with four 1¢ coins, two 1¢ and one 2¢ coins, one 1¢ and one 3¢ coins, or two 2¢ coins. [4 ways]
• 5¢ an be made with five 1¢ coins, three 1¢ coins and one 2¢ coin, two 1¢ coin and one 3¢ coins, one 1¢ coin and two 2¢ coins, one 3¢ coin and two one 2¢ coins, or one 5¢ coin. [6 ways]

This sequence continues 8, 10, 13, 16…so it’s different than the previous sequences, giving me lots of examples to choose from in class!