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
1
vote
0answers
36 views

The sets of all equivalence relations and of all partitions does not exist

Statement The sets of all equivalence relations and of all partitions does not exist. Proof. First of all we observe that the idetity relations $\text{Id}$ is an equivalence relations for ...
0
votes
1answer
41 views

Divide people to several groups

In how many ways can five people be divided into several groups? (Number of member can be 1 to 5) One person can't be in two groups at the same time. Also, everyone have to join any groups. I ...
1
vote
0answers
62 views

White/black toys are placed into boxes. %75 has high white chance (rest black). Majority of boxes have white>black toys probability more than 1/2?

I am an economic theorist working on deterministic models almost exclusively. I have an undergrad degree in mathematics and as a hobby (due to time constraints, not as much as I would like to) I try ...
1
vote
1answer
33 views

Counting the number of rows that has repeated elements in the columns

Suppose the following list: $$ \begin{matrix} j_1 & j_2 & j_3 & j_4\\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 3 \\ 1 & 1 & 2 & 1 \\ 1 &...
3
votes
1answer
90 views

Entropy of partitioning for set of all $\binom{n}{k}$ combinations

Let $\binom{[n]}{k}$ represent the set of all $k$-combinations of the set $[n]=\{1,\dotsc,n\}$. We will use the notation: $$\{x_1, \dotsc, x_k\} \in \binom{[n]}{k},$$ where $x_1 < x_2, < \dotsc ...
0
votes
0answers
19 views

Proof Check of this Maximum Principle using The Notion of Gauges and Tagged Partitions

This theorem is well known, but i wonder of the following proof works or not. I doubr that its so easy. Theorem :Suppose $S$ is compact. If $f : S \to \mathbb R$ is continuous on $S$ then $f$ attains ...
0
votes
1answer
22 views

Assume the function $f: \mathbb R^2 \rightarrow \mathbb R$ satisfies the property $f(x+s,y+t) \geq f(x,y) -s^2-t^2$

Assume the function $f: \mathbb R^2 \rightarrow \mathbb R$ satisfies the property $f(x+s,y+t) \geq f(x,y) -s^2-t^2$ for every $(x,y) \in \mathbb R^2$ and every $(s,t) \in \mathbb R^2$. Prove that $f$ ...
0
votes
1answer
18 views

How many way to partition a set of n number into k subsets (empty subset is allowed)

I am working on finding the upper bound iterations of k-means algorithm. Many research show that the trivial upper bound is $O(k^n)$ since it can be shown that no clustering occurs twice during the ...
0
votes
1answer
15 views

Is this definition for partitions in analysis correct?

I think of this new definition - Suppose $X$ is a bounded interval. A Partition $\mathbb P$ of $X$ is the set $S= \{S_1,S_2,S_3,...,S_n\}$ such that $S_i \subseteq X ~ \forall i$ such that $1\leq ...
-2
votes
1answer
16 views

Set of finite partitions of the unit interval [closed]

Is the set of partitions of a given length, say $n$, of the unit interval compact?
5
votes
1answer
49 views

Number of elements of permutation group

Let $G$ be a permutation group of a set $X\neq \emptyset$ and let $x,y\in X$. We define: \begin{align*}&G_x:=\{g\in G\mid g(x)=x\} \\ &G_{x\rightarrow y}:=\{g\in G\mid g(x)=y\} \\ &B:=\{y\...
0
votes
0answers
29 views

Find all combinations of numbers from {x1,x2,…,xn} that sum of to sum S

Given a list of some integers, I would like to find every combination that can be summed to some sum S. For example for the sum S=16, and the list of integers I={3,4,5}, I'd expect to get: 5,4,4,3 (=...
3
votes
1answer
134 views

A certain composition into the elementary symmetric polynomials

Preliminaries Let $\mathbb{F}$ be a field such that $\operatorname{char}(\mathbb{F})\neq2$. Let $n$ be a non-zero natural number. Let $\mathbb{F}\left[x_1,x_2,\ldots,x_n \right]$ be a polynomial ...
1
vote
1answer
21 views

Set partition graph

We define set partition graph as follows: Consider a set $\{1,2,..,n\}$ where $n\geq2$, the vertices in our graph are all the set of partition of $\{1,2,..,n\}$. Now, two vertices $V$ and $V'$ ...
2
votes
1answer
29 views

2-split of $n$ is $\left\{ \lfloor \frac{n}{2} \rfloor,\lceil \frac{n}{2} \rceil \right\}$. What about 3, 4, …?

Clarification: $k$-split of $n$ is an ordered integer sequence $\left\{ a_1,\cdots,a_k \right\}\quad \text{s.t.}$ $0\le a_1\le\cdots\le a_k$ $a_1+\cdots+a_k=n$ ${\left(a_k-a_1\right)}$ is minimized. ...
1
vote
1answer
30 views

Meaning of the “greater than” operator when using sets

Consider the following construction, $$\sum_{\rho'\in\mathcal{P}(n), \rho'>\rho} f(\rho)$$ where $\rho$ and $\rho'$ are partitions of the set $\{1,2,\dots,n\}$ and $\mathcal{P}(n)$ is the set of ...
0
votes
0answers
19 views

Partition a set into two subset that maximize sum of sum of squares over sum

Given a multiset of positive integers $S$ . Is there any efficient algo to partition it into two subsets $S_l , S_r$ where $\frac{\sum_{i \in S_l} i^2}{\sum_{i \in S_l} i} + \frac{\sum_{j \in S_r} j^...
0
votes
1answer
31 views

How to partition the numbers 1 to $𝑘^2$ into 𝑘 subsets of equal cardinality and equal sum

I came across this question: A farmer has 25 cows. These are numbered 1 to 25, and i-th cow gives i litres of milk. The farmer has 5 sons. How should he divide his cows among his sons such that ...
2
votes
0answers
28 views

Learning Optimal Partitions

Let $f,f_i:[0,1]^d\rightarrow \mathbb{R}^k$ be continuous functions. Suppose that there are regions $\Omega_i \subset [0,1]^d$ (Compact) such that $f=\sum_i f_i 1_{\Omega_i}$. Is there a learning ...
6
votes
0answers
69 views

Partitioning a Cartesian Product Yields Sierpiński Triangle… ish?

I wanted to find an efficient method to partition a Cartesian product of $n$ sets $S_i$ of varying sizes into maximum size subsets that are defined by all tuples in the partition differing in at ...
0
votes
1answer
16 views

Enumerable partition set $C/R$

Let $C=\{z\in\mathbb{C}:|z|=1\}$ and let $R$ be an equivalence relation such that $zRw$ if $\exists n\ge1$ such that $z^n=w^n$. Is $C/R$ enumerable? I found that C is not enumerable because it is in ...
0
votes
0answers
25 views

Combinatorics, Permutations, Sets, Cards, Partitions and more…?

So I have this problem, and I simply cannot find anything that helps me solve it. It's kind of similar to "Twelvefold Way" but not quite. Lets say you have 100 cards. Of these 10 cards have the ...
1
vote
1answer
49 views

Given a set of $n$ elements, how many partitions in $k $ subsets have at least size $x$.

How do you do fellow Stackers, recently I've beeen studying combinatorics and surprise surprise, failing at it. My questions is probably pretty simple, in fact, it can be considered a duplicate of [...
0
votes
2answers
24 views

A specific partition of the interval $[1,n]$ of $\mathbb{N}$

Let $n>0$. I would like to partition the interval $[1,n]$ of $\mathbb{N}$ in a specific manner. For example, if $n=6$, the partition I want is $$[1,2]\cup[3,4]\cup[5,6].$$ Is there a general way to ...
1
vote
0answers
28 views

Computing an average of many sums by dynamic programming (?)

Let $N$ be a large integer, let $x_1, \ldots, x_{2N}$ be a subset of some space $\mathcal{X}$ (the details of which are irrelevant), and let $f, g, h$ be functions mapping $\mathcal{X}$ to $(0, \infty)...
0
votes
1answer
30 views

Understanding A Short Proof on Integrable Functions

Let Q be a rectangle in En and assume that f : Q → E is integrable. (a) Show that if f(x) ≥ 0, for all x ∈ Q, then $\int Q f ≥ 0.$ (b) Show that if f(x) > 0 for all x ∈ Q, then $\int Q f > 0.$ ...
-1
votes
1answer
27 views

Sum and product of 2 partitions of a set

There was this question in my Discrete Maths exam: Let S={1,2,3,4,5,6}. 2 partitions P1 and P2 are given as: P1={(1,2,3),(4,6),(5)} P2={(1,2),(3,4,5),(6)} Define and find the sum and product of ...
0
votes
0answers
30 views

Number of contiguous set partitions of $\{1,\dots,N\}$ is same as number of ordered arithmetic partitions of $N$? (Because of stars and bars?)

Note: This question is more of a sanity check than anything, and is probably a duplicate, so if you find the original question (I was unable to), please link to it and close this question. Question:...
0
votes
1answer
23 views

Notation for a size of a partitioning and mapping between set elements and partitions?

Consider a infinite set of continuous numbers $A$. Now, I partition the set in N subsets $A_0, A_1, \cdots, A_N$. Thus, $A = \bigcup_{i=0}^N A_i$ and $\bigcap_{i=0}^N A_i = \emptyset$. We can say that ...
0
votes
0answers
71 views

Simple cooperative games

In the snippet below, I do not understand what is the set of players in $N$ that form ${}_{i}A.$ They say: We think of ${}_{i}A$ as the set of those voters of $N$ who vote approval level $i$ for ...
0
votes
1answer
25 views

Exercise on refinement of a cover

For any cover $\cal{U}$ of a topological space $X$ there is a finest partition $P(\cal{U})$ refined by $\cal{U}$. Each element of $\cal{U}$ is contained in a unique element of $P(\cal{U})$. Willard, ...
3
votes
1answer
103 views

Say a finite set $M$ has two partition $A_1,A_2,…A_p$ and $B_1,B_2,…B_p$ such that …

Say a finite set $M$ has two partitions $A_1,A_2,...A_p$ and $B_1,B_2,...B_p$ such that $$A_i\cap B_j = \emptyset \implies |A_i|+|B_j|\geq p.$$ Prove: $$|M|\geq {1\over 2}(p^2+1).$$ As far as I can ...
0
votes
0answers
16 views

Constructing a partition of a finite nonempty set from a partition of its cardinality

Let $E$ be finite nonempty set of cardinality $n$. Let $(k_i)_{i\in I}$ be a finite family of integers $>0$ such that $$\sum_{i\in I} k_i=n.$$ Since $|E|=n$, there exists a bijection $x:[1,n]\...
2
votes
1answer
55 views

On day 1, Adam can take 1 walk, on day 2 he can take 2 (so on until day n), how many ways can he take 3 walks?

I'm trying to solve this question, but I'm not quite there and need some help. Question: Adam has just recovered from a serious leg injury and is encouraged to walk to aid his recovery. On day 1, he ...
4
votes
1answer
38 views

Dividing 12 people into any number of groups, such that person A and B are not in the same group?

In how many ways can you divide 12 people into any number of groups, such that person A and B are not in the same group? I am trying to solve this question and so far I am thinking of this in terms ...
2
votes
1answer
24 views

Is it required that singletons of a finite decomposition be closed in order for it to be upper semicontinuous?

In Willard's "General Topology", exercise 9E (p67 of the Dover edition), he writes: A decomposition $\mathscr{D}$ of a space $X$ will be called finite iff only finitely many elements of $\mathscr{D}...
0
votes
2answers
26 views

Need help in dividing a set into different pairs

In how many ways can you divide the set of eight numbers {2,3,4,5,6,7,8,9} into 4 pairs such that no pair of numbers has G.C.D equal to 2?
1
vote
1answer
37 views

What is the reasoning behind Stirling number $S(n,2)$?

The answer that was given in class was $(2^n -2)/2$. I think it's trying to use the theorem that the number of $k$-digit strings that can be formed over $n$ element set is $n^k$. Or, I think it ...
2
votes
1answer
38 views

What is the difference between these two theorems?

From Rosen's Discrete Mathematics and Its Applications, 3ed, chapter 6 p. 428-429: It seems to me that both of them are talking about partitioning a set of n ...
0
votes
1answer
69 views

Notation for partitions of sets

Given the wikipedia definition of partition of a set: A partition of a set $X$ is a set of non-empty subsets of $X$ such that every element $x$ in $X$ is in exactly one of these subsets (i.e., $X$...
0
votes
1answer
35 views

Non-crossing partitions on a line

If I have $n$ posts in the ground, arranged in a horizontal line, how many distinguishable placements of rings are there over the posts, where: The $i$th ring encloses $k_i$ posts. There are exactly $...
1
vote
0answers
44 views

finer/coarser relation

Given a set $S=\left\{1,2,3\right\}$ and two equivalence relations $\sim_B$ and $\sim_A$ on $S$, such that, $\sim_A$ is defined as : $$\sim_A=\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),...
1
vote
1answer
31 views

Writing an equivalence relation defined on $ℚ$.

I need to write a equivalence relation defined on $ℚ$ to partition it on two equivalent classes. I think the best way is to split it on negative and non-negative numbers. $A = \{ \frac{m}{n}∣ m,n ∈ ...
4
votes
4answers
335 views

What does “relation induced by a partition” mean?

The question is: What is the equivalence relation R, induced by the partition P of A? (A, P are given) I don't get what "induced by" means.
0
votes
4answers
43 views

Equality of equivalence relations that partition the same set.

Let $A$ be a set and suppose that $R$ and $R'$ are two equivalence relations in $A$ that induce the same partition $\mathcal{P}$. Prove that $R=R'$. I am not sure how to start but I want to believe ...
0
votes
0answers
43 views

Set Partition , approximation, optimal solution --need help in designing algorithm and writing its psedocode in latex

Let S = {S1, . . . , Sn} be a set of sets of integers, e.g. S = {{1, 3}, {2, 4}, {3, 4}, {2, 5}}. We say that D = {D1, . . . , Dk} is a partition of S if the following conditions hold. • Di ⊆ S for ...
2
votes
1answer
119 views

Formula for computing the coefficients of Bell polynomial

I'm working on Bell polynomials and have learned some of its properties, but I've never seen any formula for calculating the coefficient in Bell polynomials. My trying to find these coefficients was ...
1
vote
1answer
96 views

Exponential generating function of the partition set

Let $P_n$ be the partitions set of $[n]$ . Let $f: P_n \to N_0$ be a statistic that suits for each block/class, the number of the block/class that contains the maximum number $n$. Write a recurrence ...
0
votes
1answer
26 views

Prove $P_{n,n-i} = P_{n+1,n-i+1}$

Let $i,n \in \mathbb{N}$ with $n \geq 2i$. In our combinatorics script it is written that for the number of different, random partitions it holds that $$P_{n,n-i} = P_{n+1,n-i+1}$$ But how can one ...
-1
votes
1answer
113 views

I can not find out a formula for this :

Between 1 and 45, (and included, 1 and 45) ; How many --5 set combinations-- are there from 1 to 45 with a total of 155? *What are these combinations ? (PS: each number can only be written once ) ...

1
2 3 4 5
10