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
77
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
0
votes
1
answer
69
views
Showing $k! \cdot q_k(n) \leq \binom{n-1}{k-1}$?
Let $q_k(n)$ denote the number of distinct partitions of some $n \in \mathbb{N}$ with exactly $k$ parts. How can I show that:
$$k! \cdot q_k(n) \leq \binom{n-1}{k-1}$$
There is a related inequality ...
- 682
0
votes
1
answer
77
views
Number of integer partitions with at most a parts and each with a size of at most b, where a and b are positive integers
Partitions of integers. Let π(n) count the ways that the integer n can be expressed
as the sum of positive integers, written in non-increasing order. Thus π(4) = 5,
since 4 can be expressed as 4 = 3 + ...
- 31
1
vote
1
answer
38
views
Equality between q shifted factorials and sum with partitions
I am looking at WilliamY.C.Chen,Qing-HuHou,and Alain Lascoux proof for the Gauss Identity in q shifted factorials. At some point they claim that it is easy to see that
$$
\frac{q^r}{(q ; q)_r}=\sum_{\...
0
votes
2
answers
40
views
max length of list s.t sum of the powers list equals n
I am trying to find out what is the best upper bound on the size of a list such that
All its values are integers between $1$ and $n$
Its values are all different from each other
The sum of the $k^\...
- 103
1
vote
1
answer
83
views
Euler's pentagonal number theorem, the notion of $\omega(n)$ and $\omega(-n)$
I'm studying chapter 14 "Partitions" of the famous Apostol's Introduction to Analytic Number Theory. Down at page 311 (section 14.4) and endeavoring to study the pentagonal numbers, Apostol ...
2
votes
2
answers
174
views
Number of ways to complete a partial Young tableau
Suppose we have a Young tableau with missing entries. Then there can be many number of ways we can complete the Young Tableau.
Is there any specific method to find the number of ways we can complete a ...
- 399
1
vote
1
answer
49
views
Understanding about paper related to integer partition with even parts distinct
Let $ped(n)$ denote the number of partition of a positive integer $n$ wherein the even parts are distinct and the odd parts are unrestricted. I follow this paper:
Andrews, G. E., Hirschhorn, M. D., &...
- 447
0
votes
1
answer
57
views
On a certain kind of integer partitions
Background: I am investigating partitioning integers using a fixed radix base.
Problem: Suppose we have $x$, an arbitrary integer. Let $M = \{2, 3, 5, ..., p\}$ be a set of prime moduli.
The prime ...
- 3,341
1
vote
0
answers
70
views
Closed form version of partition and combination problem
We have an original set of n integers, $0, ... , (n-1)$. From these integers generate a set of $k$-tuples, with repetition where order does not matter. From this, want to know the probability that any ...
- 203
0
votes
1
answer
60
views
Self transpose of partitions and odd parts
Let a partition be called self-transpose if its Ferrers diagram is symmetric about the diagonal,
i.e. if the partition is its own transpose. For instance, there are two self-transpose partitions of
8: ...
user1154312
7
votes
2
answers
217
views
Number of ways to distribute $n$ identical balls into $k$ identical boxes such that no box contains more than $m$ balls?
I wonder how to count the number of ways (algorithmically is fine) to distribute $n$ identical balls into $k$ identical boxes such that no box contains more than $m$ balls?
I've run into answers in ...
0
votes
1
answer
40
views
Unable to understand the base cases for this recurrence relation: DPn = DPn-1 + DPn-3 + DPn-4
I read the following here
Sub-problem: DPn be the number of ways to write N as the sum of 1, 3, and 4.
Finding recurrence: Consider one possible solution, n = x1 + x2 + ... xn. If the last number is 1,...
1
vote
0
answers
100
views
Partitions with maximal length
Suppose $L$ is a non-empty finite set of positive integers, and let $d=\max L$.
For a positive integer $n$, define an $L$-partition of $n$ to be any sequence $a_1,a_2,\ldots,a_m$ of elements of $L$ ...
- 1,136
0
votes
1
answer
76
views
Derivation of Integer Partition from Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 447
0
votes
0
answers
39
views
Why is $ \sum_\mu [s_\lambda](s_\lambda s_\mu)_{/\mu} = \sum_\rho [s_\rho](s_{\rho /\mu}) s_\mu$ for any partition $\lambda$?
Say $\lambda \vdash n$ and $\mu \vdash m$ and $|\rho|=|\lambda|+|\mu|$ then for all $\lambda$ and $m$ it appears to hold that
$$ \sum_\mu [s_\lambda](s_\lambda s_\mu)_{/\mu} = \sum_\rho [s_\rho](s_{\...
- 910