Articles of multisets

distance metric between multisets

I am trying to define a distance $F(X,Y)$ between two multisets $X$ and $Y$. For each pair of $x \in X , y \in Y$ there exists a distance function $f(x,y)$ which takes the range of $[0,1]$. An additional requirement of $F(X,Y)$ is that $F=0$ if one of $X,Y$ is a multiple of the other. […]

Combinatorics: Number of possible 10-card hands from superdeck (10 times 52 cards)

I have the following problem from book “Introduction to Probability”, p.32 A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. Thus, the superdeck has 52 · 10 = 520 cards, with 10 copies of each card. How many different 10-card hands can be […]

Stirling numbers of the second kind on Multiset

Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into k nonempty subsets.What if there were duplicate elements in the set?That is,the set is a multiset?

What is the number of bijections between two multisets?

Let $P$ and $Q$ be two finite multisets of the same cardinality $n$. Question: How many bijections are there from $P$ to $Q$? I will define a bijection between $P$ and $Q$ as a multiset $\Phi \subseteq P \times Q$ satisfying the properties: $\Phi=\{(p_1,q_1),(p_2,q_2),\ldots,(p_n,q_n)\}$, $P=\{p_1,p_2,\ldots,p_n\}$, and $Q=\{q_1,q_2,\ldots,q_n\}$. For example, suppose $P=\{1,1,1,3\}$ and $Q=\{1,1,2,2\}$. Then there […]

How to find unique multisets of n naturals of a given domain and their numbers?

Let’s say I have numbers each taken in a set $A$ of $n$ consecutive naturals, I ask myself : how can I found what are all the unique multisets, which could be created with $k$ elements of this set $A$? For example I’ve got $A=[1,2,\dots,499]$. If I wanted to create unique multiset of 3 elements, […]

Permutations with identical objects

How can I find the number of $k$-permutations of $n$ objects, where there are $x$ types of objects, and $r_1, r_2, r_3, \cdots , r_x$ give the number of each type of object? Example: I have 20 letters from the alphabet. There are some duplicates – 4 of them are a, 5 of them are […]

Combinations of multisets – the theory?

I’ve read over the theory countless times, and I still have no idea how to think of it. The formula for the combinations of multisets is $C(k + r – 1, r)$, where $k$ = the number of distinct elements, and $r$ is the $r$-combinations required. Let’s use an example. If I have the set […]

Finding total number of multi-sets

I am provided with a multi-set, let’s say S with elements as [num1, num2, num3] and these elements are integers (both negative as well as non negative). As this is a multi-set, elements in the multi-set can be present multiple times. I need to choose an element from this multi-set and multiply it with -1. […]

Derangements of multisets

Find the number of ways string of numbers (may contain similar items) could be deranged so that a number is not placed in the same place as it or its similar numbers were placed. For example, $\{0,0,0,1,1,1\}$ could be arranged in only one way and that is $\{1,1,1,0,0,0\}$. $\{0,0,0,1,1,1,1\}$ cannot be arranged in any way. […]

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color $i$. Let $\msP=(1^{n_1} 2^{n_2} \dots c^{n_c})$ be the multiset $\small\{\underbrace{1, \dots, 1}_{n_1},\underbrace{2,\dots,2}_{n_2},\dots,\underbrace{c,\dots,c}_{n_c}\}$ in frequency representation. The number of distinct permutations of $\msP$ is given by the multinomial: $$\left|\mfS_{\msP}\right|=\binom{n}{n_1,n_2,\dots,n_c}=\frac{n!}{n_1!\,n_2!\cdots n_c!}=n! \prod_{i=1}^c \frac1{n_i!}.$$ […]