# Questions tagged [multisets]

For questions about or related to multisets, a notion similar to sets with the difference that elements can be repeated.

357 questions
Filter by
Sorted by
Tagged with
143 views

### Expressing Numbers Without Any Decimal Presumptions

I have long been uncomfortable with how numbers in alternative bases are expressed. Alternative bases are marketed as transcending our arbitrary base-$10$ conventions, but I wonder if they really ...
• 1,904
73 views

### Multiset Matching

Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
13 views

### Size of a Power Set of a Multiset where some items are Indistinguishible [duplicate]

Note: I do not know all the terminology for my question, so I am making some educated guesses. Please let me know the correct terminology for anything I get the name of wrong. Suppose I have a ...
• 101
44 views

### Image of the standardization of permutations of a finite multiset

Let $M$ be a multiset $\{1^{m_1},2^{m_2},...\}$ whose cardinality $\#M:=m_1+m_2+...=:n$. Let $\Sigma:S_M\to S_n$ be the standardization map defined in Stanley combinatorics volume 1 ($S_M$ is the set ...
• 3,719
190 views

### 20 identical red balls, 20 identical blue balls, 20 identical green balls, 1 white ball, and 1 black ball. You draw 15. How many outcomes?

A bag contains 20 identical red balls, 20 identical blue balls, 20 identical green balls, 1 white ball, and 1 black ball. I reach in to get 15 balls. How many outcomes are there? The problem came from ...
• 21
177 views

### Number of Partition of a Set with Repeated Elements

It is well known that for a set of $n$ elements, say $\{1,\ldots, n\}$, the total number of possible partitions of this set is equal to $B_n$, where $B_n$ is the Bell number, and a set partition is a ...
120 views

### Exercise 10 in Stanley Combinatorics volume 1 chapter 1

I'm again having some trouble understanding a solution of an exercise of chapter 1 of Stanley Combinatorics volume 1. It's the exercise 10 that requires to prove that the number of ways we can choose ...
• 3,719
70 views

• 1,176
1 vote
40 views

### Multiset Covers with a Uniformity Condition

I was playing around with the indices of tuples of functions, and these objects came up naturally. Is there a name for them? Are there any resources on them that provide some properties or even a ...
• 696
1 vote
159 views

### Understanding David Deutsch's second equation from his paper The Structure of the Multiverse

Background David Deutsch's paper The Structure of the Multiverse is concerned with the theory of quantum information and quantum computation, but the first few pages contain a purely mathematical ...
89 views

### Trying to understand multisets. Given 4 random letters, what is the formula for finding the number of ways to get multisets? Then for 5 letters?

*Added an Addendum at the end Hopefully my Title isn't too vague, but I will try to elaborate here. I posted a similar question: Given 10 random letters where the number of repeated letters is known (...
1 vote
87 views

### What does multiset imply?

Does a multiset operation (($^n_k$)) only work for sets with identical elements, or does it also apply to replacement of distinct elements. Is there any difference in the calculation? Furthermore, is ...
• 102
2k views

58 views

1 vote
31 views

• 3,032
1k views

### Algorithm to generate all combinations of list of sets with up to one element per set

For a given list of sets where the elements of the sets do not share any elements between the sets I want to compute all possible combinations where a combination can have up to one element per set. ...
• 793
38 views

### Name for number of unique items in a multiset which appear only once

Question about terminology describing finite multisets. What is the proper term for the number of items which have a frequency of one? Are they called singletons? Cardinality of singletons? i.e. {a,a,...
• 929
1 vote
54 views

### Subsets that add up to zero in finite sequence {1,-1,1-1..}

This problem must be simple, but it's driving me crazy (Following the comments I edit) If I have for example the following sequence $\{1, -1, 1, -1, 1, -1, 1, -1\}$ and ask how many subsets of two ...
• 381
77 views

### Combinations on multisets and ordered pairs

I came across this question while doing some revisions. There are 3 parts to this question. One of them I asked here before. Suppose you have a series of scrabble tiles, each tile has one letter on it,...
• 325
116 views

### Growth of n multichoose k when n and k increase by the same number

The multiset coefficient $$\left (\binom{n}{k} \right ) = \binom{n+k-1}{k}$$ denotes the number of multisets of cardinality k, with elements taken from a finite set of cardinality n. I'm interested ...
1 vote
106 views

### Counting partitions of fixed size in a specific multiset

If we have the multiset $$\{1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5\},$$ i.e. five distinct elements and five of each type, how many ways can we partition this multiset into five equally ...
• 51
1 vote
78 views

### Proving combinatoric identity using vote casting example.

I'm still having trouble giving a combinatorial proof of this identity using the vote casting example: $$\sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0$$ ...
• 919
94 views

### Combinatorial proof of this identity: $\sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0$ [duplicate]

I'm trying to give a combinatorial proof of this identity: $$\sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0$$ I think the right-hand side could be ...
• 919
1 vote
### How would one distribute $a$ alike things of one kind and $b$ alike things of other kind and rest different things into groups
My question is that how would one count the number of ways to distribute things from a group of different things and different groups of alike things (for e.g., $a$ alike things of one kind, $b$ alike ...