Associated Topics || Dr. Math Home || Search Dr. Math

### Mean of a Set of Numbers by Subsets

```
Date: 08/15/99 at 01:53:54
From: Dave Bartlett
Subject: Mean of a set of numbers

Dear Dr. Math,

Suppose that we have a finite set of numbers. Prove that the mean of
this set is the mean of the means of all the non-empty subsets of the
set.

I can see that this is true for some simple examples, e.g. {1, 2, 3},
and I can imagine that it is true in general, but I'm not sure how to
prove it. Could you help?

Dave
```

```
Date: 08/17/99 at 11:31:09
From: Doctor Budrow
Subject: Re: Mean of a set of numbers

Hello Dave,

Thanks for writing to Dr. Math.

This is a good problem that illustrates several concepts in
combinatorics. It is also a good exercise in complicated notation.

To prove your proposition you need to know that:

1) The number of non-empty subsets of a finite set with N elements
is 2^N-1.

2) C(N,0) + C(N,1) + ... + C(N,N) = 2^N, where C(N,n) =
N!/((N-n)!*n!). So C(N,1) + ... + C(N,N)=2^N-1.

3) (N/n)C(N-1,n-1) = C(N,n).

If you need some help on the above, please write back.

Using the above facts, let's see how to prove your problem. If S is a
set with N numbers, S = {x_1, x_2, ..., x_N}, then it has 2^N-1
non-empty subsets, say S_1, S_2, ..., S_M, where M = 2^N-1. The mean
of S is

(1/N)*(x_1 + x_2 + ... + x_N)

Let mu_i be the mean of subset i so the mean of the subsets is

(1/M)*(mu_1 + mu_2 + ... + mu_M)

The contribution of x_1 to the mean of S is x_1/N, but what is the
contribution of x_1 to the mean of the non-empty subsets of S? To
answer this question, we have to count how many subsets x_1 appears in
and calculate x_1's contribution to the mean of means for these
subsets. This is where the notation becomes a little confusing if you
aren't careful, but let's start counting.

First, there is only one set of size 1 that has x_1 as a member and
whose mean is just x_1. This means (no pun intended) that for this
subset, x_1 contributes x_1/M to the mean of means.

Next, there are C(N-1,1) subsets of size 2 that have x_1 as a member,
so for these subsets x_1 contributes

C(N-1,1)*(x_1/(2*M))

to the mean of means. To see this, note that if we chose x_1 to be in
a subset of size 2, there are N-1 elements to choose from for the
other element. There are C(N-1,1) ways to pick them.

Similarly, there are C(N-1,2) subsets of size 3 that have x_1 as a
member, so for these subsets x_1 contributes

C(N-1,2)*(x_1/(3*M))

to the mean of means. To see this, note that if we chose x_1 to be in
a subset of size 3, there are N-1 elements to choose from for the
other 2 elements. There are C(N-1,2) ways to pick them.

In general there are C(N-1,n-1) subsets of length n that have x_1 as a
member. The contribution of x_1 from these subsets to the mean of
means is

C(N-1,n-1)*(x_1/(n*M))

Finally, let's add all the contributions of x_1 to the mean of means.
This sum will be

(x_1/M)*(1 + C(N-1,1)/2 + C(N-1,2)/3 + ... + C(N-1,N-1)/N)

Let's write this sum as

(x_1/M)*(C(N-1,0) + C(N-1,1)/2 + ... + C(N-1,N-1)/N)

This is where a trick is needed to put this a form that will almost
show the result. Multiply this sum by N/N (which is just one) to get

(x_1/(N*M))*((N/1)*C(N-1,0) + (N/2)*C(N-1,1) + ... + (N/N)*C(N-1,N-1))

From (3), this sum becomes

(x_1/(N*M))*(C(N,1) + C(N,2) + ... + C(N,N))

and from (2) the sum becomes

(x_1/(N*M))*(2^N-1)=(x_1/(N*M))*M = x_1/N

In other words, the contribution of x_1 to mean of means is exactly
the same as its contribution to the mean of S.

Since the same argument holds for each of the x_i's, the mean of the
means is the same as the mean.

You should try this on your example of S = {1,2,3} just to make sure
you understand the notation, which you see can get quite involved.

If you need more, please write back.

- Doctor Budrow, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search