Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [multisets]

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

0
votes
0answers
14 views

Can a Multiset product, mapping the relation x intersects y draw a roadmap

Can a multiset product ( like a cartesian product on sets) plotted with the relation x intersects y, draw a road map ? I tried this once before with sets (doesn't work with angling streets), but ...
0
votes
0answers
19 views

Partially ordered multiset

I am interested what is the basic idea of partially ordered multiset (also called pomset)? So far the references I find online are quite convoluted and hard to read. For example, in a pomset $\{x,x,...
1
vote
0answers
21 views

Finding set with equal-size intersection given a set family

I'm wondering if there are any non-trivial sufficient conditions (or even just a google-search-friendly name for) for the following scenario: I am given a set family $\mathcal{F}$ on ground set $E$ (...
0
votes
2answers
17 views

Calculating r-combinations by hand (canceling out numbers in the denominator)

My textbook does an interesting cancellation process to simplify the r-combinations. How does this process work? How do you cancel out $4!$ with $19*18*17*16$? BTW how do you do this 31! with <...
0
votes
0answers
36 views

Category of multisets, spans and pullbacks

I want to define a category of multisets, $Multi$. To do this, I take the ambient category $SET$, and represent the multisets as functions. So, the objects $Multi$ are functions. We define ...
1
vote
0answers
34 views

Representing multisets

Multisets are like sets, but the "elements" can have multiplicities. An example is $M = \{ a,a, a, b,c,b,c \}$. We can present the multiset by giving the multiplicities for each set element. Can we ...
0
votes
0answers
13 views

Multisets of scalars from a multiset of real vectors

Suppose that we have a multiset $M$ of real vectors of dimension 3 such as $M = \{\{(1,2,3),(1,5,6),(7,8,9)\}\}$. How can we define a multiset $M_n$ containing the $n$-th components of the vectors in ...
0
votes
1answer
26 views

Applying a function on any multiset of real numbers

I would like to define a function whose domain is any multiset of real numbers and image is a real number. To my understanding, the domain of a function that can be applied on any set of real numbers ...
0
votes
1answer
18 views

Reference request: Set of n-Multisets of elements in $\mathbb{N}$ is countable set

Let $n \in \mathbb{N}$ be fixed. I need a reference for the statement, that the collection of multisets of length $n$ with elements in $\mathbb{N}$ \begin{equation} M_{\mathbb{N}} = \{ \{a_1, ..., ...
1
vote
1answer
35 views

Permutations of pairs with restrictions

$n$ friends get together and decide to play a game. Thankfully one friend has a deck of $n$ cards, numbered from $1$ to $n$. How the Game Works The group splits into pairs (the game only works when ...
1
vote
0answers
34 views

Is possible to represent natural number X without 'splitting' it as additive-finitely repeated element set property?

I have a $Set$ of elements $n$ (a multiset). Each element of this set $n$ is the same, is a multiset because one element $n$ is replicable using addition operation, in other words we can have finitely ...
2
votes
1answer
95 views

Formula for r-Permutations of a Multiset

Suppose we have a multiset $M$, which contains $k$ distinct elements. Each element $x_i$ has multiplicity $n_i$ for each $i\in\Bbb{N}$ such that $0\le i<k$. $n$, the number of elements in $M$ ...
0
votes
1answer
29 views

Proof - Make two array same with minimal element increment or decrement

The problem goes like this: Given two arrays of same size, we need to convert the first array into another with minimum operations. In an operation, we can either increment or decrement an ...
0
votes
0answers
18 views

Transition between sequence and (multi-)set

Do you know any generalization of both sequence and multiset that would allow to get "something in between"? Something like a tendency to be ordered with the one extreme being unordered and the other ...
0
votes
1answer
129 views

Proof for bijection between the set of k-multisets & the set of k-subsets.

In the u.g. book on combinatorics, by David Mazur, there is question #13 on proof in sec. 1.3. Note: The book, use $[n]$ to denote the set of the first $n$ positive integers. This exercise outlines ...
0
votes
2answers
65 views

Set membership and a box of bananas

Suppose that I have two boxes $A$ and $B$, each of which contains some number of identical (indistinguishable)* bananas. If I treat $A$ and $B$ as multisets whose elements are bananas, it follows ...
0
votes
1answer
28 views

Most efficient set of characters for cracking passwords (Parallelized)?

For an assignment, we are required to crack a password from a hash given a salt. The password will always be 4 characters that are case sensitive (ex: CMPS, cmps, CAMP, LIST). We are to parallelize ...
0
votes
0answers
29 views

Multiset-Span monad

I have been thinking about multisets for a while. These are sets where elements can repeat, so $S =\{ a,a,b,c,b\}$ is a multiset on the set $A = \{a,b,c\}$. It is well known that there is a Monad on ...
1
vote
0answers
64 views

Category of Multisets and Spans

I have been thinking about multisets for a while. These are sets where elements can repeat, so $S =\{ a,a,b,c,b\}$ is a multiset on the set $A = \{a,b,c\}$. I have also been looking into morphisms ...
2
votes
1answer
32 views

How to define a map from a multiset to a multiset

Multisets are like sets, but can contain duplicates. Suppose we have two multisets $A, B$, and we want to define a map from one to the other ie: $$ f : A \rightarrow B.$$ How do we do this? Is it ...
0
votes
1answer
30 views

8-element permutations of a multiset {3:0,1:1,1:3,1:5,1:8,1:9} with the restriction 0 is not allowed in left or rightmost position

I am lost in how to approach this problem due to the wording: Count the number of distinct 8-digit numbers that may be made by permuting the multi-set: $$MS:=\{0:3,1:1,3:1,5:1,8:1,9:1\}$$ ...
0
votes
1answer
91 views

Prove set of primes is equal to set of natural numbers

I was studying for an upcoming test in college and was looking at an old test. I'm struggling to understand how to prove this problem and was hoping someone could help me out. Prove that |P| = |N| ...
0
votes
0answers
39 views

Family of multisets that generates the smallest covering

Let $X_i$ be the family of multisets defined as $X_i:=\lbrace\lbrace 1^{i_1}, \dots, n^{i_n}\rbrace| i_j \leq i \text{ for every } j=1,\dots, n\rbrace$. Let $X:=\bigcup_{i=1}^{\infty} X_i$. Let $A$ ...
0
votes
1answer
35 views

Strange sum notation

I have the following sum and I would like to generalize the notation but I don't see how to choose i index... $$ -2P(A_{1} \cap A_{2}) - 2P(A_{1} \cap A_{3}) - 2P(A_{2} \cap A_{3}) = -2\sum_{i=...
1
vote
1answer
62 views

An infinite division and balls problem

Suppose you have a bottle with infinite volume and infinite number of balls. Now it's 11 o'clock and an hour left till 12. So you put 10 balls in and take one out 30 minutes later. You repeat this ...
0
votes
1answer
64 views

Proving that a map is bijective

Prove that the statements are equivalent For every $b \in B$, the set $f^{-1}(b)$ has exactly one element. $f$ is bijective. Hint: it involves stating two facts: $f^{-1}\neq \emptyset$ and $f^{-1}(b)...
1
vote
1answer
45 views

Number of $n\times n$ matrices with fixed columns sums and only one non-zero elements among each row

I would like to find an explicit, analytical formula that counts the number of $n\times m$ matrices with given sums $c_1, \ldots , c_n$ along the columns and only one non-zero value along each row (...
5
votes
1answer
77 views

Finding the amount partitions with gives sizes of a multiset

A multiset $A$ contains $E$ positive integers. The multiplicity of each element is $r_i \; i=1,\ldots ,N$. $A$ is partitioned in $M$ (we do not necessary have $M=N$) ordinary sets (where elements are ...
3
votes
1answer
50 views

The number of ways to pile n white circles, when in the bottom row there are n white circles?

I am struggling with this Question: What are the number of ways to pile circles (as long as they don't fall from the sides) when in the bottom row there are $n$ white circles. each row can hold ...
0
votes
1answer
60 views

Let S be a Set and let A be a subset of S. how many options there are to choose 2 subsets from S that their intersection is exactly A?

I'm struggling with this combinatoric problem - i marked the size of Set S as n and the size of A as k. I first thought of it this way: in order that the interaction of 2 subsets of S will be exactly ...
1
vote
1answer
120 views

How many sequences length $n$, taken from $\{1,2,3,…,k\}$ that the sum of the $n$ elements in the sequence will be divisible by $k$.

I wonder if you can help me with this question I am being dealing with. My line of thinking was this: I know that the sequence is of length $n$, so I divided it into $n$ cells. $$x_1+x_2+x_3+\dotsb ...
0
votes
0answers
22 views

Prove the maximum sum of products algorithm

We are given two equal sized sets of positive integers (n integers). We can multiply any two numbers from different sets, each number being used once. All multiplied pairs are added. Prove that ...
1
vote
1answer
39 views

Counting “mulstisets” on a given sequence.

So, i have the following problem: Let $a_1, a_2, a_3, ..., a_n$ be an integer sequence. How many distinct sequences of size $1$ to $n$ can you make from $a$, given for each element $a_i$, there are $...
1
vote
0answers
30 views

Notation for sum over a multiset

Let $\mathcal M$ be a multiset and $\odot$ an associative operation over the support set $M$ of $\mathcal M$. Further, denote by $\mu_{\mathcal M}(x)$ the multiplicity of the element $x$ in $\mathcal ...
4
votes
2answers
360 views

Partitioning a multiset into multisets of fixed sizes

Say we have a multiset $S(\mathbf{d}$) where $\mathbf{d}$ is a list of $l$ numbers and the multiplicity of the $i$th element of $S$ is $d_i$. The cardinality $N$ of $S$ is $\sum d_i$. We want to ...
1
vote
1answer
106 views

Leave-$k$-out greatest common divisor

The problem I have a multiset $M=\{m_1, \dots, m_n\}$ of positive integers (that is, a number $m_i$ can appear multiple times in $M$), and a positive integer $k$. I am looking for an algorithm to ...
3
votes
2answers
92 views

Generating function for sequence $a_i={n+im-1 \choose im}$

It is well known that $\sum_{i=0}^\infty {n+i-1 \choose i}x^i=\frac{1}{(1-x)^n},$ i.e. $\frac{1}{(1-x)^n}$ is generating function for sequence $a_i={n+i-1 \choose i.}$ But I want to find generating ...
0
votes
1answer
36 views

Family over a set such that the union is the set

I'm new to combinatorics, so this may be a common scenario with which I'm unfamiliar. I'm trying to define a family of set $\mathbb{F}$ over a set $\mathcal{S}$, where the size of each member of $\...
1
vote
4answers
38 views

Sets and Subsets

How many distinct subsets of the set $S=\{1,8,9,39,52,91\}$ have odd sums? Let, $O = $ Odd, and $E = $ Even. I figured, that only $\text{odd}+\text{even}=\text{odd}$, so I divided up the problem into ...
-1
votes
3answers
32 views

I am confused with braces inside braces. Please help me to figure out which are elements and which are sets in this set given in the picture . [closed]

Does 2 belongs to this set A? Does 2 an element of A..? (https://i.stack.imgur.com/Plc8B.jpg)
1
vote
2answers
83 views

Simplification of a Finite Sum

For $m, n \in \mathbb{N}$, can $$\sum_{k=0}^{m} (m-k)! { m \choose m-k } { n \choose n - (m-k) } ( 1 - p)^{k} \cdot p^{m-k} \cdot \frac{ e^{-\lambda} \lambda^{n-(m-k)} } { (n - (m-k) )! } $$ be ...
2
votes
0answers
32 views

Can I use inclusion symbol to address a multiset's elements?

Suppose a particular tree whose leaf elements are all objects $x$. Then, a collection $M$ represents the nodes of the tree (Obviously, $M$ is a multiset since it hosts $n$ repetitive objects $x$ for a ...
3
votes
1answer
86 views

Permutation of a multiset with restrictions on two characters.

Consider the following: apples?and?oranges. I have to find the number of arrangements with the restriction that the two ? can't be together and they can't be located at the ends like ?...
0
votes
1answer
42 views

Binary Entropy solving over uniform distributions

Compute the Binary Entropy for X is uniform over the set {1, 2, 3, . . . , 80} $$H(X) = -\sum_{i=0}^n p(x)log _2p(x) $$ I am pretty confused on this topic if someone could explain an easy way to ...
2
votes
0answers
38 views

Optimal way to choose a “prediction” for a random variable

Let $X$ be a random variable with distribution $$\mathbb {P}(X=k) = p_k, \space k=1,2,\dots n$$ $$(\text{and } \mathbb {P}(X=x) = 0 \text{ otherwise}).$$ We must choose a multiset $A$ of values $a_j\...
1
vote
3answers
197 views

Bijection between sets and multisets

I know that there are ${n+k-1 \choose k}$ multisets of size $k$ of a subset of size $n$. This means that there must be a bijection between multisets of size $k$ of a set of size $n$ and subsets of ...
1
vote
1answer
94 views

Expected “overlap” between permutations of a multiset

Given an ordered multiset, such as $\{1,2,2,3,3,3,4,4,4,4\}$, what is the expected number or proportion of matching elements under a random permutation? In other words, how many times would you expect ...
0
votes
2answers
25 views

What is solution set of the given equation and why?

What is the solution set of the below given equation and why? Find the solution set of the equation: $| 7 - x | < 2 , \forall x\in\mathbb R$ A) $\{ x \mid x\in\mathbb R, x < 5 \}$ B) $\{ x ...
0
votes
3answers
145 views

Mathematical notation for number of times an element appears in a multiset

I have a multiset, say $\{8,5,7,8,8,9,5,5,3,0,1\}$, and I wish to compute a weight with the following formula: number of times an element appears in the multiset divided by the total number of ...
5
votes
2answers
182 views

Convolution formula for multisets coefficients

I've been trying to solve the following problem: (a) Give two proofs of the binomial coefficient identity, called the convolution formula, $\sum_{j = 0}^k \binom{m}{j}\binom{n}{k - j} = \binom{m + n}...