[AMOF] [GENERATE] [Schoolnet Icon]


Information on Permutations of a Multiset

[Description | Example | History | Applications | Implementation | Classroom | Links]


Description of the Problem

If you are given the letters in the word SUDS, how many ways are there to arrange these letters? All the different ways can be listed: DUSS, DSUS, DSSU, UDSS, USDS, USSD, SUDS, SDUS, SUSD, SDSU, SSUD, SSDU. So, there are 12 ways in all. These arrangements are called permutations of a multiset.

A multiset is like a set, except that repeated elements are allowed. When referring to permutations of a multiset we assume that the elements of the multiset are 1, 2, ..., t, that the number of occurrences of i is ni and that N = n1 + n2 + ... +nt. Note that if all the ni = 1 then we have our regular definition of a permutation. In the example above, n1 = 2, n2 = 1, and n3 = 1.

Permutations of a multiset are often listed in lexicographic (dictionary) order as in regular permutations. Another common order is Gray Code order, in which each consecutive permutation differs from the permutations before and after it by only two elements. Gray Code order is not found on AMOF, but is in COS.


Example

An example has been given above. Another one is to arrange a group of boys and girls in a line. Supposing there are 2 boys and 3 girls, a number of possibilities are shown below as they would appear in AMOF. Boys = B, girls = G.

Symbols
Coloured Balls
BBGGG

BGBGG

BGGBG

BGGGB

GBBGG

GBGBG

GBGGB

GGBBG

GGBGB

GGGBB


A Brief History

The study of permutations began in ancient times. The number of ways of arranging an n number of items was known to be n! for at least 2500 years.

Not much is known about the history of permutations of a multiset. It is quite possible that permutations of a multiset were first considered when analyzing the probabilities of certain gambling outcomes, such as getting a full house in a poker hand.


Applications to Mathematics and other Areas

Mathematics is the science of patterns and permutations are one of the most fundamental of all patterns. It is not surprising, therefore, that permutations of both sets and multisets occur in much of mathematics. A knowledge of permutations is necessary for understanding basic concepts of discrete mathematics and probability theory.

There are many problems whose solutions are permutations of a multiset. For example, consider a woodworkers shop that has 5 orders which require the use of one of its saws. Two of the orders are from one customer, and two others are from a second customer. Those orders will have to be scheduled in order to meet deadlines, have material available, and satisfy other constraints. The order in which the orders are completed is a permutation of a multiset. Some scheduling problems involving creating a permutation of a multiset.


Explanation of ECOS Implementation

In AMOF, there are 5 numerical inputs for permutations of a multiset. These represent the number of occurrences of each item in the multiset. Thus, you are restricted to 5 items in any multiset. You are also restricted to the input numbers summing to 20 or less. This should be enough for educational purposes. AMOF also provides a place to specify the symbol for each of the inputs. If a symbol is not provided in the input, AMOF will set the symbol to a number corresponding to the input.

There are two output options - symbols and coloured balls. If symbols is chosen, the output will show a list of symbols for each result, representing inputs 1 through 5 using the symbols given or using the corresponding number if no symbol is provided. The output results are given in lexicographic (dictionary) order if the symbols used are 1 through 5. If coloured balls is chosen, the output will show the results in terms of coloured balls, where a color represents each of the inputs. An example of both output options is shown in the Example section of this page.


In the Classroom

The study of permutations and of sets is a part of the grade 11 and 12 math curriculum in British Columbia. The intended outcome is for students to learn how to compute the number of permutations of n things taken k at a time, and to apply the rules of permutations to solve problems. A problem-solving approach with lots of examples that are meaningful to everyday life can make learning this concept more enjoyable.

[NCTM] recommends for students who have finished second year algebra a discrete math course that includes permutations, combinations, Pascal's triangle, and recurrence relations. It also contains a useful chapter "Permutations and Combinations: a Problem Solving Approach for Middle School Students".

The concept of permutation is easily grasped by secondary school children. Try asking how many ways there are to arrange a red, a blue, and a yellow crayon in a row. Or expand the question by asking how many ways there are to arrange 2 red, and 2 blue crayons in a row. You should get six as an answer to either question, but adding a third color or using higher values will provide a good challenge for most of them. AMOF can be used to show explicit listings of all such permutations, provided the total of the inputs is not too high.

Permutations of a multiset can also be used in elementary probability questions such as the following. If there are 3 red balls, 1 green ball, 1 blue ball, and 1 white ball in a bag, what is the probability of pulling out all 3 red balls first when one tries to pull all balls out of the bag one at a time? Such a problem involves counting the total number of ways to arrange the items and the number of ways to arrange them if the first 3 are red.

AMOF allows students to try many different values of inputs, and very quickly lets them see the number of possible solutions and what those solutions look like. They can test their understanding of generating permutations of a multiset, and list them in lexicographic order.


Links to Other Relevant Sites and Sources of Information


[AMOF] [GENERATE] [Schoolnet Icon]


This page created by Frank Ruskey and Scott Lausch, March 1998. ©Frank Ruskey and Scott Lausch, 1998.