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
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
63
votes
1
answer
2k
views
Why are asymptotically one half of the integer compositions gap-free?
Question summary
The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
- 3,199
36
votes
3
answers
2k
views
Very curious properties of ordered partitions relating to Fibonacci numbers
I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon.
We call an ordered ...
- 361
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
34
votes
0
answers
710
views
Visualizing the Partition numbers (suggestions for visualization techniques)
So Ken Ono says that the partition numbers behave like fractals, in which case I'd like to try to find an appropriately illuminating way of visualizing them. But I'm sort of stuck at the moment, so ...
- 5,698
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 ...
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
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
24
votes
1
answer
1k
views
Ellipse 3-partition: same area and perimeter
Inspired by the question,
"How to partition area of an ellipse into odd number of regions?,"
I ask for a partition an ellipse into three convex pieces,
each of which has the same area
and the same ...
- 30.4k
21
votes
3
answers
3k
views
Closed-form Expression of the Partition Function $p(n)$
I feel like I have seen news that a paper was recently published, at most a few months ago, that solved the well-known problem of finding a closed-form expression for the partition function $p(n)$ ...
- 364
20
votes
1
answer
1k
views
On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$
For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since
$4=1+1+1+1=1+1+2=1+3=2+2=4.$
Prove ...
- 1,256
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
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
19
votes
1
answer
1k
views
Can we partition the reciprocals of $\mathbb{N}$ so that each sum equals 1
Let $S = \{1, 1/2,1/3,\dots\}$
Can we find a partition $P$ of $S$ so that each part sums to 1, e.g.
$$P_1 = {1}$$
$$P_2 = { 1/2,1/5,1/7,1/10,1/14,1/70}$$
$$P_3 = {1/3,1/4,1/6,1/9,1/12,1/18}$$
$$P_4 = \...
- 702
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
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
17
votes
1
answer
4k
views
Demystifying the asymptotic expression for the partition function
A partition of an integer $n$ is a way of writing $n$ as a sum of integers. The partition function $p(n)$ counts the number of distinct partitions of $n$.
In 1918, Hardy and Ramanujan proved the ...
user139000
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
17
votes
0
answers
255
views
For what $n$ can $\{1, 2,\ldots, n\}$ be partitioned into equal-sized sets $A$, $B$ such that $\sum_{k\in A}k^p=\sum_{k\in B}k^p$ for $p=1, 2, 3$?
This is a recent problem in American Mathematical Monthly. The deadline for this question just passed:
$\textbf{Problem:}$ For which positive integers $n$ can $\{1,2,3,...,n\}$ be partitioned into ...
- 1,914
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
15
votes
2
answers
373
views
A question on partitions of n
Let $P$ be the set of partitions of $n$. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : f_\...
- 228
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 ...
- 757
15
votes
5
answers
36k
views
Count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$ [duplicate]
How to count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$ such that $x_1\ge 4,x_3 = 11,x_4\ge 7$
And how about $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$
In both cases, $x_1,x_2,x_3,x_4,...
- 2,060
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
14
votes
2
answers
5k
views
For what coinage systems does a greedy algorithm not work in providing change?
For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.
However, for a coinage system with 12 cent coins, a greedy ...
- 3,445
13
votes
2
answers
2k
views
Number of ways to represent any N as sum of odd numbers? [duplicate]
I was solving some basic Math Coding Problem and found that For any number $N$, the number of ways to express $N$ as sum of Odd Numbers is $Fib[N]$ where $Fib$ is Fibonnaci , I don't have a valid ...
- 512
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
13
votes
2
answers
1k
views
What weights should I buy for my gym? (a case of integer partitioning)
I am trying to solve for possible combinations of weights that would be appropriate for use in my home gym. I have been told that this is a case of integer partitioning, but I am not sure how to solve ...
13
votes
1
answer
987
views
Formula for evaluation of character on a transposition
Let $\lambda\vdash n$ be a partition of $n\in\mathbb N$ and $\chi=\chi_\lambda$ the corresponding irreducible character of the symmetric group $S_n$. Denote by $\lambda^t$ be the transpose of $\lambda$...
- 14.9k