We write each element of [$n-1]$ on a separate card, then randomly select any number of cards, and take the product of the numbers of written on them. Then we do this for all $2^{n-1}$ possible subsets of the set of $n-1$ cards. (The empty product is taken to be $1$) . Finallly, we take the sum of the $2^{n-1}$ products obtained. What is the sum? give a combinatorial answer.
attempt: Let $[n-1]= {\{1,2,....,n-1}\}$. Let $S(n)$ the sum of $n$ terms. Then if we pick randomly any number of cards, then we assume that the card can have a number or not, and so there are two options, either yes, or no. then we can do this for all $2^{n-1}$ possible subsets.
If we choose 1 element, the element would have its sum as either zero or that number. For example if we say $1 \leq a \leq n-1 $ So if $a$ is just one element, then $a$ has to options So S(1) = 0 or S(1) = a
For two numbers, say $b,d$ then $S(2) = 0 $ or $S(2) = b+d$.
So if we take three cards, for example, and get A, 3s, and 2s, then their product will be 1 because we would have empty product.
or its sum.
I am not sure how to define a sum, could someone please give me an example or some feedback? I don't know how to define a formula , I was thinking a recursive formula to give the sum of the $2^{n-1}$ products obtained. I would really appreciate it. Thank you.
Use induction,the empty product is equal to $1$. Let $F_n$ be the desired number.
We have $F_2=1+1$.
For $n\geq 3$ notice that the sum of the product over all the subsets that dont contain $n-1$ is $F_{n-1}$ and the sum of the products over all subsets that do contain $n-1$ is $(n-1)F_{n-1}$ so we get $F_n=nF_{n-1}$
and so we clearly have $F_n=n!$