Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [integer-partitions]

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

27
votes
7answers
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 ...
14
votes
1answer
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 ...
9
votes
2answers
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 ...
10
votes
2answers
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 ...
10
votes
2answers
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 ...
2
votes
3answers
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?...
14
votes
5answers
780 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 ...
6
votes
3answers
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 ...
3
votes
1answer
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 ...
15
votes
5answers
5k 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 ...
2
votes
1answer
176 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 ...
5
votes
1answer
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. ...
4
votes
2answers
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 ...
1
vote
1answer
969 views

Generating functions of partition numbers

I don't understand at all why: \begin{equation} \sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1} \end{equation} Where $p_n$ is the number of partitions of $n$. Specifically ...
12
votes
2answers
195 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-...
18
votes
1answer
637 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 $...
2
votes
3answers
33k 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 ...
1
vote
1answer
5k 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) ...
6
votes
2answers
482 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 ...
4
votes
2answers
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, ...
4
votes
3answers
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 ...
4
votes
3answers
913 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 ...
3
votes
2answers
724 views

Partitions with at most k parts, each of at most l

I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify: $$ P^{(\leq l, \{1,\ldots,k\})}(z) = \frac{(1-...
2
votes
2answers
443 views

Partitioning $[0,1]$ into pairwise disjoint nondegenerate closed intervals

My friend threw me a challenge. He told me that he proved the follow proposition: The topological space $[0,1]$ cannot be partitioned into pairwise disjoint nondegenerate closed intervals (except ...
1
vote
1answer
647 views

Combinatorial proof involving partitions and generating functions

Show that any number of partitions of $2r + k$ into $r + k$ parts is the same for any $k$. I've tried this, but I haven't come up with anything; hence why I have nothing written here. But in any case,...
11
votes
5answers
10k views

Algorithm for generating integer partitions

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 ...
11
votes
8answers
5k 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 + ...
3
votes
4answers
18k views

How many solutions does the equation $x_1 + x_2 + x_3 = 11$ have, where $x_1, x_2, x_3$ are nonnegative integers?

Help me understand problems of this type a bit more intuitively. The solution $C(3+11−1,11)$ seems simple enough, but I got stuck thinking about how many integers you are choosing from within $x_1$, ...
25
votes
1answer
855 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,...
3
votes
3answers
1k views

Distribution of the sum of $N$ loaded dice rolls

I would like to calculate the probability distribution of the sum of all the faces of $N$ dice rolls. The face probabilities ${p_i}$ are know, but are not $1 \over 6$. I have found answers for the ...
7
votes
1answer
3k 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\...
5
votes
1answer
564 views

Proving an Inequality Involving Integer Partitions

I am having a bit of trouble beginning the following: Prove that for all positive integers $n$, the inequality $p(n)^2<p(n^2+2n)$ holds, where $p(n)$ is defined as the number of all partitions of $...
3
votes
1answer
56 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; ...
3
votes
2answers
785 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
3
votes
3answers
1k 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 \...
2
votes
2answers
254 views

Counting set for generating functions

Give a proof of the following identity by counting two sets of partitions in two different ways. \begin{equation*} \prod_{i\geq 0}(1+x^{2i+1})=1 + \sum_{n\geq 1}x^{n^2}\prod_{j=1}^n\...
4
votes
1answer
182 views

Partition problem for consecutive $k$th powers with equal sums (another family)

This is the partition problem as applied to a special set, namely the first $n$ $k$th powers. Assume the notation, $$[a_1,a_2,\dots,a_n]^k = a_1^k+a_2^k+\dots+a_n^k$$ I. Family 1 The following ...
4
votes
2answers
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 ...
4
votes
2answers
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 ...
1
vote
1answer
378 views

Combinatorics problem based on Ferrers graph

Need help with this proof using Ferrers' graph or otherwise. Show that the number of partitions of $r+k$ into $k$ parts is equal to The number of partitions of $r + {k+1 \choose 2}$ into $ k $ ...
1
vote
3answers
1k views

Frobenius coin problem

Suppose that you only have coins worth, say 3 and 5 euros. According to Sylvester result we can find the Frobenius nr $g(3,5)=15-3-5=7$ so 7 is the largest integer that cannot be written as $a_{1}k_{1}...
1
vote
1answer
962 views

Prove : $p$(n│even number of ODD parts)=$p$(n│distinct parts ,number of ODD parts is even )

I'm trying to prove the following Integer Partition claim : $p$(n│even number of ODD parts) = $p$(n│distinct parts ,number of ODD parts is even) . So I tried to prove a stronger claim : $p$(n│...
1
vote
0answers
225 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 ...
6
votes
2answers
3k views

Partitions and Bell numbers

Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks. Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$ Find a formula for $F(...
4
votes
1answer
76 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 ...
2
votes
1answer
98 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"...
1
vote
1answer
269 views

Total number of solutions of an equation

What is the total number of solutions of an equation of the form $x_1 + x_2 + \cdots + x_r = m$ such that $1 \le x_1 < x_2 < \cdots < x_r < N$ where $N$ is some natural number and $x_1, ...
1
vote
3answers
180 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 ...
1
vote
1answer
240 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. ...
0
votes
1answer
401 views

Friendly graph partitioning

The question is from the "Introduction to Algorithm" 3rd edition: B-2 Friendly graphs: Reword the following statements as a theorem about undirected graphs, and then prove it. Assume that friendship ...