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 ...
- 465
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 ...
- 901
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 ...
- 497
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 ...
- 271
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 ...
- 293
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 ...
- 153
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 ...
- 427
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; ...
- 40.1k
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!
- 5,622
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)
...
- 175
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 ...
- 5,756
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 ...
- 53
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?...
- 264
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 ...
- 129
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,...
- 6,268
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 ...
- 587
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. ...
- 71
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 ...
user10575
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-...
- 123k
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{...
- 4,660
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(...
- 131
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 ...
- 173
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, ...
- 63
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 ...
- 395
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 ...
- 207
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,453
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.
- 113
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 ...
- 7,418
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 $...
- 383