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
8
votes
1
answer
203
views
Asymptotic of the number of partitions of $n$ into numbers from $\{1, 2, \dots, k\}$
How to find the asymptotic behavior ($n \to +\infty$) of the number $q(n, k)$ of partitions of $n$ into addends from $\{1, 2, \dots, k\}$?
I proved that $q(n, k)$ satisfies the recurrent relation $q(...
- 136
8
votes
2
answers
249
views
Minimizing over partitions $f(\lambda) = \sum \limits_{i = 1}^N |\lambda_i|^4/(\sum \limits_{i = 1}^N |\lambda_i|^2)^2$
I'm trying to characterize the behavior of the the quantity:
$$A = \frac{\sum \limits_{i = 1}^N x_i^4}{(\sum \limits_{i = 1}^N x_i^2)^2},$$
subject to the constraints that
$$ \sum \limits_{i = 1}^N ...
- 664
8
votes
0
answers
209
views
Is every positive integer the sum of 1 square number, 1 pentagonal number, and 1 hexagonal number?
I found this interesting conjecture, but maybe I'm not the first to state it. I have tested it for the first $10^4$ positive integers, but that is not a proof. Can anybody prove or disprove this ...
- 301
8
votes
0
answers
1k
views
Partitions of 13 and 14 into either four or five smaller integers
There are exactly 18 partitions of the integer 13 into 4 parts, as on the left of the table, and also 18 partitions into 5 parts, as on the right of the table:
$$\begin{array}{c|c}
10+1+1+1 & 9+1+...
- 65.8k
8
votes
0
answers
813
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 ...
- 32.9k
7
votes
2
answers
9k
views
1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,... (partition numbers): What is the recurrence relation / recursive formula / closed formula for this?
I have already read this:
Number partition - prove recursive formula
But the formula from the above link requires a parameter k which is the required number of ...
7
votes
4
answers
3k
views
Computing partition numbers
Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
- 29.9k
7
votes
2
answers
222
views
Combinatorial Interpretation of a partition identity
I am working on the book "Number Theory in the Spirit of Ramanujan" by Bruce Berndt.
In Exercise $1.3.7$: He wants us to prove that
$$
np\left(n\right) = \sum_{j = 0}^{n - 1}p\left(j\right)\...
- 439
7
votes
3
answers
6k
views
Partitions of $n$ into distinct odd and even parts proof
Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts.
How do I ...
- 129
7
votes
2
answers
794
views
Partitions in which no part is a square?
I asked a similar question earlier about partitions, and have a suspicion about another way to count partitions.
Is it true that the number of partitions of $n$ in which each part $d$ is repeated ...
- 73
7
votes
3
answers
234
views
Prove that $\prod_{i\geq 1}\frac{1}{1-xy^{2i-1}} = \sum_{n\geq 0} \frac{(xy)^{n}}{\prod_{i=1}^{n}\left( 1-y^{2i} \right)}.$
Prove that
$$\prod_{i\geq 1}\frac{1}{1-xy^{2i-1}} = \sum_{n\geq 0} \frac{(xy)^{n}}{\prod_{i=1}^{n}\left( 1-y^{2i} \right)}.$$
Here I am trying the following
\begin{align*}
\prod_{i\geq 1}\frac{1}{1-xy^...
- 376
7
votes
3
answers
3k
views
Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)
Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
- 485
7
votes
7
answers
2k
views
$a+b+c+d+e=79$ with constraints
How many non-negative integer solutions are there to $a+b+c+d+e=79$ with the constraints $a\ge7$, $b\le34$ and $3\le c\le41$?
I get that for $a\ge7$ you do $79-7=72$, $\binom{72+5-1}{5-1}=\binom{76}4$...
- 81
7
votes
2
answers
6k
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 $F(...
- 131
7
votes
1
answer
4k
views
Number of permutations with a given partition of cycle sizes
Part of my overly complicated attempt at the Google CodeJam GoroSort problem involved computing the number of permutations with a given partition of cycle sizes. Or equivalently, the probability of a ...
- 294