Questions tagged [multisets]

For questions about or related to multisets, a notion similar to sets with the difference that elements can be repeated.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Measure of uniformity that compares multisets with different number of elements?

Suppose we have multisets $A=\left\{a_1,...,a_n\right\}$ and $B=\left\{b_1,...,b_r\right\}$ and suppose A multiset is uniform (or has uniformity) when $a_1=\cdot\cdot\cdot=a_n$ and $b_1=\cdot\cdot\...
1
vote
1answer
49 views

Subsets that add up to zero in finite sequence {1,-1,1-1..}

This problem must be simple, but it's driving me crazy (Following the comments I edit) If I have for example the following sequence $\{1, -1, 1, -1, 1, -1, 1, -1\}$ and ask how many subsets of two ...
0
votes
0answers
32 views

Combinations on multisets and ordered pairs

I came across this question while doing some revisions. There are 3 parts to this question. One of them I asked here before. Suppose you have a series of scrabble tiles, each tile has one letter on it,...
0
votes
1answer
37 views

Growth of n multichoose k when n and k increase by the same number

The multiset coefficient $$\left (\binom{n}{k} \right ) = \binom{n+k-1}{k}$$ denotes the number of multisets of cardinality k, with elements taken from a finite set of cardinality n. I'm interested ...
1
vote
0answers
33 views

Counting partitions of fixed size in a specific multiset

If we have the multiset $$\{1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5\},$$ i.e. five distinct elements and five of each type, how many ways can we partition this multiset into five equally ...
0
votes
0answers
26 views

Intuitive explanation for the equality of n-permutations and (n-1)-permutations

I observed this while reading about the Permutation of a Multiset, that the equation which comes out for n-permutations of n objects consisting of n1, n2, n3,..., nk similar objects is the same as (n-...
1
vote
2answers
61 views

Proving combinatoric identity using vote casting example.

I'm still having trouble giving a combinatorial proof of this identity using the vote casting example: $$ \sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0 $$ ...
0
votes
0answers
82 views

Combinatorial proof of this identity [duplicate]

I'm trying to give a combinatorial proof of this identity: $$ \sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0 $$ I think the right-hand side could be ...
1
vote
0answers
29 views

How would one distribute $a$ alike things of one kind and $b$ alike things of other kind and rest different things into groups

My question is that how would one count the number of ways to distribute things from a group of different things and different groups of alike things (for e.g., $a$ alike things of one kind, $b$ alike ...
0
votes
2answers
193 views

How to Prove this Multiset Identity by Combinatorial Proof

I was wondering how to do a combinatorial proof of the following identity: $\bigl(\!\!\binom{n}{k}\!\!\bigr)$= $\bigl(\!\!\binom{n-1}{k}\!\!\bigr)$ + $\bigl(\!\!\binom{n}{k-1}\!\!\bigr)$ for all n, k ...
2
votes
2answers
60 views

find number of unordered subsets of multiset

From a multiset $S = \{a, a, a, a, b, b, b, c, c\}$, how many ways are there to pick an unordered group of $3$ objects? (Objects of the same letter are identical.) For example, in a set $\{m, n, n\}$, ...
0
votes
0answers
62 views

Set-builder Notation for Sets of Sets

I have two questions about the set-builder notation for sets of sets. Technically, I believe they are multisets as multiple instances of the same element are allowed. Let $A_i$ be a set of integers ...
0
votes
0answers
40 views

Combinatorial problem about finding optimal subsets of numbers forming pairs

I am trying to solve a combinatorial problem computationally (currently using python) and cannot find a good algorithmic solution for it. I have n individual numbers (eg. 0,1,2,3,4,5). These numbers ...
0
votes
0answers
14 views

TOP p most informative elements in a mutually recursive multisets?

Let say we have two groups of multi-sets /repeatable elements are allowed/ i.e. ...
1
vote
1answer
60 views

Multiset/Set/List initiation and use in pseudocode

I'm writing a paper and I've come across interesting problem. In my algorithm, I create a list of 0's (example [0,0,0,0]), where the number of 0's is given by parameter "x". Later I want to ...
0
votes
0answers
26 views

Sampling multisets uniformly at random

In his 2005 paper Analysis of the Bose-Einstein Markov chain Persi Diaconis writes at the end of Section 2: Of course, there are other, easier ways to directly generate Bose-Einstein configurations. ...
0
votes
0answers
34 views

How to count k-size multi-subset of a N-size multi-set

$A$ is a multiset $\{x_1, \cdots, x_1, x_2, \cdots, x_2, \cdots, x_j\}$ which has different objects $x_1, x_2,\cdots, x_j$ and the number of $x_i$ is $n_i$ ($\sum_{i=1}^{j} n_i = N$) How many ...
2
votes
1answer
24 views

How to get the smallest cardinality multiset that can add up to another set?

Suppose I have set $z = \{ 1, 5, 6, 10, 11, 35, 36 \}$ How can I find the smallest multiset $x$ that can add up to all the components of $z$? For example, $x = \{1, 5, 5, 30\}$ ...
1
vote
0answers
48 views

Understanding MacMahon's formula for k-combinations on finite multisets

According to this paper, MacMahon's formula for finding $k$-combinations in finite multisets is given as follows. Let $A = \{m_1 \cdot a_1, m_2 \cdot a_2, ..., m_n \cdot a_n \}$ be a multiset, in ...
1
vote
0answers
44 views

Can we apply the symmetric difference operation on two multisets?

I was just reading about multisets and operations on them. I didn't find mention of applying symmetric difference on multisets. Can we apply the operation on multisets like we can over sets? I ...
0
votes
0answers
10 views

multiset integral decomposition

Problem: given a multiset S of positive integers, find (if they exist) two nontrivial (with more than 1 element) multisets X and Y such that S is equal to the Minkowski sum of X and Y. Minkowski sum ...
1
vote
1answer
28 views

Let X, Y, Z and W be sets defined on the universal set $U = N $ as follows: How can I solve this Venn Diagram?

So I have the following assertions and I have to illustrate this on a Venn Diagram. $ (X - Y) \cap Z = ${1,2,3,4} $ Y = $ {5,6} $Z \cap Y = \emptyset $ $ W \cap (X - Z) =$ {7,8} $ X \cap W \cap ...
0
votes
1answer
23 views

Is it possible to show that no multiset may exist to satisfy a given constraint without knowing the multiplicity of the set's elements?

I'd like to preface my question by stating that I have no education in mathematics beyond A levels (UK), which was 7 years ago, so I apologise if I'm asking a silly question or if I misuse any terms. ...
0
votes
1answer
81 views

Let $n$ be a positive integer. Determine the number of solutions to $x_1 + \cdots + x_k \leq n$ with nonnegative integer solutions.

Let $n$ be a positive integer. Determine the number of solutions to $x_1 + \cdots + x_k \leq n$ with nonnegative integer solutions. Determine the number of solutions with positive integer solutions. I ...
0
votes
1answer
28 views

Why is the sum of multiplicity lengths the same as the cumulative sum of partitions up to the previous integer?

Let $\lambda$ be a partition of $N$ ($\lambda\vdash N$). In the multiplicity representation, $\lambda=(a_{1},a_{2},\ldots a_{m(\lambda)})$, such that $$\sum_{k=1}^{m(\lambda)}{ka_{k}}=N,$$ where $m(\...
3
votes
2answers
122 views

Number of possible Scrabble draws

I would like to compute the number of Scrabble draws, when starting a game. Translated to mathematics, this asks for the number of sub-multisets of a multiset. Lets say we have a multiset $M$ over a ...
1
vote
1answer
52 views

Can a multiset be a subset of a set?

This is a bit of a silly question but its bothering me. Given a multiset say $p=\{a,a,g,h,h\}$ And another set $t=\{a,g,h\}$ Can I say that $p\subset t$. In other words is p a subset of t?.
0
votes
1answer
40 views

Number of multisets with at most twice the same element

I know that the number of multisets of cardinality $K$ with elements taken from the set $\{1,...,N\}$ is $\binom{N+K-1}{K}$. I only want to consider the multisets such that an element appears at most ...
1
vote
4answers
167 views

Multiset identity.

How does one get to the following combinatorial identity: $$\sum_{i=0}^{k-1}\binom{n}{i+1}\binom{k-1}{i}=\binom{n+k-1}{k}$$ I'm well aware of the definition of a multiset, as well as of the derivation ...
0
votes
0answers
14 views

Homogeneous multiset functions such that $f(S) = f(S \setminus T \cup \{f(T)\})$

Let $f$ be a multiset function: it takes any finite multiset $S$ as input and outputs a number $f(S) \geq 0$. For instance, $f(S)$ might be the size of $S$; it might measure the "length" of $...
1
vote
2answers
77 views

Analysing ways to choose $m$ naturals from set of first $n$, s.t. they differ by $\ge k$.

Ways to choose $m$ distinct natural numbers from set of first $n$ natural numbers, s.t. the chosen natural numbers differ by at least $k$. Request vetting for my approach: The numbers to be chosen are ...
0
votes
1answer
33 views

Counting the number of distinct groups with and without repeat items

Here's a simple question that popped into my head. I shouldn't be struggling with but am. Suppose there are $n$ objects. We want to find the number of distinct groups. First let's take the case where ...
0
votes
2answers
48 views

Expected number of distinct elements when drawing from a multiset with replacement

Suppose I have a multiset $M$ with elements $1,\dots,m$ and respective multiplicities $n_1, \dots, n_m$: $$ (1, n_1) \\ (2, n_2) \\ \dots \\ (m, n_m) $$ What is the expected number of distinct ...
0
votes
1answer
43 views

Number of combination with repetitions containing a subset of all the root element

I am in trouble with this question: Given the set $S$={$a,b,c,d,e,f$} and 10 position to arrange these elements. How many combination with repetitions exist if the only allowed must contain at least ...
0
votes
1answer
35 views

Finding the R-minimal and R-maximal

For any two integers $a,b$, we say that $a$ divides $b$ (written as $a\mid b$) if $b=ak$ for some $k∈\Bbb Z$. Let $A=\{3,6,7,9,12,14,21,42,252\}$. Consider the partial order relation $R$ on $A$ given ...
0
votes
1answer
18 views

Determining what relation means

If we have to consider the relation R from {1,2,3,4} to {3,4,6,7,9} given by aRb ↔ b = a + 3 then would the relation given be {1,2,3,4,6,7,9}? I'm a little confused on what is meant when I'm being ...
2
votes
0answers
72 views

Counting permutations of multisets obtained from the prefix sum of certain integer arrangements

Consider distinct arrangements of $k$ nonnegative integers that sum to $s$ with the the additional condition that the sum of every other integer is $t \le s$. A bijective mapping of these arrangements ...
3
votes
1answer
29 views

Finding relation of two sets

If A = {1, 2, 3} and B = {1, 2, 3, 4}, would R = {(a, b) ∈ A × B | b = a^2} be {(1,1), (2,4)} since the only time that b = a^2 is true is when (A,B) = (1,1) and (A,B) = (2,4)?
0
votes
1answer
22 views

How can i resolve this point (a,b) combinations?

In a given programming language, an identifier is a sequence of a certain number of characters in which the first character must be a letter of the English alphabet and the rest can be a letter or a ...
1
vote
2answers
129 views

In how many ways can 15 identical math books be distributed to six students?

question: In how many ways can 15 identical math books be distributed to six students? i try do this: P(15,6) could be this the answer or i should check the question, i find out other? help please
0
votes
0answers
91 views

Defining the Set of Rational Numbers

I was wondering about how to define the set of rational numbers, as I am currently learning about set theory in a class of mine. We were going through using set builders to define sets and produced ...
3
votes
2answers
199 views

How many groups of pentagonal flower bouquets can be formed?

A florist has three types of flowers: tulips, roses, and daisies. There are 4 tulips, 5 roses, and 6 daisies. These 15 flowers are to be arranged into three bouquets of 5 flowers each. Assume that ...
0
votes
0answers
59 views

How is Set Difference Defined for Multisets?

I'm interested in understanding the definition of set difference in multisets, but haven't been able to find a definition online. For an example, suppose $A = \{a, b, b, c, c, c\}$ and $B = \{a, b, c\}...
1
vote
1answer
36 views

Determine sets A and B

I need help solving this task, if anyone had a similar problem it would help me. The task is: Determine sets A and B if valid: $ A\cup B = \left\{x\in \mathbb{N} : x\le6 \right\}, A\cap B = \left\{x\...
0
votes
0answers
24 views

Some sum of two elements exceeds a third one in a finite multiset with bounded values

For a multiset $S = \{ a_1,a_2,a_3,\ldots,a_k \}$ where $k = 13$ and $1 \leqslant a < 32$, prove that there exists a subset $s = \{ a_i, a_j, a_k \}$ such that each sum of two elements exceeds the ...
0
votes
1answer
36 views

How do you translate 'positions of a value 2' into a mathematical notation when defining a bijection?

Let's say I have a multi-set: $(1,1,2)$ And I want to define a bijection from $A$ to $B$ such that: $(1,1,2)$ becomes {3} and, $(1,1,1)$ becomes {} and, $(2,2,2)$ becomes {1,2,3} or, in general, it is ...
0
votes
1answer
85 views

Find number of ways to divide a set into 2 parts

In how many ways can we divide a set into 2 parts having an element in equal number in both of resulting subsets. For example, multiset = {1, 2, 3, 5, 5, 5, 5} and ...
3
votes
1answer
143 views

Multiset equivalence

Let $a,b,c,d,e,f,g,h$ be natural numbers such that the multisets $\{a,b,c,d,a+b,c+d\}$ and $\{e,f,g,h,e+f,g+h\}$ are the same. Can we say that $\{a,b\}=\{e,f\}$ or $\{g,h\}$ ? and similarly $\{c,d\}=\{...
1
vote
1answer
237 views

Permutation with Repetition Index Conversion

I'm looking for the equation to determine the index of a permutation with repetition with known parameters. For example: A total of $9$ values, $4$ A's and $5$ B's Gives a total of $126$ permutations ...
2
votes
1answer
118 views

Counting k-combinations excluding duplicate mathematically

Let's say I have a multiset of integers a with a size n (here n = 10) $$a = \{1, 1, 2, 2, 3, 4, 5, 6, 6, 10\}$$ I'd like to know ...

1
2 3 4 5
7