# Combinatorics: set partitions of a poset

Let $\pi_n$ be the poset of all set partitions of $\{1,...,n\}$ ordered by refinement, $\sigma = \{B_1,...,B_k\}$ be a set partition with blocks $B_i$, and $\max(B_i)$ be the maximum value in the block $B_i$. I'm trying to prove the following:

$$\Sigma_{\sigma\in\pi_{n-1}}\Pi_{B_i\in\sigma}(-1)^{|B_i|-1}(|B_i|-1)!(n+\max(B_i))=(2n-1)!!$$

I've already coded this in Mathematica to check that it's true until n=11 (after which the numbers become too large):

<<Combinatorica

f[x_]:=(-1)^(x-1)*(x-1) !

Total[Times @@@ Map[f, Map[Length, SetPartitions[n-1], {2}], {2}]*Times @@@ (Map[Max, SetPartitions[n-1], {2}] + n) ] == Factorial2[2*n-1]


Any thoughts would be greatly appreciated.

• I don't understand the formula. The variable $i$ is local to the inner product and has no meaning for the outer product. And how is "ordered by refinement" relevant? – Brendan McKay May 15 '16 at 1:19
• The original equation was $\Sigma_{\sigma\in\pi_{n-1}}\mu(\hat{0},\sigma)\Pi_{B\in\sigma}(n+max(B))=(2n-1)!!$ where $\mu(x,y)$ is a Moebius function, given by $\mu(x,y)=1$ if $x=y$, $\mu(x,y)=0$ if $x \not\leq y$ under the refinement, and $\Sigma_{x\leq z \leq y} \mu(x,z) =0$ for $x <y$. After some work, it turns out that $\mu(\hat{0}, \sigma)= \Pi_{i=1}^k(-1)^{|B_i|-1}(|B_i|-1)!$ – C Sel May 15 '16 at 1:45
• True for $n=14$ (which is as far as I will go). – Brendan McKay May 15 '16 at 1:56
• If instead of $n+\max(B_i)$, you have $n+\max(B_i)+x$, what does the resulting polynomial look like? – Douglas Zare May 15 '16 at 8:09
• That looks like $(x+3)(x+5)(x+7)...$. That might be easier to prove that the evaluation at $x=0$. – Douglas Zare May 15 '16 at 18:49

Let us prove even more general formula that Douglas Zare's one from the comments. Let $a_1>\dots>a_n$ be real numbers. Then $$\sum_{\sigma\in\pi_{n}} \prod_{B_i\in\sigma}(-1)^{|B_i|-1}(|B_i|-1)!a_{\min B_i} =\prod_{i=1}^n(a_i-i+1).$$ (The required formula follows by setting $a_i=2(n+1)-i$ and shifting $n$ by $1$.)
To see this, rewrite the right-hand side as $$\prod_{i=1}^n\left(a_i-\sum_{1\leq j<i}u_{i,j}\right),$$ where $u_{i,j}=1$ for $j<i$, and expand all the brackets. We get the sum of the terms each having the form $$(-1)^{n-|I|}\prod_{i\in I}a_i\prod_{i\notin I}u_{i,j(i)},$$ where $I$ is a subset of $\{1,\dots,n\}$ containing $1$. To each such term, put into correspondence a partition into $|I|$ parts, where $a_i$ ($i\in I$) are the maximal elements of the parts, and each $u_{i,j}$ is interpreted as $a_i$ and $a_j$ lie in the same set of partition'.
This way, each partition $(B_i)$ will correspond to exactly $\prod_i (|B_i|-1)!$ terms, all having the sign we need. Thus, after substituting $u_{ij}=1$ we obtain the required formula.
• I have a couple questions. First, should it be $(-1)^{n-|I|}\Pi_{i\in I}a_i\Pi_{i\notin I}\Sigma_{j<i}u_{i,j}$ instead? That is, shouldn't we be summing over j somewhere? Also, I'm not entirely sure how knowing the minimal elements in the blocks will give you information about the size of a block. For example, for n=5, if 1 and 2 were our minimal elements for a partition, we could have 234/1 or 13/24 as our partition, which would yield different block sizes. – C Sel May 18 '16 at 17:29
• On the first question: I just consider each summand (i.e. each specific choice of the values of $j$ for each $i$) separately, On the second one: we have additional information from the abovementioned values of $j$: the block for every $a_i$ is determined inductively by means of them. So, the partition $13/24$ corresponds to the choice $u_{31}u_{42}$, while the partition $234/1$ corresponds to $u_{32}u_{42}$ and to $u_{32}u_{43}$. – Ilya Bogdanov May 18 '16 at 20:55