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
twoone 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: triominos
360 
November 2, 2008 at 10:29 pm |
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
September 22, 2013 at 4:45 pm |
“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.
September 22, 2013 at 5:37 pm |
Thanks! I just updated it. 🙂
January 10, 2017 at 9:27 pm |
This site/posting is quite old, so I am not sure if you still monitor it. Nevertheless, I am failing to see how your bead example works. For three beads (say Black and White), would each of the following be a distinct necklace?
BBB
BBW
BWB
WWB
WBW
WWW
This would indicate that the pattern would be 1 (0 beads), 2 (1 bead), 3 (2 beads), 6 (three beads). What am I not understanding?
January 10, 2017 at 10:25 pm |
We’re still around! The assumption in reference to the necklace problem is that it’s a circular necklace where the beads move freely, so BBW and BWB (as well as WBB) would actually be a single example, as would WWB and WBW (and BWW). Essentially, you can have 0, 1, 2, or 3 black beads. Once you get to 4 beads the number of possibilities jumps because if you have 2 beads of each color, even with the circular necklace they might be next to each other or the colors might alternate.
January 11, 2017 at 6:37 am |
Thank you! I was envisioning a clasp to hinder the beads from moving. I realized that BBW and WBB were the same by simply reversing the necklace, but wasn’t allowing for bead movement “over the top.” Thank you for the clear response.
January 11, 2017 at 6:54 am
My pleasure! And I’m glad you explained where you got your numbers – I wasn’t sure why you included some combinations but not others. I like the designation of a clasp versus a solid chain (or very small clasp).