# Counting small subsets of a given set

Denote by $P_n$ the set of all subsets of $\lbrace 1,2,3, \ldots ,n \rbrace$. Obviously, the proportion of subsets in $P_n$ of size $\leq \frac{n}{2}$ tends to $\frac{1}{2}$. What about the proportion of subsets of size $\leq \frac{n}{3}$ ?

-
Numerical computation would suggest it goes to $0$. But the naive bounds don't seem to give it to you. –  JSchlather Nov 13 '12 at 20:31

The number of subsets of size $k$ is $n \choose k$. The first fact is true because the left half of a late row of Pascal's triangle (maybe you're missing the middle term) has roughly half the total (by symmetry). However, in late rows of Pascal's triangle, the middle third terms are far greater than the first third, so you should expect the proportion to tend to zero.

One quick and dirty way to make this formal is to use this mathoverflow bound on the sum of the first k terms in the nth row. Explicitly, if $n=3m$, then $2^{-n}\sum_{k=0}^{n/3}{n \choose k}\le2^{-3m}{3m \choose m}\frac{3m-\left(m-1\right)}{3m-\left(2m-1\right)}\to2^{1-3m}{3m \choose m}\to0$.

-

The law of large numbers says that for every $\epsilon>0$ the probability that you get less than a fraction ${1\over2}-\epsilon$ heads in $n$ tosses of a coin tends to $0$ when $n\to\infty$. This is true in particular for $\epsilon={1\over6}$.

-

The following heuristic argument may help in understanding the phenomenon. Let $X$ be the number of heads when a fair coin is tossed $n$ times. We want to estimate $$\Pr\left(X \le \frac{n}{3}\right).$$ This probability is well approximated by the probability that a normally distributed random variable with mean $\dfrac{n}{2}$ and standard deviation $\dfrac{\sqrt{n}}{2}$ is less than or equal to $\dfrac{n}{3}$.

That in turn is equal to the probability that a standard normal is $\gt \dfrac{\sqrt{n}}{3}$. This probability approaches $0$ rapidly as $n$ increases.

More formally, we can use the Central Limit Theorem to prove that the limit is $0$. There are good estimates available for the error in the normal approximation to the binomial. These can be used to get precise information about the speed of convergence to $0$.

-