Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 3 / b / Solution

For $q\ge 1$, 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 coefficientFor fixed $q$ and $n\ge 2q$, every numerator factor lies between $n/2$ and $n$. ConsequentlyThe constants depend on the fixed $q$, not on $n$. These inequalities prove $\left(\genfrac{}{}{0ex}{}{n}{q}\right)=\Theta (n^q)$ in big theta notation. More precisely, dividing the product by $n^q$ gives the fixed-cardinality binomial coefficient asymptotic $\left(\genfrac{}{}{0ex}{}{n}{q}\right)\sim n^q/q!$. For $q=0$, there is exactly one empty subset, and the assertion is $1=\Theta (1)$.