Questions tagged [integer-partitions]
Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.
1,430
questions
89
votes
7
answers
164k
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