Number of ways to form a partition from another.

201 Views Asked by At

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? For instance given $1+1+1+1$, there are $6$ ways to form $2+1+1$ by choosing different pairs of ones from the first partition to form the $2$ in the second. For a second example, from $2+1+1$, there are $2$ ways to from $3+1$, but only $1$ way to form $2+2$.

I'm imagining a directed graph, with $1+1+1+\cdots+1$ at the top and $n$ at the bottom. Each node of the graph is a partition of $n$. Each edge goes from 1 partition to another if the second can be formed by combining numbers in the first. The number I'm asking for above is the weight on each edge.

I'm really just looking for the name of such numbers or a reference. But, a formula would be swell too.

Aside: What other tags would be appropriate here?

1

There are 1 best solutions below

3
On

The number you are looking for seems to be the number of $b$ partitions reachable from given $a$ partition in a Hasse diagram of noncrossing partitions of a set $\underbrace{\{1,\ldots,1\}}_{n}$. Consider the following figure taken from wiki on noncrossing partitions.

enter image description here

Your first example, $1,1,1,1$ starts with the bottom node and reaches six possible $2,1,1$ pink nodes. Your second example, $2,1,1$ starts with arbitrary pink node and reaches two possible $3,1$ green nodes or one possible $2,2$ yellow/brown node.