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
33 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; ...
0
votes
1answer
34 views

Number of Partitions of 𝑛 No Part Appears Exactly Once

So I am having a little trouble here. The question is "Let $r_n$ be the Number of Partitions of $n$ No Part Appears Exactly Once. Find the generating function." I realize there is already an answer ...
6
votes
0answers
61 views

Faa di Bruno's formula and alternating functions

Suppose you have a function $f(x)$ such that ${\rm sgn}\Big(\frac{d^k}{dx^k}\big(f(x)\Big) = (-1)^k$ and a function $g(x)$ such that ${\rm sgn} \Big(\frac{d^k}{dx^k}g(x)\Big) = (-1)^{(k+1)}$, $\forall ...
0
votes
1answer
27 views

Number of ways to divide $n$ into parts that are not divisible by $r$.

Prove that the number of ways to divide $n$ into summands so that no number included in the sum more than $r − 1$ times, equal to the number of ways to divide $n$ into parts that are not divisible by $...
0
votes
0answers
17 views

Recurrence relation for partition function for pentagonal numbers.

I know the following theorems. Theorem 1 $:$ For $|x|<1$ we have $$\prod\limits_{k=1}^{\infty} \frac {1} {1-x^k} = 1 + \sum\limits_{k=1}^{\infty} p(k)x^k.$$ Theorem 2 $:$ For $|x|<1$ we have $...
0
votes
0answers
28 views

Clarification of the proof of Euler's identity regarding the generating function for partitions.

In reference to this question which I asked here couple of days back but didn't get any answer I am posting this question to clarify whether we can able to extend Euler's identity regarding the ...
4
votes
1answer
95 views

How to extend Euler's identity regarding partition on the unit disk?

Theorem (Euler) $:$ For $|x|<1$ we have $$\prod\limits_{m=1}^{\infty} \frac {1} {1-x^m} = \sum\limits_{n=0}^{\infty} p(n) x^n,$$ where $p(n)$ denotes the number of partitions of $n$ for $...
0
votes
1answer
36 views

A Question related to probability.

Question is described here last question G1† Solution is here last solution Please explain the solution in simple language. And please explain how to do it using partition. My approach using ...
2
votes
0answers
35 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
44 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
38 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
25 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
65 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
36 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
53 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
98 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
35 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
61 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
98 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
140 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
111 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
46 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
65 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
81 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
35 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
40 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
31 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
77 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
76 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 ...