Counting certain partitions of integers

236 Views Asked by At

[Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting $1$ from any of the terms (including terms equal to $1$, so one of those disappears) and the elements just one step above are those you can get by either adding $1$ to one of the terms or by adding a new term equal to $1$. At the very bottom of the whole thing is the partition of $0$, with no terms.

Now consider the set $$ S=\left\{\underbrace{1+\cdots+1}_{n}, \underbrace{2+\cdots+2}_{n-1}, \underbrace{3+\cdots+3}_{n-2},\ldots , \underbrace{{}\quad n\quad{}}_1 \right\}. $$ For example, when $n=6$, $$ \begin{align} S=\{ & 1+1+1+1+1+1,\\ & 2+2+2+2+2,\\ & 3+3+3+3,\\ & 4+4+4,\\ & 5+5,\\ & 6\,\}. \end{align} $$ We want to look at the closure of $S$ under "going downward", i.e. the set $$ T=\{p : \exists q\in S\ \ p\le q \}.\tag1 $$ About three years ago I read a paper by Ruedi Suter proving that the set $T$ defined in $(1)$ has certain rotational symmetries. (Everyone has long known Young's lattice is bilaterally symmetric and it's easy to see why the set $T$ in $(1)$ is as well, but I gather Suter's discovery of rotational symmetries surprised people.)

My question is: Why is the cardinality of $T$ equal to $2^n$? Or might I be mistaken in thinking that that pattern persists?

If I weren't lazy, I'd dig out Suter's paper again and see if that answers the question, and in fact I will, but it still might be interesting to see what answers people post here.

1

There are 1 best solutions below

0
On BEST ANSWER

To distinguish the sets $S$ and $T$ for different $n,$ introduce subscripts: $S_n$ and $T_n.$ Let $T_{n,k}$ be the set of partitions in $T_n$ with largest part $k.$ The elements of $T_{n,k}$ are precisely those partitions with largest part $k$ and at most $n+1-k$ non-zero parts. This follows from the fact that any partition that is less than a partition in $S_n$ and has largest part $k$ must be descended from a partition in $S_n$ with largest part $k$ or more, which has $n+1-k$ or fewer non-zero parts, and from the fact that any partition with largest part $k$ and at most $n+1-k$ parts can be obtained by successively subtracting $1$ from elements of $$ \underbrace{k+\cdots+k}_{n+1-k}\in S_n. $$

We show that $\lvert T_{n,k}\rvert=\binom{n}{k},$ from which the result follows. This is done by showing that it satisfies the Pascal's triangle recurrence. Clearly $\lvert T_{0,0}\rvert=1$ and $\lvert T_{n,k}\rvert=0$ for $k<0$ or $k>n.$ For $0\le k\le n,$ the elements of $T_{n,k}$ are of two types. Type $1$ elements have only one part of size $k.$ Type $2$ elements have two or more parts of size $k.$ The Type $1$ elements are constructed by adding $1$ to the largest part of an element of $T_{n-1,k-1}.$ The Type $2$ elements are constructed by adjoining a part of size $k$ to an element of $T_{n-1,k}$. It is easily verified (by checking inclusions in both directions), that these constructions establish bijections between the Type $1$ elements of $T_{n,k}$ and $T_{n-1,k-1}$ and between the Type $2$ elements of $T_{n,k}$ and $T_{n-1,k}.$ Therefore $\lvert T_{n,k}\rvert=\lvert T_{n-1,k-1}\rvert+\lvert T_{n-1,k}\rvert.$