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
23 views

Number of multisets with restrictions on specific element count

I am looking to find the number of multisets with restrictions on the number of specific elements. This isn't for homework, it is a work related problem. My set of items is {A, a, B, b}. I want to ...
2
votes
0answers
22 views

Inclusion-exclusion principle for multisets

Lets say I want to count the number of monic polynomials of degree $d$ in $\mathbb{F}_p[X]$ that have no roots in $\mathbb{F}_p$. Fix a $1 \leq k \leq d$ and choose $k$ distinct elements of $\mathbb{F}...
1
vote
1answer
19 views

Return a cross product of two sets A and B such that only one entry is returned based on a condition

Lets say I have a set $A={\text{'Akshat'},\text{'John'},\text{'Mike'}}$ and a set $B={\text{'Modi'},\text{'Kerry'}}$. Set $A$ represents a set of voters while $B$ represents a set of candidates for an ...
0
votes
0answers
16 views

Notation for combinations involving sum of products of elements of sets

I am looking for a concise notation to represent a set operation. The operation is as follows: Given a set $A = \left\{ {a,b,c} \right\}$ and another set $B = \left\{ {d,e,f} \right\}$ we define * to ...
0
votes
0answers
32 views

Calculate maximum value limit in set partition

I have all the subset of 4 element as follows with value associated with each subset ...
1
vote
1answer
54 views

Reverse and forward doubling identity in Fibonacci sequence $\text{mod 9}$

Fibonacci sequence ($\mathbb{F}$) has a repeating cycle known as Pisano number $\pi\text{(x)}$ , when $mod \text{ x}$ is applied upon the sequence. Length of the cycles can be found from: http://oeis....
1
vote
0answers
101 views

Finding total number of multi-sets

I am provided with a multi-set, let's say S with elements as [num1, num2, num3] and these elements are integers (both negative as well as non negative). As this is a multi-set, elements in the multi-...
3
votes
3answers
63 views

how many strings of length 21 from letters {D,L,O} with repetition that have DOLL appearing only once

The word DOLL has length $4$. There will be $18$ possible positions where 'DOLL' can appear, each with $3^{17}$ choices. So there will $18 \cdot 3^{17}$ cases where it can appear at least once. But I ...
0
votes
2answers
51 views

How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies?

A cookie store sells 6 varieties of cookies. It has a large supply of each kind. How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies? For my answer, I put $6 \cdot 6 \...
0
votes
0answers
53 views

Formula for combinations-

While I was thinking I found this formula: $\binom{n-k}{r-k} + \binom{n-k}{r-k +1} + \binom{n-k}{r-k +2} + ....+ \binom{n-k}{r-k +r}$ Where ...
0
votes
1answer
64 views

Choose 3 letters.

Find in how many ways an arrangement of $3$ letters can be made from the $26$ different letters of the alphabet if any letter may be used once, twice or thrice. How many of these arrangements will not ...
-4
votes
1answer
55 views

Prove $\left(\dbinom nk \right)= \left(\dbinom{k+1}{n-1}\right)$ [closed]

I need to prove $\left(\!\dbinom nk \!\right)= \left(\!\dbinom{k+1}{n-1}\!\right)$ where the double parens denote multiset coefficients and $n,k$ are integers with $1 ≤ k≤ n$ using an algebraic proof. ...
-2
votes
1answer
51 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
46 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
25 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, $...
0
votes
3answers
48 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
44 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, r=...
0
votes
1answer
35 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
37 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
48 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 \binom{c(i_s)-\lambda_1-...
0
votes
0answers
16 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\{ \{i,...
0
votes
1answer
70 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
26 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
32 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) &= \{y,z,z\}\...
6
votes
3answers
359 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}) = \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
40 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
0answers
86 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
20 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} + {4\...
2
votes
0answers
56 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
22 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
27 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?- P(A ...
1
vote
1answer
78 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
113 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 $j$...
4
votes
2answers
499 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
77 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
137 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
122 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
40 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
78 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
35 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
39 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 ...