Think of a long word in your head. For me, that word would be Supercalifragilisticexpialidocious. What if I told you that we had a way of turning that long word into a mathematical set? Even further, what if I told you that we have a way of counting the number of ways we could rearrange the letters? That’s pretty awesome, right?
That is just one of the thousands of things you can do once you understand multisets.
Don’t worry about the mathematics part as I designed this paper to connect what you do know, like sets, subsets, Pascal’s Triangle, and the Binomial Theorem, to what you don’t know (Dickson, 2021).
If you need a refresher on those concepts, there is a review section.
In addition to teaching you about multisets, I’ll also introduce multichoose functions. These are likely to be useful in subjects such as combinatorics, discrete mathematics, graph theory, and more!
History and Background
When were multisets first utilized? Multisets have been a thing ever since the foundation of numbers. Think even before the concept of mathematics! How is that even possible? Wayne Blizard claims that a number n was “often represented in ancient times by a collection of n strokes, tally marks, or units.” These are considered multisets since strokes, tally marks, or units are all unable to be distinguished from each other mathematically (Blizard, 1989).
Over time, multisets have been used by a wide range of people but disguised as different names. According to the literature you are reading, you may see a multiset called a bag, aggregate, heap, occurrence set, fireset, weighted set, sample, or bunch. Since it was named differently according to the person using them, it is difficult to trace who discovered them first.
However, we can look into the mathematicians behind the permutations of multisets to get a somewhat decent timeline. The first person known to study the permutation of multisets is Bhāskarāchārya. An Indian mathematician who lived around 1150 (Wikimedia Foundation, 2023, October 1). The individual who actually coined the word “multiset” is Nicolaas Govert de Bruijn in the 1970s. The picture of Nicolaas is seen to the left (O'Connor & Robertson, 2008).
Now that there were multisets, we wanted to figure out how to count them. Hence, the birth of the multichoose function. It is linked explicitly to binomial coefficients, aka choose functions. You will see how they relate in the Explanation of Mathematics section of this paper.
MathJax Example
Brief Review of Mathematics
For the sake of being thorough, let’s do a brief review and build our knowledge from there!
Recall that a set is a collection of objects.
Those objects are what we call elements of a set (Galvin, n.d.).
For example, let’s say we want to group together even numbers.
Therefore, we have the following set:
A={2,4,6,8,10,12,14,16,...}
The elements of the set are the numbers listed inside the brackets.
Now, let’s branch over to Pascal’s wonderful discovery, Pascal’s Triangle. It is built with each entry being the sum of the two entries above it.
The top row that holds a single element, is considered the “zero-th” row (Wikimedia Foundation, 2023, October 30). This triangle is useful to us since it tells us the expansion of powers of a binomial.
For instance, let’s say we want to expand out (x+y)n. The nth row of Pascal's Triangle will tell us the coefficients for each term. For the exponents of the variables, you do the first variable in decreasing order and the second in increasing order. This looks like
(x+y)n=axny0+bxb-1y1+cxn-2y2+...+zx0yn
Notice how each term's exponents in the expansion adds up to n.
Now, let’s expand out (x+y)^n for n=3.
Since n=3, refer to the 3rd row of Pascal’s Triangle. The 3rd row states the coefficients are 1 3 3 1.
Put down the coefficients in front of each term where the first variable is in increasing order and the other is in decreasing order.
Thus, we got for n=3,
(x+y)3=1x3y0+3x2y1+3x1y2+1x0y3
Now, let's move on to choose functions. The number of combinations, possible arrangements, of k objects taken from a set of n objects (n-set) without repetition is denoted as \(\binom{n}{k}\).
\(\binom{n}{k}\) read it as "n choose k", aka the binomial coefficient (Jenn, 2021).
Recall that \(\binom{n}{0}\)=\(\binom{n}{n}\)=1 and \(\binom{n}{k}\)=0 if k>n.
We can rewrite the binomial coefficient algebraically as \(\binom{n}{k}\) = \(\frac{n!}{k!(n-k)!}\)
Explanation of Mathematics
Multisets
Now knowing what a set is, what is a multiset?
A multiset (aka a mset) of S is, in basic terms, a set with multiplicity. This means that it is a set of objects that are able to repeat. Basically, you are taking a set of objects and then creating a set of objects from that original set.
Suppose S is a finite set, i.e. S = {s1, s2, s3}.
Let µ be the function from S to the non-negative intergers. µ is called a multiset (Brown, 2021).
Let's go over an example of what µ can be.
Example
Suppose we have a set S = {s1, s2, s3}. The function µ on S can be defined as µ(s1)=4, µ(s2)=2, and µ(s3)=0.
The value µ(si) is the multiplicity (number of) of si's. This is a mset.
In other words, our new set µ, the mset, contains 4 s1's, 2 s2's, and 0 s3's.
Now, for notation, instead of using { and } to denote the grouping of a mset, we use 〈 and 〉
(Other mathematicians may choose to use [ and ].It all depends on preference.)
Therefore, the mset µ defined above may be written as follows:
µ=〈s1, s1, s1,s1,s2,s2〉 or =〈s1(4), s2(2)〉
The sum of the multiplicities of each si for i=1,2 is the size of the mset. Thus, |µ|=4+2=6.
Trying to learn new concepts of mathematics in generalized number form is overwhelming. To change things up, let’s look at a real-world example.
Example
Let’s say we are at a fast-food restaurant and we want to order food. We look at the menu and see that we can buy hamburgers (HA), salads (SA), shakes (SH), and chicken nuggets (CN).
So my options of things to buy are S={HA,SA,SH,CN}.
I am very hungry, so I decide that I want to have 3 hamburgers, 2 salads, 1 shake, and 6 chicken nuggets.
Therefore, my order is µ=〈HA, HA, HA, SA, SA, SH, CN, CN, CN, CN, CN, CN〉.
Let’s rewrite it as µ=〈HA(3),SA(2),SH(1),CN(6)〉
So the size of my order |µ|=3+2+1+6=12. I have ordered 12 things.
In summary, S is our menu and our mset µ is what I ordered from that menu. The size of mset µ is the number of things I bought.
If µ (for µ: S → ℕ) is a mset, then the starting set S is called the ground set for µ or the basis set for µ.
To figure out more properties of msets together, let's go over another example.
Example
Consider we have a mset β: A → ℕ where A={a,b} is our ground set.
If 〈a, a, b〉 = 〈a(2), b〉, then |β|=2+1=3.
If 〈a,b, b〉 = 〈a, b(2)〉, then |β|=1+2=3.
Same cardinality (size), but different sets!
Thus, we can note that the same cardinality does NOT, alone, imply that 2 msets are the same.
If 〈a, b, a〉 = 〈a(2), b〉, then |β|=2+1=3. This is the same mset as 1.
This is a great concept, but are there examples that tie in to other mathematical concepts?
Yes! We can relate this to msets of prime factors of n, a natural number. Consider the number 200. It has the prime factorization
200=2352
which gives us the multiset 〈2,2,2,5,5〉.
292=2273
gives us the multiset 〈2,2,73〉.
Moreover, you can have msets of solutions to an equation. With a quadratic equation, that means you will have 2 solutions. Therefore, your multiset of the solutions could look like 〈5,7〉, 〈2,6〉, 〈3,3〉= 〈3(2)〉, etc.
Notice how the msets 〈5,7〉 and 〈2,6〉 look like they can be written as sets. Well, they can! Basically, a multiset can be a regular set if the multiplicity of every element is one (Wikimedia Foundation, 2023, October 1).
Permutations of Multisets
Next, let’s go over permutations of multisets. Recall that a permutation is the number of possible arrangements in a set where order matters (Taylor, 2023). Here are some examples:
The 2-permutations of 〈a(2),b〉 are aa, ab, and ba.
The 3-permutations of 〈a(∞),b(2)〉 are aaa, aab, aba, baa, abb, bab, bba.
Let’s tie this in to binomial coefficients. Consider the number of permutations of a multiset with limited repetitions. A fun example I found of this is MISSISSIPPI (Leiserso & Nagpal, 2002).
Example
How many permutations are there of MISSISSIPPI?
We have a groundset S={M,I,S,P}.
Put MISSISSIPPI in mset form.
µ = 〈M,I(4),S(4),P(2)〉
Figure out the size of the mset.
|S|=1+4+4+2=11. This tells us we have 11 slots total to arrange our letters.
Determine the number of choices we get for each letter.
Number of choices for M: Out of 11 letters, we are choosing 1 M. Therefore we have \(\binom{11}{1}\) which is a choose function (aka binomial coefficient). Pascal’s triangle tells us \(\binom{11}{1}\)=11.
Number of choices for I: Out of 10 remaining letters (11-1=10), we are choosing 4 I’s. Therefore we have \(\binom{10}{4}\)=210.
Number of choices for S: Out of 6 remaining letters (11-1-4=6), we are choosing 4 S’s. Therefore we have \(\binom{6}{4}\)=15.
Number of choices for P: Out of 2 remaining letters (11-1-4-4=2), we are choosing 2 P’s. Therefore we have \(\binom{2}{2}\)=1.
5. Multiply the numbers we got to get the number of permutations.
11*210*15*1=34,650 permutations for MISSISSIPPI.
Multichoose Functions
Now let’s move on to the concept of multichoose functions (aka multiset coefficients or multiset numbers).
These are generally noted as \(\left(\binom{k}{n}\right)\) which is intentionally supposed to look like a variation of binomial coefficients. This is because multichoose functions are part of a negative binomial distribution (Wikimedia Foundation, 2023, October 1).
\(\left(\binom{k}{n}\right)\) is the number of ways to choose a set of n objects by choosing them from a set of k objects. You read it as “k multichoose n” where k,n are non-negative integers (Wikimedia Foundation, 2023, October 1).
This is different from binomials as k\(<\)n does not mean that \(\left(\binom{k}{n}\right)\)=0.
With multichoose functions, the following are true:
\(\left(\binom{k}{0}\right)\)=1
\(\left(\binom{1}{n}\right)\)=1
\(\left(\binom{k}{1}\right)\)=k
\(\left(\binom{k}{2}\right)\)=\(\binom{k}{2}\)+k
Example
For example, let’s say we wanted to figure out what value 4 multichoose 2 is, \(\left(\binom{4}{2}\right)\).
In other words, we are trying to find the number of possible ways to choose a mset of 2 items from a set of 4 items.
For the sake of convenience, let’s say those 4 elements are {a,b,c,d}. Now try to find the possible number of 2-item multisets derived from those 4 elements.
There are 10 in total. Thus, we got that \(\left(\binom{4}{2}\right)\)=10.
An interesting thing that was discovered combinatorically is that \(\left(\binom{k}{n}\right)\)=\(\binom{n+k-1}{n}\) where n,k are non-negative integers.
This means, we now have a way of manipulating a multichoose function into becoming a basic choose function.
Now we know that \(\left(\binom{k}{n}\right)\)=\(\binom{n+k-1}{n}\) and \(\binom{n}{k}\) = \(\frac{n!}{k!(n-k)!}\), we can combine the two to get the following:
Therefore, algebraically, we can write \(\left(\binom{k}{n}\right)\)=\(\frac{(n+k-1)!}{k!(n-1)!}\).
Exercises
As an exercise for you, verify the following are true using the fact that \(\left(\binom{k}{n}\right)\)=\(\binom{n+k-1}{n}\) or \(\left(\binom{k}{n}\right)\)=\(\frac{(n+k-1)!}{k!(n-1)!}\).
\(\left(\binom{3}{2}\right)\)=6
\(\left(\binom{7}{9}\right)\)=5005
\(\left(\binom{6}{6}\right)\)=462
\(\left(\binom{4}{7}\right)\)=120
\(\left(\binom{9}{12}\right)\)=125,970
Technology Help
After going through the calculations in the Explanation of Mathematics section, you probably noticed that these numbers can be rough to deal with. It is easy to make a mistake somewhere along the way. No need to fear though, as there are resources out there to assist you.
I created an applet specifically for calculating the answer to multichoose functions quickly. You are free to utilize it!
Original Applet
In addition, there is a tool out there called Wolfram Alpha. It can be found by going to www.wolframalpha.com.
For the MISSISSIPPI example, you can type in their search bar “permutations of MISSISSIPPI” and it will output 34,650 which matches with we figured out earlier.
You can also use this resource directly for multichoose problems. Try saying "5 multichoose 4" and it will give you 70. This matches my applet.
Once you understand how things work, using a calculator just shortens the process and won’t inhibit your learning.
Another cool thing that I found was that people have manipulated Pascal’s Triangle to match multichoose functions!
You can either go to StatisticsHowTo or view their picture here:
Please note that StatisticsHowTo uses the notation \(\left(\binom{n}{k}\right)\) instead of \(\left(\binom{k}{n}\right)\). So everything is slightly different from what I have taught you.
This goes all the way up to \(\left(\binom{6}{6}\right)\).
References
Blizard, Wayne D. (1989). "Multiset theory". Notre Dame Journal of Formal Logic, 30(1), 36–66. doi:10.1305/ndjfl/1093634995.
Brown, David. (2021, October 13). MATH 3310 – Meeting Nineteen. Zoom.
Dickson, S. (2021, May). Appendices Utah Secondary Supplemental Standards for Mathematics High School (9-12). Salt Lake City, Utah; Utah State Office of Education.
Galvin, D. (n.d.). Topic01_6p1_Galvin. Notre Dame.
