This is exercise $1.2$ in Nicholas Loehr's book "Combinatorics".
Which is larger: the number of binary strings of length $56$, or the number of permutations of the English alphabet ($26$ letters)?
Letting $D$ and $P$ denote these sets, respectively, it is obvious that $|D|=2^{56}$ and $|P|=26!$. I checked using a calculator that $26!$ is indeed larger, but I want to find a combinatorial argument for this.
So far, I have been unsuccessful. I have been trying to find an injection $D\hookrightarrow P$, though I'm not sure this is the best strategy.
I know that any binary string can be represented uniquely in the form $0^{\alpha_1}10^{\alpha_2}1\cdots 10^{\alpha_k}$ where $0^j$ denotes a string of $j$ consecutive zeroes. However, this doesn't immediately help to get a permutation of $26$ letters, since the $\alpha_i$ could be between $0$ and $56$, and they could repeat. But maybe there is something that can be done with the $\alpha_i$ to get an injection.
On the other hand, one can uniquely represent a permutation as a $26\times 26$ matrix with exactly one $1$ per row and column and zeroes elsewhere. But I don't see a way to get a map from these matrices that would surject onto $D$.
I also considered that $2^{56}$ is the number of subsets of a $56$-element set, but that didn't seem to lead anywhere so far yet either.
Any hints on how to continue any of the above ideas to get a combinatorial proof, or alternative methods would be appreciated.
Edit: I am aware that it can be shown, e.g., inductively, that $n!$ is larger than $2^n$ for $n$ sufficiently large (or that $n! > 2^{2n+4}$ in this case), but I am interested in a more combinatorial argument for this.
Best Answer
One way to do it:
De Polignac's Formula allows us to factor factorials easily. Here we get $$26!= 2^{23}\times 3^{10}\times 5^6\times 7^3\times 11^2\times 13^2\times 17\times 19\times 23$$
But it is easy to see that $3^{10}>2^{10}$ and $5^6>2^{12}$ and $7^3>2^6$ and $11^2>2^6$ and that's more than sufficient.