Password strength and combinatorics

xkcdpassword_strength

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

Permutations and Combinations

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

http://mathwithbaddrawings.com/2014/02/17/permu-combi-what-now-or-the-mathematics-of-my-wedding-playlist/

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

BugsBunny20cents

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:

\left[1 + x + x^2 + x^3 + x^4 + x^5 + \dots \right]

\times \left[1 + x^5 + x^{10} + x^{15} + x^{20} + x^{25} + \dots \right]

\times \left[1 + x^{10} + x^{20} + x^{30} + x^{40} + x^{50} + \dots \right]

\times \left[1 + x^{25} + x^{50} + x^{75} + x^{100} + x^{125} + \dots \right]

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 x^{20} 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.

green_speech_bubbleThere are actually 9 ways. We could choose 1 from the first, second, and fourth lines while choosing x^{20} from the third line. So,

1 \cdot 1 \cdot x^{20} \cdot 1 = x^{20}

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.

1 \cdot x^{10} \cdot x^{10} \cdot 1 = x^{20}

1 \cdot x^{20} \cdot 1 \cdot 1 = x^{20}

x^{10} \cdot 1 \cdot x^{10} \cdot 1 = x^{20}

x^5 \cdot x^{15} \cdot 1 \cdot 1 = x^{20}

x^{10} \cdot x^{10} \cdot 1 \cdot 1 = x^{20}

x^5 \cdot x^{15} \cdot 1 \cdot 1 = x^{20}

x^{20} \cdot 1 \cdot 1 \cdot 1 = x^{20}

x^5 \cdot x^5 \cdot x^{10} \cdot 1 = x^{20}

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.

  • 1 \cdot 1 \cdot x^{20} \cdot 1 = x^{20}: 2 dimes (20 cents).
  • 1 \cdot x^{10} \cdot x^{10} \cdot 1 = x^{20}: 2 nickels (10 cents) and 1 dime (10 cents)
  • 1 \cdot x^{20} \cdot 1 \cdot 1 = x^{20}: 4 nickels (20 cents)
  • x^{10} \cdot 1 \cdot x^{10} \cdot 1 = x^{20}: 10 pennies (10 cents) and 1 dime (10 cents)
  • x^{15} \cdot x^5 \cdot 1 \cdot 1 = x^{20}: 15 pennies (15 cents) and 1 nickel (5 cents)
  • x^{10} \cdot x^{10} \cdot 1 \cdot 1 = x^{20}: 10 pennies (10 cents) and 2 nickels (10 cents)
  • x^5 \cdot x^{15} \cdot 1 \cdot 1 = x^{20}: 5 pennies (5 cents) and 3 nickels (15 cents)
  • x^{20} \cdot 1 \cdot 1 \cdot 1 = x^{20}: 20 pennies (20 cents)
  • x^5 \cdot x^5 \cdot x^{10} \cdot 1 = x^{20}: 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.

green lineUsing the formula for an infinite geometric series (and assuming -1 < x < 1), we may write the infinite product as

f(x) = \displaystyle \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}

When written as an infinite series — that is, as a Taylor series about x =0 — 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:

generating1Looking at the coefficient of x^{20}, 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:

generating2Finally, 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.

generating3

green line

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/

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

BugsBunny20cents

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.

green line

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 1, 1, 1, 1, \dots. The generating function for this sequence is

f(x) = 1 + 1x + 1x^2 + 1x^3 + \dots

If -1 < x < 1, then f(x) = \displaystyle \frac{1}{1-x}, using the formula for an infinite geometric series.

Example #2. For the slightly less boring sequence of 1, -1, 1, -1, \dots, the generating function is

f(x) = 1 - x + x^2 - x^3 + \dots,

which (if -1 < x < 1) is f(x) = \displaystyle \frac{1}{1+x}.

Example #3. Suppose a_n = \displaystyle {10 \choose n} if $0 \le n \le 10$ and a_n = 0 for n>10. Then the generating function is

f(x) = \displaystyle \sum_{n=0}^{10} {10 \choose n} x^n = (x+1)^{10}.

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

green line

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