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

Help proving this combinatorics identity

Suppose $I_{N} := \{1,...,N\}$, $N \ge 1$, is a subset of $\mathbb{N}$ and $\mathcal{P}(I_{N})$ denotes the set of all subsets of $I_{N}$. Suppose we have a family of objects $\{f_{X}\}_{X\in \mathcal{...
user avatar
  • 1,451
0 votes
2 answers
52 views

Notation: function returning the element of a partition containing $x$

Suppose $Y=\{y_1,\ldots,y_m\}$ partitions the set $X=\{x_1,\ldots,x_n\}$. I would like to define a function $y: X \to Y$ which returns $y \in Y$ if and only if $x \in y$. Is there a way to write this ...
user avatar
0 votes
1 answer
29 views

Proving that the quotient of a set by an equivalent relation is a partition

I need to show that the quotient of a set $S$ with respect to the equivalence relation $\sim$ is a partition of $S$. To show this, we will denote the quotient by $P_\sim.$ Note that $$ P_\sim = \{[a]_\...
user avatar
3 votes
1 answer
76 views

Distributing $n$ distinct objects into $m$ types of urns with $k_1,k_2...k_m$ urns of each type

I came accross this (rather complex?) combinatorial problem: I have $18$ distinct objects, $3$ red urns, $7$ blue urns, and $11$ green urns. In how many ways can I distribute the objects into those ...
user avatar
0 votes
0 answers
9 views

Stratification of a space which induces a stratification of a subspace

Let $\{X_i\}_i$ be a stratification of the (smooth, complex, algebraic) manifold $X$ and let $Y\subset X$ be a closed submanifold of $X$. Is it true that the family $\{Y\cap X_i\}_i$ defines a ...
user avatar
0 votes
1 answer
90 views

How many partitions does an infinite set have? [duplicate]

I've been looking into how many partitions a set has, mainly for infinite sets since for finite ones we have the Bell number $B_n$. I'll use the following notation:$$B(S)=\{P|P \text{ is a partition ...
user avatar
0 votes
1 answer
81 views

Prove that $\{A,B\}$ and $\{C,D\}$ partition for $X$ and $Y$ (in order).

Question: Suppose $f:X\to Y$ and $g:Y\to X$ two arbitrary functions. Prove that $\{A,B\}$ is a partition for X and $\{C,D\}$ is a partition for Y such that : $$\begin{align} f(A) = C\end{align}$$ $$\...
user avatar
  • 35
0 votes
0 answers
55 views

Proving that Iterative Process of a Partition Converges

An Econ student doing their graduate thesis here, with no formal maths background so I'd be grateful if any kind soul can nudge me in the right direction. I am studying a partition of the space [0,1] ...
user avatar
1 vote
1 answer
20 views

Bijective function from relations of equivalency set to partitions set

I am proving that f: R->P, a function that associates a relation of equivalency to a partition is bijective. Let g: P->R. I showed that g(p=partition of X)={(a,b) belonging to X²| exists A ...
user avatar
  • 11
0 votes
1 answer
44 views

How do I prove the following statement regarding partitions of a set?

$\exists! x:Px\implies (\forall x(Px \implies Qx) \iff \exists x(Px \land Qx))$ Essentially, the values of x for which P is true form partitions of the universe. This question came to mind when ...
user avatar
1 vote
2 answers
51 views

Set Partition: Subsets must be disjoint or equal?

I'm reading a Mathematical Proofs by Polimeni, Chartrand, and Zhang and their definition of a set partition is confusing me: A partition of A can be defined as a collection S of subsets of A ...
user avatar
  • 113
2 votes
1 answer
39 views

Prove that a list can be made of all the subsets of a finite set such that these conditions hold

Prove that a list of subsets of a finite set can be made such that i. The empty set is the first in the list. ii. Every subset is used only once in the list. iii. Each subset in the list is obtained ...
user avatar
0 votes
0 answers
18 views

"Product structure" for a set of partitions

Let $A$ and $B$ be disjoint sets and let $X=A\cup B$, and $\mathcal{P}(X)$ be the set of all partitions of $X$. I am interested in subsets $\mathcal{Q}\subset\mathcal{P}(X)$ with a "product ...
user avatar
  • 3,254
4 votes
0 answers
36 views

Without the axiom of choice, is there always a partition refining a collection of sets that is the same size?

Let $\Omega$ be a set and let $\mathcal{C} \subset \mathcal{P}(\Omega)$ be some collection of subsets that covers $\Omega$, so $\bigcup_{C \in \mathcal{C}} = \Omega$. We would like to find a partition ...
user avatar
0 votes
1 answer
58 views

Partitions of set with maximal cardinality

Is there a way to compute the number of partitions such that each set in the partition has a cardinality lower or equal to two? If yes, is there also an efficient algorithm to compute these partitions?...
user avatar
  • 324
1 vote
1 answer
52 views

How would you use Stirling numbers to partition a n unique objects, into m unique subsets, with minimum cardinality of 2 for each subset?

For example, how would one go about partitioning 10 numbered balls into 4 numbered boxes, such that each box contains at least 2 balls?
user avatar
3 votes
0 answers
124 views

When is it possible to split three sets?

There are three sets, each of which contains some $2 k$ elements. The sets may overlap. Is it possible to color the elements red and green, such that each set contains exactly $k$ red and $k$ green ...
user avatar
0 votes
0 answers
26 views

How many different partitions with exactly n parts can be made of a set with k-elements?

Find all partitions of S = {a, b, c, d}. Note first that each partition of S contains either 1, 2, 3, or 4 distinct cells (1) in 1 distinct cell Solution: 1 case [{...
user avatar
0 votes
0 answers
16 views

Can you explain me (and illustrate) a proposal on the partitions $A_i$ of $E$?

I'm stumbling upon this proposal that isn't followed by an example, and then I cannot really figure what it means. Can you explain it to me, or give me an illustration? Be $E$ a set and $(A_i)_{i \in ...
user avatar
0 votes
0 answers
15 views

"Canonical" ways to generate a partition from a fixed set of subsets.

Fix $A_1, A_2,...,A_N \subset U$. I can create a partition as $P_1 = A_1, \\ P_2=A_2 \setminus A_1, \\...,\\ P_N = A_N \setminus (\cup_{i<N} A_i)$. ... Is there an official name for this ...
user avatar
  • 725
0 votes
1 answer
51 views

Number of ways to partition a set into 2-element subsets.

This is from C. C. Chen & K. K. MENG, Principles and Techniques in Combinatorics, p. 21. Let $A$ be a set of $2n$ distinct objects. A pairing of $A$ is a partition of $A$ into 2-element subsets; ...
user avatar
2 votes
1 answer
39 views

Determing number of partitions which can be formed from a given partition by manipulating a single element

Background: I know it is possible to calculate the number of partitions of a set of size $n$ using the Bell numbers: https://en.wikipedia.org/wiki/Bell_number I am also aware that you can calculate ...
user avatar
  • 23
0 votes
1 answer
31 views

What is the proper name for an "ordered partition" of an "ordered set"?

Suppose I have an ordered set $X$ with a finite number of elements. Say, for instance, $S = \{0.16, 0.34, 1.15, 3.16, 5.7\}$. Note that for "ordered set" I mean that the set elements are ...
user avatar
0 votes
0 answers
37 views

number of maps from [n] to [6], if there are conditions on at least how many elements must have each image?

For example, how many maps $f: [n] \to [6]$ are there, if at least one element must have image $2$ and at least $4$ different elements must have image $5$? or in general: at least $a_i$ distinct ...
user avatar
  • 21
3 votes
1 answer
71 views

If the cosets of $S\subseteq G$ partition $G$, must $S$ be a coset of a subgroup of $G$?

If $G$ is a group and $H\le G$ is a subgroup, then the left (or right) cosets of $H$ partition $G$. If $S\subseteq G$ is a left [right] coset of $H$, then the left [right] cosets of $S$ also partition ...
user avatar
  • 4,888
0 votes
1 answer
83 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 ...
user avatar
1 vote
1 answer
53 views

Estimating the number of parts in a partition of a set

In trying to solve a problem for a project I am working on, I thought about a way to use estimation to make one of its components easier. I do not know much about probability since it is not the crux ...
user avatar
  • 825
0 votes
1 answer
26 views

Tree and total probability rule (two events)

I'd like to know if the tree related to the following rule: is the first or the second one or can be both depends on the context. If possible, make some example.
user avatar
1 vote
1 answer
37 views

Number of partitions for given list into three ways

I want to decompose given list $P=\{1,2,3,...,n\}$ into three subsets $Q,R,S$ considering without ordering of a given set. Let me explain my situation by counting the rank $3$ case. Let $P=\{1,2,3\}$ ...
user avatar
  • 5,924
4 votes
1 answer
95 views

A recurrence for the number of non-crossing partitions without singletons, using Dyck paths

Let $f(n+1)$ be the number of non-crossing partitions without singletons of $\{1,2,\dots,n+1\}$. There is a well known bijection between the non crossing-partitions (counting also those with ...
user avatar
  • 1,111
3 votes
0 answers
125 views

Can you convert a packing with overlap to a packing without overlap?

There is a finite set $X$ of positive integers, and an integer $M$. A subset of $X$ is called packable if its sum is at most $M$. Suppose there are $2 n$ packable subsets of $X$, such that each ...
user avatar
-1 votes
1 answer
15 views

Is this Partition affirmation correct? [closed]

This is the sentence. If {$A_i$}$_i$$_∈$$_\mathbb{Z}$ is a partition of $\mathbb{R}$ then {$\sqrt{2}$} $⊆ A_i$ for one and only one value of $i$. I guess it's true, because each partition differs from ...
user avatar
-2 votes
1 answer
87 views

cardinality of the set of all partitions of N which contain only finite sets [closed]

Cardinality of the set of all partitions of N which contain only finite sets? My intuition tells me c would be the answer but don't know how to proof that.
user avatar
  • 7
0 votes
0 answers
23 views

How to check the following sets partition another set?

Suppose I have a sample space $S$. I would like to check that the events $A^{c} \cap B \cap C$ and $(A^{c} \cap B \cap C)^{c}$ partition $S$, i.e. that: 1.$(A^{c} \cap B \cap C) \cap (A^{c} \cap B \...
user avatar
  • 163
0 votes
1 answer
59 views

What is the operation through which a Coset is created?

Most books initially explain Cosets in terms of $\mathbb{Z}$ & then use the subgroup $n\mathbb{Z}$ to partition into $n$ Cosets. Is the group $\mathbb{Z}$ used here the additive $\mathbb{Z}^+$ or ...
user avatar
  • 359
0 votes
0 answers
26 views

1 dimensional object requires more than 2 cuts

Given a string, to break it into 2 pieces, one can simply cut it at any point. Given a loop, to break it into 2 pieces, there are two cuts needed, as the first cut will make it into a string and the ...
user avatar
  • 1,111
0 votes
0 answers
17 views

Inversions of a partition of a certain type

I am having trouble getting started on this problem as I'm not sure what partitions of type (2, 0, 3) refer to. I have been unable to research partitions of a "type" like this. Does anyone ...
user avatar
2 votes
1 answer
28 views

Minimum # of subsets in partition $\{2, 3, 4..., 2^n\}$ so that every subset contain only numbers that are not multiples of each other.

Example: if $X = \{2,3,4,...,16\}$ then, subsets are $A=\{2,3,5,7,11,13\}$ , $B=\{4,6,9,10,14,15\}$ , $C=\{8,12\}$ and D=$\{16\}$. I notice that for $2^n$ consecutive elements I'll have $n$ subsets ...
user avatar
  • 35
3 votes
1 answer
125 views

Confusion about a factor in a composition of series/Faa di Bruno formula

In the wikipedia article on the Faà di Bruno formula, one considers the composition of two "exponential/Taylor-like" series $\displaystyle f(x)=\sum_{n=1}^\infty {\frac{a_n}{n!}} x^n\; $ ($...
user avatar
  • 2,955
0 votes
1 answer
43 views

How to measure the information contained in a partition of set?

Is there any formal way to measure the information contained in a partition of set? Consider the case when $[n]$ is the full set. Intuitively, I would expect that the two extremal partitions $\{[n]\}$ ...
user avatar
  • 638
1 vote
2 answers
73 views

Can a symmetric, open, simply connected set in $\mathbb{R}^2$ be partitioned into two congruent sets?

Can an open, "symmetric" (in a non-rigorous sense), simply connected set $S$ in $\mathbb{R}^2$ be partitioned into two congruent sets? This sounds obvious (eg. for a circle, cut it in half) ...
user avatar
0 votes
1 answer
45 views

Inequality with Stirling numbers of second kind

I have to prove that, $\forall n\geq 1$, $\forall 1\leq k\leq n$, $$ \frac{k^{n}}{k^{k}}\leq S(n,k)\leq \frac{k^{n}}{k!} $$ The second inequality, is quite obvious for me, as $k!\cdot S(n,k)$ is the ...
user avatar
2 votes
1 answer
54 views

How many partitions $A_1,A_2,A_3$ are there of a set $S$, $|S| = 30$, and $|A_i| = 10$?

Let $S$ be a set with $|S| = 30$ and let $\pi = \{A_i\}_{i=1}^3$ be a partition of $S$ such that each set $A_i$ of $\pi$ has ten elements. How many such partitions $\pi$ are there? This questions ...
user avatar
  • 746
0 votes
1 answer
14 views

Compare partition based on minimum pairwise distance

Suppose I have a set of objects $X = \{ x_1, x_2, \cdots, x_n \} $ with some metric space defined $d: X \times X \to \mathbb{R}_+$. And i have is the gram matrix $G$ instead, $G \in \mathbb{R}^{n\...
user avatar
  • 1,111
1 vote
1 answer
34 views

How to relate the number of all applications $X\to Y$ with the Stirling numbers of the second kind?

I am studying Stirling numbers of the second kind, and I have just saw why $S(n,k)=\frac{1}{k!}\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$ (knowing that $\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{...
user avatar
1 vote
0 answers
41 views

partition of a vector space with the condition $x+y \neq z$ in any group

I find an equivalence for a linear algebra problem which seems not easy. Consider the vector space $$ \mathbb{Z}_2^n $$ for a natural number n. We want to partition $$ \mathbb{Z}_2^n \setminus\{(0,\...
user avatar
1 vote
0 answers
127 views

Prove the $\sigma$-algebra

I have a proposition in the textbook: Let $\Pi$ be a partition of a set $\Omega$. Then $\sigma(\Pi)$ consists of all countable unions of sets in $\Pi$ (including the empty set, which is the union of ...
user avatar
1 vote
2 answers
66 views

Does the (Stirling number of the second kind) equality ${2n\brace 2} = 2^{2n-1}-1$ hold?

I filled in from the definition of a Stirling number of the second kind that the following holds. $${2n\brace 2} = \frac{1}{2} \sum_{i=0}^{2} (-1)^i \binom{2}{i} (2-i)^{2n}$$ And I've visually ...
user avatar
  • 1,326
6 votes
2 answers
385 views

Arranging books in bookshelves with the capacity of each shelf given

I am struggling to solve the problem on Combinatorics: There are $k$ identical bookshelves in which each shelf cannot contain $m$ or more books. In how many ways can $n$ distinct books be arranged on ...
user avatar
  • 261
2 votes
1 answer
204 views

Given a set of both positive and negative numbers, what is a time optimal approach to find the two numbers whose sum, plus a third number is zero

Coming from an engineering background I want to solve this question. I have isolated two keywords, dynamic programming and number partitioning (number theory) and a reference to this hard problem I ...
user avatar
  • 163

1
2 3 4 5
14