Let $X\triangleq\{x_1,\dots,x_n\}$ be a set of $n$ vectors $x_1, \dots, x_n \in\mathbb{R}^d$. I'm trying to formalize how to index all possible subsets $Y\subseteq X$ because I have to compute a summation in the following form \begin{equation*}S(X)\triangleq\sum_{Y\subseteq X} f(Y)\end{equation*} where $f$ is a set function $f:\mathcal{F}(\mathbb{R}^d)\mapsto \mathbb{R}$, with $\mathcal{F}(\mathbb{R}^d)$ being the set of all finite subsets of $\mathbb{R}^d$. In order to fix the ideas we can consider \begin{equation*} f(\{x_1,\dots,x_n\})=\begin{cases} \quad\hfil 0 & \text{ if } n=0 \\ \quad\hfil \prod_{i=1}^n \lVert x_i \rVert & \text{otherwise} \end{cases} \end{equation*} there is nothing special in this function, it is just a random example.
toy example
Let $n\triangleq3$, so that $X=\{x_1,x_2,x_3\}$. In this case the possible cardinalities $c\triangleq|Y|$ of $Y$ are $c=0,1,2,3$. Then, listing in cardinality $c$ order, we have the following possible 8 subsets of $X$
- for $c=0$: $Y=\varnothing$
- for $c=1$: $Y=\{x_1\},\{x_2\}.\{x_3\}$
- for $c=2$: $Y=\{x_1,x_2\}, \{x_1,x_3\}, \{x_2,x_3\}$
- for $c=3$: $Y=\{x_1,x_2,x_3\}$
the idea to indicize the previous subsets $Y$ is the following: lets forget for the momement the empty case, then for a given cardinality $c\in\{1,2,3\}$, we have to pick up $c$ indexes $i_{1},\dots,i_c$ from the set $\{1,2,3\}$. Since we are defining a set $Y$, the $c$ indexes must be constructed according to the following rules:
- no repetitions, in the sense that $i_1\neq i_2 \neq \dots \neq i_c$
- no permutations, in the sense that $i_1< i_2 < \dots < i_c$
Clearly, rule 2 absorb rule 1. Let's call the set of all possible indexes $i_{1},\dots i_c$ satisfying rule 2 as $P_{c,3}^{>}$. This set is given by \begin{equation*} P_{c,3}^{>}\triangleq \left\{\begin{array}{rl} i_1&=1,2,3\\ i_2&=1,2,3\qquad i_2>i_1\\ \vdots&\\ i_c&=1,2,3\qquad i_c>i_{c-1}> \dots >i_1 \end{array}\right\} \end{equation*} we have (sorry for the different representation of the elements, I hope you get the point) \begin{equation*} P_{1,3}^{>}=\left\{\begin{array}{c} (i_1=1)\\ (i_1=2)\\ (i_1=3) \end{array}\right\} \qquad P_{2,3}^{>}=\left\{\begin{array}{c} (i_1=1, i_2=2)\\ (i_1=1, i_2=3)\\ (i_1=2, i_2=3) \end{array}\right\} \qquad P_{3,3}^{>}=\left\{\begin{array}{c} (i_1=1, i_2=2, i_3=3) \end{array}\right\} \end{equation*} accordingly, if I'm not wrong so far, we can write \begin{equation*} \sum_{Y\subseteq X} f(Y)= f(\varnothing)+\sum_{c=1}^{3} \sum_{i_1,\dots,i_c\in P_{c,3}^{>}} f(\{x_{i_{1}},\dots, x_{i_c}\}) \end{equation*}
Just for a quick check, the total number of terms in the summation is, as expected, \begin{equation*} 1+\sum_{c=1}^3 |P_{c,3}^{>}|=1+\sum_{c=1}^{3} \binom{3}{c}=\sum_{c=0}^{3} \binom{3}{c}=2^3=8 \end{equation*}
general case
For an arbitrary set $X$ it should hold the following \begin{equation*} S(X) = f(\varnothing)+\sum_{c=1}^{|X|} \sum_{i_1,\dots,i_c \in P_{c,|X|}^{>}} f(\{x_{i_1},\dots, x_{i_c}\}) \end{equation*} which should include $2^{|X|}$ terms because such number is \begin{equation*} 1+\sum_{c=1}^{|X|} \binom{|X|}{c}=\sum_{c=0}^{|X|} \binom{|X|}{c}=2^{|X|} \end{equation*}
Question
Does it makes sense my solution? Is it correct?