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

-2
votes
1answer
42 views

Infinite Sets Proof [closed]

I have a few questions regarding this problem below: Prove that if A and B are finite sets, then A ≈ B if and only if |A| = |B|. Would I assume that |A| = |B|? Which would obviously make A ≈ B ...
-1
votes
1answer
37 views

Combination and Permutation S= {A,B,B,C,C,C,D,D,D,D,E,E,E,E,E}.

S= {A,B,B,C,C,C,D,D,D,D,E,E,E,E,E}. If I choose n element from S, how many possible combination (unordered) and permutation (ordered) are possible (without using decision tree or counting)? What is ...
0
votes
1answer
22 views

Generating function for multiset formula

It's said that the generating function for $g(x) = \sum_{d=0}^\infty {d+m-1 \choose m-1} x^d$ is equal to $\frac{1}{(1-x)^m}$. In the proof that I have seen it states that: By the geometric series, ...
-1
votes
0answers
22 views

Multiset Combination without repetition

Now, How should we find the r-combinations of a multiset without repetition? Well, If there are repetitions allowed then we use ${k+r-1\choose r}={k+r-1\choose k-1}$. What should we do when ...
0
votes
3answers
39 views

Expectation Value of a Multiset

Imagine that I have $k$ balls randomly distributed (uniformly) among $n$ boxes. I.e., with repetition. How could I calculate the expected number of balls in a randomly chosen box?
0
votes
2answers
30 views

UpMultiset Combination-choose 3

Today I saw this question in a book: There are $12$ objects, $3$ of which are alike and the remainder all different. In how many ways can a selection of $5$ be made? I tried to answer: $k=11, ...
0
votes
1answer
28 views

Multiset Combination

How many Combinations can you make with the set {1,1,2,3,4} taken 2 at a time? If I do this in the way I do in Permutation: C(5,2) / 2!, I end up in wrong answer. Actually, there are 7 Combinations: ...
0
votes
2answers
25 views

Given that the relation that aRb if and only if the smallest element of a is is equal to the smallest element in b?

X is the set of all nonempty subsets of the set {1,2,3,4,5,6,7,8,9,10}. a,b are elements of X. a) Find the number of elements in the equivalence class [{2,6,7}]? ...
1
vote
2answers
34 views

Proving $\left(\binom{n}{k}\right)=\left(\binom{n-1}{0}\right)+\left(\binom{n-1}{1}\right)+\cdots+\left(\binom{n-1}{k}\right)$

Here, $\left(\binom{n}{k}\right)$ denotes the number of multisets in $N$ with length $k$. I can prove it using the fact that $\left(\binom{n}{k}\right) = \binom{n+k-1}{k}$ but I want another access. ...
1
vote
1answer
33 views

Algorithm for calculating multiset permutations

I have this algorithm to calculate multiset combinations: $$\mathcal P(k; m_1, m_2, \ldots, m_n) = \Sigma \binom{c(i_1)}{\lambda_1}\ \binom{c(i_2)-\lambda_1}{\lambda_2} \cdots ...
0
votes
0answers
14 views

Unordered Set Pair Formal Definition

I am stuck in what would be the best way to define a pair of unordered items. Say I have a set of items $D$. Now, I want to have a set of a pair of items. I currently defined that as $S=\left\{ ...
0
votes
1answer
67 views

Conjugate Partition and Multiset Equality

Suppose we have a partition of a number $n$, written as $(x_1, x_2, \dots , x_r)$. and its conjugate partition written as $(y_1, y_2, \dots , y_r)$ (assume that the conjugate has the same number of ...
1
vote
1answer
24 views

How to find explicit form of recurrence relation with four variables for combinatorical value

I want to know how many ways there are to choose $l$ elements in order from a set with $d$ elements, allowing repetition, such that no element appears more than $3$ times. I've thought of the ...
2
votes
1answer
31 views

Metrics for sets

Other than the Hausdorff metric, are there any common/useful metrics for sets? I'm having a bit of trouble finding any, though maybe I'm searching for the wrong things. I'd also be interested in ...
0
votes
0answers
20 views

Notation of a function from a set to a multiset

Given two sets $A$ and $B$ and a function $F$ from $B$ to multisets of $A$, e.g.: \begin{align} A &= \{x, y, z\} \\ B &= \{b_1, b_2, b_3\} \\ F(b_1) &= \{x,x,y\}\\ F(b_2) &= ...
6
votes
3answers
351 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
42 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
39 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
75 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
64 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
17 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
26 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
51 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
21 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
20 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
25 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
69 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
106 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
452 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
60 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
117 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
42 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
102 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
38 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
48 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
67 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
32 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
35 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
351 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
76 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
44 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 ...
1
vote
1answer
130 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
188 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
390 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
143 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\|.$ ...