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
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)$...
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 $...
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 $...
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, ...
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
4
answers
19k
views
number of ordered partitions of integer
How to evaluate the number of ordered partitions of the positive integer $ 5 $?
Thanks!
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 \...
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,...
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 ...
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{...
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.
...
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 + ...
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 ...
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 ...
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 (...