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
-1 votes
1 answer
143 views

Expressing Numbers Without Any Decimal Presumptions

I have long been uncomfortable with how numbers in alternative bases are expressed. Alternative bases are marketed as transcending our arbitrary base-$10$ conventions, but I wonder if they really ...
user10478's user avatar
  • 1,904
2 votes
1 answer
73 views

Multiset Matching

Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
SpringLandMid's user avatar
0 votes
0 answers
13 views

Size of a Power Set of a Multiset where some items are Indistinguishible [duplicate]

Note: I do not know all the terminology for my question, so I am making some educated guesses. Please let me know the correct terminology for anything I get the name of wrong. Suppose I have a ...
Benyamin's user avatar
  • 101
2 votes
0 answers
44 views

Image of the standardization of permutations of a finite multiset

Let $M$ be a multiset $\{1^{m_1},2^{m_2},...\}$ whose cardinality $\#M:=m_1+m_2+...=:n$. Let $\Sigma:S_M\to S_n$ be the standardization map defined in Stanley combinatorics volume 1 ($S_M$ is the set ...
Kandinskij's user avatar
  • 3,719
0 votes
0 answers
190 views

20 identical red balls, 20 identical blue balls, 20 identical green balls, 1 white ball, and 1 black ball. You draw 15. How many outcomes?

A bag contains 20 identical red balls, 20 identical blue balls, 20 identical green balls, 1 white ball, and 1 black ball. I reach in to get 15 balls. How many outcomes are there? The problem came from ...
dutch's user avatar
  • 21
0 votes
0 answers
177 views

Number of Partition of a Set with Repeated Elements

It is well known that for a set of $n$ elements, say $\{1,\ldots, n\}$, the total number of possible partitions of this set is equal to $B_n$, where $B_n$ is the Bell number, and a set partition is a ...
Raymond Kan's user avatar
2 votes
1 answer
120 views

Exercise 10 in Stanley Combinatorics volume 1 chapter 1

I'm again having some trouble understanding a solution of an exercise of chapter 1 of Stanley Combinatorics volume 1. It's the exercise 10 that requires to prove that the number of ways we can choose ...
Kandinskij's user avatar
  • 3,719
2 votes
1 answer
70 views

Find the value of $\sum_{d=0}^\infty\binom{d+m-1}{m-1}\frac{x^d}{d!}$. [closed]

It is known that the generating function of the number of multisets is given by $$ \sum_{d=0}^\infty\binom{d+m-1}{m-1}{x^d}=\frac{1}{(1-x)^m}. $$ Then, does a similar series $$ \sum_{d=0}^\infty\binom{...
Nobo's user avatar
  • 21
2 votes
0 answers
92 views

Defining permutations of multiset using bijections

In Stanley's Enumerative Combinatorics, he defines a permutation $w$ of the set $S=\{x_1,...x_n\}$ with cardinality $n$ to be linear ordering $w_1w_2...w_n$, so that the word $w=w_1w_2...w_n$ ...
David Raveh's user avatar
  • 1,795
0 votes
1 answer
69 views

Number of combinations of size $k$ of elements in a multiset with finite multiplicites

Suppose I have 3 types of balls each in varying amounts, e.g. 3 Red (R) balls, 3 Green (G) balls, and 2 Blue (B) balls. How many combinations of size $k, k\leq n$ where $n$ is the total number of ...
BadBayesian's user avatar
0 votes
1 answer
79 views

Problem with the proof of unordered sampling with replacement

This problem comes from the page 2 of "Probability - 1" of A.N. Shiryaev, where the book talks about the cardinality of finite unordered sampling with replacement. Consider an urn consisting ...
JacobsonRadical's user avatar
0 votes
1 answer
63 views

Simplifying a series with multiset coefficients

I am struggling to simplify this series: $$\sum_{k = 0}^{\infty} \left(\!\!{n\choose k}\!\!\right) a^k k^2 = \sum_{k = 0}^{\infty} {n + k - 1\choose k}\ a^k k^2.$$ I understand that the square under ...
Dr. Timofey Prodanov's user avatar
0 votes
2 answers
69 views

How to solve "linear multiset equations"?

I have a bunch of linear forms in the same number of variables, with the number of linear forms much larger than the number of variables. Say, they are $\ell_i(x_1,...,x_n)=l_{i1}x_1+...+l_{in}x_n$, ...
მამუკა ჯიბლაძე's user avatar
2 votes
3 answers
387 views

Set vs Multi-set in specific examples

I'm not a set theorist, but I feel like I've been taught all my life that I can write sets with repeating elements but those repeats are sort of degenerate and not counted as separate. So $\{a, b, a\} ...
cheyne's user avatar
  • 347
0 votes
1 answer
57 views

Sufficient condition for equality of multisets

Give three finite multisets $A,B,C$ I am trying to devise a sufficient condition that implies equality of both $A$ and $B$ with $C$. More formally, if $A,B,C$ are defined over a space $\Omega$, I am ...
Bean Guy's user avatar
  • 321
3 votes
1 answer
64 views

Are two finite-dimensional subspaces not disjoint iff the union of any of their bases is linearly dependent?

First I need to show the following Lemma: Lemma Let $\mathcal{M},\mathcal{N}$ be finite-dimensional subspaces of $V$ with any bases $\mathcal{M}_{0}$ and $\mathcal{N}_{0}$. Then, $\mathcal{M}\cap\...
Kr'aamkh's user avatar
  • 187
0 votes
1 answer
21 views

Elegant notation for partial intersections in cartesian products?

Let $A⊆X×Y$ $A$ be a multi-set over $X×Y$ $A∈⋃_{n∈ℕ}(X×Y)^n$ Anyway, $A$ is a collection of tuples $(x, y)$, potentially with duplicates in cases (2) and (3). Given $F⊆X$, I am looking for an ...
Hyperplane's user avatar
  • 11.7k
2 votes
2 answers
193 views

Notation for collection of elements that may contain duplicates [closed]

I want to represent document D as a collection of words. I was inclined to do this with: D = {w_1, w_2, ... }. However, the ...
Emil's user avatar
  • 131
1 vote
0 answers
44 views

What is a partial multiset?

A. Rabinovich, and B. A. Trakhtenbrot, in their Behavior Structures and Nets paper, uses the expression "partial multiset" without defining it. In context, they have an alphabet $\Sigma$, a ...
Clément's user avatar
  • 167
0 votes
1 answer
57 views

Formula for calculating the combination of a multiset taken r at a time? [duplicate]

If we have a multiset S = {a,a,b,b,b,c,d} How to calculate all possible combinations if we take r items at a time? For example if r = 3 then the combinations will ...
Software Carpenter's user avatar
5 votes
0 answers
217 views

What is the growth rate of OEIS A347913?

OEIS A347913 is an extremely interesting sequence about multisets of integers. It is defined as the number of multisets one can get starting with a multiset of $n$ zeros and "splitting", ...
mathlander's user avatar
  • 4,017
-1 votes
1 answer
39 views

Is a multiset an element of itself?

I know that a set cannot be an element of itself, but I don’t find anything about multisets. So, my question is: is a multiset an element of itself?
Lepticed's user avatar
  • 111
2 votes
1 answer
54 views

Distributive property for signed multiset

I'm reading through Wayne Blizard's introduction to signed multisets, which says at the bottom of page 9 that additive union distributes over intersection. I see how this is true for normal (non-...
Johannes Riecken's user avatar
1 vote
0 answers
30 views

Polynomials considered as multisets of roots: extend polynomial addition and derivation to $\mathbb{R}^n$

Informal context In $\mathbb{C}[X]$, all polynomials are split, so monic polynomials are in bijection with the multisets of their roots, i.e. the finite sub-multisets of $\mathbb{C}$. Polynomial ...
Jean-Armand Moroni's user avatar
0 votes
2 answers
290 views

Algorithm for optimal partition of a multiset with bounded sum.

Consider the following problem: Let $S$ be a multiset (you can think of it as an array) of positive integers. Given a bound $W\geq \max(S)$, we want to find a partition of $S$ into multisets $\{S_1,.....
Pedro Vaz Pimenta's user avatar
-1 votes
2 answers
201 views

Why probability two sevens had been chosen wo replacement before a one only dependent on the number of ones and sevens in multiset $\{7,7,3,2,1\}$?

If the digits $7,7,3,2$, and 1 are randomly arranged from left to right, what is the probability both of the 7 digits are to the left of the 1 digit? The answer is $1/3$ because $1 7 7$, $7 7 1$, $7 ...
Boron Herring's user avatar
3 votes
0 answers
56 views

What is the name of this multiset-like object?

My understanding is that a multiset (roughly, a set where we care about multiplicity) can be modeled as a function $V\to\Bbb{Card}$ with set-sized support, where $V$ is the class of all sets, $\Bbb{...
Akiva Weinberger's user avatar
0 votes
2 answers
80 views

What is the appropriate way to describe an "ordered union" of sequences?

Given the $\langle $sequences$\rangle$: $$ \begin{aligned} S_1 & = \langle \color{magenta}{D_1}, \color{orange}{D_2}, D_3 \rangle \\ S_2 & = \langle \color{orange}{D_2}, D_4 \rangle \\ S_3 &...
Rax Adaam's user avatar
  • 1,176
1 vote
1 answer
40 views

Multiset Covers with a Uniformity Condition

I was playing around with the indices of tuples of functions, and these objects came up naturally. Is there a name for them? Are there any resources on them that provide some properties or even a ...
user816709's user avatar
1 vote
1 answer
159 views

Understanding David Deutsch's second equation from his paper The Structure of the Multiverse

Background David Deutsch's paper The Structure of the Multiverse is concerned with the theory of quantum information and quantum computation, but the first few pages contain a purely mathematical ...
Paul Razvan Berg's user avatar
0 votes
1 answer
89 views

Trying to understand multisets. Given 4 random letters, what is the formula for finding the number of ways to get multisets? Then for 5 letters?

*Added an Addendum at the end Hopefully my Title isn't too vague, but I will try to elaborate here. I posted a similar question: Given 10 random letters where the number of repeated letters is known (...
user avatar
1 vote
1 answer
87 views

What does multiset imply?

Does a multiset operation (($^n_k$)) only work for sets with identical elements, or does it also apply to replacement of distinct elements. Is there any difference in the calculation? Furthermore, is ...
Bafs's user avatar
  • 102
0 votes
1 answer
2k views

What does "$\epsilon$" mean in this formula

I have started seeing the "$\epsilon$" symbol in this paper. What exactly does $\epsilon$ it mean in the formula? The hard part is this definition: "Range$(p,\epsilon)=\{o\mid ||p,o||_2\...
sujong's user avatar
  • 11
1 vote
0 answers
68 views

Number of non-negative integer solutions of the equation: $rx_1 + x_2 + \cdots + x_n=kr$

I have this excersice: Determines the number of non-negative integer solutions of the equation: $rx_1 + x_2 + \cdots + x_n=kr$ where $k, r, n\in\mathbb{N}$. I tried to use that the number of $r-...
Lennis Mariana's user avatar
3 votes
1 answer
58 views

Multiset image of a set under a homomorphism

I know the basic group theory definition of the image of a subset of group elements under a homomorphism is the following: The image of any subset $X \subseteq G$ is given by $\phi(X) = \{\phi(x) : x ...
M. McIlree's user avatar
0 votes
1 answer
204 views

Complement of a Set: What do I do when a set contains an element that is not in the Universal Set

Let $U = \{x: x \in \mathbb{N}, x>10 \hspace{4 pt} and \hspace{4 pt} x <40\} , \hspace{4 pt} A = { 5,10,20,40}$ The complement of the set should be Aᶜ = {All natural numbers between greater ...
Jardani Jovanovich's user avatar
1 vote
2 answers
64 views

map two sets of integers into two integers such that the number of intersections of these two sets can be found using only these two integers

Given two multisets $A$ and $B$, is it possible to map all of the elements of these two multisets into two integer (for example, integer $A_1$ will represent the elements of multiset $A$, and integer $...
liam casey's user avatar
1 vote
1 answer
31 views

Probability that two sets of balls have disjoint labels (i.e. probability of disjoint multisets)

I have $k$ distinct balls split into two sets $A$ and $B$, $A$ has $k_1$ balls and $B$ has $k_2$ balls, and $k_1, k_2 \geq 1$. I have a random label machine which prints numbers from {1, 2, ... n} ($n ...
Wishmaster97's user avatar
0 votes
1 answer
120 views

Combinatorial proof for formulas involving partitioning a multiset into 2 equal sums

$A$ is a non-empty multiset that contains $m$ integers $a_{1},a_{2},...,a_{m}$. $P(X,n)$ is the number of ways to partition $X\cup [n]$ into 2 equal sums (where $X$ and $[n]$ are multisets and $n$ is ...
Quý Nhân Đặng Hoàng's user avatar
0 votes
1 answer
228 views

How to compactly write a simple set for 2 variables when second variable may have same properties as first or it may optionally be positive infinity?

A Little Bit of Background (May Be Skipped) It's been about 40 years since learning higher math like partial differential equation and linear algebra including simple tensors but never needed much of ...
Jules Manson's user avatar
1 vote
2 answers
249 views

Bijection between $3^{\mathbb N}$ and $\mathcal P(\mathbb N)$?

Since $\mathcal P(\mathbb N)$ is the set of all subsets of $\mathbb N$, For each element $a \in \mathbb N$ and every subset $S\subset N$, we can define a function $f$: $f(a) = 0$ if $a \notin S$ $f(a) ...
J. Linne's user avatar
  • 3,032
2 votes
2 answers
1k views

Algorithm to generate all combinations of list of sets with up to one element per set

For a given list of sets where the elements of the sets do not share any elements between the sets I want to compute all possible combinations where a combination can have up to one element per set. ...
Mahoni's user avatar
  • 793
0 votes
1 answer
38 views

Name for number of unique items in a multiset which appear only once

Question about terminology describing finite multisets. What is the proper term for the number of items which have a frequency of one? Are they called singletons? Cardinality of singletons? i.e. {a,a,...
sheppa28's user avatar
  • 929
1 vote
1 answer
54 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 ...
Pedro's user avatar
  • 381
0 votes
0 answers
77 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,...
Bryan Hii's user avatar
  • 325
0 votes
1 answer
116 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 ...
Daniel N's user avatar
1 vote
0 answers
106 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 ...
Kilian's user avatar
  • 51
1 vote
2 answers
78 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 $$ ...
IGY's user avatar
  • 919
0 votes
0 answers
94 views

Combinatorial proof of this identity: $ \sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0$ [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 ...
IGY's user avatar
  • 919
1 vote
0 answers
33 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 ...
Damstridium's user avatar

1
2 3 4 5
8