Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that $P$ and $C$ are two unordered partitions of $[n]$, the set of positive integers from 1 to $n$. Let $c(C,P,x)$ be the number of functions $f$ from $[n]$ to $[x]$ for which

(1) $f(a)=f(b)$ if $a$ and $b$ belong to the same part of $C$,

(2) $f(a)≠f(b)$ if $a$ and $b$ belong to the same part of $P$.

Conjecture: The sum $\sum (-1)^{p-1} (p-1)! c(C,P,x)$ is independent of $C$. Here the sum is over all partitions $P$, and $p$ denotes the number of parts of $P$.

Consider the case where $C$ has a single part. Then $c(C,P,x)$ is zero unless $P$ is the trivial partition into $n$ parts, and the sum is $(-1)^{n-1} (n-1)! x$. Thus the conjecture is that this is always the value of the alternating sum, for arbitrary $C$.

This conjecture arises from the same context as questions "Stirling number identity via homology" and "Polynomials akin to Bell polynomials," asked by the same user.

share|improve this question
    
I changed the notation since $p$ was used for two things, added links, and took the extra $\sum$ out. –  Douglas Zare Jul 3 '12 at 18:43
    
Thanks for the edits! –  Gary Kennedy Jul 4 '12 at 1:09
add comment

1 Answer

Fix a function $f$ such that $(1)$ holds. The contribution of that function to the sum is the sum over all partitions $P$ such that $(2)$ holds of $(-1)^{p-1}(p-1)!$. We will prove that this contribution is $0$ for all nonconstant $f$. Since every constant $f$ is satisfies $(1)$ for every partition, the identity is true.

Fix a nonconstant $f$. Take a partition $P_{-}$ of $[n-1]$ for which $(2)$ holds. How many ways can we extend this partition to $[n]$? We can create a new part, or add $n$ to any part which does not contain any of the $k$ such that $f(k)=f(n)$. Let $a$ be the number of such $k$, then those $a$ must be contained in $a$ different parts of $P_{-}$ since $P_{-}$ satisfies $(2)$. So there are $p-a$ ways to extend $P_{-}$ and keep the number of parts fixed, and one way to extend it and increase the number of parts.

The contribution to the sum of extensions of $P_{-}$ is $(p-a)(-1)^{p-1}(p-1)! + (-1)^p p! = -a (-1)^{p-1} (p-1)!$.

Since each partition $P$ of $[n]$ satisfying $(2)$ is an extension of a unique partition $P_{-}$ of $[n-1]$ satisfying $2$, the total contribution of all partitions of $[n]$ satisfying $(2)$ is equal to $-a$ times the total contribution of all partitions of $[n-1]$ satisfying $(2)$. By induction, this is $0$ unless $f$ is constant on $[n-1]$. But if $f$ is nonconstant on $[n]$ and constant on $[n-1]$ then $f(n)$ must be a new value, so $a=0$, so the product is $0$ anyways. The base case for the induction is $n=1$ where all partitions are constant so there is nothing to prove. This completes the argument.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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