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 [set-partition]

The tag has no usage guidance.

-1
votes
0answers
6 views

Prove the problem with partitions of set

I want to prove this question, but I cannot:( Q. Suppose P1 is a partition on A1, P2 is a partition on A2. Then P1*P2 is also a partition on A1*A2. How can I prove it?? Thanks:)
2
votes
1answer
19 views

Definition of an arrangement of the plane

... for a finite set $H$ of lines in the plane, the arrengement of $H$ is a partition of the plane into relatively open convex subsets, the faces of the arrangement. In this particular case,(*) the ...
0
votes
0answers
13 views

Choosing an optimal partition

We have a finite list of length $N$ of positive integers, $$B=[b_1,b_2,b_3,...,b_N]$$ We partition this list into three sublists by choosing two points of division: $p,q \in \mathbb{N} $ such that $1&...
0
votes
1answer
31 views

Equivalent definition of partition in set theory

According to my Prof, the definition of partition in Set-theory is $S\subseteq P(A) \smallsetminus\{\emptyset\} $ is partition of A if for All $a\in A$ exists $T\in S$ unique such that $a\in T$. ...
0
votes
0answers
12 views

Right Partition vs Right Graph

I came up with this problem yesterday: Let $R$ in $\mathbb{R}^2$, $P$ a finite partition of $R$ into rectangles such that every rectangle in $P$ has its sides parallel to the sides of $R$ and $P_c$ ...
0
votes
0answers
70 views

Exact formula of equal partitioning of group stage matches

There are N players in a tourney, each plays exactly one match with the others. How can I partition these matches up to K parts to get the most equal partitions if I want to keep the left side of a ...
1
vote
1answer
36 views

Is this a partition of $\mathbb{N}$ into two sets such that neither has an infinitely long arithmetic progression?

We want to partition $\mathbb{N}$ into $A,B$ such that $A$ has no infinite arithmetic progression and $B$ has no infinite arithmetic progression. Here is my attempt. I am looking for possible ...
0
votes
0answers
70 views

Proof for sets given constraints

My question is one from my graph & set theory class that I'm not sure how to solve. Any help would be greatly appreciated. Let $\{(A_i, B_i) \mid 1 \leq i \leq h\}$ be a family of pairs of sets ...
0
votes
1answer
47 views

Renumerating partitioned sets [duplicate]

This is a problem in my graph theory class and I'm unsure about how to solve it.. Let $X$ be the set $\{1,2,\dots,mn\}$. Suppose we partition $X$ into $m$ sets $P_1,\dots,P_m$, each of size $n$. ...
1
vote
1answer
47 views

Combinations of N letters from an alphabet of N different letters [duplicate]

I'm trying to determine the number of combinations of $N$ letters from an alphabet of $N$. For instance for $N = 2$, with alphabet $(A, B)$, I can obtain $AA$, $AB$ and $BB$, $BA$ and $AB$ are the ...
1
vote
1answer
28 views

Formula for the total number of partitions

I am trying to tackle the following exercise from Norman L. Biggs, Discrete Mathematics , p.91 Suppose we are given a partition of the $n$-set $X$ into $k$ parts, and we delete the part containing ...
0
votes
2answers
10 views

Partitioning the real line

I was looking for an equivalence relation between the points of the real line such that the equivalence classes are $1$ unit long segments. I found two so far 1) Let $x_1,x_2\in\mathbb{R}$ and $$ ...
2
votes
0answers
16 views

Intervals partitioning: minimum overlap

Suppose there are intervals in the format of r = (start, end), and D = {r1, r2, ..., rn). Now we would like to partition ...
0
votes
0answers
18 views

Partition of a normally distributed random vector

Let $ X=(X_i) $ represent a $ k $-dimensional random vector following a normal distribution, i.e., $ X \sim N(m,S) $ with mean vector $ m=(m_i) $ and covariance matrix $ S=(s_{ij}) $. Let $ p \in (0,1/...
1
vote
1answer
48 views

A problem about partition of the set $\{1,2,..,n\}$

I have a problem from my sister's studies: Find the minimum number $n$ such that, for every partition of the set $X=\{1,2,...,n\}$ into three non-empty subsets, there always exist two numbers $a$ and ...
1
vote
1answer
29 views

Partitioning $\mathbb{R}^3$ into two convex sets.

I know that there are $4$ partitions of $\mathbb{R}^3$ into two convex sets, up to affine transformation. One of the partitions is the trivial $\{\emptyset,\mathbb{R}^3\}$ (note that by partition, I ...
2
votes
1answer
40 views

Combinatorics of weighted vector compositions

I am interested in a problem related to the one of enumerating all vector compositions (as described in chapter 4.3 from "The Theory of Partitions" from G.E.Andrews): Vector (2,1) can be decomposed ...
0
votes
1answer
49 views

Rotation of sequences

(a) Show that for any sequence $(r_1,r_2,...,r_{n+k})\in \mathbb{N}^{n+k}$ such that $\sum r_i=n$, exactly $k$ of its rotations $(s_1,s_2,...,s_{n+k})=(r_{l+1},...,r_{n+k},r_1,...,r_l)$ satisfy $$s_1+...
1
vote
1answer
79 views

How many partitions of a set $S$ into $K$ different subsets of size $k_1, k_2, k_3,\cdots, k_K$?

I want to code a program to solve a variation of the salesman problem but I am encountering some difficulties. The idea is that I have $S$ points (customers) I'd wish to visit and I always depart and ...
8
votes
2answers
90 views

What natural ways of partitioning a group $G$ are there?

What natural, or at least useful, ways are there to partition a finite group $G$? The two examples that come to mind are: Partitioning $G$ into all the left (or right) cosets of a subgroup $H$ of $G$....
0
votes
1answer
39 views

Different ways to split 8 people into at least two non-empty groups

In how many different ways can you split 8 people into at least two non-empty groups? My attempt: Since Bell number of 8 elements set is 4140 and we don't need whole set in one partition, is the ...
1
vote
1answer
33 views

Meaning of $X(B_1)$ where X is a random variable

I'm studying the formal definition a Dirichlet process: $${if } X \sim \operatorname{DP}(H,\alpha)$$ $$\text{then }(X(B_1),\dots,X(B_n)) \sim \operatorname{Dir}(\alpha H(B_1),\dots, \alpha H(B_n))$$ ...
0
votes
1answer
25 views

Prove or disprove that every finite $\sigma$-algebra on $\Omega$ is generated by a finite partition of $\Omega$.

Prove or disprove that every finite $\sigma$-algebra on $\Omega$ is generated by a finite partition of $\Omega$. I have a feeling this must be true, but I could not do more than the following: Being ...
3
votes
0answers
31 views

distribution of bisecting great circles

For any point on the globe, I believe there is (by the mean value theorem) at least one great circle containing that point and dividing the world's land area (or water mass, or population, whatever) ...
3
votes
1answer
49 views

Is there any work on partition a partial order set into minimum number total order subsets?

The problem is what's the minimum number of total order subsets can a partial order set partition into? For example, (1,2) and (3,4) are comparable i.e. (1,2) < (3,4), and (1,2) and (2,1) are ...
4
votes
1answer
40 views

Infinite set of positive integers - choose infinitely many to be relative primes or not

Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes ...
1
vote
1answer
88 views

Partition of positive reals with each part closed under addition without choice

It is an easy exercise using transfinite recursion to prove the following (in ZFC): There exists sets $S,T$ that partition $\mathbb{R}_{>0}$ such that each of $S$ and $T$ is closed under ...
-1
votes
1answer
32 views

Find Equivalence Classes and the quotient set defined by the relationship in Reals.

$xTy\iff |x^{2}-2|=|y^{2}-2|$ I'd love to solve it but we don't deal in absolutes. Joke aside I have no clue where to start with this one, it has me stumped. If I had been provided the answer to the ...
2
votes
1answer
48 views

Find Integer Partition using only integers belonging to S = { 1, 2, 3 }

I spent all afternoon looking for this but I wasn't able to find anything, so... Is there a formula to know the NUMBER of partitions with a constraint on the integer domain ? E.g.: Find the number of ...
2
votes
1answer
81 views

Coloured partitions

I have $2n$ elements, $n$ of which are blue and the other $n$ are orange. Other than sharing a colour, they are distinct, i.e. each of those $2n$ objects is different and recognizable from any other. ...
0
votes
1answer
52 views

What are isomorphic partitions?

Let $R_1, R_2 ∈ R(X)$ be equivalence relations on $X$. Define $R_1$ and $R_2$ to be isomorphic if there exists a bijection $f : X → X$ such that the following holds: For all $y, z ∈ X : (y, z) ∈ R_1$ ...
1
vote
0answers
57 views

Prove there is a bijection φ : R(X) → P(X)

For a set $X$, let $R(X)$ be the set of equivalence relations on $X$ and let $P(X)$ be the set of partitions of $X$. Prove there is a bijection $\varphi : R(X) \to P(X)$. Stuck on how to proceed with ...
1
vote
1answer
33 views

How to create sets of nodes on a colored graph while cutting as few edges as possible

I'm a programmer not a mathematician so my jargon is terrible and I apologize. My problem: I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of ...
0
votes
1answer
36 views

What is the appropriate weight ($W_k$) (for two arbitrary partitions)?

I already asked a similar question, And from the answer I received, another question came to my mind. A positive integer can be partitioned, for example, the number 7 can be partitioned into the ...
3
votes
1answer
48 views

Is this true for every partitioning?

I have two categories (category1 and category2 ) and The size of both categories is equal to each other. if we partition each categories arbibtrary .Is this proposition proven? or rejected? $n_T \...
0
votes
1answer
24 views

Let $a \in A \ and\ U \in C \ such\ that\ a \in U\ $. Prove that $[a] = U\ $.

If you refer to this link and the question, it's this same question, this is the last part of the 4 part question . The equivalence relation $\sim$ is defined as: $$\textsf{For }x,y\in A,x\sim y\...
0
votes
1answer
45 views

Prove that $\sim$ is an equivalence relation on the set $A$

Let $A$ be a nonempty set and $C$ is a partition of $A$. A relation $\sim$ is defined as: $$For \ x, y \in A, x\sim y\ \ if \ and \ only \ if \ there \ exists \ U \in C \ such \ that\ x \in U and\ y \...
1
vote
3answers
50 views

Why does there not exist a particular finite set of congruences that forms a partition of the set of integers

There is a paragragh that I saw in an article and could not really understand. The article is Covering Systems of Congruences, J. Fabrykowski and T. Smotzer, Mathematics Magazine Vol. 78, No. 3 (Jun., ...
3
votes
0answers
38 views

Counting 2-partitions of $\{1, 2, \cdots, n\}$ of equal size and sum [duplicate]

The following question solves the existence of such a partition: Partitioning $\{1,\cdots,k\}$ into $p$ subsets with equal sums. However, I'm trying to count how many such 2-partitions exist. ...
5
votes
2answers
81 views

Using basic arithmetic, how do I count constrained partitions of a set?

On my 9-year-old daughter’s recent test over multiplication and grouping that included questions about the total number items in m groups of n and converting between multiplication sentences and ...
1
vote
2answers
46 views

$A_r=\{(x, y) \in \mathbb{R} \times \mathbb{R} : x+y=r\}$

I have figured out how to prove $A_r$ is nonempty but I am stuck on the last two parts of proving a partition of Real numbers. For part 2 I have "Let r, s $\in \mathbb{R}$ with x+y=r and x+y=s, so ...
0
votes
3answers
38 views

Determinant matrix projective space?

Let $M_n(\mathbb{R})$ the space of all real square matrices of dimension $n$, with the equivalence relation E, defined as: 2 matrices are equivalent if and only if they have the same determinant. ...
4
votes
3answers
361 views

Why are partitions and equivalence relations the same thing?

My lecturer omitted the proof in the lecture notes. From what I can gather, it's because equivalence classes partition always partition a set (the class can contain only that element or more and the ...
1
vote
0answers
43 views

Inclusion exclusion and partition of a set - making sure I understand the concepts

If I may, I would like to verify my solution of a couple of homework questions, and by doing so asking a few questions about these topics. Let $X$ be a set of size $n$. How many distinct triplets $(A,...
0
votes
1answer
13 views

The cardinality of interval partitions of $ℝ$

Let $\mathcal X$ be a partition of $ℝ$ into non-degenerate intervals (i.e., intervals that aren't just points). Must $\mathcal X$ be countable? It's clear to me that the answer is yes if we assume ...
1
vote
2answers
24 views

~$_P$ is an equivalence relation in A.

Prove Proposition 2.23. Use the notations defined in Definition 2.21 and 2.22. Definition 2.21. Let A be a set and R be an equivalence relation in A. Let x $\in$ A be an arbitrary element in A. The ...
1
vote
0answers
25 views

Combinatorial problem of noncrossing partitions for recursively defined functions

Let $N$ be an even integer. Assume a class of functions $g(b_1,...,b_N)$ with $b_i\neq b_j$ for all $i,j$. These functions are defined recursively by the symmetric function $g(b_i,b_j)=g(b_j,b_i)$ ...
0
votes
1answer
36 views

In how many different ways can 50 children be distributed in 5 identical classrooms

This problem is solved using Stirling numbers of the second kind : We can have empty classrooms If no classroom is empty we get $S(50,5)$ If one classroom is empty we get $ {5}\choose{4 } $ $ S(50,...
2
votes
3answers
33 views

What is wrong with my reasoning on this partitioning question?

I set the following question for my secondary school students, but realised it's harder than I intended. How many ways can a class of 20 students be divided into three teams of any size? I realise ...
0
votes
1answer
42 views

Let $P$ be a partition of a group with $AB \subseteq C$. Why is $1 \in P_n$? $P_n$ is the equivalence class of $n \in N$ and $1 \in N=P_1$.

Let P be a partition of a group G with the property that for any pair of elements A, B of the partition, the product set AB is contained entirely within another element C of the partition. Let N be ...