Questions tagged [set-partition]
This tag is for questions relating to "partition of a set" or, "set-partition", which is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in exactly one subset.
736
questions
0
votes
0
answers
29
views
What is the upper bound of this function?
What is the upper bound of this quantity given $p_1+p_2+p_3=n$? (or $2p_1+p_2=n, p_3=0$ or $3p_1=n, p_2=p_3=0$)?
$$\frac{n!}{p_1!p_2!p_3!}\cdot \exp\left(-\frac{\binom{n}{2}-\binom{p_1}{2}-\binom{p_2}{...
- 119
6
votes
1
answer
155
views
When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?
Now also posted to MathOverflow.
Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will refer to such a set as a triplet. Consider now the problem of ...
2
votes
1
answer
52
views
Definition and construction of a quotient space using a toy example
To make headway into Agebraic Topology I need to precisely understand the definition and construction of the quotient space. Definitions in my textbooks and online have felt handwavy to me, and I don'...
- 545
1
vote
1
answer
40
views
Question on proving surjectivity of the map $f: P\mapsto \sigma(P)$ from set of partitions of a set finite $X$ to set of $\sigma$-algebras on $X$
The starting place is this question on trying to show that the map $\sigma$ from the set of partitions $\mathcal{P}$ of a finite set $X$ to the set of algebras $\mathcal{A}$ on $X$ defined by $\sigma:...
- 5,351
0
votes
0
answers
20
views
Statistical Metric for Dominance of the Largest Subset in a Partition of a Set
Given a set and a partition of it, I want to calculate a score (between 0 and 1) reflecting how much is the set "dominated" by the largest subset of the partition.
The intuitive idea I'm ...
- 1
2
votes
1
answer
64
views
Bijection between the set of all Partitions and the set of all Algebras
I am interested in showing that, given a set $S$ there exists a bijection between the set of all algebras of $S$, denoted $A$ and the set of all partitions of $S$, denoted $P$.
As a simple example, I ...
- 5,351
0
votes
1
answer
106
views
How to fill a set of container by partition of set?
Let $\{A,B,C,D\}$ be a table with $4$ containers of sizes respectively $5,5,3,2$. Let $\pi=\{B_1,B_2,\cdots B_k\}$ a partition of a set, where $k\in \mathbb{N}$. I wonder how to enumerate the ...
2
votes
0
answers
23
views
Terminology for Combining (Intersecting?) Partitions
What's the term for making a new partition from two existing partitions of a space? For example, if you have a partition $X = \{A, B\}$ and $Y = \{C, D\}$, and you form the partition $\{AC, AD, BC, BD\...
- 31
0
votes
0
answers
35
views
equivalence relations divides sets into partitions whose union is the set but if some elements of the set aren't in the relation how does this work?
The proposition given is:- every equivalence relation induces a partition
of the underlying set, the parts of the partition being the equivalence
classes, i.e. the equivalence classes are pair-wise ...
0
votes
0
answers
16
views
Showing that a union of subset partition spans a whole set
Again, a question based on "An Invitation to Applied Category Theory". This time, exercise 1.15 on page 10.
Here we have an equivalence relation $\sim $.
Under $ \sim $ we form a partition ...
- 418
0
votes
2
answers
51
views
Distinguishing partitions of a set
This is another question based on "An Invitation to Applied Category Theory", this time based on exercise 1.12 (p. 9). I was able to instinctively answer the question but I don't know why ...
- 418
0
votes
0
answers
63
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 ...
3
votes
1
answer
2k
views
In how many ways can 12 similar balls be divided into three identical groups, with each group containing at least one and at most six balls?
My attempt :-
a+b+c=12 ; I am assuming the groups be distinct for the time being
We need to distribute 1 ball to each group, which would make our equation as follows
x+y+z=9
Now, ways of distributing ...
- 717
1
vote
1
answer
70
views
Another formulation for Stirling numbers of the second kind
I find another formulation for Stirling numbers of the second kind:
Let $n\ge k\ge 1$. Denote by
$$\mathbb N_<^n := \{ \alpha = (\alpha_1,\cdots,\alpha_n): 0\le \alpha_1\le\cdots\le\alpha_n, \...
- 1,903
-1
votes
1
answer
19
views
Are there twice as many generalized partitions as partitions?
A partition of a set $S$ is a subset of the powerset of $S$, which covers $S$, is pairwise disjoint, and does not contain the empty set. If we drop the last condition, we get what I call a generalized ...
- 18.5k
1
vote
2
answers
70
views
Can you partition the set of 9 consecutive integers 1 to 9 in 2 sets, s.t. no member of either set is the mean of two other members of the same set? [duplicate]
Is it possible to partition the set $\Omega=\{1,2,3,4,5,6,7,8,9\}$ in two subsets $\Omega=A\cup B$, $A\cap B=\emptyset$, such that no member of either subset is the mean of two other members of the ...
- 11.2k
-1
votes
1
answer
35
views
Is the following Knapsack Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 63
1
vote
0
answers
53
views
Automorphism group of a set partition
Let $\mathcal{P} = \{ A_1, \ldots, A_k \}$ be a set partition of $[nk] := \{ 1,\ldots,nk \}$ into $k$ blocks of $n$ elements. This means that:
For all $i$, $A_i \subset [nk]$ and $|A_i| = n$;
if $i \...
- 656
3
votes
1
answer
33
views
When partitioning the odd and even numbers on the clock such that blocks don't cross, how to show that always 7 blocks are needed?
I want to partition the numbers 1 to 12 on the clock into blocks of numbers such that
no block contains both odd and even numbers,
no two blocks cross each other,
given the blocks of odd numbers, ...
- 954
0
votes
0
answers
23
views
Exclusion-Inclusion principle for set partition.
have you ever encountered works on set partition in which the principle of inclusion exclusion is used in the case of a single parameter and reused in the generalized case (with several parameters) ?
- 11
-1
votes
1
answer
81
views
Riemann Integration using Geometric Partitions
I have this questions about Reimann Integration using a given geometric partition with an unknown value of n for the function $f(x) = 1/x^3$ . enter image description hereI have attached the work I ...
- 1
1
vote
1
answer
58
views
decompose complete directed graph with n vertices into n edge-disjoint cycles with length n-1
I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in this paper (Theorem 3). However, the proof ...
- 21
2
votes
2
answers
78
views
Math Grouping Optimization
I have roughly 10 employees assigned a random cost (for this example, lets say $0-$500). I'm trying to optimize grouping the employees into 3 groups. Every employee in the group must be paid the same ...
- 23
1
vote
0
answers
74
views
Can the real numbers be partitioned into two sets which are both closed under multiplication?
Except for the trivial case of the partition consisting of the real number $0$ and everything else, is there any other partition of the entire set of real numbers $\mathbb{R}$ into two sets $A$ and $B$...
- 18.5k
2
votes
1
answer
111
views
Partition the set $\{1,2,\ldots, 2n\}$ into $n$ subsets of size 2, such that each pair differs by 1 or $n$.
Encountered this problem in a textbook - find the number of ways to partition the set $\{1,2,\ldots, 2n\}$ into $n$ subsets of size 2, such that each pair differs by 1 or $n$. I wasn't too sure how to ...
- 29
1
vote
0
answers
18
views
Existence of two element Partitions for Sets X and Y where Functions f and g map partition elements to each others
Let $X$ and Y be two non-empty sets and f be a function from X to Y and g be a function from Y to X. We need to prove that there are partitions (A,B) of X, and (C,D) of Y such that f(A)=C and g(D)=B. ...
1
vote
2
answers
106
views
Number of partition of $[1,m]$ of cardinality $n$.
Given an integer $m \geq 1$, let $\pi_{m, n}$ the set of partition $\pi$ of $[1,m] = \{1,\dots,m\}$ such that $|\pi|$ equal $n$.
I am interested in the cardinality of $\pi_{m, n} $.
For example let $m ...
- 2,001
0
votes
1
answer
38
views
Derivation of Integer Partition from Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 393
1
vote
1
answer
126
views
How to assign tasks to a set of machines, given that the more tasks you assign to a machine the slower they will run? Bin covering with merging bins?
Intro
I need to design an algorithm that will distribute a known set of tasks with a known RAM requirement to a known set of machines with known RAM capacities. The tasks require a certain amount of ...
- 113
0
votes
1
answer
85
views
Link Between Integer Partition and Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 393
1
vote
2
answers
72
views
Partition a positive integer sequence into subsequencies of equal weight
For a finite sequence of $N$ positive integers $a_1, a_2,.., a_N$ let us define its weight as
$w (\{a_i\}) = \log(N) \cdot \sum_{1}^{N}{a_i}$.
I want to partition such sequence into $K$ non-empty ...
- 130
2
votes
1
answer
87
views
What does $\wedge$ mean for measurable partitions?
Sorry for this silly question, but I'm reading a textbook on Ergodic theory by Cornfeld, Sinai & Fomin and suddenly this operation on measurable partitions appears, and I didn't find definition in ...
- 370
1
vote
1
answer
57
views
Toy exercise on ultrafilters for $\mathbb{N}$
I'm reading something that defines ultrafilters like this.
An $\text{ultrafilter}$ on $\mathbb{N}$ is a subset $\omega$ of $2^{\mathbb{N}} - \{\varnothing\}$ so that
(Completeness) For any $A \subset ...
- 484
2
votes
1
answer
113
views
A number partition problem
I have encountered the following interesting integer partitioning problem.
Let $n,k,t \in \mathbb{N}$ be given parameters and let $S_1,\ldots, S_t$ be a partition of the numbers $1,2,\ldots,n$ such ...
- 63
2
votes
0
answers
46
views
Some questions about resolvable group divisible designs
In the context of some other construction (which is irrelevant here), I was looking for a way to generate a collection "orthogonal partitions" on a set of nodes with a fixed and uniform set ...
- 193
0
votes
1
answer
27
views
Equivalence of Dedekind cuts and Dedekind left sets
I am currently working on the book "Classic Set Theory" by Goldrei. Goldrei is using Dedekind left cuts or left sets, i.e. the subset $L$ of a Dedekind cut. He gives the following definition ...
- 615
0
votes
0
answers
54
views
How to calculate the number of set partitions of an arbitrary set? [duplicate]
Pre-Amble
I would like to rephrase the question
PREVIOUS INSTANCE OF THIS QUESTION ( Was closed due to an alleged duplicity ).
Considering sets of four elements we can consider sets of the following ...
- 2,708
0
votes
1
answer
105
views
Calculate number of partitions where partitions have certain size
Suppose we have some set $S = \{1,...,N\}$ and partition this set into subsets $S_i \in S$ such that $S_i \cap S_j = \emptyset$ if $i\neq j$. How many different partitions can make such that the ...
0
votes
0
answers
45
views
Does this kind of partition have a name?
Note: Reposting from OR Stackexchange as advised there.
Consider a convex polyhedron $A$. Assume we have subsets $A_1,\ldots,A_n$ of $A$ that are themselves covex polyhedra and are mutually disjoint ...
- 41
1
vote
1
answer
52
views
Is $S(n,k)= \sum_{r=k-1}^{n-1} \binom{n-1}{r} S(r,k-1)=\sum_{r=k-1}^{n-1} k^{r-1} S(r,k-1)$?
I've recently solved the problem:
Prove that
Is $S(n,k)= \sum_{r=k-1}^{n-1} \binom{n-1}{r} S(r,k-1)?$
I eventually proved the property but with my first approach I found a different expression and ...
- 489
1
vote
0
answers
63
views
Minimizing the magnitude of the sum of a vector of complex numbers with an integer constraint
Let $h_{1}, ..., h_{N} \in \mathbb{C} $
Consider minimizing the function below:
$ \min \left| \sum\limits_{i=1}^N h_{i} x_{i} \right| $
with the constraints $x_{i}^2 = 1$
i.e., $x_{i}$ can only take ...
- 11
0
votes
0
answers
46
views
find a partition of Z into 10 infinite sets? For each partition, what is the corresponding equivalence relation?
I need to find a
partition of Z into 10 infinite sets, and for each partition, what is the
corresponding equivalence relation?
so I know there's a theorem that states "let P be a partition of a ...
- 81
1
vote
1
answer
83
views
Number of ways to partition a set into k even subsets
Stirling numbers of the second kind give the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. I wondered if it is instead possible to calculate the number of ways of ...
- 113
-1
votes
2
answers
47
views
Why is it possible to define a partition of integers as prime, composite and {1,-1,0} although divisibility is not an equivalence relationship?
It's a known theorem that if $\mathcal{R}$ is an equivalence relation defined on a set, let's say $A$, then $\mathcal R$-equivalence-classes define a partition of $A$. It is also known that the ...
1
vote
0
answers
50
views
In how many ways can I partition a partition?
Let $\mathbf{k}= \langle k_1,...,k_u \rangle$ denote cardinalities of $\sum_{i=1}^{u}k_i = n$ objects, where $k_i$ is the cardinality of the $i^{th}$ object. In how many ways can I partition this ...
- 1,777
2
votes
0
answers
26
views
For a fixed $n$, which partition leads to the lowest upper sum?
Let $f(x)$ be bounded on $[a,b]$ . Let $P_0$ be a partition such that:
$P = \{a=t_0,t_1,\dots t_n=b\}$, where $a=t_o<t_1<t_2\dots t_n=b$ and $\;t_k= a+ \frac{k(b-a)}{n}$, for all $k$. ...
0
votes
0
answers
48
views
Conditions for a sorted partition of the edges of $K_n$ to generate a total order of the vertices
Given a complete undirected graph $K_n$, it's given a refinement algorithm that builds, at iteration $t$, a sorted partition $E^t$ of the edges and a sorted partition $V^t$ of the vertices by refining ...
- 441
6
votes
0
answers
118
views
Count number of ways to distribute n distinct positive integers into $r$ identical bins such that the product of integers in each bin is $\le M$
Problem Statement:
We have $n$ distinct positive integers say $a_1,a_2....a_n$ and a given integer value $M$.
We have to count number of ways to distribute these integers to $r$ identical bins subject ...
user1068604
3
votes
1
answer
60
views
Partition $\mathbb{N}_0$ into two sets where each set must have the same number of ways to add to m
For any set that is a subset of the natural numbers $S \subseteq \mathbb{N}_0$ we may consider the number of possible ways to form $m$ by adding two distinct elements in $S$. Call this $c_S(m)$. For ...
- 424
0
votes
1
answer
93
views
Partition Theorem for expectations - why only dependent on value of X and not Y?
Hi there,
In my textbook above, there is a theorem stating that the expectation of $E [Y | X]$ is equal to $E[Y]$.
However, the textbook also states that this theorem only depends on the value of $X$. ...
- 1