Median of the subsets of a finite set of real numbers Starting from this$^1$ question, using Mathematica I did the following.
Generated a sequence of $n$ random distinct "real" numbers.
Computed the median of the $2^n$ subsets (conventionally $\emptyset$ has a median zero) and deleted duplicates.
The number $m$ of distinct medians I got, was constant for fixed $n$ and followed a simple rule
$$m=\frac{1}{2} \left(n^2+n+2\right)$$
The code I used is the following
Table[{n, 
  Length[DeleteDuplicates[
    Median /@ Subsets[Table[RandomReal[10^12], {k, 1, n}]]]]}, {n, 1, 20}]

Do you know why this happens?
Edit
There are exceptions
Consider $A=\{1,2,3,4\}$
The value predicted by the formula is $m=11$ but we have
$$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{4\},\{1,2\},\{1,3\},\{1,4\},\\\{2,3\},\{2,4\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,3,4\}\}$$
Medians are $$\left\{0,1,2,3,4,\frac{3}{2},2,\frac{5}{2},\frac{5}{2},3,\frac{7}{2},2,2,3,3,\frac{5}{2}\right\}$$ and the distinct ones are only $8$:
$$\left\{0,1,2,3,4,\frac{3}{2},\frac{5}{2},\frac{7}{2}\right\}$$
[1]: Efficient way to get median of all subsets.

Median has to be equal to either some number from $x_1,\ x_2,\ldots,x_n$, or arithmetic mean of two of these numbers (plus our case with zero). So number of different results is
$$ {{n}\choose{0}} + {{n}\choose{1}} + {{n}\choose{2}}  = \frac{n^2+n+2}{2} $$
