Mathematical notation for number of times an element appears in a multiset

Question

I have a multiset, say $\{8,5,7,8,8,9,5,5,3,0,1\}$, and I wish to compute a weight with the following formula: number of times an element appears in the multiset divided by the total number of elements in the multiset. For example, if the element is $8$ then the weight becomes $3$ (eight appearing three times) divided by $11$ (the total number of elements in the multiset).

How can I express this formula in mathematical notation using symbols like the sigma (sum) symbol for the number of times an element appears and what should be the symbol for expressing the size of the multiset?

Answer 1

First, it is not a set: it is a multiset (a set does not include multiplicities: $\{1,1,1,1,1,2\} = \{1,2\}$. A multiset does).

A possibility, using the indicator $\mathbf{1}$: for a multiset $S$,the number of times $x$ appears in $S$ (the multiplicity of $x$ in $S$) can be written $$ \sum_{s\in S} \mathbf{1}_{\{x\}}(s) $$ or $$ \sum_{s\in S} \mathbf{1}_{\{s=x\}} $$ (What it means is, literally: sum, over all elements of $S$, of a value which is $1$ if $s=x$ (that is, equivalently, if $s\in\{x\}$) and 0 otherwise).

This is quite standard; at least, I have seen it in numerous occasions (papers and lecture notes). From there, the frequency of $x$ in $S$ can be written simply as $$ \frac{1}{\lvert S\rvert}\sum_{s\in S} \mathbf{1}_{\{x\}}(s) $$ using again the standard notation $\lvert S\rvert$ for the cardinality of $S$.

Answer 2

As set we would have $A := \{8,5,7,8,8,9,5,5,3,0,1\} = \{0,1,3,5,7,8,9\}$. So what you want to define here is a multiset defined by the function $$f:A \rightarrow \Bbb N _0, \begin{cases} 0 \mapsto 1\\ 1 \mapsto 1\\ 3 \mapsto 1\\ 5\mapsto 3\\ 7\mapsto 1\\ 8\mapsto 3\\ 9\mapsto 2 \end{cases} $$ where $f$ counts how often an element $a\in A$ is in the multiset defined by $f$

Now we can give the formula for a number $a\in A$ you search for by $$\frac{f(a)}{|A|}$$

Answer 3

When an object contains multiple occurrences of the same element it is called a multiset, we sometimes use strong brackets (but generally use normal ones) to differentiate the multiset $\mathcal A$ from its support set $A$.

For instance $\mathcal A=\boldsymbol\{8,5,7,8,8,9,5,5,3,0,1\boldsymbol\}$ would have support set $A=\{8,5,7,9,3,0,1\}$

The multiplicity of an element can be noted $\displaystyle \nu(a)=\#\boldsymbol\{x\in \mathcal A\mid x=a\boldsymbol\}=\sum\limits_{x\in \mathcal A}1_a(x)$

And the cardinality is noted $\displaystyle |\mathcal A|=\#\mathcal A=\sum\limits_{a\in A} \nu(a)$

The function you want is then $\dfrac{\nu(a)}{|A|}$.

---

In general a multiset $\mathcal S=\langle S,\nu\rangle$ is the provision of a set $S$ and a multiplicity function $\nu:S\to\mathbb N$ (with zero).

This is how we perform operations on them like $\mathcal A\cap\mathcal B$, by operations on the multiplicity functions $\nu_{\mathcal A\cap\mathcal B}(x)=\min(\nu_{\mathcal A}(x),\nu_{\mathcal B}(x))$ for all $x\in A\cap B$ for instance.

Note that the definition allow for the multiplicity to be $0$, so the support set $S$ can be somehow "larger" than the canonical support set which would have a strictly positive multiplicity function, for instance $S=\mathbb N$.

When $\nu_{\mathcal A}(x)=0$ then $x\notin\mathcal A$.

This apparent lax in the definition allows in fact to have the same support set for multisets which all have the same "type" of elements and concentrate on the multiplicity functions.

For instance a normal set $A$ of integers could also be identified as $\langle \mathbb N,1_A\rangle$.