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
29 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
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
1answer
35 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
2answers
22 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
60 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
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..!
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$.
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 \...
2
votes
2answers
83 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}$ ...
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
46 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 ...
3
votes
1answer
95 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\...
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\...
4
votes
1answer
101 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 ...
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
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 ...
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$ ...
1
vote
1answer
38 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 ...
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
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)$
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?
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 ...
3
votes
1answer
73 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!). ...
0
votes
2answers
26 views

limit of ratio of partition function

Does the following limit exists? $$\lim_{n \rightarrow \infty} \frac{p(n)}{p(n-5)}$$ where $p(n)$ denote the partition function. If this limit exists, is it equal to 1? Kindly share your thoughts....
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
2answers
32 views

Limit the maximum value of the composition of an integer

I was doing a coding test (already finished, so no cheating for me) and came across this problem, which I'll describe in few steps: We have a keypad, like on cellphones, with keys from 1 to 9, where ...
2
votes
0answers
51 views

An upper bound for integer partitions with unique summands

Let $p_\neq (n)$ be the number of all partitions of $n$ such that all summands are distinct (for example $p_\neq (6)=4$). How do we show that $p_\neq (n) \leq e^{2\sqrt n}$?
1
vote
1answer
32 views

Verifying that $ \prod_{j=1}^{\infty} \frac{1}{1-q^j} = \prod_{j=1}^{\infty} \frac{1}{(1-q^{2j-1})(1-q^{2j})}$

On page 165 of Chapter 13, how was the equality made from line 1 to line 2? https://archive.org/details/NumberTheory_862/page/n173 Namely, how $$ \prod_{j=1}^{\infty} \frac{1}{1-q^j} = \prod_{j=1}^{\...
2
votes
1answer
48 views

Find Integer Partition using only integers belonging to S = { 1, 2, 3 }

I spent all afternoon looking for this but I wasn't able to find anything, so... Is there a formula to know the NUMBER of partitions with a constraint on the integer domain ? E.g.: Find the number of ...
0
votes
0answers
29 views

Relation between partitions of $n$ into $k$ distinct parts and partitions of $n$ into at most $k$ parts [duplicate]

I'm working on a problem that I'm completely stuck on: Let $Q(n,k)$ be the number of partitions of $n$ into $k$ distinct (unequal) parts. Prove that the number of partitions of $n$ into at most $k$ ...
11
votes
2answers
846 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 $n\ n-$...
0
votes
1answer
53 views

Number of Partitions of n into 4 parts equals the number of partitions of 3n into 4 parts of size at most n-1.

Let $n\geq 4$. Prove that the number of partitions of $n$ into 4 parts equals the number of partitions of $3n$ into 4 parts of size at most $n-1$. I am stuck on this problem but I suspect I need to ...
4
votes
1answer
57 views

Ramanujan congruence mod 7

Hello I am trying to prove this congruence: $$P(7n+5)\equiv 0 \pmod{7}$$ In order to do that I have done the next thing: We have that $\displaystyle\sum_{n\geq0}\;P(n)q^{n}=\frac{1}{(q;q)_{\infty}}...
0
votes
1answer
36 views

What is the appropriate weight ($W_k$) (for two arbitrary partitions)?

I already asked a similar question, And from the answer I received, another question came to my mind. A positive integer can be partitioned, for example, the number 7 can be partitioned into the ...