Rewrite sum on tuples

59 Views Asked by At

Let $J_n:=\{1,\dots,n\}$ and let $f:\mathcal{P}(J_n)\to[0,\infty]$ be a map on the power set $\mathcal{P}(J_n)\equiv 2^{J_n}$. For any $0\leq m\leq n$, define $F_m := \sum_{S\subseteq J_n:|S|=m}f(S)$ and $L_m := \sum_{j_1,\dots,j_m\in J_n}f(\{j_1,\dots,j_m\})$. The goal is to rewrite $F_m$ as a linear combination of $L_m$.

Examples: Clearly $F_0 = L_0$, $F_1=L_1$.

Now the problem starts for higher $m$, since already for $m=2$ we are over-counting. Firstly because $\{j_1,j_2\}=\{j_2,j_1\}$ and secondly because $\{j_1,j_1\}=\{j_1\}$. To deal with this I thought that one could first remove the diagonal term and then divide by two: $F_2 = \frac{1}{2}(L_2-L_1)$.

Assuming this is correct, I would like to derive such a formula of $F_m$ for arbitrary $m$. What I could come up with is $F_m=\frac{1}{m!}(L_m-\frac{m(m-1)}{2}L_{m-1})$.

My question is: is this correct? If not, what is the correct formula to express $F_m$ in terms of $L_{m'}$?