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
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
0
votes
1
answer
201
views
Link Between Integer Partition and 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
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
1
answer
122
views
Combinatorial interpretation of $\prod_{\lambda\vdash n} \prod\lambda_{k} = \prod_{\lambda\vdash n} \prod m^{(\lambda)}_i!$
Notation:
(i) $\uparrow^{G}_{H}$ denotes the induced representation (or its corresponding character) of $H$ to $G$, and $\downarrow^{G}_{H}$ denotes restriction similarly.
(ii) $\lambda = \...
- 245
6
votes
2
answers
200
views
Can we use Burnside's lemma to count partitions of an integer?
I am currently learning group theory and find that Burnside Lemma can be used to calculate partition number, although not that efficiently.
Suppose we want to distribute $n$ different balls into $n$ ...
- 605
2
votes
1
answer
138
views
A number partition problem
I have encountered the following interesting integer partitioning problem.
Let $n,k,t \in \mathbb{N}$ be given parameters and let $S_1,\ldots, S_t$ be a partition of the numbers $1,2,\ldots,n$ such ...
- 193
2
votes
0
answers
79
views
Weighted sum over integer partitions involving hook lengths
I am trying to compute the following quantity:
$$ g_n(x) = \sum_{\lambda \vdash n} \prod_{h \in \mathcal{H}(\lambda)} \frac{1}{h^2} \exp\left[x\sum_i \binom{\lambda_i}{2} - \binom{\lambda_i'}{2}\right]...
- 484
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
1
vote
0
answers
89
views
A summation formula for number of ways $n$ identical objects can be put in $m$ identical bins
A famous counting problem is to calculate the number of ways $n$ identical objects can be put into $m$ identical bins. I know that this problem is somewhat equivalent to Partition problem. There is no ...
- 415
2
votes
1
answer
78
views
the bracket partition function ? $3 = 1 + 1 + 1 = 1 + 2 = 1 + (1 + 1) $
I want to know in how many ways we can write a positive integer by using strict positive integers, addition and brackets. The order of addition does not matter.
For instance
$$3 = 1 + 1 + 1 = 1 + 2 = ...
- 16.4k
1
vote
1
answer
133
views
Understanding a Proof Related to Binary Partitions
In Section 10.2 Rödseth's Theorem for Binary Partitions of The Theory of Partitions by G. Andrews, we find the following:
For $q \in \Bbb C$ with $|q|<1$,
\begin{align}
\mathcal{F}_2(q) &= \...
- 447
1
vote
0
answers
127
views
Minimizing the magnitude of the sum of a vector of complex numbers with an integer constraint
Let $h_{1}, ..., h_{N} \in \mathbb{C} $
Consider minimizing the function below:
$ \min \left| \sum\limits_{i=1}^N h_{i} x_{i} \right| $
with the constraints $x_{i}^2 = 1$
i.e., $x_{i}$ can only take ...
- 11
2
votes
2
answers
168
views
Finding the generating function.
Find the generating function for the number of solutions for the equation $x_1+x_2+x_3+x_4 = n$, where $x_1,x_2,x_3,x_4\geq1$, and $x_1 < x_2$.
My attempt so far: I have tried putting a $y$ value ...
- 165
3
votes
2
answers
172
views
Finding "Hamiltonian paths" in fixed-size integer partitions
For $ p_k(n) $, the partitions of $ n $ with exactly $ k $ parts, it's possible to order them such that each adjacent pair of partitions differ only by one, i.e. one can be transposed to the other by ...
- 225
0
votes
0
answers
31
views
No. of partitions of $m$ with bounded $k$ parts [duplicate]
Let $\bar{n} = (n_1,\dots, n_k)$ be a fixed tuple of positive integers. Define $\mathcal P_m ({\bar{n}}) $ to be the set of all partitions of $m$ with exactly $k$ parts and the i-th part is bounded ...
- 4,360
0
votes
0
answers
60
views
Books for developing an intuitive understanding of the partitions of numbers
I understand from the fundamental theorem of arithmetic that every number can be written as a product of its prime factors,but I’m curious about partitions,how numbers can be broken up into sums and ...
1
vote
1
answer
96
views
Combinatorial proof of binary partition function $b(n)$ is always even
For all integer $n$, let $b(n)$ be the number of partition of $n$ into power of two.
For instance, $b(4)=4$, since
\begin{align*}
4 &= 2^2 \\
&= 2^1+2^1 \\
&= 2^1+2^0+2^0 \\
&= 2^0+2^0+...
user1089451
0
votes
1
answer
75
views
How many Young diagrams with length of at most $p$ rows and $q$ columns
How many Young diagrams are there with length of at most $p$ rows and $q$ columns, without restrictions on the weight of the diagrams?
The previous 2 questions asked for
Total number of Young ...
- 502
1
vote
1
answer
143
views
Generating function of ordered odd partitions of $n$.
Let the number of ordered partitions of $n$ with odd parts be $f(n)$. Find the generating function $f(n)$ .
My try : For $n=1$ we have $f(1)=1$, for $n=2$, $f(2)=1$, for $n=3$, $f(3)=2$, for $n=4$, $...
user1137804
3
votes
1
answer
344
views
Congruence properties of binary partition function
For every positive integer $n$, denote $b(n)$ be the number of binary partition of $n$, i.e., the number of partition of $n$ into power of two, where the power is decreasing.
For instance, $b(5)=4$ ...
user1089451
0
votes
1
answer
34
views
Number of ways to compose a number such that there is a maximum pile size and for each pile size there are a finite number of valid piles of that size
So, I want to count all of the different ways that a number $n$ can be written as the sum of numbers that are less than or equal to $k$ where the order of the numbers matters. Now, this is just ...
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
1
vote
1
answer
92
views
Identity about generating function related to binary expression of integers
For any nonnegative integer $n$, let $\mu(n)$ be $1$ if the binary expression of $n$ contains even number of ones; and $-1$ if the binary expression of $n$ contains odd number of ones. For example, $\...
user1089451
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
0
votes
0
answers
61
views
Compute a certain sum [duplicate]
How would I find a formula for $$S(n,r) = \sum_{i_1+\ldots+i_r = n,~(i_k)\in\mathbb{N}^r} ~~~i_1\ldots i_r ~~~~.$$
It's easy to find that it satisfies $$ S(n,r+1) = \sum_{j=0}^n(n-j)S(j,r),$$ which ...
- 181
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
1
vote
0
answers
49
views
Generating function of sequence related to binary expression of integer as follows
For any $n \in \Bbb N$, let $O(n)$ be $1$ if the binary expression of $n$ contains even number of ones; and $-1$ if the binary expression of $n$ contains odd number of ones, and $Z(n)$ be $1$ if the ...
user1089451
2
votes
0
answers
59
views
Sum of Schur functions incorporating the length statistic
Macdonald's Symmetric Functions and Hall Polynomials includes
the following identities (listed as exercises on pages 76 and 78
respectively):
\begin{equation}
\begin{array}{ll}
\text{Ex.} \,(4) \quad \...
- 567
0
votes
1
answer
63
views
Summing over tuples $(b_1, \ldots, b_n)$ with $\sum ib_i = n$ and $b_j = k$.
Let $T_n$ denote the set of $n$-tuples $\left(b_1, \ldots, b_n \right)$ of non-negative integers such that $\sum_{i=1}ib_i=n.$ I am trying to simplify the sum
\begin{align*}
\sum_{\underset{b_{j}=k}{\...
- 3,918
2
votes
1
answer
119
views
Does the partition function $p(n)$ generate infinite number of primes
Wikipedia says
As of June 2022, the largest known prime number among the values of $p(n)$ is $p(1289844341)$, with $40,000$ decimal digits
citing [1].
Is it known whether the partition function ...
- 3,341
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