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
0answers
26 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
votes
0answers
9 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
53 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
99 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
271 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
28 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
56 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 Distal Points or Farthest points of sets

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 $ u_x\in K: \|x-u_x\|=\min\limits_{u\in K}\|x-u\|.$ Question: ...
0
votes
0answers
12 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
13 views

On Proximinal sets

A subset $K$ of a Hilbert space $H$ is called proximinal if every $x\in H$ has a vector of minimum norm. Question: How do I show that if $K$ is proximinal and bounded, then $K$ also has ...
0
votes
0answers
13 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
107 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
21 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
26 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
53 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
33 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
76 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
26 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
44 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 ...
2
votes
2answers
72 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
43 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
161 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
138 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
157 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
1answer
31 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
31 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
42 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
34 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
59 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
40 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
63 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
34 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
31 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
29 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
19 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
134 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: ...
0
votes
0answers
7 views

Weighted ordering of subgroups

As you may have guessed by my title, I've got no background in maths, but I think this is the right bit of StackExchange to ask in and hopefully I've picked the right tags... but forgive me if not ! ...
2
votes
1answer
45 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
30 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
19 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
53 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
56 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
55 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
51 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 ...
1
vote
1answer
118 views

Solving problem involving intersection of sets

In a certain office,one-quarter of the staff are left-handed. One-twelfth of them are left-handed and short-sighted; 13 are short sighted while 17 are neither left handed nor short-sighted.Find the ...
0
votes
1answer
51 views

How to represent a multiset?

I have a graph $G(V,E)$ and each $v_i\in V$ has a value $v_i\cdot s$ ($v_i\cdot s$'s are not unique). How can I show a multiset representing the $v_i\cdot s$'s? This is what I have come up with so far ...
0
votes
2answers
95 views

Two sets given : solve $A \cup X = B$

Do you know how to solve this problem? I have two sets and need to solve $A \cup X = B. $ Thanks a lot for your help.
0
votes
1answer
82 views

Exterior square of multiset in representation theory

General Setting: In a paper I'm working on, the author uses multisets to describe the representation theory of the cyclic group $G = C_n = <\sigma>$ of ...
1
vote
1answer
95 views

Select r items from a set with multiplicity k and total items n.

Let N be a set of n distinct objects having the same multiplicity k. For instance, N={1,1,2,2,3,3} where n=3 and k=2. Now I want to select r numbers from ...
0
votes
1answer
75 views

Inclusion of sets

let $F$ be a multi application :$F: X\leadsto Y$ I have this definitions "If $B\subset Y$ is an non empty set we have : $F^{-1}(B)=\lbrace x\in X, F(x)\subset B\rbrace $ $F^{-1}_+(B)=\lbrace x\in ...