Разместить 4 одинаковых шарика по 8 ячейкам.

[DLL]

Сколько существует способов размещения 4 одинаковых шариков по 8 ячейкам, так чтобы хотя бы некоторые два шарика находились рядом?

Мыслю так: нужно чтобы некоторые два шарика находились рядом, поставим их сразу в ячейки - всего 7 способов размещения. Затем разместим еще два шарика в оставшиеся 6 ячеек и того получается: 6*5/2 способов.

Всего способов: 7*6*5/2.

Правильно?

[arseniiv]

Должно быть меньше. При данном построении можно получить одну и ту же расстановку: к примеру, сначала поставим два шарика в ячейки 3 и 4, а потом добавим в 1 и 2. То же можно получить, поставив сначала в 1 и 2, а потом дополнив шариками в 3 и 4.

Более того, даже очевидная оценка сверху $\binom 84 = \frac{8\cdot 7\cdot 6\cdot 5}{2\cdot 3\cdot 4} = \frac{7\cdot 6\cdot 5}3$ меньше вашей.

[Dave]

DLL в сообщении #542069 писал(а):

Сколько существует способов размещения 4 одинаковых шариков по 8 ячейкам, так чтобы хотя бы некоторые два шарика находились рядом?

Мыслю так: нужно чтобы некоторые два шарика находились рядом, поставим их сразу в ячейки - всего 7 способов размещения. Затем разместим еще два шарика в оставшиеся 6 ячеек и того получается: 6*5/2 способов.

Всего способов: 7*6*5/2.

Правильно?

Неправильно. Так некоторые варианты посчитаются более одного раза. Нужно подсчитать общее количество размещений (несмотря на слово "размещений", в данном случае это будут сочетания), а потом вычесть количество тех размещений, в которых никкакие два шарика не находятся рядом.