Questions tagged [integer-partitions]

Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.

Filter by
Sorted by
Tagged with
7
votes
1answer
685 views

Elementary proof of Ramanujan's “most beautiful identity”

Ramanujan presented many identities, Hardy chose one which for him represented the best of Ramanujan. There are many proofs for this identity. (for example, H. H. Chan’s proof, M. Hirschhorn's proof....
7
votes
1answer
178 views

Asymptotic behavior of unique integer partitions

Okay, this is one of those questions that I'm sure has a very simple answer I'm missing, and I'd appreciate any push in the right direction. Consider a very large integer $N$. Stealing an example ...
7
votes
1answer
119 views

What is the significance of this identity relating to partitions?

I was watching a talk given by Prof. Richard Kenyon of Brown University, and I was confused by an equation briefly displayed at the bottom of one slide at 15:05 in the video. $$1 + x + x^3 + x^6 + \...
7
votes
1answer
243 views

Number of Sets of Partitions

I looked at the partitions of numbers, like let's say $n=5$. You get $$ \begin{eqnarray} 5&=&5\\ \hline &=&4+1\\ &=&3+2\\ \hline &=&3+1+1\\ &=&1+2+2\\ \hline &...
7
votes
1answer
247 views

Partitions of a prime power into powers of the same prime

Fix a prime $p$, and $k$ a natural number. The question is then: How many partitions of $p^k$ are there into powers of $p$? So, for instance, if $p = 2$ and $k = 2$, there are 4, namely (4), (2, 2), ...
7
votes
2answers
208 views

For every partition $\pi$ of a fixed integer $n$, $\sum{F(\pi)}=\sum{G(\pi)}$

I need to prove the following question. For every partition $\pi$ of a fixed integer $n$, define $F(\pi)$=number of occurrences of 1 as a summand, and $G(\pi)$=no. of distinct summands in the ...
7
votes
1answer
124 views

Generating function for $r^\binom{n}{2}$

I'm trying to find a closed form of the generating function $$ G(x) = \sum_{n \ge 0} r^\binom{n}{2} x^n $$ for a real number $0 < r < 1$. I found that $G(x) = 1 + xG(rx)$. Any hints where to ...
7
votes
1answer
232 views

Representations of an integer as the sum of other integers

Given a finite set $S$ of (distinct) integers $s_1, \dots, s_n$ and an integer $x$, I'm looking for all representations (where order is important) $$ x=\sum_{i=1}^ks_{t_i} (t_i\in\{1,\dots,n\}) $$ ...
7
votes
1answer
433 views

Creating generating functions for integer partitions

Say I have a generating function $\Phi_\mathcal{A}$ for the set of partitions $\mathcal{A}$ which have no parts congruent to 2 mod 4, and I have the generating function for $\Phi_\mathcal{B}$ for the ...
7
votes
0answers
166 views

Is every positive integer the sum of 1 square number, 1 pentagonal number, and 1 hexagonal number?

I found this interesting conjecture, but maybe I'm not the first to state it. I have tested it for the first $10^4$ positive integers, but that is not a proof. Can anybody prove or disprove this ...
7
votes
0answers
342 views

Is there a connection between the 3D random walk constant and the partition function?

In thinking about this question, I took a look at Pólya's random walk constants and was struck by the fact that an expression for the constant for a three-dimensional random walk, $$\frac3{(2\pi)^3}\...
7
votes
1answer
149 views

Asymptotic of the number of partitions of $n$ into numbers from $\{1, 2, \dots, k\}$

How to find the asymptotic behavior ($n \to +\infty$) of the number $q(n, k)$ of partitions of $n$ into addends from $\{1, 2, \dots, k\}$? I proved that $q(n, k)$ satisfies the recurrent relation $q(...
6
votes
1answer
218 views

When is the sum of first $n$ numbers equal to the sum of the next $k$ numbers?

When is the sum $1+2+\cdots + n = (n+1) + (n+2) + \cdots +(n+k)$? The easiest solution $(n,k)$ is $(2,1)$. For example, $1+2 = 3$. Do any others exist? Roots of $(n+k)^2 + (n+k) = 2n^2 +2n$ give ...
6
votes
7answers
971 views

Book Recommendation for Integer partitions and $q$ series

I have been studying number theory for a little while now, and I would like to learn about integer partitions and $q$ series, but I have never studied anything in the field of combinatorics, so are ...
6
votes
2answers
2k views

Find all ways to factor a number

An example of what I'm looking for will probably explain the question best. 24 can be written as: 12 · 2 6 · 2 · 2 3 · 2 · 2 · 2 8 · 3 4 · 2 · 3 6 · 4 I'm familiar with finding all the prime factors ...
6
votes
2answers
487 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
6
votes
3answers
4k views

Partitions of $n$ into distinct odd and even parts proof

Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts. How do I ...
6
votes
3answers
302 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
6
votes
2answers
5k views

Distribution of the sum of a multinomial distribution

I have distilled an error analysis problem into the following: I have a multinomial distribution, $X$, consisting of $n$ independent trials where each trial takes on the values $\{0,1,\ldots,k-1\}$ ...
6
votes
2answers
3k views

Partitions and Bell numbers

Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks. Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$ Find a formula for $F(...
6
votes
2answers
1k views

Lower bounds for the partition function

In this question we consider the partition function $p(n)$ - that is, the number of ways to express $n$ as a sum of positive integers. One easy exercise is to show that $$ p(n) \geq 2^{\lfloor \sqrt{...
6
votes
2answers
383 views

Is an algebraic formula for the number of cyclic compositions of n known?

From Wikipedia: In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) (...
6
votes
2answers
71 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?...
6
votes
3answers
385 views

Counting problem: generating function using partitions of odd numbers and permuting them

We have building blocks of the following lengths: $3, 5, 7, 9, 11$ and so on, including all other odd numbers other than $1$. Each length is available in two colors, red and blue. For a given number $...
6
votes
1answer
428 views

How to extract coefficient of $x^n$ in an infinite product generating function?

Are there methods for obtaining the coefficient of $x^n$ in a generating function like $$\prod_{i=1}^\infty Q(x),$$ where $Q(x)$ is a rational function? This arises when we want to count partitions of ...
6
votes
1answer
709 views

Using Durfee squares to prove partition identities?

I was surprised to learn of Durfee squares, which can be visually explained as the largest square contained within a partition's Ferrers diagram. Moreover, partition identities have always amused me ...
6
votes
1answer
861 views

Number of ways to sum square numbers to yield a given number

I would like to know how many choices of $x_i$ there are such that $$\sum_{i=1}^{n}x_i^2=m$$ where $n$, $m$ are given. The $x_i$ can be any nonnegative integer and need not be unique and the order is ...
6
votes
1answer
185 views

Why is there a derivative in this formula?

This is a very simple question. Why is Rademacher's formula presented with d/dx in it? Why not just "do" the derivative? Then replace x with n? Is it so there is only one transcendental function ...
6
votes
1answer
118 views

Text about connections between complex analysis and partition theory?

I hope this is enough about maths to ask here. As part of my degree I need to do a project consisting of a 7,000-word report on some area of maths (quite a general guideline). I've noticed in studying ...
6
votes
1answer
178 views

Number of ways to form a partition from another.

Suppose I'm given two partitions of $n = a_1+a_2+\cdots+a_r$ and $n=b_1+b_2+\cdots+b_s$ with $s<r.$ How many ways can I form the second partition by adding elements of the first partition together?...
6
votes
2answers
102 views

Partitions of n that generate all numbers smaller than n

Consider a partition $$n=n_1+n_2+\cdots+n_k$$ such that each number $1,\cdots, n$ can be obtained by adding some of the numbers $n_1,n_2,\cdots,n_k$. For example, $$9=4+3+1+1,$$ and every number ...
6
votes
0answers
64 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 ...
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....
6
votes
0answers
159 views

The smallest non-zero integer $c$ such that $\sum\limits_{n=1}^m\pm(x+n)^6 = c$?

We have the neat equalities, I. Group 1 For $k=2,3,4,5,\dots$ $$\sum_{n=1}^{2^k}\epsilon_n(x+n)^k = 2^{\frac{k(k-1)}{2}}k! = 4,\;48,\;1536,\;\color{brown}{122880},\dots$$ for appropriate $\...
6
votes
1answer
129 views

Flattening Young Tableaux

Let $\lambda=(\lambda_1,\lambda_2,\cdots,\lambda_k)$ be a partition with $|\lambda|=n$ and $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_k$. For any Standard Young Tableaux (SYT) $T$ of shape $\...
6
votes
0answers
71 views

Degree distribution of a graph of integer partitions

Consider a graph whose nodes are the integer partitions of $n$, connected by an edge if you can get from one partition to the other by ‘sliding one square of its Young diagram’ – that is, if one ...
6
votes
0answers
336 views

Invariant element in the tensor product of rectangular Specht modules?

Denote by $\mathfrak{S}_k$ the symmetric group on $k$ elements. Let $\lambda=(n^2\times n)=(n^2,\ldots,n^2)$ be a rectangular partition and $k=n^3$. Denote by $S_\lambda$ the Specht module ...
5
votes
2answers
221 views

How many ways to choose $a<b<c<d<e$ from the set $\{1,2,3,\cdots,100\}$ such that $100<a+b+c+d+e<145$? [closed]

I would appreciate if somebody could help me with the following problem In how many ways can I choose a five number $a,b,c,d,e(a<b<c<d<e)$ from the set $\{1,2,3,\cdots,100\}$ such that $...
5
votes
4answers
2k views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
5
votes
3answers
804 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)$ ...
5
votes
2answers
460 views

Partitions in which no part is a square?

I asked a similar question earlier about partitions, and have a suspicion about another way to count partitions. Is it true that the number of partitions of $n$ in which each part $d$ is repeated ...
5
votes
1answer
572 views

Proving an Inequality Involving Integer Partitions

I am having a bit of trouble beginning the following: Prove that for all positive integers $n$, the inequality $p(n)^2<p(n^2+2n)$ holds, where $p(n)$ is defined as the number of all partitions of $...
5
votes
3answers
3k views

How many combinations of $3$ natural numbers are there that add up to $30$?

How many combinations of $3$ natural numbers are there that add up to $30$? The answer is $75$ but I need the approach. Although I know that we can use $_{(n-1)}C_{(r-1)}$ i.e. $_{29}C_2 = 406$ but ...
5
votes
2answers
207 views

Partition Bijection

I'm not sure what I'm missing. I think I'm thinking too hard about finding this bijection. Please help!
5
votes
2answers
225 views

Congruent division of a shape in euclidean plane

Any triangle can be divided into 4 congruent shapes: http://www.math.missouri.edu/~evanslc/Polymath/WebpageFigure2.png An equilateral triangle can be divided into 3 congruent shapes. Questions: 1) ...
5
votes
1answer
3k views

Number of permutations with a given partition of cycle sizes

Part of my overly complicated attempt at the Google CodeJam GoroSort problem involved computing the number of permutations with a given partition of cycle sizes. Or equivalently, the probability of a ...
5
votes
1answer
199 views

Combinatorial interpretation of $ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j}$?

By logarithmic differentiation, one can deduce that \[ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j} \] where $P_n$ is the $n$-th partition number, and $\sigma(j)$ the sum of the divisors of $j$. I see ...
5
votes
2answers
878 views

Why does $S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$?

I've been trying to get back into some combinatorics, and in my reading, I find that $$ S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1} $$ where the sum is taken over all compositions $a_1+\cdots+a_k=...
5
votes
4answers
951 views

Partition with minimum size of parts

In how many ways can we partition a number $N$? The answer is given by the partition function $p(N)$. So for instance, the partitions of the number $4$ are: \begin{equation} 4; ~~~ 3+1;~~~ 2+2;~~~ 2+1+...
5
votes
1answer
3k views

Partition an integer $n$ into exactly $k$ distinct parts

I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. ...