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

learn more… | top users | synonyms

1
vote
2answers
57 views

Why is it called a “multiset”?

According to Wolfram MathWorld, "A set is a finite or infinite collection of objects in which order has no significance, and multiplicity is generally also ignored ..." and A multiset is "A ...
1
vote
1answer
32 views

Has anyone ever suggested a name or notation for this operation on multisets?

A basic multiset identity says: $$A+B = (A \cap B) + (A \cup B)$$ Allowing ourselves to use negative multiplicities and rearranging: $$A-(A \cap B) = (A \cup B)-B$$ But since $A \supseteq (A \cap ...
-4
votes
0answers
20 views

Quiz: examples for trivial subsets. [duplicate]

trivial subsets examples, please insert 3 examples. its for my quiz tomorrow hope that you'll help me. i've tried to look from any resources. but it doesn't tell me the explanations of each examples. ...
0
votes
2answers
48 views

How do I evaluate this combinatorically?

I recently came across this problem and couldn't even start on it. Would someone be able to help me? Given $m$ identical symbols, say H's, show that the number ...
0
votes
0answers
40 views

understanding uniform distribution on multiset

If I have a set of words that form a text, say text $a$, and a set of texts, I then calculate the similarity between text $a$ and each text in the set. Then, I get a multiset. For example: $$s = ...
1
vote
2answers
39 views

Generate all multisets of length k for n symbols [duplicate]

I am trying to generate a list of all multisets of length $k$ in a set with $n$ symbols. For example, if I had the set $S = {A, B, C}$ I would expect the following output for $k = 2$ and $n = 3$: ...
2
votes
0answers
22 views

composition of relations and multiset relations

As is well known, composition of relations is defined as $$R\circ S = \{(a,b):\exists x: (a,x)\in S \land (x,b)\in R\} \tag 1$$ This is formally the very same definition as for function composition. ...
1
vote
1answer
29 views

Why do we study multi-valued(set valued) mappings?

I am working on a problem that has to do with multi-valued mappings. Precisely, Iterative methods for Fixed points for multivalued mappings. However, I have no clear motivation for studying such ...
10
votes
0answers
266 views

Distributing groups of objects into boxes

How can I enumerate the number of ways of distributing distinct groups of identical objects (but various cardinality) into $k$ boxes such that at most one box is empty $(1)$ and no combination of ...
2
votes
2answers
53 views

How many ways can I sort 50 distinct items into 2 lists with no repetition, order matters?

I must use all $50$ items, but either list can be empty. I know that the default answer is $2^k$ for $k$ elements when order does not matter. However, I am not sure how to arrive at the answer when ...
1
vote
0answers
39 views

Existence of increasing pair of labeled trees in an infinite sequence

Assume labeled rooted trees with labels from a fixed set $\{1\ldots m\}$. For a tree $T$, we have: $V(T)$ the set of vertexes, $root(T)$ the root of the tree, $l_T: V(T)\rightarrow \{1\ldots m\}$ ...
0
votes
1answer
32 views

multiset/combination question

I have a bag full of: 7 green rocks, 12 yellow rocks, and 15 red rocks. How many ways are there to reach in and grab 4 rocks? Is the answer 37C34 (37=7+12+15+4-1) or 6C3 (6=3+4-1)...or something ...
1
vote
0answers
36 views

Data analysis: How did people beat the Great Hall game?

This is the game: There is a Great Hall with 102 doors. 100 of these doors lead to one of 100 different side rooms. The 101st door, at the end of the Great Hall leads to the Great Tower, where ...
-2
votes
1answer
37 views

question related to sets

What is the difference between Ordered and unordered pair of subsets? And s=1,2,3,4. how to find total unordered disjoint sets?
1
vote
1answer
95 views

How many unique ways can I sum $k$ non-negative numbers to $N$?

I have a similar question but not exactly the same as this. I'm trying to determine the number of unique multisets $S\in \mathbb{N}$ that exist when the members are required to sum to a number $N$. ...
1
vote
1answer
123 views

How to calculate sum of combinations with different n and k

Input: $[X,Y]$ and $L$ Output : no of increasing sequence of length L and all elements should be $X\le i \le Y$ e.g: for $[6,7]$ and $2$ sequences are $6,66,67,7,77.$ For the above question my ...
10
votes
2answers
325 views

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 ...
2
votes
1answer
33 views

Number of multisets on $[2m]$ which satisfy certain conditions.

I am trying to find the number of $n$-element multisets on $[2m]=\left\{1, \ldots, 2m\right\}$ such that $m+1, \ldots, 2m$ appear an even number of times in the $n$-multiset. I have tried several ...
-1
votes
2answers
75 views

counting non-unique sub-multisets of a set.

Thank you all for your replies. I am so sorry for the inconvenience, I think I have messed up a lot in here. I'll just rephrase the whole question again. Let N be the original set which follows the ...
0
votes
0answers
22 views

On the farthest point of sets

It is known that a subset $K$ of a Hilbert space $H$ is called proximinal if every $x\in H$ has a vector $u_x$ of minimum norm in $K$. i.e $\exists u_x\in K: \|x-u_x\|=\min\limits_{u\in K}\|x-u\|.$ ...
0
votes
0answers
19 views

Equation involving multiset addition

I'm working with multisets and I need to know some properties about addition. I'm uncertain about the third equivalence. $$M_1 + M_2 = \{\} ↔ M_1 = \{\} ∧ M_2 = \{\}$$ $$M_1 + M_2 = \{x\} ↔ M_1 = ...
8
votes
3answers
134 views

Uniformly Random Tuples

Consider a multiset of natural numbers. As an example take $$ M = \{1, 2, 2, 3, 3, 3\} $$ If we treat copies of the same number as indistinguishable, there are 8 distinct 2-tuples we can form from ...
0
votes
1answer
24 views

N choose K and assumptions.

I have a process by which people must compare a bunch of items against each other in pairs. For now, let's say we're comparing two at a time from a set of six items. The problem is that people end up ...
1
vote
0answers
37 views

The parity of the sum of a multiset (of integers) and of the cardinality of the odd submultiset are equal

This is a fairly simple concept, yet surprisingly difficult [for me] to state simply. Given a multiset of integers, $M$, of finite (but arbitrary) cardinality. And, $S_m$ is the sum over the ...
1
vote
2answers
67 views

Partition of not-so-distinguishable objects into indistinguishable bins

Every textbook on combinatorics seems to deal with either totally indistinguishable objects and bins, or completely distinguishable objects and bins. What I have is something in between: objects are ...
1
vote
0answers
42 views

Strict total ordering

I'm not able to understand how the below relation is example of "strict total order". Consider a set $X = 2^Y$ where $Y = \{1,2,3,4,5,6,7,8,9\}$. The expected order of $X$ is for all $x, y$ ...
4
votes
3answers
107 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
1
vote
1answer
32 views

How to denote the result of application of a function on items from other multiset?

Let $A$ be a set, i.e. $A=\{2,3\}$. Then it is common to denote by $\{f(a)|a\in A\}=\{f(2),f(3)\}$ the result of application of function $f$ on items from $A$. But this work just for sets. How is ...
1
vote
1answer
75 views

What is the name for this Cartesian product-like operation?

I have two sets of multisets, like this: a: { { 11, 21, 31, 41 }, { 12, 22, 32, 42 }, { 13, 23, 33, 43 } } b: { { 21, 121, 131 }, { 22, 122, 132 } } I'm combining them together into another set of ...
3
votes
2answers
83 views

Pulling balls from a box

This is a homework problem I just need checked before I hand it over. It seems deceptively easy so I'm not sure if I'm missing something. In a box there are $10$ balls, each coloured differently. In ...
2
votes
2answers
62 views

Verify one of DeMorgan’s Laws for sets

Verify one of DeMorgan’s Laws for sets: $$\bigcap \{S\setminus U:U \in \mathcal U\} = S \setminus \bigcup \{U :U \in \mathcal U\}.$$ Can anyonw show me how to do this? a little confused, thanks
4
votes
2answers
300 views

Using Sticks and Stones for Counting number of Ways

From the first twenty positive integers, how many ways can we select 6 integers so that no two integers from the six chosen ones are consecutive? I tried using sticks and stones, but my thought ...
0
votes
1answer
194 views

Combinatorial proof (multi choose)

I'm struggling to explain why these two sides are equal in a non algebraic way. Basically I'm looking for a combinatorial proof of why these sides are equal. I know they are equal by algebra. N ...
4
votes
1answer
168 views

Unfamiliar notation in an AoPS paper

Here it is, from this paper: Proposition 5.1.1. The number of skyline polyominoes of area $A$ and width $w$ is $\left(\!\binom{w}{A-W}\!\right) = \binom{A-1}{w-1}$. I'm referring to the first ...
0
votes
2answers
42 views

$r-$ combinations of multisets

I have the topic $r-$ combinations of multisets in my notes Let $S=\{\infty a_1,\infty a_2,\ldots ,\infty a_k\}$ , then the formula for the $r-$*combinations of S* is given as: ...
0
votes
2answers
34 views

Probability with Multiple Sets and Anti Sets

Calculate: $P(A \cap B'\cap C')$ Given: $P(A) = 0.7$ $P(B) = 0.8$ $P(C) = 0.75$ $P(A \cup B) = 0.85$ $P(A \cup C) = 0.9$ $P(B \cup C) = 0.95$ $P(A \cup B \cup C) = 0.98$ I can upload a pic of my ...
0
votes
3answers
50 views

Combinatorial problem - multisets

As I am solving some basic combinatorial problems today, I found out this problem: How many different 5-digit numbers can be formed from digits 2, 2, 7, 7, 9? Can someone guide me to a solution for ...
1
vote
1answer
36 views

Solving basic combinatorics

I started course in combinatorics and, as I'm still not much into it, I'm solving some basic problems to start with. So here is one of them: How many 5-digit positive integers are there such that 9 ...
0
votes
1answer
64 views

Structural Induction Subsets

Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition: • $(3, 2) \in S$ (basis) • If $(x, y) \in S$, then $(3x − 2y, x) \in S$ ...
1
vote
1answer
49 views

Maximum product for multisets with same sum

Given a positive number N, among all multisets (containing only positive numbers) with sum N, is there a reliable method for determining the set with the maximum product? For example, for N = 5, the ...
1
vote
2answers
88 views

Permutations of a Multi-Set

Find the number of permutations of the multi-set {m.1,n.2}, where m,n $\in N $, which must contain m 1's. I thought the permutation is $\frac{(m+n)!}{m!n!}$ since multi-set is basically a collection ...
1
vote
0answers
38 views

Question concerning defining a particular class of functions

I have a multiset of real numbers $X \subseteq \mathbb{R} $ and I want to create a class of injective function to map the elements of $X$ to the unit interval(so basically a normalization). However ...
4
votes
1answer
33 views

Maximum operation order for a set of integers

Say we are given the positive integers $[1,1,2,2,3]$ We want to know what the maximum number is using only the operators $+$, $\times$. For this set the maximum operation is ...
1
vote
0answers
23 views

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 ...
1
vote
1answer
142 views

Count the number of ways n different-sided dice can add up to a given number

I am trying to find a way to count the number of ways n different-sided dice can add up to a given number. For example, 2 dice, 4- and 6-sided, can add up to 8 in 3 different ways: ...
2
votes
1answer
69 views

What is Vandermonde's formula with multisets?

I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation? Here's the original: $$ ...
1
vote
1answer
32 views

Name for a generalized relation to be a multiset?

A relation between two sets $A$ and $B$ is a subset of $A \times B$. If taking a multiset subset of $A \times B$, e.g. allowing $(a,b)$ appears twice in the subset, is there a name for such a ...
0
votes
1answer
21 views

Is there any special name for an algebraic structure (set, equivalence relation)?

I've seen the term "real multiset" but it doesn't seem to be very appropriate so i wonder whether there are any others. My second question is about multisets. In most sources i've seen one of the ...
1
vote
0answers
86 views

Notation to count tuples

I have the following set: V={(0,0),(1,2),(1,3),(2,2),(3,2)} I need to count tuples containing x = 1. Can I use |V_{(1,y)}| ? Or I should use |{(x,y) \in V | x = 1}| ? Thanks, Luiz
1
vote
1answer
69 views

Number of k-colorings as a fraction of all possible ways to color a graph

I have a graph with $n$ verices, and I want to compute the number of ways to color the graph (with no adjacent vertices having the same color) using anywhere between $1$ and $n$ colors. This number ...