Alphabet

N

nasi112

Full Member
Joined
Aug 23, 2020
Messages
708
This question is done on the 26 letters of the alphabet.

The answer is
[math]!26 = \lfloor \frac{26!}{e} + \frac{1}{2} \rfloor[/math]
I will explain the question for three letters A, B, C

The question is in how many ways can the letters A, B, C be rearranged so that no letter appears in its original position?

All combinations

ABC
ACB
CBA
BAC
CAB
BCA

Only CAB and BCA have no fixed letters

The answer is 2

With the formula

The answer is

[math]!3 = \lfloor \frac{3!}{e} + \frac{1}{2} \rfloor = 2[/math]
How to derive this formula

[math]!n = \lfloor \frac{n!}{e} + \frac{1}{2} \rfloor[/math]
 
An induction requires proving
[math] (-1)^{n+1} +(n+1)\left\lfloor \dfrac{n!}{e}+\dfrac{1}{2}\right\rfloor\stackrel{!}{=} \left\lfloor (n+1) \dfrac{n!}{e}+\dfrac{1}{2}\right\rfloor [/math]
 
It is way easier:
[math]\begin{array}{lll} !n&=n!\displaystyle{\sum_{k=0}^n\dfrac{(-1)^k}{k!}}\\[16pt] \dfrac{1}{e}&=\displaystyle{\sum_{k=0}^\infty \dfrac{(-1)^k}{k!}}\\[16pt] \end{array}[/math][math]\begin{array}{lll} \left\lfloor \dfrac{n!}{e}+\dfrac{1}{2} \right\rfloor&=\left\lfloor \dfrac{1}{2}+n!\displaystyle{\sum_{k=0}^\infty \dfrac{(-1)^k}{k!}}\right\rfloor= !n+\underbrace{\left\lfloor \dfrac{1}{2}+\displaystyle{\sum_{k=n+1}^\infty \dfrac{(-1)^kn!}{k!}}\right\rfloor}_{=0} \end{array}[/math]
 
Thanks guys for the help.

If I did not see the answer, I will not know there is this formula

[math]!n = \lfloor \frac{n!}{e} + \frac{1}{2} \rfloor[/math]
I will start solving the question by 2 letters

AB
BA

Combination 2
Answer 1

Then 3 letters

ABC
ACB
CBA
BAC
CAB
BCA

Combination 6
Answer 2

Then 4 letters

Combination 24
Answer 9

Then 5 letters

Combination 120
Answer 44

Then 6 letters

Combination 720
Answer 265

and so on

After that I will look for a pattern to write a general formula. I do not see the pattern. If I do not write the formula, I will not be able to solve the original question of the 26 letters of the alphabet.

If my attempt to solve this question is wrong, what is the correct way to solve this question?
 
First, look at the first line of #4; that is the result you should get by looking for a pattern. See if you can find a way to explain that formula. A useful approach is the inclusion-exclusion principle.

The formula you initially asked about essentially says that this formula (for the probability !n/n!) is an approximation to the series that yields 1/e (the second line), and that the actual value of the former can be obtained by rounding the latter to the nearest integer.
 
You must log in or register to reply here.
Top