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
0answers
10 views

equal size ranked partition notation

Let $X$ be a set of $n=mk$ solutions, the objective value of which can be evaluated by $f(x)$ for any $x \in X$. We can rank the set by their objectives to get $X'$ with: $X' = x_1,x_2,\dots,x_n : f(...
0
votes
1answer
30 views

Is $\{\{1,2,3\},\emptyset\}$ a partition of $\{1,2,3\}$?

Title says it all. Is $\{\{1,2,3\},\emptyset\}$ a partition of $\{1,2,3\}$? I'm guessing it isn't, because the definition in Naive Set Theory states the following: A partition of $X$ is a disjoint ...
1
vote
0answers
32 views

Bipartite Graph Construction

Assume $m$, $n$ to be positive integers. Given two partitions $[mn]=A_1 \cup A_2 \cup \dots \cup A_m$ and $[mn]=B_1 \cup B_2 \cup \dots \cup B_m$ of $[mn]$ into sets of cardinality $n$, show that the ...
1
vote
0answers
15 views

How can I find the minimum number of components of a partition of a set X such that the components are ordered? [closed]

I have a permutation on the set $X=\{1, ...,n\}$, say $(1,3, 2,...,n)$ and I want to know what is the minimum number of components that I need to create a partition of X such that the components of ...
4
votes
1answer
60 views

prove that $S$ is a subgroup of $G$

QUESTION: Let $S$ be a subset of $G$ such that the identity element $1 \in S$. Assume that the subsets $aS := \{as \mid s \in S\} \subseteq G$ for $a \in G$ form a partition of $G$. Prove that $S$ is ...
10
votes
1answer
181 views

Does there exist a continuous partition of the sphere into sets of cardinality 4?

Define $X^{\{n\}}:=\{A\subseteq X:|A|=n\}$, the set of subsets of cardinality $n$. If $X$ is a topological space, $X^{\{n\}}$ can be given a topology by considering it to be a quotient of $X^n$ minus ...
0
votes
2answers
31 views

5 books in 3 bundles

5 distinct books can be tied in 3 indistinct bundles in how many ways, if order of book within a bundle does not matter? I have counted in following way, and I saw another person counting in a ...
1
vote
0answers
38 views

Can a singleton be a partition?

Can a set, A, {1} be a partition ? Let say I let C be a partition of A such that C = {{1}}. Definition of partition C is a set of which all elements are nonempty subsets of A Since there is only 1 ...
0
votes
0answers
12 views

Generalized Laplace expansion formula for a partition family

Edit: I think my question isn't well formulated and I have to reconsider what I'm actually trying to ask. I will ask a new question then. According to wikipedia there is a generalized Laplace ...
0
votes
0answers
24 views

Number of partitions with limited cardinality [duplicate]

We are given $k$ urns labeled from $1$ to $k$. What is the number of ways to put $n$ indistinguishable balls into the $k$ (distinct) urns, given that each urn has a limited capacity equal to $c$, ...
0
votes
3answers
65 views

Proof that there is exactly one equivalence relation that forms a partition

So I've just started trying to teach myself some topology and i cant quite grasp how an equivalence class forms a partition more specifically i don't understand the proof that there is exactly one ...
0
votes
0answers
52 views

Finding a specific partitioning of a finite ordered set of positive integers.

Definition of partitioning Let $S$ be a finite ordered set of positive integers. $$S = \{s_i \mid s_i \in \Bbb{Z}^+\}$$ E.g. $S = \{4, 7, 9, 8, 3, 2, 5\}$ Given this set $S$, we define $P$ as a ...
1
vote
2answers
43 views

Is a quotient set the same as a partition?

So I've just started trying to teach myself some topology and im really confused on what a partition is and how it is in any way related to an equivalence relation. My main confusion however is that ...
1
vote
1answer
15 views

What notation to use for case distinction in a set

I'm currently in the following framework: $n \in \mathbb{N}$, $I \subseteq \{1, \dots, n\}$ and $X \subseteq \mathbb{R}$. Now, I need to define a set which contains all vectors $v \in \mathbb{R}^n$ ...
0
votes
2answers
35 views

Proof of partition of natural numbers

I have a set $A_n$ = $ \{2^i(2n-1): i \in \mathbb{N} \cup {0} \}$ It is said that the set $P = $ $\{A1, A2, A3,...\}$ partitions the natural numbers. I am attempting to solve this by the definition ...
0
votes
0answers
10 views

verify if pair of numbers are median of two way partition subsets.

Given a finite discrete set $X \subset \mathbb{R}$. There can be many two-way partitions $A, B$ of it. Namely, $A, B \subset X, A\cup B = X, A \cap B = \emptyset$. For every finite discrete set of ...
0
votes
1answer
10 views

relation of medians of two way partition

Given a set of finite real numbers $X \subset \mathbb{R}$, one can obtain the median using $M: X \to \mathbb{R}$. And $X$ can be partitioned into two subsets $A_i, B_i \subset X, A_i \cup B_i = X , ...
1
vote
1answer
57 views

Mathematical formulation of an optimization problem

I have the following optimization problem at hand. There are N integer numbers, $a_{i},a_{i+1},\dots,a_{n}$ where $a_{i} > 0$. We need to partition these numbers ...
0
votes
2answers
28 views

How many different equivalence relations with exactly two different equivalence classes are there on a set with $n$ elements

I came across with this topic. It looks straight forward for $5$ elements, but what if I want to find how many different equivalence relations with exactly two different equivalence classes are there ...
0
votes
0answers
17 views

Partitioning of a duplicated set without duplicates

If there is a set $S$ and each unique element $P$ in this set has one duplication, then $S = 2P$. Is there any efficient algorithm that can randomly partition this set $S$ into $K$ partitions, while ...
1
vote
1answer
64 views

Show that the number of ways of splitting a set with $n$ elements into $k$ non-empty subsets is equal to $x^n$'s coefficient in a series

The series evaluates to (could not put it in the title): $$\frac{x^{k}}{(1-x)(1-2x)...(1-kx)}$$ I tried to come up with something. A solution would probably require a use of the geometric series ...
0
votes
1answer
42 views

What does “the partition of $\mathcal{P}(A)$ induced by $R$” mean? [closed]

I am working on the following question: Let $A$ be a non-empty set and fix a subset $B$ of $A$. Define a relation $R$ on the set $\mathcal{P}(A)$ of subsets of $A$ as follows: $$R = \{(X, Y) | X \cap ...
0
votes
1answer
63 views

Prove whether this is true or false: For every two sets $A$ and $B$, $\{A\oplus B, A\cap B\}$ is a partition of $A \cup B$.

I am having trouble with this question. Does anyone have an idea?
0
votes
1answer
22 views

What is the algebraic structure of all the quadtrees under these operations?

I was implementing a quadtree in a programming language, and I realized I could define operations such as negation $\bar{x}$, reunion $a\cup b$ and intersection $a \cap b$ on these objects. These ...
2
votes
1answer
44 views

What is the minimum number of sets such that the product of elements in each of them is less than k?

Given a positive number n and a positive number k. How to find the minimum number of sets such that for each set s , the product of all elements in s is less than or equal to k. And also all the sets ...
5
votes
0answers
51 views

Partitions of integers and coloring tesseract graphs

I posed myself the problem of partitioning the integers $0\leqslant n<16$ into 4 equal parts, such that if they are expressed in 4-digit binary, any number selected can be switched to a number in ...
-1
votes
2answers
51 views

how to prove that a set is a partition of another set

problem 2 let f:X$\rightarrow$Y be onto . For each b$\in$Y, let $A_b$=f^-1[{b}]. Prove that { $A_b$:b$\in$ Y} is a partition of X I know I need to prove that for all sets in { $A_b$:b$\in$ Y} they ...
0
votes
0answers
50 views

Question about partitioning a finite cycle

Does anyone know if there's any theorem/statement that says that any finite group can be partitioned into the direct product of cyclic, dihedral, symmetric, etc groups? I'm working on a problem and a ...
0
votes
2answers
39 views

Recursively generating all partitions

Given a set $\{1,2,\ldots,n\}$, I would like to recursively generate all partition of size $r$ and $n-r$. For instance, we start with the partitions $$\{1,2,\ldots, r\} \quad \{r+1,\ldots, n\}$$ and ...
1
vote
1answer
56 views

Interesting question about exponential generating function of the number of partitions under a certain statistic.

Find the exponential generating function of the number of partitions of $[n]$ ( according to) under the statistic of the number of blocks that contain an even number of elements (a block $K$ such that ...
0
votes
1answer
25 views

How many partitions to divide a set of n elements into k subsets, mantaining order of the set?

For example I have a string 'bbbbb' (n = 5) and want to divide it in 3 (k = 3) groups. The possibilities are 6: b|b|bbb b|bb|bb b|bbb|b bb|b|bb bb|bb|b bbb|b|b How can I find the number in advance?
1
vote
2answers
54 views

How do you call a partition of a totally ordered set that…

A partition of a set S is a collection P={B1,B2,...,Bk} of subset of S such that for each i, j, ∈ {1,2,...,k}: Bi ≠ ∅ Bi ⋂ Bj ≠ ∅ B1 ⋃ B2 ⋃...⋃ Bk = S now if S is a totally ordered set and P is ...
0
votes
2answers
25 views

Partitioning a set of cardinal $np$

I wish to compute the number of possible partitions $S$ of a set of cardinal $np$ into $n$ subsets of cardinal $p$. It is easy to obtain the formula : $\displaystyle S=\sum_{k=0}^n {{pk}\choose{p}}$. ...
1
vote
1answer
26 views

In this probability question about counting using partitions and the multinomial coefficient in a probability question, are the events disjoint?

I designed a question where there are 12 employees, and they are to be assigned to 3 distinct teams (let's call them team 1, 2 and 3). Suppose the twelve people are $A$, $B$, $C$, $D$, $E$, $F$, $G$, $...
2
votes
4answers
102 views

Lemma used to prove $\left|HK\right|=\frac{\left|H\right|\left|K\right|}{\left|H \cap K\right|}$

Given a group $G$ and $H,K \le G$,then : $$\left|HK\right|=\frac{\left|H\right|\left|K\right|}{\left|H \cap K\right|}$$ Where $HK:=\left\{hk:h \in H ,k \in K\right\}$ Lemma: For $h_1,h_2 \in H$ $$hK=...
0
votes
0answers
16 views

Formula for successive subset partition counting?

I've been trying to find a formula for this, but i'm not sure if it's already existing? Is there a formula for set partition which takes sets as symbols, for example: $A,B,C,D,...$, then let's say you ...
0
votes
0answers
16 views

How to determine if a positive integer is comparatively small

Given a set of positive integers, what is a basic statistical method that cuts off the smallest numbers in the set if the method (fed some parameter) determines they are "negligible" or &...
0
votes
2answers
98 views

Similarity relations on sets

Good evening, I am reading Hazel and Humberstone's "Similarity Relations and the Preservation of Solidity", a paper that has the aim of defining, starting from partitions and equivalence ...
0
votes
0answers
27 views

Finding all non-overlapping subgraphs / non-intersecting sets

Consider a graph like so: My task is find the all of the non-overlapping subgraphs, i.e. the union of the "groups" (nodes gN) that share no leaves. For ...
0
votes
2answers
88 views

Proving surjectivity with partitions with a set

I've got the following sentence : Let \begin{array}{ll} F :& P(A)\times P(B) \longrightarrow P(E) \\ &(X,Y) \longrightarrow X\cup Y \end{array} where $A$ and $B$ are two subsets of E. I ...
3
votes
2answers
182 views

How many groups of pentagonal flower bouquets can be formed?

A florist has three types of flowers: tulips, roses, and daisies. There are 4 tulips, 5 roses, and 6 daisies. These 15 flowers are to be arranged into three bouquets of 5 flowers each. Assume that ...
2
votes
0answers
89 views

On a type of stability for irrational rotation

I hope you can give me some suggestion. Definition: Given two bijections $f,g:\mathbb{S}^1\to \mathbb{S}^1$ and $\mathcal{P}$ a partition of $\mathbb{S}^1$ (a partition of $\mathbb{S}^1$ is a finite ...
1
vote
1answer
86 views

Prove the set of all left (right) cosets of $H$ partitions $G$.

Given a group $(G,\circ)$ and $H \le (G,\circ)$,the left coset of $H$ is the set of all elements of $H$ multiplied by a fixed element in $G$,formally given $g \in G$,then the left cosets of $H$ is ...
0
votes
1answer
46 views

Number of Partition [closed]

Let a subset of integer S = { -4<a<15; a is integer}.We have make partition for S such that Partition will contains exactly 5 disjoint subsets. 2)Among these 5 subsets exactly one has 4 ...
0
votes
1answer
41 views

Combinatorial interpretation behind the recurrence relation $L(n+1,k)=(n+k)L(n,k)+L(n,k-1)$ ,where $L(n,k)$ are Lah numbers

Lah numbers are the number of ways to partition $n$ distinct objects into $k$ non-empty linearly ordered subsets and is denoted by $L(n,k)$, an explicit formula can be derived: $$L(n,k)=\sum_{r_1+...+...
0
votes
0answers
45 views

Optimal Set Partitioning

Consider a set of integers $1$ to $n$, $$ \mathcal{S} = \{1,2,3,\ldots,n\} $$ initialised with no-partitions. Now let $L[f(\mathcal{S})]$ be a cost function we wish to minimise that depends on some ...
0
votes
1answer
35 views

$D_n:=$ number of partitions of set with $n$ elements with not more than one singleton subset. Express $D_n$ through $F_n$

IMPORTANT: $F_n$ is amount of partitions where in each partition there are no subsets of size less than 2 (no singletons). I don't know if it can be helpful but I know how to express Bell's number ...
0
votes
0answers
37 views

What can say about the behaviour of the sum $S$?

First, let us consider $0<s<1$ and $0<\epsilon <1$ fixed. Suppose we have to cover $[0,1]$ by closed intervals each of whose length is less than $\epsilon$. Suppose we name those intervals ...
2
votes
2answers
117 views

$F(n)$ is number of ways to partition set of $n$ without singleton blocks. Prove that $B(n) = F(n) + F(n+1)$

In this case $B(n)$ is $n$-th Bell number. To be honest, I would really love to know if there is a combinatorial proof for that. If there is not, other proofs are appreciated too.
1
vote
1answer
40 views

Partition of a set of positive integers

Problem: Let $A$ be a non-empty set of positive integers. Suppose that there are positive integers $b_1,\ldots b_n$ and $c_1,\ldots,c_n$ such that for each $i$ the set $b_iA+c_i=\left\{b_ia+c_i\colon ...

1
2 3 4 5
12