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

6
votes
3answers
302 views

Give a combinatorial proof for a multiset identity

I'm asked to give a combinatorial proof of the following, $\binom{\binom n2}{2}$ = 3$\binom{n}{4}$ + n$\binom{n-1}{2}$. I know $\binom{n}{k}$ = $\frac{n!}{k!(n-k)!}$ and $(\binom{n}{k}) = ...
1
vote
1answer
40 views

Proof for sets and functions.

I have been proving problems like this all day with ease, but this is is just puzzling to me. Where do I start? Also, a site with questions and answers to problems like these.
0
votes
1answer
36 views

Help justifying unique 2n-1 sum pairs as (2n-1, {3, 5,…,2n-3,2n-1}) [closed]

Need help for a long proof I am doing. I need to justify that if I examine the set of {Odd+Odd}, the unique pairs exist if I utilize {2n-1, {3,5...,2n-3,2n-1}) If we have: 3 5 7 9 ...
1
vote
1answer
69 views

Probability of $X$ collisions on random selections from pool

I have a bag of $100$ marbles. I draw a marble at random and put it back in the bag. I do this a total of $50$ times. What is the probability that there is at least one marble which I picked at least ...
2
votes
1answer
63 views

How many solutions to the (general) equation?

I've been trying to hash this one out for the last few days. Please determine the number of solutions to the equation $x_1 + x_2 + x_3 + x_4 = n$, where $x_i \in N$, $x_1$ is even, $ 0 \leq x_2 \leq ...
1
vote
0answers
15 views

Multisets and cardinality

Consider $0<\lambda<1$, and let $A$ be a multiset of positive integers. Let $A_n=\{a\in A: a\leq n\}$. Assume that for every $n\in\mathbb{N}$, the set $A_n$ contains at most $n\lambda$ numbers. ...
2
votes
0answers
22 views

Combinatorics submultisets Inclusion-Exclusion

Find the number of submultisets of {$25 \cdot a, 25 \cdot b, 25 \cdot c, 25 \cdot d$} of size $80$. I applied Inclusion-Exclusion to get; $$ {80+3\choose 3} - {4\choose1}\cdot{80-26+3\choose3} + ...
2
votes
0answers
33 views

Combinatorics Inclusion - Exclusion Principle

Find the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = 25$ with $ 1 \leq x_1 \leq 6, 2 \leq x_2 \leq 8, 0 \leq x_3 \leq 8, 5 \leq x_4 \leq 9.$ Firstly, I defined $y_i = x_i - lower bound$ ...
2
votes
2answers
18 views

Number of ways to choose $4$ objects out of $6$ groups with $3$ members each

Suppose a box contains 18 balls number 1-6, three balls with each number. When 4 balls are drawn without replacement, how many outcome are possible? I took $6\choose4$ ways of picking the balls and ...
0
votes
0answers
19 views

Enumerate possibilities when choosing exactly one from 5 of 6 subsets

The problem Given an arbitrary number n of sets of possibly different sizes, generate an m-column matrix where the rows describe all possible combinations of elements with one taken from each set. ...
1
vote
1answer
24 views

How to do this simple set operation?

Suppose A and B are events with P(A) 0.4 , P(B) 0.6 and P(A and B) 0.25 . Calculate the probability P(A complement union B). A 0.25 B 0.65 C 0.75 D 0.85 What I tried?- ...
1
vote
1answer
60 views

Entropy of union of multisets

Assigning a random variable to some multiset: Assume that $S$ is a multiset. We can think of $S$ as independent sampling from some random variable. For instance, $S = \{H, H, T, T, T\}$ can be thought ...
1
vote
1answer
73 views

Combinatorial Proof for Multiset Identity

$$\left(\!\!\binom{n}{k}\!\!\right)= \displaystyle\sum_{j=0}^k \binom{n}{j}\left(\!\!\binom{j}{k-j}\!\!\right)$$ Let $X$ be a set of $k$ element multi set of an n-element set. Let $P$ be a set of ...
4
votes
2answers
411 views

Set, sequence, bag, or what?

I am dealing with finite collections of real numbers, which I will write in square brackets below. In these collections, repetitions are significant, so, for example $[1,1,5,7]$ is not the same as ...
0
votes
1answer
47 views

How to get matrix result of combinations of multiple sets' of elements?

I need to find a value within the result matrix of combinations of multiple set of elements. For example using these sets of elements: ...
0
votes
1answer
81 views

How to determine whether a set (R) is reflexive, symmetric or transitive

Trying to figure out what the differences between reflexive, symmetric and transitive are. Could do with a bit of help with the following examples. Like what makes it reflexive, what makes it ...
0
votes
1answer
40 views

How does permutation works in “multimatrices”?

I want to adequately define a $m\times n$ "multimatrix" that satisfies these properties: 0.A $m\times n$ multimatrix has $m\times n$ entries just like a normal matrix. It is the positions they occupy ...
1
vote
2answers
96 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
36 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 ...
0
votes
2answers
49 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
45 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
57 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
31 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
32 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
326 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
73 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
43 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
40 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
38 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
60 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
121 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
169 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
369 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
50 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
119 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
26 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
28 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
166 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
26 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
59 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
103 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
54 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
132 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
39 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
107 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 ...
9
votes
2answers
448 views

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. ...
3
votes
2answers
88 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 ...
3
votes
1answer
121 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
627 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
381 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 ...