What is the total sum of the cardinalities of all subsets of a set?

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 xX. We have two ways of doing this, depending which coordinate we fix first.

First way: For each set X, there are |X| elements xX, so the count is XS|X|.

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

Since both methods count the same thing, we get
XS|X|=|S|2|S|1,
as in the other answers.

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

Leave a Comment