Show that $\sum\limits_{P\subseteq S}(-1)^{n-|P|}\left(\sum\limits_{a\in P}a\right)^n=n!\prod\limits_{a\in S}a$, where $n=|S|$

Question

I want to prove the following:

$$\sum_{P\in 2^S}(-1)^{n-\mid P\mid}(\sum_{a\in P}a)^n = n!\prod_{i=1}^na_i$$ where $S = \{a_i\mid i\in [n]\}$ which is a multiset of positive integers.

It is pretty much similar to the form of principle of inclusion and exclusion

However I can't figure where to start to make up the part $\prod_{i=1}^na_i$.

Any guidance?

Additionally, it's pretty much new to me the concept of power set of multi-set.

How's it defined?

Answer 1

Just one suggestion:

Probably you can rewrite $\displaystyle{\left(\sum_{i\in P}a_i\right)^{n}}$ using the following formula:

Let $A$ and $B$ be two finite sets and $g:A\times B\longrightarrow\mathbb{R}$ a functions, then

$$\prod_{x\in A}\left(\sum_{y\in B}g(x,y)\right)=\sum_{f:A\longrightarrow B}\prod_{x\in A}g(x,f(x))$$ where the RHS sum is taken over all maps from $A$ to $B$.

Also, it's good to try to use the following formula:

Let $[n]=\{1,2,\ldots,n\}$ and let $f,g:2^{[n]}\longrightarrow\mathbb{R}$ be two functions. Then the following assertions are equivalents:

1. For all $A\subseteq [n]$, $\ \ \displaystyle{f(A)=\sum_{I\subseteq A}g(I)}.$
2. For all $A\subseteq [n]$, $\ \ \displaystyle{g(A)=\sum_{J\subseteq A}(-1)^{\vert A\vert-\vert J\vert}f(J)}.$

Take $f$ defined as $$f(X)=\left(\sum_{i\in X}a_{i}\right)^{n},\quad \forall\, X\in 2^{[n]}$$ and $g$ defined as $$g(Y)=\left(\prod_{j\in Y}a_j\right)\cdot\vert Y\vert!,\quad \forall\, Y\in 2^{[n]}$$

Answer 2

Note that for any real valued function,$f$, defined on the subsets of a finite set $S$ we have: $$ \sum_{P \subseteq S} f(P) = \sum_{P \subseteq S} f(S-P). $$

Let $n = |S|$ and $s = \sum_{i \in S} a_i$ then $$\sum_{P\subseteq S}(-1)^{n-\mid P\mid}(\sum_{a\in P}a)^n = \sum_{P\subseteq S}(-1)^{\mid P\mid}(\sum_{a\in S-P}a)^n = \sum_{P\subseteq S}(-1)^{\mid P\mid}(s - \sum_{a\in P}a)^n = s^n - \sum_{i=1}^{n}( s - a_i)^n + \sum_{1\leq i_1 < i_2 \leq n}(s-a_{i_1}-a_{i_2})^n - \dots +(-1)^{n-1}\sum_{i=1}^na_i^n $$

Method 1: Counting Argument

We have to create a sample, with replacement, of size $n$, from a given set of candidates. The candidates come from $n$ countries : $c_1,\dots,c_n$, there are $a_1$ candidates from country $c_1$,$a_2$ candidates from $c_2$,$\dots$, $a_n$ candidates from $c_n$.

How many ways can we choose our sample of size $n$ so all $n$ countries are represented?

Let $s = \sum_{i=1}^n a_i$ be the total number of candidates. The the total ways of constructing the sample is $s^n$.

Let $A_i$ denote the number of samples in which country $c_i$ is not represented. Clearly $|A_i| = (s-a_i)^n$.

Similarly for distinct $i_1,i_2,\dots,i_k$ we have $|A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}| = (s -a_{i_1}-a_{i_2} - \dots - a_{i_k})^n.$

By inclusion-exclusion the number of samples in which all countries are represented is $s^n - \sum_{i=1}^n (s-a_i)^n + \sum_{i_1 < i_2} (s - a_{i_1} - a_{i_2})^n - \dots = \sum_{P\in 2^S}(-1)^{n-\mid P\mid}(\sum_{a\in P}a)^n.$

However since there only $n$ countries, each member of the sample must come from a distinct country. Having fixed an order in the which the countries appear in the sample, we have $a_1 \times a_2 \times \dots \times a_n$ choices, and the countries can appear in the sample in $n!$ ways, giving a total of $n! \prod_{i=1}^n a_i$ ways. Equating the two gives the result.

Method 2: Comparing coefficients

$$\sum_{P\subseteq S}(-1)^{\mid P\mid}(s - \sum_{a\in P}a)^n = s^n - \sum_{i=1}^{n}( s - a_i)^n + \sum_{1\leq i_1 < i_2 \leq n}(s-a_{i_1}-a_{i_2})^n - \dots + (-1)^{n-1} \sum_{i=1}^{n} a_i^n \tag{1}$$ is a polynomial in $a_1,\dots,a_n$. A typical term of this polynomial is $a_{i_1}^{n_1}a_{i_2}^{n_2} \dots a_{i_r}^{n_r}$ where $ 1 \leq r \leq n$, $ 1 \leq i_1 < i_2 < \dots < i_r \leq n$ and $\sum_{i=1}^{r} n_i = n. $

Assume first $ r < n$. The coefficient of $$a_{i_1}^{n_1}a_{i_2}^{n_2} \dots a_{i_r}^{n_r}$$ in a polynomial of the form $(s - a_{t_1} - a_{t_2} - \dots - a_{t_s})^n$ is $0$ if $\{t_1,\dots,t_s\} \bigcap \{ i_1,i_2,\dots, i_r \} \neq \phi$ , otherwise it is $ \dfrac{n!}{i_1! i_2! \dots i_r!}$. This implies the coefficient is $0$ is $ s > n - r.$

Since it is possible to choose $t_1,t_2,\dots, t_s$ in $\binom{n-r}{s}$ ways such that $\{t_1,\dots,t_s\} \bigcap \{ i_1,i_2,\dots, i_r \} = \phi$, this implies the coefficient of $a_{i_1}^{n_1}a_{i_2}^{n_2} \dots a_{i_r}^{n_r}$ in (1) if $r < n$ is $$ \left(\sum_{i=0}^{n-r} \binom{n-r}{i}(-1)^{i}\right) \dfrac{n!}{i_1! i_2! \dots i_r!} = 0. $$

If $r = n$ we must have $i_1 = 1,i_2 =2, \dots , i_n = n$ and the coefficient of $a_1 a_2 \dots a_n$ is $\dfrac{n!}{1! 1! \dots 1!} = n!$ and the result follows.

Answer 3

The Wikipedia article Permanent section on Computation comes with a formula that can be specialized, if each row of the matrix is the same, to give your formula. The Wikipedia formula is $$\textrm{perm}(A):=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}=(-1^n\sum_{S\subset\{1,\dots,n\}}(-1)^{|S|}\prod_{i-1}^n\sum_{j\in S}a_{ij}.$$ If we let $a_{ij}=a_j$ for all $i$, and use a bit of algebra, we get your formula.