= Solution
For $q\geq1$, choose an ordered list of $q$ distinct elements: there are $n(n-1)\cdots(n-q+1)$ such lists. Every $q$-element <subset> occurs in exactly $q!$ orders, the number of <permutations> of its elements. Thus the count is the <binomial coefficient>
$$
\boxed{\binom nq=\frac{n(n-1)\cdots(n-q+1)}{q!}.}
$$
For fixed $q$ and $n\geq2q$, every numerator factor lies between $n/2$ and $n$. Consequently
$$
\frac{n^q}{2^q q!}\leq\binom nq\leq\frac{n^q}{q!}.
$$
The constants depend on the fixed $q$, not on $n$. These inequalities prove $\binom nq=\Theta(n^q)$ in <big theta notation>. More precisely, dividing the product by $n^q$ gives the <fixed-cardinality binomial coefficient asymptotic> $\binom nq\sim n^q/q!$. For $q=0$, there is exactly one empty <subset>, and the assertion is $1=\Theta(1)$.
Back to article page
