Combinatorics – Generating Function for Counting Partitions with Corners

co.combinatoricspartitionsplanar-partitionsprobability distributions

A corner of an integer partition is a location at where a box can be added to its Ferrers diagram to give a new partition.

E.g. the partition $\{1,1,1\}$ has two corners, and $\{1,2\}$ has three corners.

Let $p(n,r)$ denote the number of integer partitions of $n$ with $r$ corners.

Let $P(x,t) = \sum_{n,r\geq0} p(n,r)x^nt^r = t + t^2x + 2t^2x^2 + (2t^2+t^3)x^3 + \ldots$ be the generating function for these numbers.

  1. Is there an elementary (EDIT: i.e. probabilistic) proof that $P(x,1-x) = 1$?

Thus for $x \in [0,1)$, the map $\lambda \to x^{|\lambda|}(1-x)^{\#corners (\lambda)}$ defines a probability distribution on the set of partitions of all integers.

  1. Is it well known that $P(x,t) = \prod_{k=1}^{\infty} \frac{1-x^{k-1}(1-t)}{1-x^k} = \frac{(1-t,x)_\infty}{(x,x)_\infty}$?

Note: In Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher, and Toufik Mansour, "Counting corners in partitions", the following formula (Theorem 2.2) is given

$P(x,t) = t + t^2 \sum_{j\geq 1} \frac{x^j}{1-x^j} \prod_{i=1}^{j-1} \frac{1-(1-t)x^i}{1-x^i}$

Best Answer

Maybe this is not the kind of answer you are looking for, but it is easy to see that $$ P(x,t) = \prod_{k=1}^{\infty} \frac{1-x^{k-1}(1-t)}{1-x^k}$$ because the number of corners of a partition is one plus its number of distinct parts (you always have a corner at the "top" of a series of repeated parts, plus one at the very bottom of the partition). So the term of $\frac{1-x^k(1-t)}{1-x^k} = 1 + t \frac{x^k}{1-x^k}= 1 + t(x^k + x^{2k} + \cdots)$ correspond to choosing how many parts equal to $k$ in your partition you want. And then there is an extra factor of $1-x^0(1-t)=t$ for the extra corner at the bottom every partition has.

I guess this answers part 1 as well, right?

EDIT: Okay, in response to the comment below, here is a probabilistic proof that weighting each partition $\lambda$ by $x^{|\lambda|}(1-x)^{\#\mathrm{corners}(\lambda)}$ gives a probability distribution on the set of all partitions. Imagine constructing a partition as follows. We start with the empty partition. Then we focus on its unique corner. We flip a coin that is heads with probability $x$ and tails with probability $1-x$. If we get heads, we add a box in that corner, and then move on to consider the "next" corner of the partition we've built so far, moving left to right and top to bottom. (I am always using "English" notation for partitions/Young diagrams, by the way.) When we flip a tails at a corner, we leave that box empty, but we still move on to the next corner. Unless we flipped tails at the bottom corner (i.e., in a row with no boxes in it), in which case we stop and output the partition we've made. It is not hard to see that we produce each $\lambda$ with probability $x^{|\lambda|}(1-x)^{\#\mathrm{corners}(\lambda)}$. Maybe a small additional argument is needed to explain why we terminate with probability $1$.

Related Question