Skip to main content

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.

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

Let A be a 2n-element set. Find the number of pairings of A.

I am having trouble understanding how one of the solutions to this problem works: Let a pairing of A partition the set into 2-element subsets. Example: a pairing of {a, b, c, d, e, f, g, h} is {{a, b},...
Alt User's user avatar
0 votes
0 answers
33 views

Proof that the measure of a set is independent of its partition

I am struggling with writing and rigorousity and as an exercise from Terence Tao's Measure Theory book, I am trying to prove that the measure of a set E is independent of how it's partitioned. My ...
Seramiti's user avatar
0 votes
0 answers
20 views

Intersection of interiors of sets in a partition of $\mathbb{R}^d$

Let $\mathcal{Q}=\{Q_1,...,Q_n\}$ and $\mathcal{P}=\{P_1,...,P_m\}$ be partitions of $\mathbb{R}^d$ with $n<m$. Assume all $Q_k\in\mathcal{Q}$ and $P_i\in\mathcal{P}$ are close and convex sets. ...
Staltus's user avatar
  • 323
0 votes
1 answer
23 views

Does the quotient set uniquely determine arbitrary homogenous relations?

It seems totally reasonable to me to generalize the quotient of equivalence relations to general ones: Given a binary relation $R$ over sets $X, Y$, each $x \in X$ has an $R$-class, denoted $[x]_R = \...
n1lp0tence's user avatar
3 votes
2 answers
114 views

high school math: summands

Let's say we have a question that asks you to find the amount of all possible integers adding up to a random number, lets just say 1287. However, the possible integers is restricted to explicitly 1's ...
jackhammer's user avatar
4 votes
1 answer
164 views

Partition of a complete directed graph into hamiltonian cycles

I would like to take the $n\left(n - 1\right)$ edges of a complete directed graph on n vertices and partition them into $n - 1$ disjoint hamiltonian cycles. For example, on $n = 5$, this can be done ...
Taras Pylypenko's user avatar
1 vote
0 answers
26 views

MAE and RMSE by groups

Consider five real numbers $A_1$, $A_2$, $A_3$, $B_1$, $B_2$. They are errors, the five differences between real values and estimated values. The MAE(mean absolute error) is $$\text{MAE} = \frac{|A_1|+...
govindah's user avatar
  • 174
0 votes
1 answer
31 views

A variant of the partition problem or subset sum problem

Given a target list $T = (t_1, t_2, \ldots, t_N)$ and a multiset $S = \{s_1, s_2, \ldots, s_M\}$, both with non-negative integer elements, $t_k\in \mathbb{N}_>$ and $s_k\in \mathbb{N}_>$, ...
daysofsnow's user avatar
3 votes
1 answer
84 views

General form of finite partitions of $\{0,1\}^{\mathbb{Z}}$.

Is the following statement true? If so, how does one go around proving it? "Let $\alpha$ be a finite partition of $\{0,1\}^{\mathbb{Z}}$, then there exists a finite subset of the integers $K \...
Miguel Escobar Mendoza's user avatar
1 vote
1 answer
31 views

Partition algorithm for minimal summation

Assume 2 sets of integer $A=\{a_1,...,a_n\},B=\{b_1,...,b_m\}$ I need to find a target $n$ partition of $B$, denote $B_1,...,B_n$ such that the maximum of $a_i+\sum_{b\in B_i}b$ is minimal. I came up ...
Shore's user avatar
  • 343
3 votes
1 answer
157 views

Is there a sequence of two-set partitions of $[0,1]$ such that the partition generated by any subsequence is a partition into finite sets?

More specifically, I'm wondering if there is a sequence of partitions $\{\mathcal{P_n}\}_{n\in \mathbb{N}}$ of the unit interval $[0, 1]$, where each $\mathcal{P}_n$ consists of precisely two sets, ...
Jonathan Hole's user avatar
2 votes
1 answer
77 views

Calculate Bell polynomial $B_{l,k}(x, x^2, x^3, \ldots,x^{l-k+1})$.

I am trying to show that $$\sum_{k=1}^{l}({-}1)^{k{-}1}(k{-}1)!B_{l,k}(x,x^{2},\ldots ,x^{{l-k+1}}) = 0$$ where $B_{l,k}(x_1,x_{2},\ldots ,x_{{l-k+1}})$ is the partial (or incomplete) Bell polynomial. ...
user3236841's user avatar
1 vote
0 answers
17 views

maximal groups of elements always occurring together

I'm looking for the terminology used to describe the following concept. Given a set $S$ and a family of subsets of $S$, let $P$ be the maximal partition of $S$ (maximal in the size of the elements of $...
gernot's user avatar
  • 136
3 votes
1 answer
58 views

What does "measurable with respect to a partition" mean?

I am reading a paper. It defines the following things. $\Omega$ is a finite set of states and $S$ is the set of outcomes. An outcome function $F$ is a mapping from $\Omega$ to $S$. $P$ is a ...
Ypbor's user avatar
  • 818
2 votes
1 answer
38 views

The join of two set partitions in the refinement order

Let $X$ be a set. The set $\Pi_X$ of all partitions of $X$ is partially ordered via the refinement order, which is defined by $\alpha \leq \beta$ if and only if for each block $A\in \alpha$ there is a ...
azimut's user avatar
  • 23.1k
1 vote
1 answer
121 views

Partition of $\mathbb R$ in convex subsets/badly ordered sets

Background: These questions come from two different exercises, but since the first is much shorter and of the same kind of one of the others, I preferred to put everything in only one thread. (We work ...
lelouch_l8r4's user avatar
1 vote
2 answers
60 views

Can every (non-odd) set be partitioned into subsets of two elements?

Can every (non-odd) set be partitioned into subsets of two elements? By this I mean that given a set $A$, there is some $S \subset \mathscr{P}(A)$ such that every element of $S$ has exactly two ...
broken.eggshell's user avatar
1 vote
1 answer
31 views

Algorithm for partitioning a vector into "similar" subsets

I have to code an algorithm that optimally "partitions" a data vector into a number of $K$ subsets. In particular, the input data is a vector $X = (x_1,x_2,...,x_N)$, where $x_n\in\{0,1\}$. ...
snowtape's user avatar
  • 117
0 votes
0 answers
82 views

number of "equivalence relations" on a set with "n-elements"

I am trying to find a formula for number of equivalence relations on a set with n-elements however I am confused. I have already encountered the idea of "bell's number" and "Stirling ...
Sepehr GH's user avatar
1 vote
0 answers
18 views

Maximum number of local minima in k-means

Suppose $\mathcal{Z} = \{z_1, \dots, z_n\}$ is the set of points in $d$-dimensional Euclidean space. The aim is to partition the dataset into $(K\leq n)$ distinct clusters $R_1,\dots, R_K$ where $R_i\...
entropy's user avatar
  • 147
1 vote
1 answer
59 views

Let $(x_n)_{n\in\mathbb N}$ be a real sequence in $[0,1]$. Is there a partition of $\mathbb N$ indexed by the limit points of $(x_n)$?

Let $(x_n)_{n\in \mathbb N}$ be a sequence of reals in $[0,1]$ indexed on the positive integers. Let $L\subset [0,1]$ be the limit points of $(x_n)$, in the sense that $l\in L$ if and only if there ...
jlewk's user avatar
  • 2,072
0 votes
0 answers
23 views

Seeking Lower Bound for Partition Probability in Random Variable Analysis

I am reaching out to seek assistance with a probability problem involving random variables. For each $p$ in $[1,\infty)$, consider positive random variables $X_{1,p}, X_{2,p}, \ldots, X_{n,p}$ such ...
Diego Fonseca's user avatar
0 votes
1 answer
34 views

Can't we weaken the partition hypothesis in the law of total probability?

Law of total probability in its mainstream formulation assumes a partition ($B_i$'s) of the universe $\Omega$ to compute the probability of any event $A$ as $$\mathbb{P} (A)=\sum_i \mathbb{P}(A \cap ...
MysteryGuy's user avatar
0 votes
0 answers
86 views

Show that the set of all partitions of a set S with the relation refinement is a lattice.

This one may be one duplicate of QA_1, but its example $\{\{a,d\},\{b,c\}\}\wedge\{\{a\},\{b,c,d\}\}$ seems to not meet the definition in the book because $(\{a,d\} \not\subseteq \{a\}) \wedge (\{a,d\}...
An5Drama's user avatar
  • 416
0 votes
1 answer
75 views

Number of ways of partitioning a union of $n$ sets

Suppose $E=A+B$ is the union of two sets $A$ and $B$.Then, we can have $4$ ways of partitioning $E$ into disjoint subsets: $\{AB,Aβˆ†B\},\{B, A\bar B\},\{A,\bar A B \},\{AB,A\bar B,\bar AB\}$ which is ...
Awe Kumar Jha's user avatar
0 votes
0 answers
48 views

General form of $\sigma$-algebra of countable set

Let $\Omega$ be a countable set. I want to show that every $ \sigma $-algebra $\Sigma$ on $\Omega$ is of the form \begin{equation} \{ \bigcup_{k \in K'}A_k : K' \subset K \}, \end{equation} where $A_k$...
Einsteinwasmyfather's user avatar
1 vote
0 answers
46 views

Does this relation partially order partial partitions?

By a partial partition of $X$, I mean a collection of non-empty subsets of $X$ that are disjoint. Given partial partitions $\mathcal{A}$ and $\mathcal{B}$ of $X$, define $\mathcal{A} \leq \mathcal{B}$ ...
user avatar
0 votes
1 answer
65 views

$\sigma$-algebra generated by sequence of subsets

Let $(A_n)_n$ be sequence of subsets of a set $\Omega$. For all $a \in \{0,1 \}^{\mathbb{N}}$, define \begin{equation} \label{eu_eqn} F(a) := \bigcap^\infty_{i=1}A_i^{(a_i)} , \end{equation} where $A^{...
Einsteinwasmyfather's user avatar
4 votes
0 answers
70 views

Partition $\{1,2,...3n\}$ into $n$ disjoint triplets $\{a,b,c\}$ so that $a+b=c$

An equivalent statement is : partition the set $\{1,2,...3n\}$ into three disjoint subsets $A=\{a_1,a_2,...a_n\}$, $B=\{b_1,b_2,...b_n\}$, and $C=\{c_1,c_2,...c_n\}$, so that $a_i+b_i=c_i$ . It can be ...
Sven2009's user avatar
  • 249
1 vote
0 answers
42 views

The number of different (edge) clique covers of a clique

A simplified version Given a complete graph $K_n$ on $[n]$ for some $n \in \mathbb N$, we consider all the possible edge clique covers of $K_n$. Specifically, we aim to use a sequence of pairwise ...
Vezen BU's user avatar
  • 2,150
1 vote
0 answers
53 views

A Matroid Exchange Property

Let $(E,I)$ be a matroid, and let $A,B \in I$ be disjoint independent sets in the matroid. Moreover, let $B_1,\ldots, B_k$ be a partition of $B$. I could not decide if the following is always true. ...
John's user avatar
  • 193
0 votes
1 answer
89 views

What is the cardinalities of the quotient set and individual abstraction classes?

The given equivalence relation is defined as $r \subseteq P(\mathbb{N})^2$: $P \ r \ Q$ if and only if $P = Q = \emptyset$ or $P, Q \neq \emptyset$ and $\min P = \min Q$. What is the cardinality of ...
user avatar
0 votes
0 answers
84 views

Show that $\text{Part}(A)$ is a complete lattice

Let $A$ be a set and let $\text{Part}(A)$ denote the collection of all partitions of $A$. Define the relation $\leq $ on $\text{Part}(A)$ by $P_1\leq P_2$ if and only if for every $A_1 \in P_1$ there ...
Alphie's user avatar
  • 4,827
3 votes
1 answer
73 views

Automorphisms of a finite partition lattice

Is the group of automorphisms of a lattice of partitions of the set $X$, where $|X| = n$, isomorphic to $S_n$? I think it is (for sure it's not 'smaller' than $S_n$), but i can't find any proof of it ...
Evgeny's user avatar
  • 33
3 votes
1 answer
48 views

If $U=\{1,2,3\}$, is $\{U\}$ a partition of $U$?

From my understanding, a partition $F$ of a set $U$ means that $F$ is pairwise disjoint, and $\bigcup F=U$, and empty set is not in $F$. So if $U=\{1,2,3\}$, would $F =\{\{1,2,3\}\}$ counts as a ...
user22712878's user avatar
0 votes
0 answers
29 views

Field generated by a class of subsets

Let $A_1,...,A_n$ be subsets of a set $\Omega$. For all $a \in \{0,1 \}^n$, define \begin{equation} \label{eu_eqn} F(a) := \bigcap^n_{i=1}A_i^{(a_i)} , \end{equation} where $A^{(0)}:= A_i$ and $A^{(1)}...
Einsteinwasmyfather's user avatar
0 votes
0 answers
33 views

Extension of equivalence relation concept

We have the definition of Cartesian Product as follows: Let $X$ and $Y$ be two sets, then the set $X \times Y = \{(a, b) : a \in X,~b \in Y\}$, is called Cartesian product of $X$ and $Y$ Elements of ...
user_1729's user avatar
0 votes
0 answers
80 views

Number of equivalence relations in a set of 5 elements

Let $X$ be a set s.t $|X|=5$ , How many equivalence relations are there from X to itself? I tried to do it "manually" and I tried to create all possible relationships, Considering $X$ has ...
MASSIMILIANO MESSINA's user avatar
2 votes
0 answers
62 views

Finding all set partitions where the elements in each part are restricted to specific subsets of the set.

I want to find the number of ways x people can pick different amount of items from a set, where we can somewhat pinpoint which particular items each person can pick. My case has 3 people picking up to ...
Ziiik's user avatar
  • 21
0 votes
0 answers
28 views

Do we have recurrences for evaluating the Partition Function on Graphs?

Inspired by this question about defining the partition function on non integers, I was thinking about what sorts of other objects can a partition function be defined on. I noticed that if we have an ...
Sidharth Ghoshal's user avatar
1 vote
0 answers
96 views

Questions about the join and meet of partitions

In Aumann's ``Aggreeing to disagree" classic paper, the author defines for different partitions of a set $\Omega$, that refers to the state of the word, the join $\vee$ and the meet $\wedge$. For ...
Oliver Queen's user avatar
1 vote
2 answers
98 views

Finer partitions mean more informative partitions? (I try to give an example and answer this question)

Is the following claim true? $\textbf{Claim:}$ The finer a partition $P$ it becomes, the more informative is. Let me give an example of a partition on some space where the Lebesgue measure is defined ...
Oliver Queen's user avatar
2 votes
0 answers
47 views

Rationalization of $\frac{1}{\sum_{i=1}^{n}\sqrt{a_i}}$ (symmetric formula with multi-index)

Motivation No particular motivation, I'm just curious to see if an interesting result can emerge from such a seemingly simple problem. Problem Find the closed symmetric formula for the rationalization ...
Math Attack's user avatar
1 vote
2 answers
50 views

Bipartite graph definition in West's Introduction to graph theory

Why does it say "possibly empty" in the definition of bipartite graph? Wouldn't that mean that every graph is bipartite, moreover I don't think partitionins can have empty sets. Is this a ...
Metric's user avatar
  • 145
0 votes
0 answers
17 views

A Question Over set partitioning

There is a bit in the proof, the link, I couldn't understand. "There exists a sequence $(Π𝑛)$ of partitions, such that for each $𝑛$,$Π𝑛$ is an $𝑙+1/𝑛$-partition" How are we sure that ...
samatra's user avatar
1 vote
0 answers
39 views

Bijection between partitions of [n βˆ’ 1] into k βˆ’ 1 parts and partitions of [n] into k parts in which no part contains consecutive integers

Construct a bijection between unrestricted partitions of $[n βˆ’ 1]$ into $k βˆ’ 1$ parts and partitions of $[n]$ into $k$ parts in which no part contains consecutive integers. I was thinking of picking ...
J P's user avatar
  • 343
2 votes
1 answer
107 views

Can someone help to clarify what " the data of an equivalence relation is the same as the data of a partition" means?

I am currently self-learning Modern Algebra on MIT OCW. I am at the lecture on cosets and am stuck on the theorem connecting equivalence relation and partition. I understand what the theorem implies, ...
196884 is 196883 plus 1's user avatar
2 votes
0 answers
107 views

When is the partition refinement graph Eulerian?

Let $n$ be a positive integer, and let $p(n)$ be the number of partitions of $n$. For two partitions $p_1, p_2$ of the same integer $n$, we say that $p_2$ is a refinement of $p_1$ if the parts of $p_1$...
Hasan Zaeem's user avatar
1 vote
0 answers
42 views

How to find the number of inequivalent partitions of the powerset of a set of $n$ elements

Consider the partitions of the powerset of $\{1,2,\cdots,n\}$, which are the sets of the form $\mathcal{A}=\{S_\lambda:\lambda\in\Lambda\}$, where each $S_\lambda$ is nonempty, $S_\lambda$ and $S_{\...
Jianing Song's user avatar
  • 1,923
3 votes
1 answer
263 views

Set partition with some conditions

This is the problem I am trying. Define $S_k(n)$ to be the number of partitions of the set $[n]$ so that if $i$ and $j$ are in the same block, then $|i-j| > k$ holds. Show that $S_k(n) = B(n - k)$,...
asdkfewp's user avatar

1
2 3 4 5
…
16