Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers



Solving Equations Over the Nonnegative Integers

Restriction: Positive Integers
Restriction: Nonnegative Integers
Connection: Multinomial Expansion

We seek the number of ways to solve equations of the type when we can use only nonnegative integers as addends in such equations. Here are two problems to introduce our work:

Problem #1: If we have an unlimited supply of pennies, nickels, dimes, and quarters, how many ways are there to gather together 6 coins, if:

a) it is acceptable to have none of any particular coin?
b) we must have at least 1 coin of each type?

Problem #2: Sandy Softknuckle suffers from a mild case of obsessive-compulsive disorder. Sandy is particularly fascinated with ways to arrange dinner napkins for formal parties. Assuming Sandy has an unlimited supply of green, white, and red napkins, how many ways can Sandy create a set of 20 napkins if:

a) it is okay to have no napkins of a particular color?
b) there must be at least one napkin of each color?
c) there must be more than 3 of each color napkin?

Each of these problems is a specific case where we seek to solve an equation using some subset of the nonnegative integers as the solution set. For the first version of the coins problem, we are restricted to positive integers. For the last version of the table napkins problem, we must have solutions with value 4 or greater.

It is also important to connect our efforts to solve these problems with our yet-unanswered question about the number of collected terms in the expansion of a multinomial. While you may not yet see any similarity between these two classes of problems, the solution strategy is similar.

Coins in a Pile

In the first version of the coins problem, we want to determine the number of ways to assemble 6 coins, consisting of pennies, nuckels, dimes, and quarters, with the assurance that there is at least one of each type of coin.

One solution is to have 3 pennies and 1 of each of the other types of coins. We could express that as {3,1,1,1}, where each position in the set represents a type of coin according to the order {pennies, nickels, dimes, quarters}. Another solution is {2,1,2,1}, calling for 2 pennies, 1 nickel, 2 dimes, and 1 quarter. Note that we are not concerned about arranging the coins nor about the order we might have received them. Our focus is on the assemblage of coins.

To develop a combinatorial argument for solving the problem, consider the drawing below.

The circles represent the six coins we must assemble, initially of unknown type. The three dividers will be used to create four groups of coins, because three dividers will create four groups, as shown with the word pennies, nickels, dimes, and quarters among the dividers.

Where can we place the dividers? The five question marks among the coins are places we can position the dividers. Here are a couple ways we might do that. The top figure illustrates the solution {1,2,2,1}, or 1 penny, 2 nickels, 2 dimes, and 1 quarter. The bottom figure shows the solution {2,1,1,2}.

To count the number of ways to place the dividers, we count the combinations of 5 things taken 3 at a time. That is, from among the 5 question marks, we choose 3 as places to postion the 3 dividers. It's important to recognize that we have one less place for dividers than the total number of objects and that we need one less divider than we have different types of objects.

In general, for n total objects of k different types, there are C(n-1,k-1) ways to assemble n total objects from the k types, assuring that we will have at least 1 of each type of object.

This also is the solution strategy to answer the following question:

What if 0 is possible for one or more types of objects?

The second version of the coins problem relaxed the restriction on the required number of each type of object, in that it was possible to have none of one or more types of objects. We can therefore have {0,0,0,6} and {0,2,3,1} as solutions, where the entries in each set represent the numbers of pennies, nickels, dimes, and quarters, respectively.

In terms of objects and dividers, we still have 6 of the former and three of the latter. This time, however, dividers can be adjacent. Here are illustrations of two solutions under the new condition. The first is {0,3,0,3} and the second represents {1,0,0,5}.

An effective way to consider this in combinatorial terms is to consider the coins and the dividers as one large set of objects. There are 9!=P(9,9) ways to arrange the 9 objects. With no restrictions on arrangements, we account for all the possible ways the dividers can be places among the coins. Because the dividers are indistinguishable and because we consider the objects all as one class before we've divided them, we must divide through by 3!=P(3,3) and 6!=P(6,6). Thus, there are 9!/(3!6!) ways to arrange the dividers among the coins, or in the context of the problem, there are 9!/(3!6!) different ways to assemble 6 coins of 4 types, given that we could have 0 of one or more types.

We can express this value as a combination, since C(n,r)=n!/(r!(n-r)!). Our solution is C(9,3)=C(9,6). The general solution, when we have k different types of objects and want n total objects assembled, is C(n+k-1,k-1).

Again we note that this strategy is exactly the strategy required to solve the following problem:

We have an additional problem, however, for which this combinatorial strategy is useful:

This is because every collected term has exponents that sum to n, and the collected terms represent all possible ways to multiply the k different factors together n times.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes