5
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – Brendan McKay
    May 15, 2016 at 1:19
  • 1
    $\begingroup$ 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)!$ $\endgroup$
    – C Sel
    May 15, 2016 at 1:45
  • 1
    $\begingroup$ True for $n=14$ (which is as far as I will go). $\endgroup$
    – Brendan McKay
    May 15, 2016 at 1:56
  • 1
    $\begingroup$ If instead of $n+\max(B_i)$, you have $n+\max(B_i)+x$, what does the resulting polynomial look like? $\endgroup$
    – Douglas Zare
    May 15, 2016 at 8:09
  • 3
    $\begingroup$ That looks like $(x+3)(x+5)(x+7)...$. That might be easier to prove that the evaluation at $x=0$. $\endgroup$
    – Douglas Zare
    May 15, 2016 at 18:49

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – C Sel
    May 18, 2016 at 17:29
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Ilya Bogdanov
    May 18, 2016 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.