2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Несколько задач по комбинаторике
Сообщение14.11.2010, 02:14 
Попробуйте следующее. Имеется $n$ ячеек и в каждую их них Вы ставите число от $1$ до $n$. Общее количество способов которыми можно это сделать равно $n^n$.
Теперь выбрасываем одно число и $A_1$ - множество способов которыми можете разместить $n-1$ числа по $n$ ячейкам. Ясно, что как минимум два элемента будут совпадать. Выбрасываем два числа и $A_2$ - множество способов которыми можете разместить $n-2$ числа по $n$ ячейкам. Также, как минимум 3 элемента будут совпадать. И так далее до $A_n$.
Теперь $\cup_{i=1}^n A_i$ - множество комбинаций в которых как минимум два элемента совпадают. Подсчитайте по формуле включения исключения количество элементов в этом объединении. После этого найдите сколько элементов содержится в дополнении. Затем используйте то, что количество комбинаций в которых все элементы разные равно $n!$, количество элементов в дополнении.

 
 
 [ Сообщений: 16 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group