I’m having a hard time finding the pattern. Let’s say we have a set

S={1,2,3}

The subsets are:

P={{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

And the value I’m looking for, is the sum of the cardinalities of all of these subsets. That is, for this example, 0+1+1+1+2+2+2+3=12

What’s the formula for this value?I can sort of see a pattern, but I can’t generalize it.

**Answer**

Here is a bijective argument. Fix a finite set S. Let us count the number of pairs (X,x) where X is a subset of S and x∈X. We have two ways of doing this, depending which coordinate we fix first.

**First way**: For each set X, there are |X| elements x∈X, so the count is ∑X⊆S|X|.

**Second way:** For each element x∈S, there are 2|S|−1 sets X with x∈X. We get them all by taking the union of {x} with an arbitrary subset of S∖{x}. Thus, the count is ∑x∈S2|S|−1=|S|2|S|−1.

Since both methods count the same thing, we get

∑X⊆S|X|=|S|2|S|−1,

as in the other answers.

**Attribution***Source : Link , Question Author : Chris Vilches , Answer Author : Mike F*