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.

2
votes
0answers
12 views

Enumerating integer partitions

There is a natural way to order all $k=1..p(N)$ partitions of a given integer $N$ ($p(N)$ being a total number of partitions) in a "decreasing" order. Say, for $4$: $$ \{4\},\,\{3,1\},\,\{2,2\},\,\{2,...
1
vote
2answers
41 views

Partitioning $[1,v-1]$ into sets of size three such that the sum of each set is $3v/2$

Suppose that $v \equiv 4\;(\bmod 12)$. In general, is it possible to partition the integer interval $[1,v-1]$ into integer partitions of $3v/2$ with three distinct parts (with each part in $[1,v-1]$)? ...
0
votes
1answer
11 views

how is the abs val of excess of p(n|odd # of parts) OVER p(n|even #of parts) = p(n|distinct odd parts?)

A question in The Elementary Theory Of Partitions asks the reader to show that the absolute value of excess of the number of partitions $n$ with an odd number of parts over the number of those with an ...
0
votes
2answers
70 views

Number of partitions of $n$ formed by combinations of $2$ and $4$

I'm trying to find the number of partitions of a natural number that are a combination of $2$ and $4$. For example: $$6 = 2+2+2 = 2+4 \Rightarrow p_6 = 2$$ So I start by defining $p_n$ as the ...
0
votes
1answer
33 views

Result on partitions with distinct odd parts

Let $pdo(n)$ be the number of partitions of n into distinct odd parts. Then $p(n)$ is odd if and only if $pdo(n)$ is odd. I am well aware that a proof of this is available here but I want to do it ...
0
votes
0answers
23 views

Finding a specific case for the partitions of $n$

A generating function for the total number of partitions of $n$ is: $$\prod_{i=1}^n\sum_{j=0}^n x^{ij}$$ The polynomial generated by this generating function will have some term $x^n$, the coefficient ...
0
votes
2answers
20 views

Partitioning evens as sum of evens

Take the set $\{a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8\}$. We can partition according to rules. Every member in the partition has even number of elements. Every member in partition have to be consecutive. ...
5
votes
2answers
59 views

Average length of partitions

I'm wondering if there's a known asymptotic for an average number of terms for partitions of a given number? (I mean, given all the partitions of a given number, how many terms do they have on average?...
1
vote
2answers
51 views

How many nonnegative integral solutions for this equation $a+b+c+d=24$ with given conditions $a \leq b \leq c \leq d$ [closed]

Find number of non negative integral solutions to this equation $$a+b+c+d=24$$ such that $a⩽b⩽c⩽d$.
1
vote
1answer
35 views

No. Of ways of folding a paper strip

You have given a strip which is divided into n+1 identical parts by n folds on the strip. Now find the no. Of ways in which you can fold the whole strip into a single identical part..!
2
votes
1answer
48 views

A question on an identity involving partition

Let $n$ be a natural number. Let $\lambda \mapsto n$ , be a partition of n. So $\lambda=(\lambda_1, \lambda_2, \ldots ,\lambda_k)$, with $\lambda_1\leq \ldots \leq \lambda_k$, and $\sum_{i=1}^k \...
4
votes
4answers
219 views

A formula on partitions

Suppose that $\lambda,\mu$ are integer partitions, with conjugates $\lambda^*,\mu^*$. Could you help me to prove the following formula, please? $\sum_{i,j}\mathrm{min}(\lambda_i,\mu_j)=\sum_k\...
4
votes
2answers
66 views

Identity from integer partitions and Ferrers diagrams

So the problem I'm working on is as follows: Let $\lambda$ and $\mu$ be integer partitions, and let $\lambda^*$ and $\mu^*$ be their conjugates. By counting a set in two ways, prove $\sum_{i,j}\min\{\...
2
votes
2answers
81 views

Solving combinatorial problems with symbolic method and generating functions

I am trying to solve the following problems: a) Let $\mathcal{F}$ be the family of all finite 0-1-sequences that have no 1s directly behind each other. Let the weight of each sequence be its length. ...
0
votes
1answer
19 views

Why does this definition of the 3-PARTITION problem imply that every set contains exactly 3 elements?

I have the following definition of the 3-PARTITION problem taken from this paper: https://www.sciencedirect.com/science/article/pii/0166218X93900853 Given $3m$ positive integers $a_1, a_2,...,a_{3m}$ ...
4
votes
1answer
100 views

Partitions of $2n$ and factorizations of $n$

Let $n$ be any positive integer. Let $p_1,p_2,...,p_m$ be any positive integers such that no more than one of the $p_i$s is $1$ and $\prod_{i=1}^mp_i=n$. Finally, let $s_1,s_2,...,s_m$ be any ...
1
vote
1answer
32 views

Gen func “The number of partitions of n where each part occurs 2, 3, 5 times = number of partitions of n…”

The number of partitions of n where each part occurs 2, 3, 5 times = number of partitions of n with parts modulo 2,3,6,9,10 modulo 12 This is from Subbarao 1971 but I don't quite understand the ...
0
votes
2answers
41 views

combinatorics - self-conjugate partitions

Use Ferrers diagrams to show bijectively that the number of self-conjugate partitions of $n$ is the same as the number of partitions of $n$ whose parts are odd and distinct. An example of the latter ...
5
votes
3answers
786 views

Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)

Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
3
votes
1answer
94 views

How to count all the solutions for $\sum\limits_{i=1}^{n} \frac{1}{2^{k_i}}= 1$ for $k_i\in \Bbb{N}$ and $n$ a fixed positive integer?

After reading this question, I would like to just count all solutions for: $$\frac{1}{2^{k_1}} + \frac{1}{2^{k_2}} + \frac{1}{2^{k_3}} + \dots + \frac{1}{2^{k_n}}=1$$ for $k_i\in \Bbb{N}$ (we can ...
6
votes
0answers
138 views

Almost a prime number recurrence relation

For the number of partitions of n into prime parts $a(n)$ it holds $$a(n)=\frac{1}{n}\sum_{k=1}^n q(k)a(n-k)\tag 1$$ where $q(n)$ the sum of all different prime factors of $n$. Due to https://oeis....
0
votes
0answers
29 views

Does the problem of finding minimal weighted sums above a threshold have a name?

Does the following problem have a name? Let $N$ be a positive integer (the threshold) and let $V$ be a set of positive integers. A weighting is a function from $V$ to non-negative integers, ...
1
vote
0answers
33 views

Combinatorial proof of the formula for hook-length

Let $\lambda=(\lambda_1,...,\lambda_n)$ be a partition. My goal is to prove the following formula $$\sum\limits_{x\in\Lambda}(h(x)^2-c(x)^2)=|\lambda|^2,$$ where for $x=(i,j)\in\Lambda:=\{(i,j)\in\...
2
votes
1answer
458 views

Matrix representation of a partition

Is there a natural way to represent all the partitions of an integer set $\{1,2,3,...,n\}$ as a matrix in the similar way permutations can be mapped to group of matrices?
1
vote
0answers
12 views

Integer partition - relation for Frobenius coefficients [duplicate]

Suppose we have a partition $$\lambda =(\lambda_1,...,\lambda_n)=(\alpha_1,...,\alpha_r|\beta_1,...,\beta_r)$$ written in the Frobenius notation. I am trying to prove the following relation $$\sum\...
3
votes
0answers
20 views

Hook-length for partitions

Let $\lambda=(\lambda_1,...,\lambda_r,...)$ be a partition (i.e. $\lambda_i\ge \lambda_{i+1}$ and there are only finitely many non-zero terms.) Let $\lambda'$ be a conjugate partition, i.e. $\lambda_i'...
1
vote
1answer
48 views

Time complexity of finding the largest Goldbach partition

Suppose we are given a large even integer $N$, and we want to determine primes $p$ and $q$ such that $N = p + q$, subject to the conditions that $p \geqslant q$ and $p - q$ is as small as possible. (...
1
vote
0answers
25 views

Converse of a proof

Let $\pi$ be the partition of $n=a_1+a_2+...+a_r$, where $a_1\geq a_2 \geq ....\geq a_r\gt0$ and $\pi$’ be the partition, $n=b_1+b_2+....+b_s”.$Prove that $\pi$’ is the conjugate of $\pi$ if and only ...
0
votes
1answer
36 views

proof about one of the claims in Partition

Can anyone explain or prove to me why the claim of partition that the "number of partitions of $n$ is equal to the number of partitions of $2n$ with $n$ parts" is true, thanks.
1
vote
2answers
78 views

Forms of sum $\frac{n(n+1)}{2}$ with natural numbers.

How many ways are there of sum $\frac{n(n+1)}{2}$ with $n$ addends? Knowing than $i$ appears at most $n+1-i$ times. I really haven't had any important ideas. When speaking of a fixed number of ...
0
votes
1answer
28 views

Understanding the following steps

I asked the following question . Let $\pi$ be the partition of $n=a_1+a_2+...+a_r$, where $a_1\geq a_2 \geq ....\geq a_r\gt0$. Prove that number of partition $\pi$ of $n$ with $a_r=1$ and $a_j-a_{j+1}$...
1
vote
1answer
44 views

Number of partitions of a number into distinct parts.

Let $\pi$ be the partition of $n=a_1+a_2+...+a_r$, where $a_1\geq a_2 \geq ....\geq a_r\gt0$. Prove that number of partition $\pi$ of $n$ with $a_r=1$ and $a_j-a_{j+1}$ = 0 or 1 for $1\leq j\leq r-1$ ...
3
votes
1answer
76 views

The number of ways, $sf_2(n)$, to express an integer as the sum of two square-free integers.

It is well known that $$\sum_{n\leq x}\mid \mu(n) \mid \sim \frac{6}{\pi^2}x\left(1+o(1)\right) \text{, } x \to \infty$$ From here it follows that every sufficient large integer may be expressed as ...
1
vote
1answer
37 views

Showing two partitions to be equal

I was posed with the following problem " Let $F(n)$ denote the number of partitions of $n$ with every part appearing at least twice and $G(n)$ denote the number of partitions of $n$ into parts larger ...
1
vote
0answers
14 views

Partitioning integer with subtraction allowed

Let's imagine you want to get a number $A$ from a set of number $M$. You might use only +/- between the numbers and your job is to determine, whether it's possible to get the result $A$ or not. So ...
0
votes
2answers
64 views

To prove identity $P(n,3)= \lfloor n^2/12 \rfloor$

Suppose $P(n,k)$ is number of partitions of positive integer n by k positive integers with no duplicative tuples. And $\lfloor r\rfloor$ is largest of integers equal or less than real number $r$ If $...
0
votes
1answer
35 views

Is my answer correct? Partitioning numbers

How many ways are there to write the number 7 with the summands: 1, 2, and 3? For example, there are 7 ways to write the number 4: {1 + 1 + 1 + 1} x 1 {2 + 1 + 1} x 3 {3 + 1} x 2 {2 + 2} x 1 I ...
2
votes
1answer
301 views

Ramanujan's congruence.

There are the following formula in this link(https://en.wikipedia.org/wiki/Ramanujan%27s_congruences). $$\sum_{k=0}^{ \infty } p(5k+4)q^k = 5 \frac{(q^5)_{\infty}^{5}}{(q)_{\infty}^{6}}.$$ $$\...
1
vote
1answer
33 views

Calculating all non repeating ordered partitions in an interval

I need to calculate in how many ways can I add the integers in the interval $[1,9]$ in groups of $P$ elements, so that they sum to $N$. The set of groups must not contain sums that have the same ...
0
votes
2answers
33 views

Combinatorics-Partitions of Natural Numbers

Let $R(r,k)$ denote the number of partitions of the natural number $r$ into $k$ parts. Show that $R(r,k)=R(r-1,k-1)+R(r-k,k)$ Show that $R(n-r,1)+R(n-r,2)+R(n-r,3)+...R(n-r,r)=R(n,r)$
0
votes
1answer
33 views

Number of ordered partitions of N into K distinct parts modulo P

I've come across a combinatorics problem where I'm fairly certain that a solution exists, yet I'm unable to find it. I'm trying to find the number of vectors $(x_1,x_2,...,x_n)$ such that $\sum x_i ...
1
vote
0answers
37 views

Writing down consecutive natural numbers until a certain number of digits $k$ is reached.

A person starts writing consecutive natural numbers from $5$ until $k$ digits are reached. For some values of $k$, this will be impossible, for example $6$ or $8$ are impossible as then after writing ...
2
votes
1answer
29 views

Finding all natural number solution(s) to linear Diophantine equation of three variables

Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end. For those curious, this puzzle comes from the game West of Loathing. It's ...
-1
votes
2answers
46 views

Nine objects in non-empty boxes [closed]

In how many ways 9 identical objects can be put in non-empty boxes of arbitrary size? Is solution integer partition of 9? That is 30?
2
votes
2answers
109 views

Proof of an identity about integer partition

I'd like to know how to prove the following identity, $$\sum_{k=1}^n k\, p(n, k) = \sum_{r,s\ge 1, rs\le n} p(n-rs)$$ where $n\in N^+$. Here, $p(n)$ counts the number of possible partitions of $n$. ...
3
votes
2answers
74 views

Decomposing an integer number into up to N (not necessarily prime) numbers with minimal sum

I am writing a program that processes data based on an integer factor. The process can either be done at once, or in multiple stages. For example, one stage with factor 500 could be replaced by three ...
0
votes
0answers
13 views

On some constrained partitions of $ k $-multiperfect numbers

Let $ n $ be a $ k $ -multiperfect number. Do we know an upper bound for the number of partitions of $ n $ whose all summands are at the same time multiples of $ k $ and the sum of distinct ...
1
vote
1answer
186 views

partitions of positive integer $n$ with respect to a multiset

Recently, I think on a new problem related to partitions. Let $n$ be a non-negative integer and $\mathbb{A}=\{a_1,\ldots,a_k\}$ be a multiset with $k$ not necessarily distinct positive integers. We ...
3
votes
1answer
72 views

Combinatorial Proof that $p(n)/(1+\epsilon)^n \to 0$

I was thinking this morning about the identity $ \prod_{n=1}^{\infty} \left( \frac{1}{1-q^n} \right) = \sum_{n=0}^{\infty} p(n) q^n$. The product on the left converges for $|q|<1$, which implies ...
2
votes
1answer
30 views

Understanding Graham's proof of theorem on Unit Fractions.

In this paper by Ronald Graham, the theorem that every integer greater than 77 has a partition with the property that the sum of the reciprocals of the various "piles" in the partition is 1 (lovely!). ...