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
0answers
14 views

Demonstration with Ferrers Diagram (Integer Partitions)

Show, using the Ferrers Diagram, that a perfect square number $n$ will always have a partition with $𝑟$ odd and distinct parts ranging from $1$ to $2𝑟-1$, where $𝑟 = √n$. Explain why the parts are ...
0
votes
1answer
11 views

Partitions with multiplicity locally restricted

I am interested in finding any result, paper, taxonomy, generating function, bijection... on what I call "Partitions with multiplicity locally restricted" that is partitions in which multiplicity of ...
1
vote
0answers
25 views

An interesting way of partitioning with inner ordered combinations

Assume $ K $ labeled blocks $ s_1, s_2, \dots, s_K $ ($ s_1 < s_2 < \dots < s_K $) that arrive sequentially and need to be accomodated as they arrive in $ N $ containers (partitions with ...
0
votes
0answers
24 views

partition function - using each number once and using only odd numbers

1)I was asked to find a partition function , where each number appears only once. for example, for n=2 - 1+1 is not good but 2 is. I think the function is : $\prod\limits_{k=1}^{\infty}(1+q)^k$,...
2
votes
0answers
55 views

Which integer partitions correspond to the most set partitions?

Which integer partitions of n correspond to the most distinct set partitions? For small n where it is feasible to calculate these values for every integer partition and compare, this is a ...
11
votes
0answers
121 views

For what $n$ can $\{1, 2,\ldots, n\}$ be partitioned into equal-sized sets $A$, $B$ such that $\sum_{k\in A}k^p=\sum_{k\in B}k^p$ for $p=1, 2, 3$?

This is a recent problem in American Mathematical Monthly. The deadline for this question just passed: $\textbf{Problem:}$ For which positive integers $n$ can $\{1,2,3,...,n\}$ be partitioned into ...
0
votes
1answer
65 views

Find B(x) such that $A(x) = P(x) \cdot B(x) $

A(x) is enumerator (generating function) of partitions of number such that contain exactly $1$ (but maybe multi times) of $2,3,5$. P(x) is enumerator of all partitions. Find compact pattern for $B(x)$ ...
0
votes
0answers
33 views

Smallest rectangle inscribing Young tableaux

I am interested in knowing the name of any of this characteristics of a Young tableaux (Ferrer's diagram): Smallest rectangle that contains it or the area of such a rectangle. For instance: Partition ...
2
votes
2answers
104 views

Ways of distributing passengers in ships

I need help with the following combinatorial problem. There are $ K $ passengers and $ K $ ships. The passengers are denoted by $ U_1, U_2, \dots, U_K $. The objective is to find in how many ways the $...
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; ...
0
votes
1answer
37 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
62 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
31 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
29 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
100 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
36 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
12 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
40 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
69 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
38 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
49 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
108 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
36 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
71 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
100 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
143 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
116 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
21 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
27 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
79 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
32 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
52 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
39 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
66 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
82 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
36 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)$