Q$1\mathrm{.}11$

$1$ Point

In the Boggle game, a naive algorithm finds all possible $k-$letter words by enumerating all permutations of size $k$ of the $n$ letters and checking that the letters in the permutation are adjacent on the Boggle board and that the permutation represents a valid word in the dictionary. How many such permutations exist?

$P_k^n,$ that is$,n$ permute $k$

$n!$

$n^k$

$C_k^n,$ that is$,n$ choose $k$