48
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I want to tag this "elementary set theory". Do others agree? Combinatorics and the study of finite sets have a substantial overlap. $\endgroup$ – MathematicsStudent1122 Nov 6 '16 at 0:25
  • 2
    $\begingroup$ @MathematicsStudent1122: in this case it's really more of a simple combinatorial identity disguised as a set-theory problem. Yes the fields overlap. $\endgroup$ – smci Nov 6 '16 at 1:47
  • $\begingroup$ Elementary set theory will be more appropriate $\endgroup$ – Anurag Nov 6 '16 at 7:02
  • $\begingroup$ @Anurag: Why would you say that? $\endgroup$ – Asaf Karagila Nov 6 '16 at 13:08
  • 4
    $\begingroup$ I guess the answer to this question is the combinatorial approach to evaluating $\sum_{k=0}^n k\binom{n}{k}$. $\endgroup$ – StubbornAtom Nov 6 '16 at 14:37

11 Answers 11

55
$\begingroup$

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 \in 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 \in X$, so the count is $\sum_{X \subseteq S} |X|$.

Second way: For each element $x \in S$, there are $2^{|S|-1}$ sets $X$ with $x \in X$. We get them all by taking the union of $\{x\}$ with an arbitrary subset of $S\setminus\{x\}$. Thus, the count is $\sum_{x \in S} 2^{|S|-1} = |S| 2^{|S|-1}$.

Since both methods count the same thing, we get $$\sum_{X \subseteq S} |X| = |S| 2^{|S|-1},$$ as in the other answers.

$\endgroup$
  • 1
    $\begingroup$ Brilliant! ${}{}$ $\endgroup$ – Georges Elencwajg Nov 6 '16 at 1:03
40
$\begingroup$

Each time an element appears in a set, it contributes $1$ to the value you are looking for. For a given element, it appears in exactly half of the subsets, i.e. $2^{n-1}$ sets. As there are $n$ total elements, you have $$n2^{n-1}$$ as others have pointed out.

$\endgroup$
  • 4
    $\begingroup$ Nice and clean, +1! $\endgroup$ – Mike F Nov 6 '16 at 0:36
  • 3
    $\begingroup$ Nice, but needs more explanation why each element appears in exactly half of the subsets. I don't think this is obvious to everyone. $\endgroup$ – Zane Nov 7 '16 at 19:44
  • 1
    $\begingroup$ @Zane For a given element $x$ of your set, there is a bijection between the subsets which do not have $x$ as an element, and the subsets which have it. The bijection is simply "add $x$ to the subset". $\endgroup$ – Jean-Claude Arbaut Nov 10 '16 at 6:44
33
$\begingroup$

Let $N=|A|$.

There is one set of cardinal $0$, there are $N$ of cardinal $1$, ${N\choose2}$ of cardinal $2$, and more generally $N \choose k$ of cardinal $k$.

Thus for $N\ge1$ : $$\sum_{X \subseteq A}|X| = \sum_{k=0}^{N} k{N \choose k} = \sum_{k=1}^{N} N{N-1 \choose k-1} = N\sum_{k=0}^{N-1} {N-1 \choose k} = N 2^{N-1}$$

This formula also applies when $N=0$.

$\endgroup$
  • $\begingroup$ For $N=0$ binomial coefficients of the form $\binom{-1}{j}$ show up. $\endgroup$ – mvw Nov 10 '16 at 11:56
  • $\begingroup$ @mvw True, I edited, thanks ! $\endgroup$ – Astyx Nov 11 '16 at 9:58
31
$\begingroup$

Reading the solution of Jack M made me think of another strategy which I can't help but post as a second answer, because I think it is a splendid argument :)

Recall the trick for finding the sum $1+2+\ldots+n$.

Denote the answer by $a$. We write out the sum twice, reversing order the second time \begin{align*} a &= 1+2+3 & &&\ldots +n \\ a &= n + \ldots & &&+ 3 + 2 + 1 \\ \end{align*} Each column adds to $n+1$, and there are $n$ columns, so we get $$\begin{align*} 2a = n(n+1) && \Longrightarrow && a= \frac{n(n+1)}{2} \end{align*}$$

Let $S$ be a set with $n$ elements. We want to find the sum $|A_1| + |A_2| + \ldots + |A_{2^n}|$ where $A_1,\ldots,A_{2^n}$ are all the subsets of $S$. OK, let's play the same trick again!

Denote the answer by $b$. We write out the sum twice, taking the complement of each term the second time \begin{align*} b &= |A_1|+|A_2|+|A_3| + \ldots +|A_{2^n}| \\ b &= |A_1^c|+|A_2^c|+|A_3^c| +\ldots +|A_{2^n}^c| \\ \end{align*} Each column adds to $n$ and there are $2^n$ columns so we get $$\begin{align*} 2b = n 2^n && \Rightarrow &&b = n 2^{n-1}. \end{align*}$$

$\endgroup$
  • 2
    $\begingroup$ Ah, very nice too. $\endgroup$ – Georges Elencwajg Nov 6 '16 at 1:06
21
$\begingroup$

Yet another way, a manipulation of summations without binomial coefficients:

$$\begin{align*} \sum_{A\subseteq S}|A|&=\sum_{A\subseteq S}\sum_{x\in A}1\\ &\overset{(1)}=\sum_{x\in S}\sum_{A\subseteq S\text{ s.t. }x\in A}1\\ &\overset{(2)}=\sum_{x\in S}2^{|S|-1}\\ &=|S|2^{|S|-1} \end{align*}$$

Step $(1)$ is just reversing the order of summation, and step $(2)$ uses the fact that each $x\in S$ is in half of the subsets of $S$, one for each subset of $S\setminus\{x\}$.

This is really just a computational version of the basic idea of Mike F’s combinatorial argument.

$\endgroup$
7
$\begingroup$

There are $2^n$ subsets of the original set. We can pair these sets by grouping a given set with its complement (i.e. $A$, $S - A$). There are $2^n / 2 = 2^{n-1}$ such pairs and the sum of the cardinalities of each set in the pair is $n$. This gives us a total of $n2^{n-1}$.

EDIT: Also, if anyone is interested, there is a nice "story proof" of the above identity $$ \sum_{k=0}^n k \binom{n}{k} = n2^{n-1}.$$ Suppose we want to pick a committee of any size with a president from a group of $n$ people. Two committees are distinct if the set of people that compose them are different or if they are the same but have a distinct president. We would like to count the number of distinct committees. We first can pick a committee of size $k$ with $k=0,1,2, \ldots, n$ (this happens in $\binom{n}{k}$ ways) and then select a president from the $k$ committee members. This gives the LHS of the above identity. Alternatively, we can first elect the person we want to be president (we have $n$ choices) and then pick a subset of the remaining $n-1$ people to round out his committee (there are $2^{n-1}$ choices). This gives the RHS of the above identity.

$\endgroup$
6
$\begingroup$

Let $n$ be the cardinality of your set. We have to calculate $\sum \binom n k k$. Since $\binom n k=\binom n {n - k}$, we can pair off the terms of this sum like: $\binom n k k + \binom n {n - k} (n - k)=\binom n k n$. When $n$ is even we also get the extra term $\binom n {n/2}\frac n 2$. Thus, for odd n:

$$\sum_{k=0}^n \binom n k k = n \sum_{k=0}^{n/2} \binom n k=n\frac 1 2\sum_{k=0}^n\binom n k=n2^{n-1}$$

For even $n$ we have essentially the same calculation, except that there's the extra $\binom n {n/2} \frac n 2$ term in the second step.

$\endgroup$
  • 2
    $\begingroup$ This is really nice, but I think it can be used to inspire an even nicer argument! We want to add up the cardinalties of all sets $A \subset S$. But each set $A$ can be paired with its complement $A^c$, such that the total sum is always $|A|+|A^c| = n$. Since there are $2^{n-1}$ complementary pairs $\{A,A^c\}$, this gives the count $n 2^{n-1}$. In fact, phrasing this slightly differently, one could think of this as being exactly analogous to the legendary trick for summing $1+2+\ldots+n$. Look instead at two times the sum, and strategically pair off the terms. $\endgroup$ – Mike F Nov 5 '16 at 23:56
  • $\begingroup$ See Mike F. above. $\endgroup$ – richard1941 Nov 10 '16 at 17:17
5
$\begingroup$

For the subsets of size $k$ one needs the number of ways how to draw $k$ distinguishable elements from $\lvert S \rvert$ available, which is given by the binomial coefficient. This is multiplied by the number of elements, thus $k$, and summed up over all possibilites: $$ \sum_{A \in 2^S} \lvert A \rvert = \sum_{k=0}^{\lvert S \rvert} \binom{\lvert S \rvert}{k} k $$ For your example: $$ \sum_{A \in 2^S} \lvert A \rvert = \sum_{k=0}^3 \binom{3}{k} k = 1 \cdot 0 + 3 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 0 + 3 + 6 + 3 = 12 $$ Setting $$ s(n) = \sum_{k=0}^n \binom{n}{k} k $$ we have \begin{align} s(n+1) &= \sum_{k=0}^{n+1}\binom{n+1}{k} k \\ &= \sum_{k=1}^{n+1}\binom{n+1}{k} k \\ &= \sum_{k=1}^{n+1}\frac{(n+1)!}{k!(n+1-k)!} k \\ &= \sum_{k=1}^{n+1}\frac{(n+1)!}{(k-1)!(n-(k-1))!} \\ &= (n+1) \sum_{k=1}^{n+1} \binom{n}{k-1} \\ &= (n+1) \sum_{k=0}^n \binom{n}{k} \\ &= (n+1) \sum_{k=0}^n \binom{n}{k} 1^k \cdot 1^{n-k} \\ &= (n+1) (1+1)^n \\ &= (n+1) 2^n \end{align} This gives $s(0) = 0$ and $s(n) = n 2^{n-1}$ for $n \ge 1$ and $$ \sum_{A \in 2^S} \lvert A \rvert = \lvert S \rvert \, 2^{\lvert S \rvert - 1} $$

For your example this would mean $s(3) = 3 \cdot 2^2 = 3 \cdot 4 = 12$.

$\endgroup$
  • $\begingroup$ What does 2^S mean in this context? $\endgroup$ – Felo Vilches Nov 5 '16 at 15:49
  • $\begingroup$ That is a notation for the power set of $S$, thus the set of all subsets of $S$. $\endgroup$ – mvw Nov 5 '16 at 15:53
5
$\begingroup$

For finite sets, it's easy to derive this formula by induction.

Let $n_k$ denote the sum of the cardinalities of all the subsets of a $k$-element set. Clearly, $n_0 = 0$, since the only subset of an empty set is empty. Now, let $S$ be a $k-1$ element set, and consider what happens when we add one more element $x$ to $S$ to obtain the $k$ -element set $S' = S \cup \{x\}$.

Clearly, the subsets of $S'$ can be divided into two groups of equal size: those that contain $x$, and those that don't. The subsets of $S'$ that do not contain $x$ are exactly the subsets of $S$, and so the sum of their cardinalities is $n_{k-1}$.

The subsets of $S$ that do contain $x$, meanwhile, can be mapped one-to-one onto those that don't, simply by removing $x$ from them, with each subset containing exactly one more element (namely $x$) more than the corresponding $x$-less subset. Thus, the sum of their cardinalities equals $n_{k-1} + m_k$, where $m_k = |P(S)| = 2^{k-1}$ is the number of subsets of $S$ (and thus also the number of subsets of $S'$ that contain $x$).

Thus, the total sum of the cardinalities of the subsets of $S'$ is $n_k = 2n_{k-1} + 2^{k-1}$. Noting that:

\begin{eqnarray} n_1 &=& 2 n_0 + 2^0 &=& 0 + 1 &=& 1 &=& 1 \cdot 2^0, \\ n_2 &=& 2 n_1 + 2^1 &=& 2 + 2 &=& 4 &=& 2 \cdot 2^1, \\ n_3 &=& 2 n_2 + 2^2 &=& 8 + 4 &=& 12 &=& 3 \cdot 2^2, \\ n_4 &=& 2 n_3 + 2^3 &=& 24 + 8 &=& 32 &=& 4 \cdot 2^3, \\ n_5 &=& 2 n_4 + 2^4 &=& 64 + 16 &=& 80 &=& 5 \cdot 2^4, \\ \end{eqnarray}

we may observe a pattern, and guess that a closed-form solution would be $n_k = k \, 2^{k-1}$.

We can then easily verify that this guess indeed satisfies the recurrence we derived above: if $n_{k-1} = (k-1)2^{k-2}$, then $n_k = 2(k-1)2^{k-2} + 2^{k-1} = k \, 2^{k-1}$.

$\endgroup$
3
$\begingroup$

There are three things you can do to find the pattern (and, knowing the answer, the first two will work for this problem):

  1. Work out MORE examples than just one. It's hard to find a pattern in one number.
  2. Write out the prime factorizations of the numbers.
  3. Write down the difference of every two consecutive terms and see if there is a pattern there.
$\endgroup$
  • 1
    $\begingroup$ You don't even attempt to answer the question... Take a look at @stableMatch's answer to see how your post was supposed to look like. $\endgroup$ – Alex M. Nov 6 '16 at 11:40
  • 2
    $\begingroup$ @AlexM. OP: "I'm having a hard time finding the pattern." that sort of seemed worth addressing no? There were answers already stating the solution. I don't think posting another one was valuable. It seems like learning how to find a pattern is a good skill in mathematics. And it's not like my answer is ruining the others. $\endgroup$ – djechlin Nov 6 '16 at 14:44
  • $\begingroup$ In principle I agree with you, but in this case it seems that none of your three suggestions helps. $\endgroup$ – Alex M. Nov 6 '16 at 14:50
  • $\begingroup$ @AlexM. the first two make the answer pretty obvious. Obvious enough that I'm positive the OP did not try it. $\endgroup$ – djechlin Nov 6 '16 at 20:07
  • 2
    $\begingroup$ @AlexM., “supposed to”? Are you kidding? $\endgroup$ – Carsten S Nov 7 '16 at 9:35
2
$\begingroup$

You can encode every subset of a set as a binary number. If the set has $n$ elements, then you need the binary numbers of length $n$. Position $i$ in the number is element $i$ of the original set. An element $i$ is in the subset, if you have a 1 at position $i$.

There are $2^n$ numbers of length $n$, and there are $n$ digits per number. So in all the digits of all numbers are $n*2^n$.

Now the sum of the cardinality of all subsets is just the number of 1's in all these numbers. For each binary number, you can complement each bit to get another binary number of the same length. Thus the number of 0's and 1's must be the same, or put it another way: the number of 1's must be half of the digits.

Therefore, the number of 1's is $n*2^n/2$ or $n*2^{n-1}$, and that is the number of the sum of the cardinalities.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.