Questions tagged [multisets]
For questions about or related to multisets, a notion similar to sets with the difference that elements can be repeated.
351
questions
0
votes
0
answers
43
views
cardinality of a multiset
Multiset Notation
First, let's agree on the following representation of a multiset (a set that allows duplications). A multiset Multiset is represented as a pair <...
- 71
0
votes
2
answers
47
views
How to solve "linear multiset equations"?
I have a bunch of linear forms in the same number of variables, with the number of linear forms much larger than the number of variables. Say, they are $\ell_i(x_1,...,x_n)=l_{i1}x_1+...+l_{in}x_n$, ...
- 1,533
1
vote
3
answers
124
views
Set vs Multi-set in specific examples
I'm not a set theorist, but I feel like I've been taught all my life that I can write sets with repeating elements but those repeats are sort of degenerate and not counted as separate. So $\{a, b, a\} ...
- 278
0
votes
1
answer
19
views
Sufficient condition for equality of multisets
Give three finite multisets $A,B,C$ I am trying to devise a sufficient condition that implies equality of both $A$ and $B$ with $C$. More formally, if $A,B,C$ are defined over a space $\Omega$, I am ...
- 269
3
votes
1
answer
56
views
Are two finite-dimensional subspaces not disjoint iff the union of any of their bases is linearly dependent?
First I need to show the following Lemma:
Lemma
Let $\mathcal{M},\mathcal{N}$ be finite-dimensional subspaces of $V$ with any bases $\mathcal{M}_{0}$ and $\mathcal{N}_{0}$. Then, $\mathcal{M}\cap\...
- 177
0
votes
1
answer
16
views
Elegant notation for partial intersections in cartesian products?
Let
$A⊆X×Y$
$A$ be a multi-set over $X×Y$
$A∈⋃_{n∈ℕ}(X×Y)^n$
Anyway, $A$ is a collection of tuples $(x, y)$, potentially with duplicates in cases (2) and (3). Given $F⊆X$, I am looking for an ...
- 11k
2
votes
2
answers
68
views
Notation for collection of elements that may contain duplicates [closed]
I want to represent document D as a collection of words. I was inclined to do this with: D = {w_1, w_2, ... }. However, the ...
- 131
0
votes
0
answers
29
views
Combinatorics of a Single-Chiral-Center Molecule
I'll preface with the fact that I'm currently studying undergrad biophysics, so I don't have much background in math.
What I want to find:
a combinatorics approach to calculating the number of unique ...
- 1
0
votes
0
answers
14
views
How to get count and generation of all the unordered pairs for multisets?
Say for $N$ sets assuming $N = 3$ with all distinct elements like in the below eg,
$A = \lbrace 1,2,3\rbrace$;
$B = \lbrace 4,5\rbrace$ and
$C = \lbrace 6\rbrace$
How to find all the unordered pairs ...
1
vote
0
answers
37
views
What is a partial multiset?
A. Rabinovich, and B. A. Trakhtenbrot, in their Behavior Structures and Nets paper, uses the expression "partial multiset" without defining it.
In context, they have an alphabet $\Sigma$, a ...
- 167
0
votes
1
answer
42
views
Formula for calculating the combination of a multiset taken r at a time? [duplicate]
If we have a multiset S = {a,a,b,b,b,c,d}
How to calculate all possible combinations if we take r items at a time?
For example if r = 3 then the combinations will ...
5
votes
0
answers
208
views
What is the growth rate of OEIS A347913?
OEIS A347913 is an extremely interesting sequence about multisets of integers. It is defined as the number of multisets one can get starting with a multiset of $n$ zeros and "splitting", ...
- 3,733
-1
votes
1
answer
29
views
Is a multiset an element of itself?
I know that a set cannot be an element of itself, but I don’t find anything about multisets. So, my question is: is a multiset an element of itself?
- 111
1
vote
1
answer
35
views
Distributive property for signed multiset
I'm reading through Wayne Blizard's introduction to signed multisets, which says at the bottom of page 9 that additive union distributes over intersection. I see how this is true for normal (non-...
2
votes
0
answers
32
views
Given the length of a word, knowing there are no consecutive letters, and knowing how many of each letter, how can I find the number of permutations?
To start, I am not a mathematician, so please keep answers and notations to something that any high school graduate could understand. I am a Software Performance Engineer by trade and am looking for ...
1
vote
0
answers
17
views
Polynomials considered as multisets of roots: extend polynomial addition and derivation to $\mathbb{R}^n$
Informal context
In $\mathbb{C}[X]$, all polynomials are split, so monic polynomials are in bijection with the multisets of their roots, i.e. the finite sub-multisets of $\mathbb{C}$.
Polynomial ...
- 3,836
0
votes
2
answers
58
views
Algorithm for optimal partition of a multiset with bounded sum.
Consider the following problem:
Let $S$ be a multiset (you can think of it as an array) of positive
integers. Given a bound $W\geq \max(S)$, we want to find a partition
of $S$ into multisets $\{S_1,.....
-1
votes
2
answers
42
views
Why probability two sevens had been chosen wo replacement before a one only dependent on the number of ones and sevens in multiset $\{7,7,3,2,1\}$?
If the digits $7,7,3,2$, and 1 are randomly arranged from left to right, what is the probability both of the 7 digits are to the left of the 1 digit?
The answer is $1/3$ because $1 7 7$, $7 7 1$, $7 ...
3
votes
0
answers
52
views
What is the name of this multiset-like object?
My understanding is that a multiset (roughly, a set where we care about multiplicity) can be modeled as a function $V\to\Bbb{Card}$ with set-sized support, where $V$ is the class of all sets, $\Bbb{...
- 21.1k
0
votes
2
answers
57
views
What is the appropriate way to describe an "ordered union" of sequences?
Given the $\langle $sequences$\rangle$:
$$
\begin{aligned}
S_1 & = \langle \color{magenta}{D_1}, \color{orange}{D_2}, D_3 \rangle
\\
S_2 & = \langle \color{orange}{D_2}, D_4 \rangle
\\
S_3 &...
- 1,042
1
vote
1
answer
35
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 ...
- 677
1
vote
0
answers
124
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 ...
- 151
0
votes
0
answers
28
views
What kind of almost-Boolean algebra is the powerset algebra of a multiset?
What do you call the Boolean-like algebra for the powerset algebra of a multiset?
Can you axiomatize it by taking a run-of-the-mill axiomatization of a Boolean algebra and dropping the equivalent of ...
- 9,278
0
votes
1
answer
51
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
1
answer
73
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 ...
- 92
0
votes
1
answer
678
views
What does "$\epsilon$" mean in this formula
I have started seeing the "$\epsilon$" symbol in this paper. What exactly does $\epsilon$ it mean in the formula?
The hard part is this definition: "Range$(p,\epsilon)=\{o\mid ||p,o||_2\...
- 11
1
vote
0
answers
50
views
Number of non-negative integer solutions of the equation: $rx_1 + x_2 + \cdots + x_n=kr$
I have this excersice:
Determines the number of non-negative integer solutions of the equation: $rx_1 + x_2 + \cdots + x_n=kr$ where $k, r, n\in\mathbb{N}$.
I tried to use that the number of $r-...
- 451
3
votes
1
answer
47
views
Multiset image of a set under a homomorphism
I know the basic group theory definition of the image of a subset of group elements under a homomorphism is the following:
The image of any subset $X \subseteq G$ is given by $\phi(X) = \{\phi(x) : x ...
- 401
0
votes
1
answer
112
views
Complement of a Set: What do I do when a set contains an element that is not in the Universal Set
Let $U = \{x: x \in \mathbb{N}, x>10 \hspace{4 pt} and \hspace{4 pt} x <40\} , \hspace{4 pt}
A = { 5,10,20,40}$
The complement of the set should be
Aᶜ = {All natural numbers between greater ...
1
vote
2
answers
48
views
map two sets of integers into two integers such that the number of intersections of these two sets can be found using only these two integers
Given two multisets $A$ and $B$, is it possible to map all of the elements of these two multisets into two integer (for example, integer $A_1$ will represent the elements of multiset $A$, and integer $...
- 43
1
vote
1
answer
29
views
Probability that two sets of balls have disjoint labels (i.e. probability of disjoint multisets)
I have $k$ distinct balls split into two sets $A$ and $B$, $A$ has $k_1$ balls and $B$ has $k_2$ balls, and $k_1, k_2 \geq 1$. I have a random label machine which prints numbers from {1, 2, ... n} ($n ...
- 13
0
votes
1
answer
102
views
Combinatorial proof for formulas involving partitioning a multiset into 2 equal sums
$A$ is a non-empty multiset that contains $m$ integers $a_{1},a_{2},...,a_{m}$. $P(X,n)$ is the number of ways to partition $X\cup [n]$ into 2 equal sums (where $X$ and $[n]$ are multisets and $n$ is ...
0
votes
1
answer
137
views
How to compactly write a simple set for 2 variables when second variable may have same properties as first or it may optionally be positive infinity?
A Little Bit of Background (May Be Skipped)
It's been about 40 years since learning higher math like partial differential equation and linear algebra including simple tensors but never needed much of ...
- 868
0
votes
2
answers
162
views
Bijection between $3^{\mathbb N}$ and $\mathcal P(\mathbb N)$?
Since $\mathcal P(\mathbb N)$ is the set of all subsets of $\mathbb N$,
For each element $a \in \mathbb N$ and every subset $S\subset N$, we can define a function $f$:
$f(a) = 0$ if $a \notin S$
$f(a) ...
- 2,881
2
votes
2
answers
760
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. ...
- 763
0
votes
1
answer
31
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
1
answer
52
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
0
votes
0
answers
54
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
0
votes
1
answer
101
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
1
vote
0
answers
72
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
2
answers
75
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
$$
...
- 899
0
votes
0
answers
85
views
Combinatorial proof of this identity [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 ...
- 899
1
vote
0
answers
33
views
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 ...
- 173
0
votes
2
answers
400
views
How to Prove this Multiset Identity by Combinatorial Proof
I was wondering how to do a combinatorial proof of the following identity: $\bigl(\!\!\binom{n}{k}\!\!\bigr)$= $\bigl(\!\!\binom{n-1}{k}\!\!\bigr)$ + $\bigl(\!\!\binom{n}{k-1}\!\!\bigr)$ for all n, k ...
user945281
2
votes
2
answers
99
views
find number of unordered subsets of multiset
From a multiset $S = \{a, a, a, a, b, b, b, c, c\}$, how many ways are there to pick an unordered group of $3$ objects? (Objects of the same letter are identical.)
For example, in a set $\{m, n, n\}$, ...
0
votes
0
answers
109
views
Set-builder Notation for Sets of Sets
I have two questions about the set-builder notation for sets of sets. Technically, I believe they are multisets as multiple instances of the same element are allowed.
Let $A_i$ be a set of integers ...
0
votes
0
answers
49
views
Combinatorial problem about finding optimal subsets of numbers forming pairs
I am trying to solve a combinatorial problem computationally (currently using python) and cannot find a good algorithmic solution for it.
I have n individual numbers (eg. 0,1,2,3,4,5). These numbers ...
1
vote
1
answer
246
views
Multiset/Set/List initiation and use in pseudocode
I'm writing a paper and I've come across interesting problem. In my algorithm, I create a list of 0's (example [0,0,0,0]), where the number of 0's is given by parameter "x". Later I want to ...
- 193
0
votes
0
answers
53
views
How to count k-size multi-subset of a N-size multi-set [duplicate]
$A$ is a multiset $\{x_1, \cdots, x_1, x_2, \cdots, x_2, \cdots, x_j\}$ which has different objects $x_1, x_2,\cdots, x_j$ and the number of $x_i$ is $n_i$ ($\sum_{i=1}^{j} n_i = N$)
How many ...
- 905
2
votes
1
answer
26
views
How to get the smallest cardinality multiset that can add up to another set?
Suppose I have set $z = \{ 1, 5, 6, 10, 11, 35, 36 \}$
How can I find the smallest multiset $x$ that can add up to all the components of $z$?
For example, $x = \{1, 5, 5, 30\}$
...
- 121