Questions related to the different ways of expressing an integer as a sum of integers; or, questions related to the subdivision of a set into smaller disjoint sets; questions related to the subdivision of an interval into smaller intervals that intersect only at the endpoints.

learn more… | top users | synonyms

8
votes
4answers
4k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
3
votes
3answers
34 views

Help with partitions, equivalence classes, equivalence relations.

The following definitions and results are from my textbook. A partition $\mathcal{P}$ of a set $X$ is a collection of nonempty sets $X_1, X_2, \dots$ such that $X_1 \cap X_j = \emptyset$ for $i ...
3
votes
4answers
42 views

Into how many equivalences classes does $R$ partition $\mathbb{Z}$?

Let $R= \{ (a,b) \in\mathbb{Z}\times\mathbb{Z} \mid a^2\equiv b^2 \bmod 7\}$. Into how many equivalences classes does $R$ partition $\mathbb{Z}$? My best guess is that there are $7$ equivalence ...
1
vote
1answer
20 views

Tool for the partition problem with planar rectangles

The classical "partition problem" asks how many ways one can write a given natural number as a sum of smaller numbers. One variant of this would be to ask if a positive real number can be expressed ...
2
votes
0answers
14 views

Wireless networks on two sequential office floors: Random partitions of a finite interval via a point process on a line

Construct a Poisson point process of density one on a line of length $L$. Allow each point in the process to "see" part of the line to their left, and part of the line the their right (such that the ...
0
votes
0answers
41 views

partitions and generating functions ( combinatorics ) [closed]

Given partition into distinct parts, let’s say the the ODD parts are: the biggest part, the $3$-rd biggest part, the $5$-th biggest part, etc.; and the EVEN parts are: the $2$-ne biggest part, the ...
0
votes
1answer
9 views

Proving $F . G$ is the greatest lower bound

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
-1
votes
1answer
85 views

partitions of the number n

I'm having difficult with the following question : show that the number of partitions of n into parts of size 3,5,7,9,... equals to the number of partitions of n into different parts which are not ...
1
vote
0answers
45 views

Finite partitions of $\mathbb{N}$ and relations betweens sets of natural numbers

Suppose that $R\subseteq \mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})$ is a relation such that $(x,y)\in R$ only if $|x|=|y|$. Say that a partition $P$ divides a set $x$ if $x$ is the union ...
1
vote
1answer
22 views

Prove that $R$ is anti-symmetric

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
0
votes
1answer
42 views

Coin Change Problem with Fixed Coins

Problem: Given $n$ coin denominations, with $c_1<c_2<c_3<\cdots<c_{n}$ being positive integer numbers, and a number $X$, we want to know whether the number $X$ can be changed by $N$ coins. ...
1
vote
0answers
24 views

Generating function for writing an even number as a sum of at most k squares

I would like to find the exact number of ways in which $n$ can be represented as a sum of at most $k$ squares such that each term is less than or equal to say, $N$. A generating function for this ...
0
votes
1answer
30 views

NP-complete proof of subset with sum zero

I'm trying to proof that a problem of subset from a group has a sum of zero. I know that i can use the partition problem that is known to be NP-complete, but i can't seems to find what i need to ...
4
votes
0answers
112 views

On Applications of the Murnaghan-Nakayama rule

The question is located below. In short, I am looking for an accessible explanation of the Murnaghan-Nakayama rule in relation to the following problem. Pardon the long setup. Let $Y$ be a standard ...
1
vote
2answers
90 views

Partitioning $[0,1]$ into pairwise disjoint nondegenerate closed intervals

My friend threw me a challenge. He told me that he proved the follow proposition: The topological space $[0,1]$ cannot be partitioned into pairwise disjoint nondegenerate closed intervals (except ...
1
vote
1answer
24 views

What is the name of the transform which finds the number of ways to make partitions of the given sizes?

I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
13
votes
5answers
463 views

How solutions of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?

How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$. For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. ...
15
votes
2answers
285 views

A question on partitions of n

Let $P$ be the set of partitions of $n$. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : ...
2
votes
0answers
38 views

Which are partitions are for $\mathbb{Z}$? Which are covers for $\mathbb{Z}$? Which are both or neither?

(a) {{x : x is an even integer}, {x : x is an odd integer}} (b) {{x : x is an even integer}, {x : x is divisible by 3}} Note - divisible by 3 includes negative integers, yes? -3, -6, -9, ... and ...
17
votes
0answers
389 views

Visualizing the Partition numbers (suggestions for visualization techniques)

So Ken Ono says that the partition numbers behave like fractals, in which case I'd like to try to find an appropriately illuminating way of visualizing them. But I'm sort of stuck at the moment, so ...
5
votes
0answers
114 views

Sum over subsets of a multiset

I have a sum that looks like the following for some multiset $S$ and some function $f$ of $n$ variables which does not depend on the ordering of its arguments: $$\sum_{\{k_1,\dots, k_n\}\subset ...
4
votes
2answers
532 views

Counting integer partitions of n into exactly k distinct parts size at most M

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
2
votes
1answer
27 views

Can someone present a visualization of the partitioning of a $L^p$ space into equivalent classes?

I am a bit confused by what it means for a $L^p$ space to be partitioned into equivalent classes instead of functions. I understand that give two or more functions $f$, $g$, $h,\ldots$ of which are ...
16
votes
1answer
374 views

On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since $4=1+1+1+1=1+1+2=1+3=2+2=4.$ Prove ...
0
votes
0answers
17 views

Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? [duplicate]

Question: Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? Someone comes along and gives us the partition $P=\{2,2,3,3,4\}$ of $14$. How can we ...
18
votes
0answers
300 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
2
votes
1answer
121 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
0
votes
0answers
61 views

What is wrong with my proof by exhaustion?

$n$ colored balls are placed in an urn, with $c$ colors such that there are an equal number of balls of each color. What is the expected number of distinct colors in $k$ randomly picked balls, ...
0
votes
0answers
13 views

k-way graph partitioning with bounded size constraint

A typical $k$-way graph partitioning problem is to partition a weighted graph into $k$ components, with the constraint that all $k$ components have the same size. However, if we drop the same size ...
2
votes
4answers
54 views

What is a simple example that shows equivalence classes constitute a partition?

Can someone illustrate using a simple concrete example that the equivalence classes defined by $\sim$ constitute a partition of a set $A$?
1
vote
1answer
22 views

Prove that family of sets generates partition

Let $X$ be any set. Let $\mathcal{F}$ be family of subsets of $X$ closed under aritrary intersections and complements. Let $P(x)=\bigcap \{A\in\mathcal{F}:x\in A\}$. I need to prove that family ...
3
votes
2answers
113 views

A curious partitions coincidence $\sum_{n=0}^\infty P(n) q^{n+1}$?

Given the partition function $P(n)$ and let $q_k=e^{-k\pi/5}$. What is the reason why, $$\sum_{n=0}^\infty P(n) q_2^{n+1}\approx\frac{1}{\sqrt{5}}\tag{1}$$ $$\sum_{n=0}^\infty P(n) ...
1
vote
1answer
24 views

Writing a Sum of Partition Items in Combinatorial Form

For each partition $\lambda$ we can define \begin{equation} n(\lambda) = \sum_{i \geq 1}(i-1)\lambda_i. \end{equation} According to my book this is equivalent to \begin{equation} n(\lambda)=\sum_{i ...
1
vote
0answers
32 views

Why does the number of ways that $n$ can be summed with at least one $1$ equal the partition function for $n-1$?

For some reason I was counting the number of partitions of $n$ that have at least one $1$ as an addend. The beginning sequence for these numbers, starting with $n=1$, is $\{1, 1, 2, 3, 5, 7, 11, 15, ...
2
votes
0answers
116 views

Partition counting problem with cap on pairwise intersection

Fix $T_1,\ldots T_m$ as pair-wise disjoint $k$-subsets of $\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. For any $j\le k$, how many sets of the form $\{C_1,\ldots,C_m\}$ are ...
1
vote
0answers
37 views

Partition Function Breakdown

Let $g(n,k)$ be the number of partitions of $n$ into exactly $k$ parts, in which no part is a $1$. Show that $$g(n,k) = g(n-2,k-1) + g(n-k,k).$$ How would I show this?
6
votes
1answer
4k views

The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
3
votes
1answer
44 views

How to measure similarity of partitions / partitioning?

Suppose a set of elements of finite size. E.g.: $X = \left\lbrace a,b,c,d,e,f,g \right\rbrace$ There are several ways to partition $X$. E.g: $P_1 = \left\lbrace \left\lbrace a,b \right\rbrace, ...
0
votes
1answer
30 views

Counting functions and stirling numbers

Let S= { f | f: A $\rightarrow$ B, |Image(f)|=k}. |A|=m, |B|=n. where k $ \le n, k \le m $ |S|=$ {n \choose k} $ S(m,k) k!. where S(m,k) are the striling numbers of the second kind. What I can't ...
0
votes
0answers
11 views

Decomposition of a Set System into Distributive Lattices

I would like to decompose an arbitrary set system $S$ over a universe $U$ into a number of distributive lattices such that these lattices partition $S$. Now, I am interested in the least number of ...
5
votes
1answer
99 views

What is the 'optimal' equal-area partition of a circle?

What is the (an?) n-partition of a circle that meets the following criteria: The boundaries of each partition can be represented as a union of finitely many finite-piecewise-smooth simple closed ...
3
votes
1answer
46 views

Integer Partitions and distinguishable permutations

I'm not a mathematician but I'm faced with a problem where I can't find an answer, also because I do not know what I shall ask for: I have to deal with partitions of an integer k, only small values, ...
0
votes
2answers
25 views

Partition and Equivalence Relation: In $\mathbb{Z}$, let $m\sim n$ iff $m - n$ is a multiple of 10

Prof. Pinter's "A Book of Abstract Algebra" presents this exercise: Prove that each of the following is an equivalence relation on the indicated set. Then, describe the partition associated with ...
0
votes
1answer
35 views

Minimum number of partitions of a set given list of numbers that can't appear in the same partition

I wish to calculate the minimum number of partitions of a set required given a list of pairs of numbers that cannot appear together in the same partition. Example 1: $$S = [1,2,3,4,5,6]\\[5pt] ...
1
vote
1answer
73 views

intersection of stabilizers of block systems

Lets assume the following situation: $G$ acts regularly on a set $M$. Then there is a bijection between the set of subgroups and the set of blocks containing a fixed element $m \in M$. The blocks ...
1
vote
1answer
66 views

Facing problem to understand the equivalence class concept.

Currently I am trying to understand the equivalence class from the Herstein's book. And I am facing problem to understand the concept and also can't understand the theorem given in the page number 8. ...
1
vote
2answers
480 views

Equivalence relation and equivalence class

I have looked around the internet for an easy to approach - down to earth explanation of equivalence relation & equivalence class but having no success. If any of you can explain in very basic ...
0
votes
1answer
22 views

Meaning of notation $\{x,y\}\subset A$ in a partition

I recently came across this notation: $$\{x,y\}\subset A$$ Where $A\in \mathbb{A}$, and $\mathbb{A}$ is a partition of a non-empty set X. Does it mean that $x,y\in A$? Isn't $A$ a set of elements and ...
0
votes
3answers
36 views

Prove $A_r$ is a Partition

Dr. Pinter's "A Book of Abstract Algebra" presents the following exercise: Prove that each of the following is a partition of the indicated set. Then describe the equivalence relation ...
2
votes
4answers
71 views

Proof of theorem about equivalence classes

I am looking to understand the following theorem, and I am also wondering what is meant by "mutually disjoint", or at least how it's to be understood in the following context: The distinct ...