Difference between revisions of "User:John0512"
m |
|||
| Line 7: | Line 7: | ||
Since the reciprocal of a factorial decreases faster than a geometric series, we have that <math>\sum_{i={n+1}}^\infty \frac{1}{i!}<\frac{1}{(n+1)!}+\frac{1}{(n+1)!(n+1)}+\frac{1}{(n+1)!(n+1)^2}\cdots</math>. The right side we can evaluate as <math>\frac{1}{n(n!)}</math>, which is always less than or equal to <math>\frac{1}{n!}</math>. This means that the terms being subtracted are always strictly less than <math>\frac{1}{n!}</math>, so we can simply write it as <cmath>\lfloor n!\cdot e\rfloor.</cmath> | Since the reciprocal of a factorial decreases faster than a geometric series, we have that <math>\sum_{i={n+1}}^\infty \frac{1}{i!}<\frac{1}{(n+1)!}+\frac{1}{(n+1)!(n+1)}+\frac{1}{(n+1)!(n+1)^2}\cdots</math>. The right side we can evaluate as <math>\frac{1}{n(n!)}</math>, which is always less than or equal to <math>\frac{1}{n!}</math>. This means that the terms being subtracted are always strictly less than <math>\frac{1}{n!}</math>, so we can simply write it as <cmath>\lfloor n!\cdot e\rfloor.</cmath> | ||
| − | Example: How many ways are there 5 clones of mathicorn to each either accept or reject me, then for me to go through the ones that accepted me in some order? | + | Example: How many ways are there 5 distinct clones of mathicorn to each either accept or reject me, then for me to go through the ones that accepted me in some order? |
Solution to example: This is equivalent to the Unnamed Theorem for <math>n=5</math>, so our answer is <math>\lfloor 120e \rfloor=\boxed{326}</math>. | Solution to example: This is equivalent to the Unnamed Theorem for <math>n=5</math>, so our answer is <math>\lfloor 120e \rfloor=\boxed{326}</math>. | ||
Revision as of 22:40, 14 September 2021
I have something called the Unnamed Theorem (which I did not name as I have not confirmed that this theorem has not existed before).
Claim: Given a set 
where 
is a positive integer, the number of ways to choose a subset of 
then permute said subset is 
Proof: The number of ways to choose a subset of size 
and then permute it is 
. Therefore, the number of ways to choose any subset of is ![\[\sum_{i=0}^n \binom{n}{i}\cdot i! = \sum_{i=0}^n \frac{n!}{(n-i)!}.\]](http://latex.artofproblemsolving.com/4/a/4/4a4de9a20d25a54b46cfe4d264efccfaea7ac703.png)
This is also equal to 
by symmetry across 
. This is also 
Note that 
is defined as 
, so our expression becomes ![\[n!(e-\sum_{i={n+1}}^\infty \frac{1}{i!}).\]](http://latex.artofproblemsolving.com/3/0/a/30ad6f9fbc2afb04fd7f5cce3eb35ef5d148aa31.png)
We claim that 
for all positive integers .
Since the reciprocal of a factorial decreases faster than a geometric series, we have that 
. The right side we can evaluate as 
, which is always less than or equal to 
. This means that the terms being subtracted are always strictly less than , so we can simply write it as ![\[\lfloor n!\cdot e\rfloor.\]](http://latex.artofproblemsolving.com/b/6/b/b6b17898bfb6718898259c7a695b8c08f23af28e.png)
Example: How many ways are there 5 distinct clones of mathicorn to each either accept or reject me, then for me to go through the ones that accepted me in some order?
Solution to example: This is equivalent to the Unnamed Theorem for 
, so our answer is 
.
