## You are here

Homemultiset

## Primary tabs

# multiset

Note that the standard definition of a set also allows repeated elements, but these are not *treated* as repeated elements. For example, $\{1,1,3\}$ as a *set* is actually equal to $\{1,3\}$. However, as a *multiset*, $\{1,1,3\}$ is not simplifiable further.

A definition that makes clear the distinction between set and multiset follows:

###### Multiset.

A multiset is a pair $(X,f)$, where $X$ is a set, and $f$ is a function mapping $X$ to the cardinal numbers greater than zero. $X$ is called the *underlying set* of the multiset, and for any $x\in X$, $f(x)$ is the *multiplicity* of $x$.

Using this definition and expressing $f$ as a set of ordered pairs, we see that the multiset $\{1,3\}$ has $X=\{1,3\}$ and $f=\{(1,1),(3,1)\}$. By contrast, the multiset $\{1,1,3\}$ has $X=\{1,3\}$ and $f=\{(1,2),(3,1)\}$.

Generally, a multiplicity of zero is not allowed, but a few mathematicians do allow for it, such as Bogart and Stanley. It is far more common to disallow infinite multiplicity, which greatly complicates the definition of operations such as unions, intersections, complements, etc.

# References

- 1 Kenneth P. Bogart, Introductory Combinatorics. Florence, Kentucky: Cengage Learning (2000): 93
- 2 John L. Hickman, “A note on the concept of multiset” Bulletin of the Australian Mathematical Society 22 (1980): 211 - 217
- 3 Richard P. Stanley, Enumerative Combinatorics Vol 1. Cambridge: Cambridge University Press (1997): 15

## Mathematics Subject Classification

03E99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella

## Comments

## some suggestions

Hi, I've some suggestions to improve the multiset definiton.

1) Multiset is also known as bag

2) in the formal definition represent f:X\to{1,2,3,...} - avoid the use of "function mapping"

3) in the formal definition say, "A multiset M is a pair..." and conclude saying "f(x) if the multiplicity of x in M"

4) stress two possible way of representing a multiset, as sequence of (element,multiplicity) pairs or as collection of objects, each repeated with its multiplicity {...}

## Re: some suggestions

An observaton on suggestion 2:

The problem with changing the formal definition would be that f:X\to{1,2,3,...} is not the same thing as f being a cardinal-valued mapping. A mapping to the cardinal numbers (or even to the nonzero cardinals) is more general in that it allows for "infinite" multiplicities (\aleph_0, \aleph_1, etc.) that are not permitted in the mapping to the positive integers.

A question regarding suggestion 4:

I'm a bit confused by this, since I don't think every multiset can actually be represented as a *sequence* of (element, multiplicity) pairs. For example, if M = (R+, f) where R+ are the positive real numbers and f(x) = ceil(x), this should be a valid multiset, but cannot be represented as a sequence. As far as I am aware, either of these representations only works for finite multisets. Am I missing something?