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
1answer
278 views

Bell number. Combinatorial proof.

$B_m$ is the Bell's number (the # of all partitions of the set $m$) and $B_m^*$ is the number of partitions of set $m$ with no singleton block We need to prove that $B_m = B_m^* + B_{m+1}^*$. ...
6
votes
3answers
373 views

How to prove it? (one of the Rogers-Ramanujan identities)

Prove the following identity (one of the Rogers-Ramanujan identities) on formal power series by interpreting each side as a generating function for partitions: ...
3
votes
3answers
1k views

How can I find the partitions of this equivalence relation?

I have the following equivalence relation: $$\{(1,1),(1,4), (2,2), (3,3), (4,1), (4,4)\}$$ On the set: $ A = \{1,2,3,4\}$ How can I find it's partitions? This example will help me understand the ...
6
votes
1answer
148 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
1
vote
1answer
184 views

Balls, Bags, Partitions, and Permutations

We have $n$ distinct colored balls and $m$ similar bags( with the condition $n \geq m$ ). In how many ways can we place these $n$ balls into given $m$ bags? My Attempt: For the moment, if we assume ...
1
vote
1answer
55 views

Balancing two sets while items in one are unmovable

I'm working on a following problem: Given two sets containing jars, each of which is assigned a random weight (weight is a real number), find a way to balance two sets by weight, i.e. the difference ...
1
vote
1answer
129 views

Determining Stirling number

In the first part of the question I was asked to find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ (a fixed constant) distinct ...
2
votes
1answer
182 views

Dilworth's Lemma

We want to place $2012$ pockets, including variously colored balls, into $k$ boxes such that either For all boxes, all pockets in a box must include a ball with the same color ...
0
votes
1answer
161 views

Generating function: number of partitions that add up to at most $n$

Find a generating function $a_n$, the number of partitions that add up to at most $n$. So I know that if it were asking the number of partitions of the integer $n$, I would have my generating ...
1
vote
1answer
342 views

Combinatorial proof involving partitions and generating functions

Show that any number of partitions of $2r + k$ into $r + k$ parts is the same for any $k$. I've tried this, but I haven't come up with anything; hence why I have nothing written here. But in any ...
7
votes
1answer
106 views

Generating function for $r^\binom{n}{2}$

I'm trying to find a closed form of the generating function $$ G(x) = \sum_{n \ge 0} r^\binom{n}{2} x^n $$ for a real number $0 < r < 1$. I found that $G(x) = 1 + xG(rx)$. Any hints where to ...
2
votes
0answers
21 views

Terminology for breaking partition diagram into “L”'s

When one thinks about partitions, it's quite normal to consider pieces of the partition diagram, such as rows, columns, arms, legs, hooks, etc. One decomposition of particular interest to me is ...
4
votes
4answers
440 views

Algorithm to partition sum between buckets in all unique ways

The Problem I need an algorithm that does this: Find all the unique ways to partition a given sum across 'buckets' not caring about order I hope I was clear reasonably coherent in expressing ...
0
votes
2answers
42 views

Relationship Question

Let $\ S\ $ be a non-empty Set, and suppose s$\ \in S $. Assuming $\ S\ $ is finite, what can we deduce about the relationship between $\ |\mathcal P(S\ \setminus \{s\} )| $ and $\ | \mathcal P(S)|?$ ...
3
votes
3answers
670 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
132 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
106 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
963 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
94 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
834 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 ...
4
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
349 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
198 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
95 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
232 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
185 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
139 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
108 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
864 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
151 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
170 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
556 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
140 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
794 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
111 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
438 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
361 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
43 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$. ...