Functions consistent with two partitions of a finite set

Question

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.

Answer 1

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.