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

0
votes
2answers
46 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
36 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
35 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
21 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
28 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
259 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
50 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
27 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
30 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
35 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
32 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
87 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
114 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 ...
9
votes
2answers
298 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
32 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
67 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
130 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
32 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
64 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
40 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$ ...
3
votes
3answers
92 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
31 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
67 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
60 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
260 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
177 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
165 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
41 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
49 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
35 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 ...
0
votes
2answers
75 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
32 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 ...
0
votes
0answers
30 views

Series of multi sets

Given that a set of numbers $K = \{n_1, n_2, n_3, ... \}$. Multiple subsets are formed by randomly extracted numbers from $K$. Then series are formed by extracting numbers from the subset orderly. ...
1
vote
0answers
22 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
139 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
67 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
81 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
65 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 ...
0
votes
1answer
56 views

Help With sets!

Can someone help me solve this question please?? Pretend you are writing traffic accident software and want to categorize accidents by the day of the week on which they occur. Pretend there are n ...
0
votes
1answer
61 views

Multiset: notation for size and number of unique items

Given a multiset, e. g. S = {1, 1, 2, 3, 4, 4, 5}, what would be a short, concise notation to express the number of unique items in the multiset? (five in the given ...