# Counting refinements of partitions

Let $p$ and $q$ be partitions of $n$. We say $q$ refines $p$ if the parts of $p$ can be subdivided to produce the parts of $q$. For example, $(5,5,1)$ refines $(6,5)$ but not $(7,4)$. $(n)$ refines only itself, and $(1,...,1)$ refines all partitions of $n$.

For each partition of $n$, count the number of partitions refining it. Let $F(n)$ be the sum of these counts. For example, $F(3) = 3+2+1=6$, and $F(4) = 5+3+3+2+1=14$. What is known about the asymptotics of $F(n)$?

My motivation is from looking at multinomials.

Note: Refinement is not the dominance order. It is related to the refinement of set partitions.

EDIT: I found why I was looking at these numbers:

JonMarkPerryBlog:WordPress

• What does $F$ take as inputs and produce as outputs. – Halbort Dec 21 '15 at 16:19
• F(n)=k. F(3)=|3,21,111,21,111,111|=6. – JMP Dec 21 '15 at 16:23
• Are you trying to count ordered pairs $(\pi,\sigma)$ so that $\pi$ dominates $\sigma$? You should state the order more clearly than just "the summands are achievable." I don't think you mean what that literally says, since, for example, $2+1+1+1$ and $2+2+1$ both have only $\{1,2\}$ among their summands so they would both dominate each other according to what you said. I think you mean that you want one partition to be a refinement of the other instead. Also, "dominate" already has a different meaning so please be careful to specify that you are using a nonstandard meaning of "dominate." – Douglas Zare Dec 21 '15 at 17:57
• Clearly JMP's definition of "dominates" is that given two sets of integers $S = \{s_i\}, t = \{t_k\}$ where $i$ ranges from $1$ to $|S|$ and $k$ from $1$ to $|T|$, then $S \text{ dom } T$ iff (1) $\sum_i s_i = \sum_k t_k$ and (2) there exists a mapping $d : S \to P(T)$ (that is, elements of $S$ to subsets of $T$) such that (a) $\forall i,j : d(s_i) \cap d(s_j) = \emptyset$ and (b) $\forall i : \sum_{t_k \in d(s_i)} t_k = s_i$. – Mark Fischler Dec 21 '15 at 23:02
• Am I right that for every partition you count the number of partitions it dominates (including itself) and then sum it all up? – Ilya Bogdanov Dec 22 '15 at 11:44

If I'm not mistaken, this simple Sage code computes $F(n)$:

def F(n):
P = Posets.IntegerPartitions(n)
return sum( len(P.closed_interval(p,P.top())) for p in P )


The values of $F(n)$ for $n=0,1,\dots,20$ are:

1, 1, 3, 6, 14, 26, 55, 99, 192, 340, 619, 1063, 1873, 3129, 5308, 8718, 14385, 23116, 37346, 58949, 93294

UPDATE. I've added these counts as the sequence https://oeis.org/A265947 in the OEIS.

I assume you are asking for the number of pairs $(\pi,\sigma)$ of partitions of $n$ so that $\sigma$ is a refinement of $\pi$. Call this $q(n)$.

Let $p(n)$ be the number of partitions of $n$. $p(n) \sim \frac{1}{4\sqrt {3}~n} \exp \left( \pi \sqrt{\frac{2n}{3}}\right)$ by Hardy and Ramanujan, so $p(n)$ has upper and lower bounds of the form $\exp (c\sqrt{n})$.

$p(n) \le q(n) \le p(n)^2$ so $q(n)$ also has upper and lower bounds of the form $\exp (c \sqrt{n})$. It is natural to try to find the limit of $\frac{1}{\sqrt{n}}\log q(n)$. The $\liminf$ is at least $\pi \sqrt{2/3}$ and the $\limsup$ is at most $\pi\sqrt{8/3}$.

Here is a construction showing that the $\liminf$ is at least $\pi \sqrt{4/3}$: Consider pairs of partitions $(\pi^-,\sigma^-)$ of $n/2$. To $\pi^-$, add $n/2$ to the largest part to get a partition $\pi$ of $n$. To $\sigma^-$, add $n/2$ $1$s to get a partition $\sigma$ of $n$. No pair $(\pi,\sigma)$ is hit twice, and $\sigma$ is a refinement of $\pi$.

Again not an answer, but just some more context and evidence that this problem seems hard. As Aaron Meyerwitz points out this is typically called the refinement order and seems like a difficult problem. Let $P_n$ be the poset of integer partitions partially order by refinement. This poset has minimal element $\hat{0} = 1^n$ the partition with all parts $1$ and maximal element $\hat{1} = n$ the partition with a unique part $n$. The quantity you are looks for is $$F(n) = \sum_{\lambda \in P_n} |[\hat{0}, \lambda]|$$ the sum of the sizes of all lower order ideals in $P_n$.

Zeigler has a paper On the Poset of Partitions of an Integer. Essentially this paper shows that the poset $P_n$ lacks some nice properties and is rather unpredictable.

The poset $P_n$ is ranked where the elements at rank $k$ are partitions with $n-k$ parts. So the Whitney numbers of the second kind are $p(n,n-k)$ the number of ways to partitions $n$ into $n-k$ parts. There is a recurrence for $p(n,k)$ (see for example the pretty well developed MathWorld page on partitions). However, I see a problem in the fact the intervals at the same rank can be very different. For example consider $[\hat{0},2^n]$ and $[\hat{0}, (n+1,1^{n-1})]$ in $P_{2n}$. We have $|[\hat{0}, 2^n]| = n$ since it is just a chains with elements $(2^k, 1^{n-2k})$. On the other hand $|[\hat{0}, (n+1,1^{n-1})]| = p(n+1)$ the number of partitions of $n+1$ which has the asymptotic formula $p(n) \sim exp(\pi \sqrt{2n/3})/(4n\sqrt{3}))$ which is due to Hardy and Ramanujan.

At this time I only see trivial and crude bounds for $F(n)$ is terms a $p(n)$. Though I would be happy to seem someone with more knowledge and more clever than me produce a nice bound.

This is not at all an answer, just an attempt to give some context. There is the answer to an easier related problem at the end.

If you have a natural sequence of sets $A_n$ you could wonder about the exact values or asymptotics of $|A_n|.$ For (unordered) partitions of an integer $n$ that is non-trivial although pretty well understood. Given some partial order $\preceq$ on the elements of $A(n)$ one could also ask, as you have done, for the asymptotics of the set of all ordered pairs $(x,y)$ in $A_n\times A_n$ with $x \preceq y.$ Two natural orders on these partitions are domination (as defined by Wikipedia, which is pretty common) and your order which I would call refinement. For either of those the question seems difficult.

For ordered partitions such as $$4,3+1,2+2,1+3,2+1+1,1+2+1,1+1+2,1+1+1+1$$ One has $|A(n)|=2^{n-1}$ whereas the number of ordered pairs with the refinement ordering is $3^n.$ For the domination ordering it seems to start $1,1,3,9,28$ so it might be the number of skew partitions of $n$ although I am not sure.