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

3
votes
3answers
665 views

Further clarification needed on proof invovling generating functions and partitions (or alternative proof)

Show with generating functions that every positive integer can be written as a unique sum of distinct powers of $2$. There are 2 parts to the proof that I don't understand. I will point them out ...
2
votes
1answer
73 views

Question about partition of open sets in $\mathbb{R^n}$

I have to prove that any open set $U \subset \mathbb{R^n}$ is a countable union of disjoint limited rectangles. I proved that it is a countable union of rectangles, the "expected classical" way, I ...
5
votes
3answers
6k 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 ...
1
vote
4answers
3k views

How many solutions does the equation $x_1 + x_2 + x_3 = 11$ have, where $x_1, x_2, x_3$ are nonnegative integers?

Help me understand problems of this type a bit more intuitively. The solution $C(3+11−1,11)$ seems simple enough, but I got stuck thinking about how many integers you are choosing from within $x_1$, ...
8
votes
1answer
131 views

Characters of the symmetric group corresponding to partitions into two parts

Let $n\in\mathbb N$ be a natural number and $\lambda=(a,b)\vdash n$ a partition of $n$ into two parts, i.e. $a\ge b$ and $a+b=n$. In this special case, is there a simple description of the character ...
2
votes
1answer
1k views

Finding a generating-function using partitions

Find a generating function for a , the number of partitions of r into (a.) Even integers (b.) Distinct odd integers. I am at a loss of starting this.
0
votes
1answer
92 views

How to find random numbers that can sum up to n?

I have a random integer $n$ and another integer called the summary. I want to know how many ways I can sum a subset of numbers from $1$ to $n$ to produce the value of summary. For example, I have ...
5
votes
2answers
104 views

Partition Bijection

I'm not sure what I'm missing. I think I'm thinking too hard about finding this bijection. Please help!
1
vote
2answers
114 views

Sum of $\prod 1/n_i$ where $n_1,\ldots,n_k$ are divisions of $m$ into $k$ parts.

Fix $m$ and $k$ natural numbers. Let $A_{m,k}$ be the set of all partitions divisions of $m$ into $k$ parts. That is: $$A_{m,k} = \left\{ (n_1,\ldots,n_k) : n_i >0, \sum_{i=1}^k n_i = m \right\} ...
3
votes
2answers
957 views

Number of partitions of $n$ with $k$ parts equals the number of partitions of $n + \binom k {2}$

How do I prove bijectively The number of partitions of $n$ with $k$ parts equals the number of partitions of $n + \binom k {2}$ with $k$ distinct parts
4
votes
2answers
93 views

Partition bijections

How do I prove bijectively that the number of partitions of n with largest part k equals the number of partitions of n with exactly k parts.
5
votes
1answer
826 views

Bijective Proof: Number of Partitions of 2n into n parts

The number of partitions of n is equal to the # of the partitions of 2n divided into n parts. I know that the number of partitions of any integer n into i parts equals the number of partitions of n ...
3
votes
1answer
1k views

Partition an integer $n$ into exactly $k$ distinct parts

I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. ...
2
votes
2answers
1k views

common knowledge and concept of coarsening partition

Here is a proof of the equivalence between my definition and Aumann's for "common knowledge". I'm assuming some familiarity with set partitions. Aumann's definition is in terms of the ...
0
votes
2answers
337 views

Get all possible partitions of number

Is there a way to get all possible partitions of an integer? Possibly specifying max and/or min summand. I'm interested in partitions themselves, not just partition count.
6
votes
1answer
197 views

Formula for evaluation of character on a transposition

Let $\lambda\vdash n$ be a partition of $n\in\mathbb N$ and $\chi=\chi_\lambda$ the corresponding irreducible character of the symmetric group $S_n$. Denote by $\lambda^t$ be the transpose of ...
3
votes
1answer
94 views

Finite Partitions of the Unit Interval

Does the unit interval have a finite partition $P$ such that no element of $P$ contains an open interval? I would think that the answer is no, because each element of $P$ would have Lebesgue measure ...
1
vote
2answers
231 views

Integer solutions

How many positive integer solutions are there to $x_1 + x_2 + x_3 + x_4 < 100$? I haven't seen any problems with "less than", so I'm a bit thrown off. I'm not sure if my answer is correct, but ...
5
votes
2answers
184 views

Congruent division of a shape in euclidean plane

Any triangle can be divided into 4 congruent shapes: http://www.math.missouri.edu/~evanslc/Polymath/WebpageFigure2.png An equilateral triangle can be divided into 3 congruent shapes. Questions: ...
0
votes
1answer
54 views

Is this a valid partition?

Say we have the $S$ which is the set of all compositions of n >= 0 with an odd num. parts. Define $S_1$ to be the set of all compositions of n >= 0 with an odd num. of parts where at least one part ...
1
vote
1answer
137 views

Question on lower & upper Riemann sums for piecewise.

Partition{$\frac{-\pi}{6},3,2\pi$} $f(x)= 1/2$ if x is rational $sin(x)$ if x is irrational. Im not sure if im doing it correctly: ...
2
votes
0answers
107 views

What is the correct technical term for this generalization of an integer partition?

Given a vector $v$ with non-negative integer coordinates, is there a technical term for an unordered tuple of vectors $(v_1,\dots, v_k)$ with non-negative integer coordinates such that $v_1+\dots+v_k ...
4
votes
2answers
847 views

Partitions and Bell numbers

Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks. Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$ Find a formula for ...
0
votes
1answer
145 views

Partitions of $n$ into $k$ blocks, without single blocks.

So I'm trying to come up with a recursive formula $f(n)$ which counts the number of all partitions of $[n]$ into $k$ identical blocks, where the number of elements in each box is more than 1. What ...
2
votes
0answers
169 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where ...
4
votes
7answers
551 views

Book recommendation for Integer partitions and q series

I have been studying number theory for a little while now, and I would like to learn about integer partitions and q series, but I have never studied anything in the field of combinatorics, so are ...
4
votes
0answers
137 views

A general Combinatorics problem (Coefficients of the q factorial)

I was solving a combinatorics problem when I encountered difficulties. The problem was: $x_1 \in \{0,1\}$ $x_2 \in \{0,1,2\}$ . . $x_{n-1}\in\{0,1,2..,n-1\}$ We have to find the number of ways ...
4
votes
0answers
116 views

Why limit Euler's Partition function P to $k\leq\sqrt n$ instead of $k\leq n$?

I solved a Project Euler problem (I won't say which one) involving the Partition Function P. I used equation #11 from the above link: $$P(n) = \sum_{k=1}^n (-1)^{k+1}\bigg(P\Big(n-{1\over ...
3
votes
2answers
781 views

Equivalence relations on natural numbers

How many equivalence relations are there on $\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers? How can one compute it?
2
votes
0answers
41 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, ...
5
votes
1answer
109 views

Elementary proof of a bound on the order of the partition function

I am interested in the asymptotic order of the partition function $p(n)$. The paper Asymptotic Formulae in Combinatory Analysis proves there are constants $A$,$B$ such that $e^{A\sqrt{n}} < p(n) ...
2
votes
1answer
429 views

How do I implement an induction argument to show that we may assume that a partition $Q$ of $[a,b]\in{R}$ which refines $P$ has only one more point?

There is a lemma (32.2) in Kenneth A. Ross's Elementary Analysis text, that states: Let $f$ be a bounded function on $[a,b]$. If $P$ and $Q$ are partitions of $[a,b]$ and $P\subseteq{Q}$, then ...
7
votes
0answers
359 views

Young Tableaux as Matrices

These questions are motivated only by curiosity. Take a Young tableau of shape $(\lambda_1,\lambda_2,\ldots,\lambda_n)$, where $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Is there any ...
1
vote
1answer
1k views

Ways to partition an n-element set

I've done a couple of searches and haven't found a solution to this here, but if I've missed it please feel free to close the question! I was wondering how many different equivalence relations I ...
1
vote
0answers
42 views

What is the big-$\mathcal{O}$ bound for the sum of function applied to the partitions of a set?

Consider a set $A$ that is partitioned into $n$ subsets $A_1 | A_2 | ... | A_n$ and a function $f \in \mathcal{O}(g)$. Question: what is the tightest bound I can establish for $\sum_{i=1}^n ...
3
votes
0answers
137 views

If $f$ is quasi and left continuous on $[a,b]$ and $\alpha$ is increasing and right continuous then $f$ is Riemann-Stieltjes integrable over $[a,b]$

Question: If $f$ is quasi and left continuous on $[a,b]$ and $\alpha$ is increasing and right continuous then $f$ is Riemann-Stieltjes integrable over $[a,b]$ with integrator $\alpha$. ...
2
votes
1answer
1k views

Partitions of an integer into k parts.

I am interested in knowing whether an exact formula (analogous to the Hardy-Ramanujan-Rademacher formula for $p(n)$) for the number of partitions of a positive integer into k parts is known. I tried ...
11
votes
4answers
5k 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 ...
4
votes
1answer
184 views

Showing two generating functions to be equal

Let $\mathcal{A}$ be the set of partitions in which each part may occur 0, 1, 4, or 5 times and let $\mathcal{B}$ be the set of partitions which have no parts congruent to 2mod4, and in which parts ...
6
votes
1answer
313 views

Creating generating functions for integer partitions

Say I have a generating function $\Phi_\mathcal{A}$ for the set of partitions $\mathcal{A}$ which have no parts congruent to 2 mod 4, and I have the generating function for $\Phi_\mathcal{B}$ for the ...
1
vote
1answer
493 views

Integer Partitions Formulas [duplicate]

Possible Duplicate: Identity involving partitions of even and odd parts. How would I go about to show the following: Let $pe(n)$ be the number of partitions of size n with an even number of ...
2
votes
3answers
112 views

Number decomposition

Recently I encountered a problem I was not familiar with. So hope someone can help me for this. Here is the problem. Given any odd integer, how many different ways of decomposition into sum of three ...
0
votes
3answers
126 views

Combination Question

I currently have an open question about counting the possible ways of summing numbers. I am still exploring all the ideas provided - those within my level of understanding. This is a question ...
4
votes
1answer
2k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
0
votes
1answer
122 views

What is minimum Eulerian partition?

I have a homework in my graph course. It asks something about minimum Eulerian partition but it doesn't give any information about it. I googled it but couldn't come up anything useful and clear. Is ...
1
vote
1answer
123 views

Nonnegative integers with unique restricted partitions

I have come over the following problem in elementary number theory: suppose that a positive integer $k$ is given. Is it possible to find, for every such $k$, a nonnegative integer $N(k)$ and a set of ...
1
vote
2answers
2k views

Distribution of the sum of a multinomial distribution

I have distilled an error analysis problem into the following: I have a multinomial distribution, $X$, consisting of $n$ independent trials where each trial takes on the values $\{0,1,\ldots,k-1\}$ ...
4
votes
2answers
881 views

Enumeration of partitions

The Stirling number of the second kind $S(n,k)$, where $S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n$ Gives the number of unique unlabeled, ...
3
votes
3answers
1k views

Partition of a set of size n into subsets of size 1 and 2.

Before I ask the question, I must admit that combinatorics has never been my forte. I am given a set X of size $n$, we may assume assume $X=\{1,2,...,n\}$. I want to count the partition of this set ...
1
vote
1answer
127 views

Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ [closed]

Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ such that condition 1: $1 \leq a_i \leq 7$ condition 2: $1 \leq b_i \leq 4$ condition 3: $\sum_{i=1}^{2} {a_i} = 8$ ...