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

by

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!

Tags:

### 3 Responses to “One, Two, Three, Four, Six [Again. And then again!]”

1. Dave Richeson Says:

If you haven’t seen it, you should watch Polya’s “Let us teach guessing” (1965). I showed it to my Discrete Math class last week. Polya gives a great example of a failed pattern: the maximum number of regions into which n planes can divide space is (starting with n=0) 1, 2, 4, 8, 15(!)…

David Bressoud wrote about it recently in his MAA column http://www.maa.org/columns/launchings/launchings_12_07.html

2. mike4ty4 Says:

“one 3¢ coin and two 2¢ coins” should be “one 3¢ coin and one 2¢ coin” The first makes 7¢, the second makes 5¢, which is what was desired.

3. Ξ Says:

Thanks! I just updated it.