Questions tagged [integer-partitions]
Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.
196
questions
33
votes
5
answers
57k
views
Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$
I want to find the number of nonnegative integer solutions to
$$x_1+x_2+x_3+x_4=22$$
which is also the number of combinations with replacement of $22$ items in $4$ types.
How do I apply stars and bars ...
35
votes
7
answers
27k
views
Making Change for a Dollar (and other number partitioning problems)
I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the ...
89
votes
4
answers
165k
views
Number of ways to write n as a sum of k nonnegative integers
How many ways can I write a positive integer $n$ as a sum of $k$ nonnegative integers up to commutativity?
For example, I can write $4$ as $0+0+4$, $0+1+3$, $0+2+2$, and $1+1+2$.
I know how to find ...
27
votes
1
answer
34k
views
The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts
This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
17
votes
2
answers
7k
views
Partitioning a natural number $n$ in order to get the maximum product sequence of its addends
Suppose we have a natural number $n \ge 0$.
Given natural numbers $\alpha_1,\ldots,\alpha_k$ such that
$k\le n$
$\sum_i \alpha_i = n$
what is the maximum value that $\Pi_i \alpha_i$ can take?
I'm ...
19
votes
3
answers
101k
views
Number of possible combinations of x numbers that sum to y
I want to find out the number of possible combinations of $x$ numbers that sum to $y$. For example, I want to calculate all combination of 5 numbers, which their sum equals to 10.
An asymptotic ...
15
votes
2
answers
4k
views
Identity involving partitions of even and odd parts.
First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
13
votes
2
answers
9k
views
Counting integer partitions of n into exactly k distinct parts size at most M
How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$?
The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
9
votes
1
answer
412
views
A "binomial" generalization of harmonic numbers
For positive integers $s$ and $n$ (let's limit the generality), define
$$H_s(n)=\sum_{k=1}^{n}\frac{1}{k^s},\qquad G_s(n)=\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^{k-1}}{k^s}.$$
The former is well-known; ...
11
votes
4
answers
19k
views
number of ordered partitions of integer
How to evaluate the number of ordered partitions of the positive integer $ 5 $?
Thanks!
14
votes
3
answers
20k
views
Integer partition of n into k parts recurrence
I was learning integer partition of a number n into k parts(with minimum 1 in each part) and came across this recurrence :
part(n,k) = part(n-1,k-1) + part(n-k,k)
...
14
votes
6
answers
2k
views
How solutions of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?
How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$.
For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. Is ...
2
votes
3
answers
3k
views
Multiplication partitioning into k distinct elements
Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are possible?...
2
votes
1
answer
4k
views
Number of positive integral solutions of $a+b+c+d+e=20$ such that $a<b<c<d<e$ and $(a,b,c,d,e)$ is distinct
This is from a previous question paper for an entrance exam I am preparing for.
https://www.allen.ac.in/apps/exam-2014/jee-advanced-2014/pdf/JEE-Main-Advanced-P-I-Maths-Paper-with-solution.pdf (Link ...
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 ...
27
votes
1
answer
1k
views
Feeding real or even complex numbers to the integer partition function $p(n)$?
Like most people, when I first encountered $n!$ in grade school, I graphed it, then connected the dots with a smooth curve and reasoned that there must be some meaning to $\left(\frac43\right)!$ — and,...
18
votes
6
answers
9k
views
Prime Partition
A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
6
votes
1
answer
5k
views
Partition an integer $n$ into exactly $k$ distinct parts
I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. ...
4
votes
1
answer
4k
views
Partitions of an integer into k parts.
I am interested in knowing whether an exact formula (analogous to the Hardy-Ramanujan-Rademacher formula for $p(n)$) for the number of partitions of a positive integer into k parts is known. I tried ...
17
votes
2
answers
562
views
Permutation induced by a partition
Let $\lambda$ be a partition of length $n$ and suppose its largest diagonal block, the Durfee square of $\lambda$, has size $r$. By this I mean that $\lambda = (\lambda_1,\ldots,\lambda_n)$ is a non-...
10
votes
2
answers
5k
views
Hardy Ramanujan Asymptotic Formula for the Partition Number
I am needing to use the asymptotic formula for the partition number, $p(n)$ (see here for details about partitions).
The asymptotic formula always seems to be written as,
$$ p(n) \sim \frac{1}{4n\sqrt{...
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(...
6
votes
3
answers
4k
views
Distribution of the sum of $N$ loaded dice rolls
I would like to calculate the probability distribution of the sum of all the faces of $N$ dice rolls. The face probabilities ${p_i}$ are know, but are not $1 \over 6$.
I have found answers for the ...
6
votes
2
answers
5k
views
Same number of partitions of a certain type?
Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, ...
5
votes
3
answers
2k
views
combinatorics: sum of product of integer compositions
I am trying to solve a problem from Stanley's book, it says:
Fix $k,n \in \mathbb{P}$. Show that:
\begin{align}
\sum a_1 a_2 \cdots a_k = \binom{n+k-1}{2k-1}
\end{align}
where the sum ranges over all ...
5
votes
2
answers
4k
views
Keep getting generating function wrong (making change for a dollar) [duplicate]
Possible Duplicate:
Making Change for a Dollar (and other number partitioning problems)
I am working on the classic coin problem where I would like to calculate the number of ways to make change ...
3
votes
2
answers
1k
views
Partitioning $[0,1]$ into pairwise disjoint nondegenerate closed intervals
My friend threw me a challenge. He told me that he proved the follow proposition:
The topological space $[0,1]$ cannot be partitioned into pairwise disjoint nondegenerate closed intervals (except ...
1
vote
2
answers
3k
views
Get all possible partitions of number
Is there a way to get all possible partitions of an integer? Possibly specifying max and/or min summand. I'm interested in partitions themselves, not just partition count.
1
vote
1
answer
1k
views
Generating functions of partition numbers
I don't understand at all why:
\begin{equation}
\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}
\end{equation}
Where $p_n$ is the number of partitions of $n$. Specifically ...
20
votes
1
answer
4k
views
Partition of ${1, 2, ... , n}$ into subsets with equal sums.
The following is one of the old contest problems (22nd All Soviet Union Math Contest, 1988).
Let $m, n, k$ be positive integers such that $m \ge n$ and $1 + 2 + ... + n = mk$. Prove that the numbers $...
15
votes
5
answers
14k
views
Algorithm for generating integer partitions up to a certain maximum length
I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
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 ...
6
votes
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
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?
4
votes
3
answers
2k
views
Number of partitions of $2n$ with no element greater than $n$
The number of partitions of $2n$ into partitions with no element greater than $n$ (copied and slightly adapted from http://mathworld.wolfram.com/PartitionFunctionq.html), so I'm looking for a nice ...
4
votes
3
answers
7k
views
The number of ways to write a positive integer as the sum of distinct parts with a fixed length
I am a topologist and not terribly familiar with the combo literature so please forgive me if this is standard. I'm hoping for some sort of reference for this. Given a positive integer $n$, I wish ...
3
votes
2
answers
1k
views
Partitions with at most k parts, each of at most l
I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify:
$$ P^{(\leq l, \{1,\ldots,k\})}(z) = \frac{(1-...
2
votes
2
answers
748
views
Number of solutions of $x_1 + 2x_2 + 3x_3 + \cdots + n x_n = p$
Given a non-negative integer $p$. What is the number of solutions of $x_1+2x_2+3x_3 + \cdots + nx_n = p$, where the $x_i$'s are non-negative integers.
Can we answer this by using number of solutions ...
2
votes
1
answer
64
views
Why does this connection of increasingly exclusive partitions $P_{n,k}$ to the harmonic series $H_k$ exist?
$\mathbf{SETUP}$
In this previous question, I show how the sum of all cycles of type defined by non-unity partitions of $n$ relates to the derangement numbers / subfactorial $!n$ (number of ...
1
vote
1
answer
1k
views
Combinatorial proof involving partitions and generating functions
Show that any number of partitions of $2r + k$ into $r + k$ parts is the same for any $k$.
I've tried this, but I haven't come up with anything; hence why I have nothing written here. But in any case,...
13
votes
3
answers
19k
views
Calculating integer partitions
A partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. The number of partitions of $n$ is given by the partition function $p(n)$...
11
votes
8
answers
6k
views
How many ways can $133$ be written as sum of only $1s$ and $2s$
Since last week I have been working on a way, how to sum $1$ and $2$ to have $133$.
So for instance we can have $133$ $1s$ or $61$ $s$2 and one and so on. Looking back to the example: if we sum: $1 + ...
11
votes
6
answers
3k
views
Proof of the duality of the dominance order on partitions
Could anyone provide me with a nice proof that the dominance order $\leq$ on partitions of an integer $n$ satisfies the following: if $\lambda, \tau$ are 2 partitions of $n$, then $\lambda \leq \tau \...
9
votes
1
answer
2k
views
Partition Generating Function
a)
Let
$$P(x)=\sum_{n=0}^{\infty} p_nx^n=1+x+2x^2+3x^3+5x^4+7x^5+11x^6+\cdots$$
be the partition generating function, and let $Q(x)=\sum_{n=0}^{\infty} q_nx^n$, where $q_n$ is the number of ...
8
votes
1
answer
1k
views
Elementary proof of Ramanujan's "most beautiful identity"
Ramanujan presented many identities, Hardy chose one
which for him represented the best of Ramanujan. There are many proofs for this identity.
(for example, H. H. Chan’s proof, M. Hirschhorn's proof....
7
votes
2
answers
8k
views
Distribution of the sum of a multinomial distribution
I have distilled an error analysis problem into the following:
I have a multinomial distribution, $X$, consisting of $n$ independent trials where each trial takes on the values $\{0,1,\ldots,k-1\}$ ...
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
1
answer
939
views
Asymptotic behavior of unique integer partitions
Okay, this is one of those questions that I'm sure has a very simple answer I'm missing, and I'd appreciate any push in the right direction.
Consider a very large integer $N$. Stealing an example ...
6
votes
4
answers
50k
views
How many solutions does the equation $x_1 + x_2 + x_3 = 11$ have, where $x_1, x_2, x_3$ are nonnegative integers? [duplicate]
Help me understand problems of this type a bit more intuitively.
The solution $C(3+11−1,11)$ seems simple enough, but I got stuck thinking about how many integers you are choosing from within $x_1$, ...
6
votes
3
answers
1k
views
Counting problem: generating function using partitions of odd numbers and permuting them
We have building blocks of the following lengths: $3, 5, 7, 9, 11$ and so on, including all other odd numbers other than $1$. Each length is available in two colors, red and blue. For a given number $...