Source: http://www.xkcd.com/936/

## All posts tagged **combinatorics**

# Password strength and combinatorics

*Posted by John Quintanilla on April 20, 2014*

https://meangreenmath.com/2014/04/20/password-strength-and-combinatorics/

# Permutations and Combinations

Courtesy of Math with Bad Drawings is a nice derivation of the formulas for permutations and combinations:

*Posted by John Quintanilla on March 1, 2014*

https://meangreenmath.com/2014/03/01/permutations-and-combinations/

# Fun lecture on geometric series (Part 2): Ways of counting money

Every once in a while, I’ll give a “fun lecture” to my students. The rules of a “fun lecture” are that I talk about some advanced applications of classroom topics, but I won’t hold them responsible for these ideas on homework and on exams. In other words, they can just enjoy the lecture without being responsible for its content.

This series of posts describes a fun lecture that I’ve given to my Precalculus students after they’ve learned about partial fractions and geometric series.

In the 1949 cartoon “Hare Do,” Bugs Bunny comes across the following sign when trying to buy candy (well, actually, a carrot) from a vending machine. The picture below can be seen at the 2:40 mark of this video: http://www.ulozto.net/live/xSG8zto/bugs-bunny-hare-do-1949-avi

How many ways are there of expressing 20 cents using pennies, nickels, dimes, and (though not applicable to this problem) quarters? Believe it or not, this is equivalent to the following very complicated multiplication problem:

On the first line, the exponents are all multiples of 1. On the second line, the exponents are all multiples of 5. On the third line, the exponents are all multiples of 10. On the fourth line, the exponents are all multiples of 25.

How many ways are there of constructing a product of from the product of these four infinite series? I offer a thought bubble if you’d like to think about it before seeing the answer.

There are actually 9 ways. We could choose from the first, second, and fourth lines while choosing from the third line. So,

There are 8 other ways. For each of these lines, the first term comes from the first infinite series, the second term comes from the second infinite series, and so on.

The nice thing is that each of these expressions is conceptually equivalent to a way of expressing 20 cents using pennies, nickels, dimes, and quarters. In each case, the value in parentheses matches an exponent.

- : 2 dimes (20 cents).
- : 2 nickels (10 cents) and 1 dime (10 cents)
- : 4 nickels (20 cents)
- : 10 pennies (10 cents) and 1 dime (10 cents)
- : 15 pennies (15 cents) and 1 nickel (5 cents)
- : 10 pennies (10 cents) and 2 nickels (10 cents)
- : 5 pennies (5 cents) and 3 nickels (15 cents)
- : 20 pennies (20 cents)
- : 5 pennies (5 cents), 1 nickel (5 cents), and 1 dime (10 cents)

Notice that the last line didn’t appear in the Bugs Bunny cartoon.

Using the formula for an infinite geometric series (and assuming ), we may write the infinite product as

When written as an infinite series — that is, as a Taylor series about — the coefficients provide the number of ways of expressing that many cents using pennies, nickels, dimes and quarters. This Taylor series can be computed with Mathematica:

Looking at the coefficient of , we see that there are indeed 9 ways of expressing 20 cents with pennies, nickels, dimes, and quarters. We also see that there are 242 of expressing 1 dollar and 1463 ways of expressing 2 dollars.

The United States also has 50-cent coins and dollar coins, although they are rarely used in circulation. Our answers become slightly different if we permit the use of these larger coins:

Finally, just for the fun of it, the coins in the United Kingdom are worth 1 pence, 2 pence, 5 pence, 10 pence, 20 pence, 50 pence, 100 pence (1 pound), and 200 pence (2 pounds). With these different coins, there are 41 ways of expressing 20 pence, 4563 ways of expressing 1 pound, and 73,682 ways of expressing 2 pounds.

For more discussion about this application of generating functions — including ways of determining the above coefficients without Mathematica — I’ll refer to the 1000+ results of the following Google search:

https://www.google.com/search?q=pennies+nickles+dimes+quarters+%22generating+function%22

FYI, previous posts on an infinite geometric series:

https://meangreenmath.com/2013/09/16/formula-for-an-infinite-geometric-series-part-9

https://meangreenmath.com/2013/09/17/formula-for-an-infinite-geometric-series-part-10

https://meangreenmath.com/2013/09/18/formula-for-an-infinite-geometric-series-part-11

Previous posts on Taylor series:

https://meangreenmath.com/2013/07/01/reminding-students-about-taylor-series-part-1/

https://meangreenmath.com/2013/07/02/reminding-students-about-taylor-series-part-2/

https://meangreenmath.com/2013/07/03/giving-students-a-refresher-about-taylor-series-part-3/

https://meangreenmath.com/2013/07/04/giving-students-a-refresher-about-taylor-series-part-4/

https://meangreenmath.com/2013/07/05/reminding-students-about-taylor-series-part-5/

https://meangreenmath.com/2013/07/06/reminding-students-about-taylor-series-part-6/

*Posted by John Quintanilla on December 2, 2013*

https://meangreenmath.com/2013/12/02/fun-lecture-on-geometric-series-part-2-ways-of-counting-money/

# Fun lecture on geometric series (Part 1): Generating functions

Every once in a while, I’ll give a “fun lecture” to my students. The rules of a “fun lecture” are that I talk about some advanced applications of classroom topics, but I won’t hold them responsible for these ideas on homework and on exams. In other words, they can just enjoy the lecture without being responsible for its content.

This series of posts describes a 50-minute fun lecture — on the topic of generating functions — that I’ve given to my Precalculus students after they’ve learned about partial fractions and geometric series.

To launch the topic: In the 1949 cartoon “Hare Do,” Bugs Bunny comes across the following sign when trying to buy candy (well, actually, a carrot) from a vending machine. The picture below can be seen at the 2:40 mark of this video: http://www.ulozto.net/live/xSG8zto/bugs-bunny-hare-do-1949-avi

Notice that the price of candy from vending machines have increased somewhat since 1949. (Elsewhere in the cartoon, the price of a ticket to the movies was listed as 55 cents for adults, 20 cents for children, and 10 cents for rabbits.)

I wasn’t alive in 1949, but I vividly remember seeing this essentially mathematical problem while watching cartoons after school in the late 1970s. Now that I’m a little older — and can freeze-frame the above sign — I can see that the animators actually missed one way of expressing 20 cents. More on that later.

**Definition**. The *generating function* of a sequence is defined to be an infinite series whose coefficients match the sequence.

**Example #1.** Consider the (boring) sequence . The generating function for this sequence is

If , then , using the formula for an infinite geometric series.

**Example #2. **For the slightly less boring sequence of , the generating function is

,

which (if ) is .

**Example #3.** Suppose if $0 \le n \le 10$ and for . Then the generating function is

.

It turns out that the above problem from the Bugs Bunny cartoon can be viewed as a generating function. Let denote the number of ways that cents can be formed using pennies, nickels, dimes, and quarters? The Bugs Bunny cartoon is related to the value of . What about one dollar? Two dollars? I’ll provide the answer in tomorrow’s post.

FYI, previous posts on an infinite geometric series:

https://meangreenmath.com/2013/09/16/formula-for-an-infinite-geometric-series-part-9

https://meangreenmath.com/2013/09/17/formula-for-an-infinite-geometric-series-part-10

https://meangreenmath.com/2013/09/18/formula-for-an-infinite-geometric-series-part-11

*Posted by John Quintanilla on December 1, 2013*

https://meangreenmath.com/2013/12/01/fun-lecture-on-geometric-series-part-1-generating-functions/

## Top Posts & Pages

- Square roots and logarithms without a calculator (Part 3)
- Importance of the base case in a proof by induction
- Engaging students: Synthetic Division
- Engaging students: Rational and Irrational Numbers
- Engaging students: Inverse Functions
- Engaging students: Equation of a circle
- Exponents and the decathlon
- Engaging students: Combinations
- Exponential growth and decay (Part 2): Paying off credit-card debt
- Full lesson plan: magic squares

## Archives

- July 2019
- June 2019
- May 2019
- April 2019
- March 2019
- February 2019
- January 2019
- December 2018
- November 2018
- October 2018
- September 2018
- August 2018
- July 2018
- June 2018
- May 2018
- April 2018
- March 2018
- February 2018
- January 2018
- December 2017
- November 2017
- October 2017
- September 2017
- August 2017
- July 2017
- June 2017
- May 2017
- April 2017
- March 2017
- February 2017
- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- October 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- February 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013

## Categories

- Algebra I (184)
- Algebra II (281)
- Bases (44)
- Calculus (228)
- Chemistry (9)
- Computer science (9)
- Discrete mathematics (218)
- Elementary (149)
- Engagement (702)
- Geometry (221)
- Guest presenter (427)
- History (54)
- Humor (243)
- News Clips (120)
- Physics (35)
- Popular Culture (216)
- Pre-Algebra (161)
- Precalculus (494)
- Preparing for college (12)
- Probability (83)
- Statistics (80)
- Tales from the Classroom (214)
- Technology (77)
- Theorems (153)
- Uncategorized (58)

## Tags

angle arccosine arcsine arctangent area binary circle combinatorics Common Core complex numbers compound interest conceptual barrier confidence interval convex polygons cosine decimal De Moivre's Theorem derivative differential equation distributive law divisibility division algorithm e exponent exponential factorial factoring fraction function gamma geometric series graph high-stakes testing hypothesis test index to a series of posts induction integral intercepts inverse function limit logarithm logic MAA magic trick matrices multiplication parallel Pascal's triangle perpendicular pi polar coordinates polynomial primes PRIMUS proof Pythagorean theorem Pythagorean trig identities quadratic formula residue sequence series sine slope sphere sports square root system of equations tangent Taylor series textbook problems triangle trigonometry unsolved problems volume xkcd## Meta