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.

0
votes
1answer
17 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
27 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
25 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
87 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
130 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
31 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
11 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
90 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 ...
0
votes
0answers
50 views

Partition the integer $10$ into distinct parts such each part is at most $10$.

The expression $$(1+x)(1+x^2) .... (1+x^{10})$$ is the Generating function of partition the integer $n$ into distinct parts such each part is at most $10$. If we put this in a CAS, we can get the ...
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
75 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
42 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
34 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
60 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
33 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
74 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
32 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
32 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
35 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
26 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
44 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
73 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
70 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
28 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
31 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
31 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
50 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
31 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
44 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
27 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
840 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
47 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
55 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
35 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 ...
1
vote
1answer
51 views

Partitions in Combinatorics

Let $2\leq k\leq n$. Prove that $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$ where $p_k(n)$ is the number of partitions of $n$ into $k$ pieces. Here's my proof: Proof: Let $2\leq k\leq n$. Let $p_k(n)$ be the ...
3
votes
1answer
48 views

Is this true for every partitioning?

I have two categories (category1 and category2 ) and The size of both categories is equal to each other. if we partition each categories arbibtrary .Is this proposition proven? or rejected? $n_T \...
0
votes
0answers
35 views

Expected number of parts of a uniformly selected partition of $n$

I have a very basic question on partition theory, which I feel should be very well known. Suppose that you fix a natural number $n$ and select a random partition $P$ of $n$ by choosing uniformly from ...
1
vote
1answer
79 views

Combinations of flowers using the counting method for integer partitions.

I have this problem to complete that wants to know how many combinations of flowers can there be in a bouquet of 25 flowers, such that: $r+c+d+t=25$ where $r=$roses, $c=$carnations, $d=$daisies and $...
1
vote
1answer
39 views

What is the coefficient of $ x^{i}$ in the product $ \ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq 1} \frac{1}{1+x^{2i-1}}$?

What is the coefficient of $ x^{i}$ in the product $ \ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq 1} \frac{1}{1+x^{2i-1}}$? Answer: $\ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq ...
0
votes
0answers
36 views

Generating Function for partition of r into distinct parts

My combinatorics class is learning about generating functions and partitions of numbers into summands. One exercise we are working on for tomorrow's lecture to better understand the concept is to find ...
0
votes
1answer
33 views

show number of partitions of $n$ equals to number of partitions of $n-k$

Let $n,k\in\mathbb{Z}^+$ and $n\geq k$. Suppose $n = \lambda_1 + \lambda_2 + \cdots + \lambda_k$ is an integer partition of $n$, and $\lambda_1 \geq\lambda_2\geq\cdots\geq\lambda_k$. Show (the number ...
-1
votes
1answer
735 views

Represent $N$ as the sum of exactly $K$ distinct positive integers

You are given two integers $N$ and $K$. Find all ways to represent $N$ as the sum of exactly $K$ distinct positive integers $x_1,x_2, \ldots,x_K$ — in other words. $xi_>0$ for each valid $i$; ...
0
votes
0answers
234 views

Partition a number $n$ in exactly sum of $k$ distinct numbers such that product of the numbers should be maximum.

The question is to partition a given number $n$ in exactly sum of $k$ distinct positive numbers such that the product of $k$ distinct number become maximum. $k$ will be given optimally so that it will ...
0
votes
1answer
51 views

Question on generating function of integer partitions

How can I show that $$\prod_{k \ge 1}(1+z^{2k}) = \prod_{k \ge 1}(1+z^k+z^{2k}+z^{3k}) \quad ?$$ I have worked on this for a while and I am even doubting that maybe both are not equal