Questions tagged [integer-partitions]
Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.
1,433
questions
2
votes
1
answer
118
views
Number of partitions of $n$ into distinct even parts.
Question from my last exam:
Let $r_n$ denote the number of partitions of $n$ into distinct parts. Prove that
$$
\sum_{i=0}^n(-1)^i r_i r_{n-i}
$$
is the number of partitions of $n$ into distinct even ...
- 675
1
vote
1
answer
80
views
What is the most precise upper bound for the partitions funcion $p(n)$? [closed]
In the paper "Asymptotic formulæ in combinatory analysis, 1918" Hardy and Ramanujan gave an upper bound $p(n) < \frac{K}{n}e^{2\sqrt{2n}}, K > 0$. Is this the best upper bound? What is ...
- 53
2
votes
0
answers
66
views
Combinatorial explanation for an identity of the partition function
One can employ elementary methods to demonstrate that $p(n) \leq p(n-1) + p(n-2)$ for $n \geq 2$. Recently, I showed that if certain restrictions are imposed on the partitions, the inequality becomes ...
- 907
0
votes
0
answers
76
views
Factoring an integer $N$ using its random partition of length $3$
While working on this MSE question that I had posted, I wondered what would be a minimal base of numbers that we could work with the algorithm described in that question.
I conjectured that a ...
- 3,341
1
vote
0
answers
53
views
Exercise I.0.9 from Tenenbaum's "Introduction to analytic and probabilistic number theory"
I'm trying to solve all the exercises from Tenenbaum's book but am unfortunately stuck on problem 9 of the very first ("tools") chapter. The problem is supposed to be an application of the ...
- 11
4
votes
1
answer
134
views
The total number of all different integers in all partitions of n with smallest part $\geq 2$
I want to show that the total number of all different integers in all partitions of $n$ with smallest part $ \geq 2$ is $p(n-2)$.
Example: partitions of $7$ with smallest part $ \geq 2$ are (7), (5,2),...
- 53
0
votes
0
answers
39
views
MacDonalds Hook content formula derivation
I was trying to understand the derivation of
$$
s_{\lambda}=a_{\lambda+\delta} / a_{\delta}=q^{n(\lambda)} \prod_{x \in \lambda} \frac{1-q^{n+c(x)}}{1-q^{h(x)}}
$$
as given in (https://math.berkeley....
0
votes
0
answers
105
views
How many different ways are there to express a positive integer as a sum?
Consider the equation $x_1+x_2+...+x_r=n$ where all values are positive integers. How many solutions are there to this equation if $n$ is given? The order of the $x_i$s does not matter i.e. $1+2+3=6$ ...
- 27
1
vote
1
answer
77
views
Another formulation for Stirling numbers of the second kind
I find another formulation for Stirling numbers of the second kind:
Let $n\ge k\ge 1$. Denote by
$$\mathbb N_<^n := \{ \alpha = (\alpha_1,\cdots,\alpha_n): 0\le \alpha_1\le\cdots\le\alpha_n, \...
- 1,972
1
vote
1
answer
288
views
A certain conjectured criterion for restricted partitions
Given the number of partitions of $n$ into distinct parts $q(n)$, with the following generating function
$\displaystyle\prod_{m=1}^\infty (1+x^m) = \sum_{n=0}^\infty q(n)\,x^n\tag{1a}$
Which may be ...
- 2,813
2
votes
1
answer
66
views
Erdos-Lehner theorem for partition function of different parts
Denote:
$p_k(n)$ as the partition of integer $n$ into $k$ parts
$q_k(n)$ as the partition of integer $n$ into $k$ different parts
It was proven by Erdos-Lehner that $p_k(n)\sim \frac{1}{k!}\binom{n-...
- 119
3
votes
0
answers
50
views
$\sum_{n=1}^m \frac{1}{n!} \sum_{\sum_{i=1}^n m_i = m, \\ m_i \in \mathbb N_+} \frac{1}{m_1\cdots m_n} = 1$? [duplicate]
I found an equation accidentally when doing my research about branching processes. I think it is correct but I don't know how to prove it:
\begin{equation}
\sum_{n=1}^m \frac{1}{n!} \sum_{\sum_{i=1}^n ...
- 1,972
0
votes
1
answer
125
views
Stars and Bars with Multiple Restrictions
I've seen this Number of solutions to $x_1 +x_2 +x_3 +x_4 = 1097$ with multiple "at least" restrictions
and this Stars and bars (combinatorics) with multiple bounds.
But I am having trouble ...
- 106
3
votes
2
answers
176
views
Where can I find a proof of the asymptotic expresion of partition numbers by Hardy-Ramanujan?
I'm starting to study number theory and I´m interested in partitions, but I don't find a proof of this asymptotic expression $p(n)$ given by Hardy-Ramanujan.
- 39
0
votes
1
answer
44
views
Is the following Knapsack Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 193