# How many subsets of size at most $\log n$ does a set of size $n$ have?

I was reading this paper on an algorithm for finding a dominating set in a tournament graph. The paper claims that an $n$-element set has $n^{O(\log n)}$ subsets of size at most $\log n$. The paper doesn't offer any proof of this, and I don't know how to prove that this is true.

Is there a straightforward way to show this?

Thanks!

-
I think it actually claims that an $n$-element set has $n^{O(\log n)}$ subsets of size at most $\log n$ (which is obviously true). The | sign appears to correspond to ^ in LaTeX. – user73985 May 7 '13 at 15:28
Oh wow, I miswrote the original question. That's definitely supposed to be $n^{O(\log n)}$. Sorry about that! – templatetypedef May 7 '13 at 15:31

If we pull with replacement, there are $n^{\log n}$ possibilities for a draw of size $\log n$. Pulling without replacement to get a subset will decrease the possibilities. Then if we sum for the number of elements from $1$ to $\log n$ we get $\frac {n^{1+log n}-1}{n-1}\in O(n^{\log n})$
You can write this number $\sum_{k=0}^{\log n} {n \choose k} \leq (\log n + 1) {n \choose \log n}$, and try to approximate this last term.