1
vote
1answer
209 views

An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product ...
5
votes
1answer
149 views

The number of partitions between two fixed partitions

Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} ...
5
votes
2answers
121 views

Length of the longest chain in dominance order

If $\Pi_n$ is the set of partitions of $n$, then for $\lambda, \mu\in \Pi_n$ we say $\mu$ dominates $\lambda$ if $\sum\limits_{i=1}^k \lambda_i \leq \sum\limits_{i=1}^k \mu_i$ for all $k$. This gives ...
3
votes
0answers
88 views

Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that ...
3
votes
0answers
59 views

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

I posted this question on MathStackexchange (http://math.stackexchange.com/questions/639878/asymptotics-of-partitions-in-at-most-n-parts-bounded-by-r) some time ago, but it did not receive any answer, ...
3
votes
1answer
276 views

Combinatorial Technique Needed

The following problem is likely too special for MO. However I have no clue how to deal with it, so I'll just try. Nevertheless it is a combinatorial problem and a discussion about general methods in ...
4
votes
0answers
147 views

Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property? Definitions: A subset S of the xy-plane is star-convex if there is ...
2
votes
2answers
218 views

Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...
3
votes
1answer
265 views

Number of 3-tuple partitions of a multiple of three which follow the triangle inequality

Given n=3t, t$\in \mathbb N$; let $\mathbb L_3$ be set of all distinct integer partitions of n having 3 parts; say $\lambda_1,\lambda_2,\lambda_3$ . If I chose any one partition randomly from ...
11
votes
3answers
884 views

A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form : $$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that : $d_{i}\vert n$ $1=d_{1}<d_{2} \le d_{3} \le ... \le ...
1
vote
1answer
378 views

Recurrence relation for coefficients of product of generating functions for partition numbers

It is well known that $$Z(x,q) = \prod_{n=1}^\infty\frac{1}{(1-xq^n)} = \sum_{m=0}^\infty\sum_{k=0}^m p_{m,k}x^kq^m$$ is the generating function for the number $p_{m,k}$ of partitions of $m$ in ...
4
votes
2answers
304 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 ...
3
votes
2answers
134 views

Databases for sequences indexed by partitions

Is there a database for sequences indexed by partitions similar to Sloane's OEIS? I mean, I am aware that in the OEIS there are some arrays indexed by partitions, but I feel as though most of such ...
3
votes
1answer
154 views

bounded partitions and bounded signed partitions of integers

Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation: $$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...
3
votes
1answer
124 views

Random RSK and Plancherel Measure

Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...
3
votes
1answer
107 views

Why are the dinv-statistic and the partition length equidistributed?

A partition of $n$ is a weakly decreasing sequence of natural numbers $\lambda = (\lambda_1, \lambda_2, \dots)$ such that $\sum \lambda_i = n$. Its length $l(\lambda)$ is the number of positive ...
10
votes
0answers
281 views

3D generalizations of permutations, RSK correspondence, contingency tables, etc.

I want to gather facts and questions related to 3D generalizations of permutations, RSK correspondence, contingency tables, etc. One reason I am interested in this is because it is potentially related ...
5
votes
2answers
245 views

Semimagic Squares and Partitions

Say, we have a semimagic square $X$, that is, an $n\times n$ square matrix with entries from natural numbers, such that each row and column of it sums up to the same natural number $s$. Let $M$ be a ...
6
votes
1answer
294 views

Partitions comprised only of divisors

How many of the partitions of a natural number $n$ are comprised only of its divisors? That is, if $$p(n)=\sum_{\sum_{1}^n kj_k=n:j_k\geq 0} 1_{\[j_1,j_2,...\]},$$ is the ordinary partition function ...
11
votes
3answers
574 views

Partitions into parts from an arithmetic progresion

Fix an arithmetic progression $R=(a, a+m, a+2m, \ldots)$, and assume that $gcd(a,m)=1$. Define $q_R(n)$ as the following coefficients: $$\prod_{i=0}^\infty (1+ t^{a+mi}) = \sum_{n=0}^\infty q_R(n) ...
2
votes
3answers
866 views

Explicit formula for the number of compositions with m strictly positive parts bounded by n?

Is there any known formula for the number of compositions of an integer k (partitions with considering the order of the parts) of length m (exactly m parts) where the parts do not exceed a given ...
5
votes
1answer
188 views

Functions consistent with two partitions of a finite set

Suppose that $P$ and $C$ are two unordered partitions of $[n]$, the set of positive integers from 1 to $n$. Let $c(C,P,x)$ be the number of functions $f$ from $[n]$ to $[x]$ for which (1) ...
5
votes
2answers
384 views

A product identity for partitions

For a partition $\lambda=(\lambda_1\ge \lambda_2\ge \dots)$, let $m_\lambda=\prod_i (\lambda_i-\lambda_{i+1})!$ be the product of factorials of consecutive differences and let $v_\lambda=\prod_{i | ...
2
votes
1answer
175 views

Box-dual of a partition - what is it called?

Fix natural numbers $n,m\in\mathbb{N}$. Given a partition $\lambda\vdash d$ with at most $n$ rows (and at most $m$ columns), we can define a partition ...
2
votes
0answers
121 views

Partitions limit shape and LDP

Hello! I am trying to understand the paper of Dembo-Vershik-Zeitouni, Large deviations for integer partitions. I am only interested in Theorem 2, which deals with the case of the uniform ...
7
votes
2answers
724 views

Inverse map for partition transform

Let $(a_n)$, $n\in\mathbb{N}$, be a sequence of complex numbers, then formally one has (1) $$\prod_{1}^{\infty}\left(1-a_nx^n\right)^{-1}=1+\sum_{1}^{\infty}\left(\sum_{j_1+2j_2+\cdots ...
8
votes
1answer
173 views

shape of random q-weighted lattice path

Where can I find a detailed write-up of the asymptotic shape of a $q$-weighted Young diagram inside an $a$-by-$b$ box, especially one that uses a variational approach? Equivalently, we can look at ...
7
votes
1answer
283 views

Distribution of big component of set partitions

Consider the set $S_n = \{1, \dotsc, n\},$ and consider the set $P(n, k)$ of partitions of $S_n$ into $k$ parts (the cardinality of $P(n, k)$ is the Stirling number of the second kind $S(n, k).$ ...
2
votes
0answers
273 views

What is 'arch' in Vershik-Kerov's 1984 paper?

In their 1984 paper Asymptotic of the Largest and the Typical Dimensions of Irreducible Representations of a Symmetric Group, Vershik and Kerov use the notation $\DeclareMathOperator{\arch}{arch}\arch ...
4
votes
2answers
546 views

How local the property of “being a partition” is?

Note: The problem is solved! See EDIT below. The following question about integer partitions arose from a purely "practical" question: Does there exist better dynamic programming algorithms for the ...
4
votes
2answers
3k views

Seeking a solution algorithm to the 3-partition problem

I need to divide 48 pieces of jewelry between 3 inheritors so as to give equal, or nearly equal value, to each. I have learned that this is called the 3-partition problem. I solved it for 9 pieces of ...
3
votes
1answer
270 views

Article about partitions with forbidden parts/multiplicities

I am looking for an article, most likely from the 90s, that generalized the bijection between partitions with odd and distinct parts by explaining how a bijection between the forbidden parts could be ...
7
votes
3answers
727 views

Binomial coefficient in Andrews' partition book

First of all, i think MathOverflow is a very great community to discuss math, either basic or advanced, and i'm glad to participate here. It's my first post, so i'm sorry if i did anything wrong, and ...
5
votes
2answers
778 views

What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?

For example, if $n = 10$ and $k = 3$, then the legal partitions are $$10 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2$$ so the answer is $4$. By choosing $k$ random elements of $\{1,\ldots,2n/k\}$, ...
1
vote
2answers
304 views

Partitions into 0,1, and 2 with a partial sum condition.

On a tangent to a problem I've been working on, I've run into a combinatorial/partition-theoretic problem that I wondered if anyone had run into before. Let $N$ be a positive integer, and ad-hoc-ly ...
3
votes
1answer
453 views

a simple combinatorial problems

what sequence $C=(c_1,\cdots,c_n)\in \mathbb{N}^n$ with $\sum ic_i=n$ maximizes the number of $\omega\in\mathfrak{S}_n$ of type $C$? For instance,when $n=4$ the maximizing sequence is $(1,0,1,0)$.
1
vote
1answer
477 views

Split sum into equal terms

Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$. Find indices $1 < p_1 <...< p_h <...< p_{t-1} < l$ such that in sum ...
20
votes
2answers
830 views

Partitions to different parts not exceeding $n$

Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
2
votes
1answer
413 views

Does this type of partition have a name?

If this question is dumb please excuse me. Does this type of partition have a name and if so, what is it? A sequence of partitions of an integer $\vec{\lambda}_1, ...
1
vote
0answers
172 views

Explicit formulas for the action of the Hall algebra of the cyclic quiver on q-Fock space?

In their paper on the decomposition numbers of Schur algebra, Vasserot and Varagnolo introduce an action of the (twisted) Hall algebra of a cyclic quiver $\Gamma$ on q-Fock space. Without q-shifts, ...
5
votes
3answers
532 views

How to recover partition from its multiset of hook lengths?

One of the invariants associated to a partition is its multiset of hook lengths. For instance, as shown here, the partition (5,4,1) has hook lengths {1,1,1,2,3,3,4,5,5,7}. Is there a good way to go ...
23
votes
4answers
1k views

Asymptotic growth of a certain integer sequence

Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows: $a(n):=$ the smallest positive integer $k$ such ...
3
votes
4answers
929 views

unique integer partitions

Let me motivate my general question with an explicit example: Suppose I am looking for all unique combinations of exactly three non-negative integers that sum to five. The solutions are 005, 014, ...
10
votes
1answer
456 views

I am searching for the name of a partition (if it already exists)

I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a ...
1
vote
2answers
428 views

Unique way to partition into two parts of equal weight

A special case says it all ... Let $ w_1 < w_2 < \ldots < w_{12} $ be an increasing sequence of $12$ integers ("weights") such that the total weight $W=\sum_{k=1}^{12}w_k$ is even. Say that ...