# algorithm – What is the chance that C and C will be on the same key?

## Question:

Given. There are 26 characters in the English alphabet. We place them on a 33-key keyboard no matter in what order.

Next, we are given 33 characters of the Cyrillic alphabet. It is known that 12 of them coincide (practically) in the style of `А,В,Е,К,М,Н,О,Р,С,Т,У,Х` with English ones. We randomly place them on the keyboard.

How do you calculate the chance that at least any one pair of similar characters (for example, `C` and `С` ) will appear on the same key? And two pairs, three, and so on?

Let's set the Cyrillic letters in some order, number from 1 to 33. Let's number the Latin letters from 1 to 26. They need to be placed in positions from 1 to 33. The number of ways to do this is equal (this is called the number of placements )

``````      33!       33!
N = --------  = --- = 1722880479922993352285356032000000
(33-26)!     7!
``````

Let us denote by `g(i)` number of ways to put our 26 Latin characters in 33 Cyrillic ones so that at least characters from `1` to `i` match. This number is

``````        (33-i)!
g(i) = --------
7!
``````

Let me explain: that is, we can put `26-i` letters in `33-i` positions:

``````      (33-i)!         (33-i)!
------------------ =  -------
((33-i) - (26-i))!       7!
``````

Now all this needs to be multiplied by the number of combinations from `12` to `i` , in order to take into account all possible `i` letters from 12:

``````                                   / 12 \
f(i) = g(i)*binomial(12,i) = g(i)*|      |
\  i /
``````

Now we use the inclusion-exclusion formula to determine how many combinations we have have no matches:

``````N - f(1) + f(2) - f(3) ... = 1193302430098089637938828023808000
(сумма идёт до 12)
``````

That is, from the total number of all possible arrangements, we subtract those that have at least one match, but when we counted them by multiplying by the number of combinations, we also took into account the coincidences of 2, 3, etc. letters several times, they are needed add back. And so on, read the theory here .

Well, we know the number of options when there is no match, and the number of all options. We divide one into another:

``````0.6926205526174549408291876419168263634...
``````

Now let's count the number of combinations when there is at least one match. It will be

``````f(1) - f(2) + ... = 529578049824903714346528008192000
``````

All according to the same formula for enabling an exception. We divide this number by `N` we get:

``````0.307379447382545059170812358083173636622...
``````

Next, we want at least two matches:

``````f(2) - f(3) + f(4) - ... = 96923942874366595575419639808000
``````

and likelihood

``````0.05625691625381857719282400555318999974
``````

And so on:

``````0 :: 0.6926205526174549408291876419168263634...
1 :: 0.307379447382545059170812358083173636622...
2 :: 0.05625691625381857719282400555318999974...
3 :: 0.006243083746181422807175994446810000...
4 :: 0.0004773463613454589132541130800...
5 :: 0.0000266858967190572157781449844444...
6 :: 0.0000011227795879505706512209777...
7 :: 3.59e-8
8 :: 8.687e-10
9 :: 1.55e-11
10:: 1.949e-13
11:: 1.54e-15
12 :: 5.88e-18
``````

Who wants to plus my answer, plus also @ Harry's answer, with his help I made sure that the calculations were correct.

Scroll to Top