All Questions
Tagged with integer-partitions number-theory
259
questions
0
votes
0
answers
15
views
Value of $k$ that gives the highest Restricted-Part Integer Partition Number for $n$
Let $p_k(n)$ be the number of possible partitions of an Integer $n$ into exactly $k$ parts. We know that for any given $n$, $p_k(n)$ gives a non-zero result for $0<k\leq n$, and that the size of ...
1
vote
1
answer
49
views
Generating function of partitions of $n$ in $k$ prime parts.
I have been looking for the function that generates the partitions of $n$ into $k$ parts of prime numbers (let's call it $Pi_k(n)$). For example: $Pi_3(9)=2$, since $9=5+2+2$ and $9=3+3+3$.
I know ...
2
votes
1
answer
155
views
About the product $\prod_{k=1}^n (1-x^k)$
In this question asked by S. Huntsman, he asks about an expression for the product:
$$\prod_{k=1}^n (1-x^k)$$
Where the first answer made by Mariano Suárez-Álvarez states that given the Pentagonal ...
0
votes
0
answers
81
views
Need help with part of a proof that $p(5n+4)\equiv 0$ mod $5$
Some definitions:
$p(n)$ denotes the number of partitions of $n$.
Let $f(q)$ and $h(q)$ be polynomials in $q$, so $f(q)=\sum_0^\infty a_n q^n$ and $h(q)=\sum_0^\infty b_n q^n$. Then, we say that $f(q)\...
- 350
0
votes
0
answers
77
views
How to prove the following partition related identity?
So I want to show that the following is true, but Iam kidna stuck...
$$
\sum_{q_{1}=1}^{\infty}\sum_{q_{2}=q_{1}}^{\infty}\sum_{q_{3}=q_{1}}^{q_{2}}...\sum_{q_{k+1}=q_{1}}^{q_{k}}x^{q_{1}+q_{2}+...+q_{...
- 1
1
vote
0
answers
39
views
How to explain arithmetic form of surprising equality that connects derangement numbers to non-unity partitions?
$\mathbf{SETUP}$
By rephrasing the question of counting derangements from
"how many permutations are there with no fixed points?"
to
"how many permutations have cycle types that are non-...
0
votes
0
answers
24
views
Congruences of partition function
I'm trying to understand Ken Ono's results showing Erdös' conjecture for the primes $\ge5$. He first shows the following: let $m\ge5$ be prime and let $k>0$. A positive proportion of the primes $\...
- 73
0
votes
0
answers
19
views
Estimate the order of restricted number partitions
There are $k$ integers $m_l,1\leq l\leq k
$(maybe negetive), satisfiying $|m_l|\leq M$ and $\sum_l m_l=s$.
I want to get an order estimate of the number of solutions for $k, M$ when fixing $s$.
I came ...
- 91
1
vote
0
answers
79
views
"Factorization" of the solutions set of a system of linear diophantine equations over non-negative integers
Suppose we have a system of linear diophantine equations over non-negative integers:
$$
\left\lbrace\begin{aligned}
&Ax=b\\
&x\in \mathbb{Z}^n_{\geq0}
\end{aligned}\right.
$$
where $A$ is a ...
- 11
0
votes
0
answers
26
views
irregularities in partition function modulo n
It is an open problem whether the partition function is even half the time. Inspired by this, I wrote some Sage/Python code to check how many times $p(n)$ hits each residue class:
...
- 387
1
vote
0
answers
33
views
Show the partition function $Q(n,k)$, the number of partitions of $n$ into $k$ distinct parts, is periodic mod m
Let $Q(n,k)$ be the number of partitions of $n$ into $k$ distinct parts.
I want to show that for any $m \geq 1$ there exists $t \geq 1$ such that
$$Q(n+t,i)=Q(n,i) \mod m \quad \forall n>0 \forall ...
- 103
0
votes
0
answers
48
views
Find generating series on set of descending sequences, with weight function as taking sum of sequence
Given the set of all sequences of length k with descending (not strictly, so $3,3,2,1,0$ is allowed) terms of natural numbers (including $0$), $S_k$, and the weight function $w(x)$ as taking the sum ...
- 183
0
votes
0
answers
45
views
Probability that the maximum number of dice with the same face is k
Let say we have $N$ dice with 6 faces. I'm asking my self, what is the probability that the maximum number of dice with the same face is $k$?
In more precise terms, what is the size of this set?
\...
0
votes
1
answer
44
views
The Asymptotic formula of the generating function related with the partition of a positive integer
This question may be duplicate with this answer_1 and here I referred to the same paper by Hardy, G. H.; Ramanujan, S. referred to by wikipedia which is referred to in answer_1.
But here I focused on ...
- 416
1
vote
1
answer
56
views
corollary of the partition congruence
I was going though the paper of Ramanujan entitled Some properties of p(n), the number of partitions of n (Proceedings of the Cambridge Philosophical Society, XIX, 1919, 207 – 210). He states he found ...
- 21
0
votes
0
answers
32
views
Constrained integer partition containing particular summands
Is there a way to calculate the number of constrained integer partitions containing particular summands? By constrained, I mean, the permitted summands must be below a certain limit, such as 5. Take ...
2
votes
1
answer
61
views
Counting gap sizes in a subfamily of partitions
Let $\mathcal{OD}$ be the set of all odd and distinct integer partitions. This has a generating function given by
$$\sum_{\lambda\vdash\mathcal{OD}}q^{\vert\lambda\vert}=\prod_{j\geq1}(1+q^{2j-1})$$
...
- 339
1
vote
0
answers
24
views
Notation for $k$-partitions of $n$ containing at least one summand equal to $s$
I am looking for whether there is any notation for the $k$-partition number of $n$ where the partitions must include some summand $s$.
An example of the kind of notation I am looking for is $P_k^s(n)$....
- 1,129
1
vote
1
answer
57
views
What is the 11th unordered combination of natural numbers that add upto 6 in the partition function?
So, I was making unordered combinations of natural numbers which add upto a certain natural number. I was able to go till 6 when I got to know about the partition function. I was pleased to see that ...
- 177
2
votes
1
answer
70
views
Identity involving Sum of Inverse of Product of Integer partitions [closed]
Is there a way to prove the following identity
\begin{equation}
\sum_{l = 1}^{k} \left( \frac{(-s)^l}{l!} \sum_{n_1 + n_2 + \ldots n_l = k} \frac{1}{n_1n_2 \ldots n_k} \right)= (-1)^k {s \choose k} \,...
- 89
1
vote
0
answers
36
views
Partition of n into k parts with at most m
I ran into a problem in evaluating a sum over kronecker delta. I want to evaluate
$$\sum_{\ell_1,...,\ell_{2m}=1}^s\delta_{\ell_1+\ell_3+...+\ell_{2m-1},\ell_2+\ell_4+...+\ell_{2m}}$$
My approach was ...
- 29
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
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....
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
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
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
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 ...
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
1
vote
1
answer
86
views
Is the set of all rational additive partitions of a rational number countable?
We usually call additive partitions the set, we call it $P$, of all the ways to write a positive integer $n$ as a sum of positive integers. Formally:
\begin{equation}
P_n = \left\{ (a_1 ,...,a_n)\in\...
3
votes
0
answers
334
views
Unsolved problems for partition function
In number theory, the partition function $p(n)$ represents the number of possible partitions of a non-negative integer $n$. For instance, $p(4) = 5$ because the integer $4$ has the five partitions $1 +...
- 907
6
votes
0
answers
175
views
When are the partition numbers squares?
I'm unsure if this question is even interesting. I am playing around with partition numbers $p(n) :=$ # partitions of $n$, and I noticed that $p(n)$ never really is a square number, except for of ...
- 1,769
2
votes
1
answer
125
views
Is there a pattern to the number of unique ways to sum to a number?
I don’t think there is a proper name for these so I will refer to them as “phactors”. Basically, a phactor is a way to sum up to a number using positive real integers that are non zero and not equal ...
- 478
1
vote
1
answer
96
views
Representation of number as a sums and differences of natural numbers
Lets consider all the combinations of:
$$1+2+3+4=10,\ \ 1+2+3-4=2,\ \ 1+2-3+4=4,\ \ 1+2-3-4=-4, $$
$$1-2+3+4=6,\ \ 1-2+3-4=-2,\ \ 1-2-3+4=0,\ \ 1-2-3-4=-8,$$
$$-1+2+3+4=8,\ \ -1+2+3-4=0,\ \ -1+2-3+4=2,...
- 1,818
2
votes
0
answers
147
views
Could this yield a formula for the Partition numbers?
Background: Lately, I have fallen down the rabbit hole of partition numbers. Specifically the partition function, $p(n)$. It's well known that no closed-form expression (with only finitely many ...
- 4,472
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
1
vote
1
answer
289
views
Number of ways to write a positive integer as the sum of two coprime composites
I've recently learnt that every integer $n>210$ can be written as the sum of two coprime composites.
Similar to the totient function, is there any known function that works out the number of ways ...
- 103
0
votes
1
answer
311
views
Partitions of a number for a fixed number of integers
Is there a name for the number of ways to write a positive integer $n$ as a sum of $k$ integers, including 0?
For example, the number 4 can be written as the sum of 3 numbers in the following ways:
4+...
- 1,620
0
votes
1
answer
46
views
Show that $p(n-k, k)=p^2(n, k)$
Let $p^m(n, k)$ denote the number of partitions of $n$ having exactly $k$ parts
with each part greater than or equal to $m$. Show that
$p(n-k, k)=p^2(n, k)$, with the convention that $p(n, k)=0$ if $n&...
- 153
1
vote
3
answers
73
views
Partitions without repetition
I want to know how many partitions without repetition 19 has. I know I should see the coefficient of $x^{19}$ in $$\prod_{k=1}^\infty(1-x^k),$$
but i'm having trouble finding it. Ay hint?
- 153
2
votes
2
answers
81
views
Show that series converges by estimating number of partitions into distinct parts
I need some help with solving the following problem: Let $Q(n)$ be the number of partitions of $n$ into distinct parts. Show that $$\sum_{n=1}^\infty\frac{Q(n)}{2^n}$$ is convergent by estimating $Q(n)...
- 155
0
votes
0
answers
127
views
Formula concerning partitions of $n$ and their transpose
I am trying to prove
$$\frac{1}{{n \choose 2}} \sum_j {\lambda_j \choose 2} - {\lambda_j'\choose 2}=\frac{1}{n(n-1)}\sum_j \lambda_j^2 - (2j-1)\lambda_j.$$
Here $\lambda$ is a partition of $n$, i.e. $\...
- 1,092
1
vote
2
answers
86
views
How many non-congruent triangles can be formed from $n$ equally spaced vertices on a circle?
How many non-congruent triangles can be formed from $n$ equally spaced vertices on a circle? I tried using the stars and bars method but it isn't working for me. Partitioning $n$ into $3$ parts looks ...
- 11
0
votes
1
answer
138
views
Infinite product expression of partition function
I'm working on a problem (specifically, I'm using an exam paper without course notes to prepare for a course starting in September),
Define the partition function $P(q)$ and give its infinite product ...
- 2,281
1
vote
2
answers
59
views
How to rigorously interpret and transform "equal chance" in different ways?
Put $100$ identical balls into $10$ identical boxes in a way that each ball enters each box with an equal chance. What's the probability that no box is empty?
I have solved it but like to discuss ...
- 2,036
0
votes
1
answer
277
views
Number of possible combinations of X numbers that sum to Y where the order doesn't matters
I am looking for the number of possible outcomes given to a set of numbers X that sum to Y. This is the same issue as here. However, I would like to consider that (i) the numbers can't be repeated and ...
0
votes
1
answer
83
views
Question on partition of positive integer
I know only basic about partition of a natural number like $p(0)=1$, $p(1)=1$,
$p(2)=2 $ that is $$2=1+1$$
$$2=2$$ and similarly $p(3)=3 $ as
$$3=1+1+1$$
$$3=2+1$$
$$3=3$$ and for further reading of ...
3
votes
0
answers
71
views
Are there exist infinitely many odd numbers and even numbers in p(an+b)?
The main question is: Are there exist infinitely many odd numbers and even numbers in $p(an+b)$? Where $an+b\ (n\geq1)$ is an arbitrary arithmetic sequence with $a\in\mathbb{Z}_{>0}$, $b\in\{0,\...
- 907
1
vote
1
answer
189
views
Summation of quantity over all integer partitions
The notation $\lambda = (1^{m_1} 2^{m_2} 3^{m_3}) \vdash n$ means that $\lambda$ is a partition of $n$ with $m_1$ 1's, $m_2$ 2's and so on. For instance, the partition (3, 1, 1) of 5 can be written as ...
- 2,342