2
$\begingroup$

I suspect something with sets since one with cardinality $n$ has $n!$ permutations and its powerset contains $2^n$ elements. It could also involve binomial coefficients because of$$\begin{pmatrix}n\\0\end{pmatrix}+\begin{pmatrix}n\\1\end{pmatrix}+\begin{pmatrix}n\\2\end{pmatrix}+\cdot\cdot\cdot+\begin{pmatrix}n\\n\end{pmatrix}=2^n$$

$\endgroup$
  • $\begingroup$ It’s an easy induction on $n$. $\endgroup$ – Brian M. Scott Nov 27 '20 at 20:00
  • $\begingroup$ Do you want a combinatorial interpretation? Base on your question you should tag it in combinatorics or combinatorial proofs. $\endgroup$ – Phicar Nov 27 '20 at 20:13
1
$\begingroup$

If $n!>2^n$ multiply both sides by $(n+1)$ to get $$ (n+1)!>(n+1)2^n> 2 \times 2^n > 2^{n+1} $$ with minor details to be filled.

$\endgroup$
1
$\begingroup$

The number $n!$ is the product of the $n-1$ numbers $2,3,\ldots,n$, each of which is greater than or equal to $2$ (and all of them but $2$ is actually greater than $2$) and, since $n>3$, at least one of them is greater than or equal to $4$. So, $n!>2^{n-2}\times4=2^n$

$\endgroup$
0
$\begingroup$

I think it's simpler than you're suggesting. Are you familiar with proof by induction? Here's a hint: once you know that $4! > 2^4$, look at how you get from $4!$ to $5!$ and from $2^4$ to $2^5$. If you can prove it for $n = 5$ given that it's true for $n = 4$, can you continue that process?

$\endgroup$
0
$\begingroup$

multiply both sides by n+1 Then prove that $(n+1)!2^n$ is greater than $2^{n+1}$

$\endgroup$
0
$\begingroup$

The OP was not very clear if them were looking for a combinatorial interpretation, in such case:

Consider the following function $Fix : S_n\longrightarrow P([n]),$ called the set of fixed points of a permutation, where $S_n$ is the set of permutations on $[n]$ and $P([n])$ is the powerset of $[n],$ defined as $$Fix(\pi)=\{i: \pi(i)= i \},$$ for some permutation $\pi ,$ meaning we are recording the fixed points of the permutation.

Notice that if we fix $n-1$ points in the permutation, we are fixing $n$ because there is no space to make the$ n-$th element not fixed. So any set $A\subseteq [n]$ such that $|A|=n-1$ is not the set of fixed points of any permutation. So, apriori, $$n!=|S_n|\geq 2^n-n+1.$$ We actually can say more, using the Derangements(permutations without fixed points, denoted by $D_m$) we can decompose $S_n$ in the statistic of how many fixed points the permutation has i.e., $$n!=\sum _{k=0}^n\binom{n}{k}D_{n-k}=\sum _{k=0}^{n-2}\binom{n}{k}D_{n-k} +1,$$ where the last equality is by the argument above on how there are no permutations that fix $n-1$ points exactly. Now, notice that $D_{n-1}>2$ iff $n>3,$ because $D_k>D_{k-1}$ for $k>1$ (why? ). So we can split this as $\binom{n}{1}D_{n-1}=\binom{n}{1}+\binom{n}{1}(D_{n-1}-1)=\binom{n}{n-1}+\binom{n}{1}(D_{n-1}-1).$ So we have that $$n!=\sum _{k=0}^n\binom{n}{k}D_{n-k}=\sum _{k=0}^{n-2}\binom{n}{k}D_{n-k} +1=D_n+\binom{n}{1}(D_{n-1}-1)+\sum _{k=2}^{n-2}\binom{n}{k}D_{n-k}+\binom{n}{n-1} +1>\sum _{k=0}^n\binom{n}{k}=2^n.$$

$\endgroup$
0
$\begingroup$

Since $n\ge 4$ we have $n! = 1\cdot 2\cdot 3\cdot 4 \cdot 5\cdots n = 24 \cdot 5 \cdots n > 16 \cdot 5 \cdots n\ge 2^4\cdot 2 \cdots 2 = 2^42^{n-4}=2^n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.