2
votes
1answer
23 views

equivalence Relation problem with some conditions

If A be a set with $|A|=n$. if R be a equivalence Relation on A and $|R|=r$, why $r-n$ always be even ?
2
votes
1answer
33 views

Intuition for Euler's Partition Theorem

Euler's Partition Theorem states the following: Every number has as many integer partitions into odd parts as into distinct parts. I played around with small examples (I wrote out the partitions ...
0
votes
2answers
33 views

How to calculate the number of ways of partitioning n identical objects into r different groups such that each group has same number of objects?

I was solving the following problem, "Given a collection of 10 identical objects calculate the number of ways in which these objects can be partitioned into 2 groups of 6 and 4 objects each" - for ...
1
vote
0answers
44 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
3
votes
1answer
26 views

Partitioning a totally ordered set into three subsets according to the order

Consider a set $S$, and a total order $R$ over that set. Part (a) Given some element $e \in S$, explain why it is possible to partition $S$ into the following three sets: $$S_1 = \{ x \in S ...
0
votes
1answer
32 views

Partition induced by a Relation

Here's the problem: Let $A=\{1,2,3,4,5,6,7,8,9\}$. Define a relation $R$ on set $A$ by $xRy$ if and only if $2\mid(x+y)$ Assuming that $R$ is an equivalence relation, determine the partition of set ...
0
votes
2answers
43 views

Alternative reference for number of restricted partitions

I am looking for the number of partitions of some number $n$ into $k$ parts. Following the Wikipedia article on partitions, I ended up with Andrew's book [1]. Judging by Google's preview Chapter 3 ...
0
votes
1answer
145 views

Two different coins on a chessboard

Two different coins are placed on squares of a standard 8x8 chessboard; they may both be placed on the same square. Let us call two arrangements of these coins on the chess board equivalent if we can ...
1
vote
2answers
214 views

Partitions of a set into three parts

How many partitions of the set $\{1,2,3, \ldots , 100\}$ are there such that both a) there are exactly three parts and b) elements $1,2,3$ are in different parts. Any help on this question would ...
0
votes
1answer
38 views

Easy set partition problem

So I have this problem : Let A be a non empty set an P1 and P2 be two random partitions of the set A. Prove that the set is also a partition of A. I know that this is probably very easy to most of ...
1
vote
0answers
28 views

Finding equivalence relations containing specific equivalences

"Find the number of equivalence relations on the set $\{1,2,3,\ldots,7\}$ such that: a) $1\sim2$ and $3\sim4$. b) $1\not\sim2$, $1\not\sim3$ and $3\not\sim2$." Solving this problem is equivalent to ...
2
votes
0answers
86 views

Partitioning an n-set into k same-size subsets [duplicate]

"How many ways can you partition a set of size $n$ into $k$ parts of the same size?" I've tried solving in the following way but I'm not sure if it's correct, feedback would be appreciated. I'm new ...
1
vote
3answers
124 views

Existence of uncountable set of uncountable disjoint subsets of uncountable set

"Can you to any uncountably infinite set $M$ find an uncountably infinite family $F$ consisting of pairwise disjoint uncountably infinite subsets of $M$?" Intuitively, I feel like it should be ...
1
vote
1answer
92 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
0
votes
0answers
32 views

Need help with a Partitions question

For $m \in \mathbb{N}$, let $C_m = \{x \in R \mid m-1 \leq x^2 < m\}$. Is $\ell=\{C_m \mid m \in \mathbb{N}\}$ a partition of $\mathbb{R}$? If I understand it correctly, $C_m$ will always be a ...
2
votes
3answers
327 views

Prove that any partition induces a unique equivalence relation.

Given any partition $D$ of $A$, $\exists !$ equivalence relation on $A$ from which it is derived. Can someone please help me solve this problem? thanks.
38
votes
0answers
878 views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
11
votes
3answers
696 views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
1
vote
1answer
156 views

Generating functions of partition numbers

I don't understand at all why: \begin{equation} \sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1} \end{equation} Where $p_n$ is the number of partitions of $n$. Specifically ...
3
votes
2answers
99 views

Probability distribution of product of integers

I have a scoring system based on 5 factors with integer values from 1 to 5: Score = A * B * C * D * E So the Score can range from 1 to 3125. Each of the factors ...
2
votes
1answer
89 views

Conjugate Ferrers diagrams

Let $\pi=\langle \pi_1,\pi_2,... \rangle , \ \pi_1\ge\pi_2\ge...,$ be a partition of a number and $\pi'=\langle \pi_1',\pi_2',... \rangle$ be a partition conjugated to $\pi$, which means that ...
3
votes
3answers
2k views

Number of equivalence relations on a finite set

I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible ...
2
votes
0answers
40 views

How to prove some properties of partitions of finite subsets of N? [duplicate]

Possible Duplicate: Any partition of {1,2,..,9} must contain a 3-Term Arithmetic Progression The problem is as such: Prove that there is not a partition of $N_9 = \{1, 2, 3, 4, 5, 6, 7, ...
1
vote
2answers
1k views

Equivalence Relations and Partitions

My university "textbook" for discrete math is Schaum's Outline. In this outline he goes over Equivalence Relations and Partitions, and I got confused at a particular theorem. From the book: Theorem ...
2
votes
4answers
436 views

Two hard number partition problems

For every positive integer $n$, let $p(n)$ denote the number of ways to express $n$ as a sum of positive integers. For instance, $p(4)=5$. Also define $p(0)=1.$ Problem 1. Prove that ...
1
vote
1answer
209 views

Two number partition problems

Let $p_k(n)$ be a number of ways to express $n$ as a sum of $k$ positive integers. For example $p_2(3)=1$. Problem 1. Prove that following recurrences are correct: ...
-2
votes
1answer
315 views

Generation of unique-sum sets

I've been beating around the bush for a long time, ever since I've been in StackExchange. Now, I really must come to the point. I have a link here that you people can see (go to about the end of the ...
1
vote
1answer
255 views

How do I approach this combinatorics problem about composition?

The question is from Bogart's A composition of the integer k into n parts is a list of n positive integers that add to k. How many compositions are there of an integer k into n parts. To ...
1
vote
1answer
388 views

Partition function without repetitions of parts and largest part $k$

Um, well, I think the title pretty much says it all. Nevertheless, allow me to explain. I am aware of a certain partition function $Q(n, k)$ that is supposed to remove duplication of parts and $k$ ...
1
vote
2answers
225 views

Number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s

How do I find the number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s? I think the title is self-explanatory. E.g., if I have to represent $13$ as a sum of only ...
3
votes
2answers
111 views

Generating sequences of numeric partitions

Definition: A tuple $\lambda = (\lambda_1, \ldots, \lambda_k)$ of natural numbers is called a numeric partition of $n$ if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + ...
0
votes
3answers
392 views

Partition an integer $n$ by limitation on size of the partition

According to my previous question, is there any idea about how I can count those decompositions with exactly $i$ members? for example there are $\lfloor \frac{n}{2} \rfloor$ for decompositions of $n$ ...
1
vote
3answers
212 views

Decomposition by subtraction

In how many ways one can decompose an integer $n$ to smaller integers at least 3? for example 13 has the following decompositions: \begin{gather*} 13\\ 3,10\\ 4,9\\ 5,8\\ 6,7\\ 3,3,7\\ 3,4,6\\ ...