MA 367

Spring 2003

Richard Hitt

•Enumerating Permutations

•Built-in Function

Mathematica does have a built-in function for enumerating permutations called (you guessed it) Permutations[].

Permutations[list] generates a list of all possible permutations of the elements in list. <a title= More... " hspace="62" width="389" height="36" align="absmiddle" />

{{a, b, c, d}, {a, b, d, c}, {a, c, b, d}, {a, c, d, b}, {a, d, b, c}, {a, d, c, b}, {b, a, c, ... {c, d, b, a}, {d, a, b, c}, {d, a, c, b}, {d, b, a, c}, {d, b, c, a}, {d, c, a, b}, {d, c, b, a}}

Note that this function enumerates the permutations in lexicagraphic order. We can check the runtime of the algorithm by doing a few calculations.

{0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.11000000000000032` Second, 1.48` Second}

{0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.11000000000000032` Second, 0.6099999999999994` Second, 5.2700000000000005` Second, 48.89` Second}

•Minimum Change Permutations

We can load a package that has a few more combinatorial algorithms that Mathematica loads automatically.

The MinimumChangePermutation function is now defined that produces an enumeration of permutations so that each differs from its next-door neighbors by a single transposition.

{{a, b, c, d}, {b, a, c, d}, {c, a, b, d}, {a, c, b, d}, {b, c, a, d}, {c, b, a, d}, {d, b, a, ... {d, c, a, b}, {d, c, b, a}, {c, d, b, a}, {b, d, c, a}, {d, b, c, a}, {c, b, d, a}, {b, c, d, a}}

We can also examine the runtime of this algorithm as we did on the previous one.

{0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.` Second, 0.04999999999999716` Second, 0.44000000000000483` Second, 3.4100000000000037` Second, 30.69999999999999` Second}

•Combinations

Mathematica can enuerate the r-combinations of n objects with the KSubsets function. For example, to generate the number of 3-subsets of 5 objects, we can use

{{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}}

•Partitions of Integers

The Mathematica funciton Partitions[] can be used to generate all of the partitions of an integer into one or more parts or into k or fewer parts.

Partitions[n] constructs all partitions of integer n in reverse lexicographic order. Partition ... ic order. <a title= More... " hspace="62" width="417" height="74" align="absmiddle" />

{{10}, {9, 1}, {8, 2}, {8, 1, 1}, {7, 3}, {7, 2, 1}, {7, 1, 1, 1}, {6, 4}, {6, 3, 1}, {6, 2, 2 ... , 1, 1, 1}, {2, 2, 1, 1, 1, 1, 1, 1}, {2, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

Once you can enumerate partitions, you can then count partitions with particular properties. For example, you can solve problem #5 on Quiz 2 with the following:

•Generating Functions

•Making Change for a Dollar

To introduce generating functions, lets think about the number of ways ot make change for a dollar given an abundant supply of pennies, nickels, dimes, quarters, and half-dollars. Lets leave out the Sacagawea dollar for now.

To solve this problem, then, we need to count the number of non-negative integer solutions to the equation

This is not easy to count using the previous methods in the course. But we can note that the left-hand side of the above equation is exactly how the exponents are built we multiply and expand the following polynomials.

$p _ 1 = Sum[t^i, {i, 0, 100}] p _ 5 = Sum[t^{5 i}, {i, 0, 20}] p _ 10 = Sum[t^{10 i}, {i, 0, 10}] p _ 25 = Sum[t^{25 i}, {i, 0, 4}] p _ 50 = Sum[t^{50 i}, {i, 0, 2}]$

1 + t + t^2 + t^3 + t^4 + t^5 + t^6 + t^7 + t^8 + t^9 + t^10 + t^11 + t^12 + t^13 + t^14 + t^1 ... + t^87 + t^88 + t^89 + t^90 + t^91 + t^92 + t^93 + t^94 + t^95 + t^96 + t^97 + t^98 + t^99 + t^100

${1 + t^5 + t^10 + t^15 + t^20 + t^25 + t^30 + t^35 + t^40 + t^45 + t^50 + t^55 + t^60 + t^65 + t^70 + t^75 + t^80 + t^85 + t^90 + t^95 + t^100}$

${1 + t^10 + t^20 + t^30 + t^40 + t^50 + t^60 + t^70 + t^80 + t^90 + t^100}$

${1 + t^25 + t^50 + t^75 + t^100}$

${1 + t^50 + t^100}$

[Long pause] Got it yet? Well, perhaps not. [Another long pause] OK, note in the above summation loops that define the polynomials that the dummy variable i measures how many coins of that particular denomination are used and the exponent measures the total value. So the exponent on , say, in the expansion of tells us how many different ways there are to select pennies, nickels, and dimes so that they total 23 cents. So to solve our problem, all we need to do is expand and find the coefficient of . No problem!

${1 + t + t^2 + t^3 + t^4 + 2 t^5 + 2 t^6 + 2 t^7 + 2 t^8 + 2 t^9 + 4 t^10 + 4 t^11 + 4 t^12 + ... 4 t^490 + 2 t^491 + 2 t^492 + 2 t^493 + 2 t^494 + 2 t^495 + t^496 + t^497 + t^498 + t^499 + t^500}$

To save unnecessary output, we could just skip out the 101st term directly to get

So we see that there are 292 ways to make change for a dollar using pennies, nickels, dimes, quarters, and half-dollars.

•Exercise

What change (pardon the pun) would you have to make in the above Mathematica code to determine how many ways there are to change a dollar using pennies, nickels, dimes, and quarters, but no half-dollars or Sacagawea dollars? What is the (numerical) answer?

Converted by Mathematica (February 10, 2003)