Изменения

Отнимая это число от общего числа перестановок <tex> 10! </tex>, получим ответ. == Задача о нахождении числа взаимно простых четвёрок ==  Дано <tex> n </tex> чисел: <tex> a_1, a_2,..., a_n </tex>. Необходимо посчитать количество способов выбрать из них четыре числа так, что они будут взаимно простыми, то есть их НОД равен единице.  Посчитаем число "плохих" четвёрок, то есть таких, в которых все числа делятся на число <tex> d > 1 </tex>. Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на <tex> d </tex> (но, возможно, делящихся и на больший делитель). <tex> answer=\sum \limits_{d>1} (-1)^{deg(d)-1} \times f(d) </tex>, где <tex> deg(d) </tex> — это количество простых в факторизации числа <tex> d </tex>, <tex> f(d) </tex> — количество четвёрок, делящихся на <tex> d </tex>. Чтобы посчитать функцию <tex> f(d) </tex>, надо просто посчитать количество чисел, кратных <tex> d </tex>, и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку. Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д.