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.

23
votes
0answers
528 views

Visualizing the Partition numbers (suggestions for visualization techniques)

So Ken Ono says that the partition numbers behave like fractals, in which case I'd like to try to find an appropriately illuminating way of visualizing them. But I'm sort of stuck at the moment, so ...
9
votes
0answers
133 views

Closed form for $\sum_{n=1}^\infty \frac{1}{P(n)}$, where $P(n)$ is the partition function.

Is there a closed form for the following infinite series? $$\sum_{n=1}^\infty \frac{1}{P(n)}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...$$ where $P(n)$ is the partition function.
8
votes
0answers
567 views

Partitions of 13 and 14 into either four or five smaller integers

There are exactly 18 partitions of the integer 13 into 4 parts, as on the left of the table, and also 18 partitions into 5 parts, as on the right of the table: $$\begin{array}{c|c} 10+1+1+1 & 9+1+...
8
votes
0answers
506 views

Young Tableaux as Matrices

These questions are motivated only by curiosity. Take a Young tableau of shape $(\lambda_1,\lambda_2,\ldots,\lambda_n)$, where $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Is there any ...
7
votes
0answers
161 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
133 views

Inequality for hook numbers in Young diagrams

Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$ define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $...
7
votes
0answers
340 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}\...
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....
6
votes
0answers
153 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
0answers
70 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
334 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
0answers
96 views

How was this result for integer partitions found

If you look at one of the comments on A053445 you'll see it mentions that the second difference of partition numbers is equivalent to the number of integer partitions with two largest parts equal and ...
5
votes
0answers
237 views

Proof of these identities

The following is a screenshot from a paper by Daniel B. Grunberg called On asymptotics, Stirling numbers, Gamma function, and polylogs. I only offer the page as a reference to explain equation 3.1. ...
5
votes
0answers
280 views

Sum over subsets of a multiset

I have a sum that looks like the following for some multiset $S$ and some function $f$ of $n$ variables which does not depend on the ordering of its arguments: $$\sum_{\{k_1,\dots, k_n\}\subset S}f(...
5
votes
0answers
96 views

The number of partitions by distinct positive numbers

Let $N>0$ be a natural number and let $P(N)$ denote the number of ways to write $N$ as a finite sum of $a_i$ such that the $a_i$ are strictly decreasing positive natural numbers. There is a paper ...
5
votes
0answers
559 views

How many partitions of 12 that fit the requirements?

How many partitions of $12$ are there that have at least four parts, such that the largest, second-largest, third-largest, and fourth-largest parts are respectively greater than or equal to $4,3,2,1$? ...
5
votes
0answers
455 views

Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim \...
5
votes
0answers
205 views

On Applications of the Murnaghan-Nakayama rule

The question is located below. In short, I am looking for an accessible explanation of the Murnaghan-Nakayama rule in relation to the following problem. Pardon the long setup. Let $Y$ be a standard ...
4
votes
0answers
109 views

Evaluate $ \frac{1}{(q)_\infty} \sum_{m \in \mathbb{Z}} q^{\frac{m^2}{2}} (-q^{-\frac{1}{2}}x)^m y^m(q^{1-m}y^{-1};q)_\infty $

This identity is taken from a physics paper [1] stated without proof, on page 43. $$ \frac{1}{(q)_\infty} \sum_{m \in \mathbb{Z}} q^{\frac{m^2}{2}} (-q^{-\frac{1}{2}}x)^m y^m(q^{1-m}y^{-1};q)_\infty =...
4
votes
0answers
73 views

Counting the number of partitions that are a distance d away from a fixed partition.

Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
4
votes
0answers
199 views

A general Combinatorics problem (Coefficients of the q factorial)

I was solving a combinatorics problem when I encountered difficulties. The problem was: $x_1 \in \{0,1\}$ $x_2 \in \{0,1,2\}$ . . $x_{n-1}\in\{0,1,2..,n-1\}$ We have to find the number of ways ...
4
votes
0answers
126 views

Why limit Euler's Partition function P to $k\leq\sqrt n$ instead of $k\leq n$?

I solved a Project Euler problem (I won't say which one) involving the Partition Function P. I used equation #11 from the above link: $$P(n) = \sum_{k=1}^n (-1)^{k+1}\bigg(P\Big(n-{1\over 2}(3k-1)\...
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'...
3
votes
0answers
67 views

Newman's proof of the Asymptotic Formula for the Partition Function

I'm working on Donald J. Newman's proof that $p(n) \sim \frac{1}{4\sqrt{3}n}e^{\pi\sqrt{\frac{2n}{3}}}$, as found in Chapter II of his book Analytic Number Theory. Here's what we have so far: the ...
3
votes
0answers
28 views

is there any formula that describes the frequency distribution of numbers(from 1 to N) across all partitions of N?

I was interested in frequency of numbers across all partitions of a particular number N. say 5 = 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 frequencies of 1 to 5 are 11,3,2,1,1 respectively. is ...
3
votes
0answers
126 views

Relationship between Riemann Zeta function and Prime zeta function

In his paper, Daniel Grunberg shows a relationship between the Stirling Numbers of the first kind and the Harmonic numbers via series of partitions (see Equation 3.1 on Page 5 in the link above). If ...
3
votes
0answers
725 views

How to make a canonical coin system so that greedy solution is the only optimal solution for change-making problem

Related to the paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf and coin-change problem in general. We say that a coin system of coins canonical if the greedy algorithm to the coin ...
3
votes
0answers
104 views

Amount of combinations of sets summing to number

(Apologies for the confused arbitrariness here; I don't have experience in formal maths to make abstract my lay-person thoughts, but I've tried my best.) I have $x$ identical but order-important sets ...
3
votes
0answers
64 views

Problem for number theory

Here it is: $c , n \in \mathbb{N}$ and $x_1,x_2,\ldots,x_n \in \mathbb{N}\cup \{0\}$ $c= 1 x_1 + 2 x_2 + \ldots + n x_n$ How many solutions $\{x_1,x_2,\ldots,x_n\}$ are there? I do not know number ...
3
votes
0answers
56 views

Arithmetic properties of the partition function

Ramanujan mentioned in his paper in 1920 that "it appears that there are no equally simple properties for any moduli involving primes other than these three" $p(5n+4)\equiv0 \mod 5$ $p(7n+5)\equiv0 ...
3
votes
0answers
184 views

Asymptotics of partitions in at most n parts, bounded by r

For every positive integers $n,r,w$ define $$ p_w(n,r)=\#\{ (i_1,...,i_r) | \, 0\leq i_1 \leq \dots \leq i_r\leq n, \, i_1+\dots+i_r=w\} $$ as the number of partitions of $w$ in at most $r$ piece ...
3
votes
0answers
109 views

Partial order on the orbits of the variety of commuting nilpotent matrices

The variety of nilpotent $n\times n$ matrices $\mathcal{N}_n$ over an algebraically closed field $k$ is the disjoint union of orbits under the action of conjugation by $GL_n(k)$. These orbits are ...
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,...
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}$?
2
votes
0answers
49 views

Degree of generating polynomial associated with two partitions

Let $\lambda=(\lambda_1,\ldots,\lambda_k)$ and $\mu=(\mu_1,\ldots,\mu_r)$ be two strictly increasing sequences of non-negative integers ($r$ and $k$ may be $0$, in which case the sequence is empty, ...
2
votes
0answers
156 views

Is there a generating function for this sequence?

The sequence is: 1, 2, 3, 5, 8, 12, 18, 25, 35, 50, 69, 93, 126, 167, 220, 290, 377, 486, 627, 800, 1017, 1290, 1623, 2032, 2542, 3161, 3917, 4843,... It is related to partitions of $n$. It is a ...
2
votes
0answers
42 views

Partitions reference

In this paper, the author mentions before Theorem 23 that the result was proven by Elmo Moore in 1968; the associated reference says "unpublished result". I would be grateful to anyone who knows a ...
2
votes
0answers
139 views

Counting Semistandard Young Tableaux For Triangular Shapes?

If $k \leq n$ I denote the Young diagram with shape $(n,n-1,n-2,\ldots,1)$ by $\lambda^{n,n-1,\ldots,1}$. I write $f^{\lambda_n^{n,n-1,\ldots,1}}$ to count the number of semistandard Young tableaux ...
2
votes
0answers
74 views

Equal and unequal partition?

Can someone please tell me what equal and unequal partition is? And if the question, I'm just putting an example here, is asking you to find at least 3 equal and unequal partitions of 2020 into 4 ...
2
votes
0answers
58 views

Is there accepted notation for the set of ways of partitioning a natural number $a$ into $b$ parts?

Recall the following: Multinomial Theorem. For all finite sets $X$, we have: $$\left(\sum_{x \in X} x\right)^n = \sum_{a}[a](X)^a$$ where $a$ ranges over the set of partitions of $n$ into ...
2
votes
0answers
196 views

$4\sum_{m,n=1}^{\infty}\frac{q^{n+m}}{(1+q^n)(1+q^m)}(z^{n-m}+z^{m-n})=8\sum_{m,n=1}^{\infty}\frac{q^{n+2m}}{(1+q^n)(1+q^{n+m})}(z^m+z^{-m})$

To prove the identity $$4\sum_{m,n=1}^{\infty}\frac{q^{n+m}}{(1+q^n)(1+q^m)}(z^{n-m}+z^{m-n})=8\sum_{m,n=1}^{\infty}\frac{q^{n+2m}}{(1+q^n)(1+q^{n+m})}(z^m+z^{-m})$$ I replaced $m-n$ by $k$ in LHS ...
2
votes
0answers
79 views

Schengen Visa rules

If a tourist wants to visit europe with a schengen visa, the following rules apply: maximum contiguous stay is 90 days (in the following treated as 3 months) in any 180 day interval the sum of days ...
2
votes
0answers
89 views

Partition set N into roughly-equal groups of size approximately k. How can I determine the “range” within which k can vary?

I'm a long way from uni, so please forgive me if I'm not presenting this question as clearly or concisely as I could. I've searched for similar questions, but they seemed to focus on "how many ways ...
2
votes
0answers
84 views

The number of partitions of $n$…Subbarao

(Subbarao) The number of partitions of $n$ in which each part appears two, three, or five times equals the number of partitions of $n$ into parts congruent to $2, 3, 6, 9,$ or $10$ modulo $12$. ...
2
votes
0answers
113 views

How do I calculate the variation of a function?

I am trying to understand how to calculate the variation of a function. In this regard, the book that I am reading offers the following definition - $$V_g([a,b] = sup \sum_{i=0}^n |f(x_{i+1}) - f(...
2
votes
0answers
42 views

show $\sum_{j=0}^n (-1)^j {n \brack j}_q =0$ for n odd

I would like to show $\sum_{j=0}^n (-1)^j {n \brack j}_q =0$ for n odd, or preferably even more generally that $\sum_{j=0}^n (-1)^j {n \brack j }_q =\frac{1}{2}((-1)^n+1)(q;q)_{\frac{n}{2}}$. Using ...
2
votes
0answers
107 views

What does this product converges to?

Let $p\in[0,1]$. I'm interested in computing $$\lim_{n\to\infty}\prod_{i=1}^n(1-p^i)$$ Any thoughts? EDIT: As Kibble mentioned, this is the Euler function. Also from Kibble: a simple upper bound ...
2
votes
0answers
57 views

What are the combinatorial numbers appearing in these repeated derivatives?

Let $f$ be a $C^\infty$-function and define $g(x) = \exp(f(x))$. I am interested in the higher derivatives $g^{(1)}, g^{(2)}, \ldots$ of $g$. Let $\lambda$ be a partition of $n$, i.e. a tuple of ...
2
votes
0answers
90 views

Link between partition function and ordered partition function

The partition function $p(n)$ measures the number of partitions of $n$, or the number of ways in which natural numbers can be summed to produce $n$, without regard to order. For example, the ...
2
votes
0answers
766 views

Is every integer $\geq5$ the sum of two primes and a power of a prime?

Is every integer $\geq5$ the sum of two primes and a power of a prime (where $1$ is included in the prime powers)? I don't really expect someone to prove this here, but I wonder if the question has ...