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.
1
vote
4answers
125 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$, ...
4
votes
0answers
43 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
98 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
43 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
58 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
81 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
1
vote
1answer
86 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\} ...
4
votes
2answers
39 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.
6
votes
1answer
83 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 ...
1
vote
2answers
125 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
67 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
74 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
43 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
91 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 ...
0
votes
0answers
23 views
separation of semi-distinguishable objects.
I have $n_1$ objects of type $1$, $n_2$ objects of type $2$, ..., $n_k$ objects of type $k$.
Now, What are the numbers of ways of making $p$ objects out of these $n=\sum n_i$ semi-distinguishable ...
4
votes
2answers
103 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:
...
3
votes
1answer
126 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
36 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
35 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
63 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 ...
0
votes
1answer
60 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 ...
4
votes
5answers
257 views
Book recommendation
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 ...
2
votes
0answers
91 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
0answers
61 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
79 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
151 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
38 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
56 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) ...
1
vote
1answer
81 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 ...
6
votes
0answers
150 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 physical ...
1
vote
1answer
140 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
34 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
43 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$.
...
8
votes
6answers
2k views
Making Change for a Dollar (and other number partitioning problems)
I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
5
votes
2answers
288 views
Number of partitions contained within Young shape $\lambda$
It is well known that the number of partitions contained within an $m\times n$ rectangle is $\binom{m+n}{n}$.
Furthermore, it is not difficult to calculate the number of partitions contained within a ...
2
votes
1answer
230 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 ...
5
votes
1answer
127 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 ...
3
votes
1answer
97 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 ...
1
vote
1answer
145 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 ...
4
votes
2answers
175 views
Find all ways to factor a number
An example of what I'm looking for will probably explain the question best. 24 can be written as:
12 · 2
6 · 2 · 2
3 · 2 · 2 · 2
8 · 3
4 · 2 · 3
6 · 4
I'm familiar with finding all the prime ...
2
votes
3answers
68 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
2answers
63 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 ...
1
vote
1answer
461 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
53 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 ...
0
votes
1answer
64 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 ...
0
votes
0answers
58 views
Knapsack like problem for product of distinct primes
While looking into ways of generating certain kinds of pseudo-random number sequences I came up with the issue of finding the maximum of products of distict primes with a sum less than N. I'm ...
0
votes
2answers
194 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\}$ ...
2
votes
2answers
136 views
On the path diagram of a partition
A path diagram is a Ferrers diagram for a partition $\lambda$ in which the dots have been replaced with numbers computed as follows. The number in position $(i,j)$ the number of paths (going either ...
3
votes
2answers
113 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, ...
2
votes
1answer
128 views
How many circular distinct compositions of $n$ into $k$ parts at most $g$
how many circular distinct sequences (e.g. $(4124)\equiv(4412$)) are there that sum up to $n$, have $k$ elements may be non-negative integers at most $g$?
In other words: we're looking for the number ...
