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
12
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)$...
- 4,687
12
votes
2
answers
1k
views
Error in solution of Peter Winkler "red and blue dice" puzzle?
This question relates to the solution give in Peter Winkler's Mathematical Mind-Benders to the "Red and Blue Dice" problem appearing on page $23.$
You have two sets (one red, one blue) of $...
- 53.3k
12
votes
1
answer
1k
views
Bijection for $q$-binomial coefficient
Define the $q$-binomial (Gaussian) coefficient ${n+m\brack n}_q$ as the generating function for integer partitions (whose Ferrers diagrams are) fitting into a rectangle $n\times m$, i.e., for the set $...
- 3,748
12
votes
2
answers
363
views
Number of ways to partition $40$ balls with $4$ colors into $4$ baskets
Suppose there are $40$ balls with $10$ red, $10$ blue, $10$ green, and $10$ yellow. All balls with the same color are deemed identical. Now all balls are supposed to be put into $4$ identical baskets, ...
- 197
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 + ...
- 149
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
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 \...
- 113
11
votes
2
answers
309
views
Identity involving pentagonal numbers
Let $G_n = \tfrac{1}{2}n(3n-1)$ be the pentagonal number for all $n\in \mathbb{Z}$ and $p(n)$ be the partition function. I was trying to prove one of the Ramanujan's congruences: $$p(5n-1) = 0 \pmod 5,...
- 4,270
10
votes
3
answers
3k
views
Number of partitions of $50$
Does someone know the number of partitions of the integer $50$? I mean, in how many ways can I write $50$ as a sum of positive integers?
I know that there's a table by Euler, which is useful to know ...
- 315
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
10
votes
1
answer
228
views
Unexpected result on the number of permutations with a restriction.
Let $p=(p_1,p_2,\dots,p_n)$ be a weak composition of a positive integer number $n$ into $n$ non-negative integer parts and let $k_i$ be the count of the part $i$ ($i=0,1,2,\dots$) in the composition.
...
- 26.7k
10
votes
3
answers
990
views
Integer Partition Refinement in Sage
A partition of an integer $n$ is a non-decreasing list of positive integers summing to $n$. For example, $3$ can be partitioned as $1 + 1 + 1$, $1 + 2$ or just $3$, but $2 + 1$ is indistinct from $1 + ...
- 25.8k
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 ...
- 287
9
votes
2
answers
264
views
P-graph of partition elements of 100 under common divisibility relation
Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than ...
- 1,162
9
votes
2
answers
401
views
Combinatorial puzzle reminiscent of knapsack problem. Is this classic?
I have $n$ red integers $a_1,\ldots,a_n$ (not necessarily distinct), all with $1\leq a_i\leq n$. I also have $n$ blue integers $b_1,\ldots,b_n$ with same constraints. I want to show that there is a (...
- 323
9
votes
1
answer
2k
views
Recurrence for the partition numbers
I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in ...
- 193
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
9
votes
3
answers
1k
views
Putnam Problem: Partitioning integers with generating functions
We were given the following A-1 problem from the 2003 Putnam Competition:
Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, $$ n= a_1+a_2+ \...
- 1,411
9
votes
1
answer
742
views
Young projectors in Fulton and Harris
In Section 4 of Fulton and Harris' book Representation Theory, they give the definition of a Young tableau of shape $\lambda = (\lambda_1,\dots,\lambda_k)$ and then define two subgroups of $S_d$, the ...
- 25.2k
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