I have the following problem. I have given a set $$N = \{1,2,3,...,n\}, n \in \mathbb N$$ and a function $$v:2^N \rightarrow \mathbb Z, v(A) = |A|^{|A|}$$.
I want to prove that the mobius inversion of $v$ is non-negative, i.e. $$\mu^v(A) \geq 0,\ \forall A \in 2^N$$.
Basically I am using the following (recursive) formulas: $$\mu^v(A) = v(A) - \sum_{B \subset A}\mu^v(B)$$ and $$\mu^v(A) = \sum_{B\subseteq A} (-1)^{|A \backslash B|} \cdot v(B)$$
What I have done so far: First, $v(A)$ as well as $\mu^v(A)$ are symmetric in the sense that the outcome doesn't depend directly on the set $A$, but more on the cardinality of $A$, formally: $$|A| = |B| \Rightarrow v(A) = v(B), \mu^v(A) = \mu^v(B)$$.
This lets me reformulate the problem: Let $A \in 2^N, |A| = k$. Then i want to show that: $$\mu^v(A) = \sum_{B\subseteq A} (-1)^{|A \backslash B|} \cdot v(B) = \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} j^j \geq 0$$ This term looks similar to the one from the binomial theorem, the only thing that isn't as in the theorem is the $j^j$, which doesn't allow me to use it. I've been trying to tackle this via induction, however without success.
I'd greatly appreciate if someone could point me in the right direction, provide a hint or solution, or in case my logic so far is flawed, tell me where.
Thanks!
First rewrite the sum:
$$\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^k=\sum_{k=0}^n(-1)^{n-k}\binom{n}{n-k}k^k=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^{n-k}\;.$$
This has the form of an inclusion-exclusion calculation, and indeed it can be so interpreted: we’ll count the functions from $[n]$ to $[n]$ that have no fixed points whose preimages are singletons.
For $k\in[n]$ let $A_k$ be the set of functions from $[n]$ to $[n]$ having $k$ as a fixed point whose preimage is a singleton. If $\varnothing\ne I\subseteq[n]$,
$$\left|\,\bigcap_{k\in I}A_k\,\right|=(n-|I|)^{n-|I|}\;,$$
so
$$\begin{align*} \left|\,\bigcup_{k\in[n]}A_k\,\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}(n-|I|)^{n-|I|}\\ &=\sum_{k=1}^n\binom{n}k(-1)^{k+1}(n-k)^{n-k}\;. \end{align*}$$
This is the number of functions from $[n]$ to $[n]$ that do have at least one fixed point whose preimage is singleton, so we want
$$\begin{align*} n^n-\sum_{k=1}^n\binom{n}k(-1)^{k+1}(n-k)^{n-k}&=n^n+\sum_{k=1}^n\binom{n}k(-1)^k(n-k)^{n-k}\\ &=\sum_{k=0}^n\binom{n}k(-1)^k(n-k)^{n-k}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^k\;. \end{align*}$$
Clearly this is non-negative, since it’s the cardinality of a set of functions. (By the way, the sequence $\langle\mu^v([n]):n\in\Bbb N\rangle$ is the absolute value of the sequence OEIS A069856; the OEIS entry has very little more information, however.