All Questions
Tagged with integer-partitions discrete-mathematics
120
questions
63
votes
1
answer
2k
views
Why are asymptotically one half of the integer compositions gap-free?
Question summary
The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
- 3,199
9
votes
1
answer
899
views
Expected Value for the Number of Parts of a Random Partition (Considering Only a Portion of the Partition Spectrum)
Let $n$ be a positive integer. If we take the set of all partitions of $n$ and choose a random partition from it (uniformly), then the expected value of the number of parts of this partition is a ...
- 113
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
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
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
6
votes
0
answers
181
views
Almost a prime number recurrence relation
For the number of partitions of n into prime parts $a(n)$ it holds
$$a(n)=\frac{1}{n}\sum_{k=1}^n q(k)a(n-k)\tag 1$$
where $q(n)$ the sum of all different prime factors of $n$.
Due to https://oeis....
- 13.9k
5
votes
1
answer
63
views
Recursion regarding number-partitions
I am learning about partitions of numbers at the moment.
Definition:
Let $n \in \mathbb{N}$. A $k$-partition of $n$ is a representation of $n$ as the sum of $k$ numbers greater than $0$, (i.e.
$n=a_1+....
- 609
5
votes
0
answers
278
views
Expected Value for the Number of Parts of a Partition of n
Given a positive integer $n$, I want to know the expected value for the number of parts of a random partition of $n$.
I am aware that a similar question has been asked already: Expected number of ...
- 113
5
votes
3
answers
140
views
Plain integer partitions of $n$ using $r$ parts
Division of number $n$ on parts $a_1,...,a_r$ where $a_1 \le ... \le a_r$ we call a plain if $a_1 = 1$ and $a_i - a_{i-1} \le 1$ for $2 \le i \le r$. Find enumerator (generating function) for plain ...
user677339
4
votes
4
answers
1k
views
# of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?
How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?
user223957
4
votes
1
answer
255
views
Alternative way of writing the stars and bars formula where each bar is associated with at least one star.
I was looking for a different way of writing the formula of the number of different $k$-tuples of non-negative integers whose sum is equal to $n$ and I thought of this formula followed by this ...
- 51
4
votes
2
answers
596
views
Number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s
How do I find the number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s?
I think the title is self-explanatory.
E.g., if I have to represent $13$ as a sum of only $1$'s ...
- 223
3
votes
4
answers
1k
views
Two hard number partition problems
For every positive integer $n$, let $p(n)$ denote the number of ways to express $n$ as a sum of positive integers. For instance, $p(4)=5$. Also define $p(0)=1.$
Problem 1.
Prove that $p(n)-p(n-1)...
- 1,517
3
votes
2
answers
549
views
Integer partitioning
Suppose we have an integer $n$. I we want to partition the integer in the form of $2$ and $3$ only; i.e., $10$ can be partitioned in the form $2+2+2+2+2$ and $2+2+3+3$.
So, given an integer, how to ...
- 133
3
votes
2
answers
2k
views
Help understanding solution to growth of partition function
I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated.
Question Let the number of ...
- 31