# Questions tagged [integer-partitions]

Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.

116 questions
20k 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 one quoted ...
15k 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 ...
4k 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 ...
4k 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 ...
2k 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 ...
2k 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?...
774 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 ...
4k 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 ...
3k 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 ...
4k 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 ...
170 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 ...
2k 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 ...
3k 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. ...
928 views

### Generating functions of partition numbers

I don't understand at all why: $$\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}$$ Where $p_n$ is the number of partitions of $n$. Specifically ...
4k 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) ...
183 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-...
31k 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 ...
475 views

### How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
901 views

### Number of partitions of $2n$ with no element greater than $n$

The number of partitions of $2n$ into partitions with no element greater than $n$ (copied and slightly adapted from http://mathworld.wolfram.com/PartitionFunctionq.html), so I'm looking for a nice ...
3k 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, ...
6k views

### The number of ways to write a positive integer as the sum of distinct parts with a fixed length

I am a topologist and not terribly familiar with the combo literature so please forgive me if this is standard. I'm hoping for some sort of reference for this. Given a positive integer $n$, I wish ...
680 views

6k views

### Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
4k views

### 1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,… (partition numbers): What is the recurrence relation / recursive formula / closed formula for this?

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
224 views

### Shifted Young tableaux & Hook numbers & Bulgarian Solitaire

I would like to find articles or documentation regarding this process: Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
1k views

69 views

### How To Apply and Understand the Generating Function for Number Partitioning

The function p(n) counts the number of ways a number can be made up of smaller numbers. For example, the p(5) = 7 because you ...
234 views

### Partitioning the edges of $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs

Why is it impossible to partition the edges in $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs for $n \ge 6$? I'm just stuck at the beginning and can't figure out how to go about this problem. ...
74 views

### Construct matrix of ones and zeros based on sequences

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers. Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and zeros("0"...
170 views

### Sums of Consecutive Cubes (Trouble Interpreting Question)

Show that it is possible to divide the set of the first twelve cubes $\left(1^3,2^3,\ldots,12^3\right)$ into two sets of size six with equal sums. Any suggestions on what techniques should be used to ...