Число комбинаций при которых хотя бы одна цифра на своем месте

#математика #комбинаторика

Есть 5 позиций (первая-пятая). Есть 5 цифр 1-5. Как посчитать число комбинаций, при
которых хотя бы одна цифра будет на своей позиции (1 в первой или 5 в пятой, или 12345
и тд). Для частного случая посчитать могу, а формулу в общем виде вывести не получается.
    

Ответы

Ответ 1

Все перестановки = N!
Все беспорядки(!n) = Сумма[k=0 -> N]((-1)^k N!/k!)
Перестановки, содержащие хотя бы одну неподвижную точку = N! - !n


Для N = 5:  

!n = N! - N!/1 + N!/2! - N!/3! + N!/4! - N!/5! 
   = N!(1/2 - 1/6 + 1/24 - 1/120)
N! - !n = N!(1 - 1/2 + 1/6 - 1/24 + 1/120)
        = 120(...) = 120 - 60 + 20 - 5 + 1 = 76




Беспорядки