Комбинаторика разбиений
При анализе стратегий различных игр требуется подсчитывать количество комбинаций при раскладе определенных предметов. Наиболее распространенная карточная игра - преферанс. В классическом варианте этой игры карты раскладываются на 3 кучки (по числу играющих) и 2 карты кладутся в "прикуп". Играют 32 картами, т. е. каждый игрок получает по 10 карт.
Определим количество вариантов расклада при игре в преферанс:
Для обоснования полученной формулы расставим все карты подряд и переставим их 32! способами. При каждой перестановке будем выделять первые 10 карт первому игроку, вторую десятку - второму, третью - третьему, а последние 2 карты будем откладывать в "прикуп". После этого заметим, что перестановка 10 карт в руках каждого игрока не меняет варианта расклада, как и положения 2 карт в прикупе. Поэтому 32! разделим, три раза на 10! и еще на 2!
При игре в древнюю китайскую игру НИМ раскладываются n спичек на 3 кучки. Сколько вариантов раскладки этих спичек?
Для определения количества вариантов расклада выпишем подряд n единиц и справа добавим к ним 2 нуля. Переставляя эти объекты всеми возможными способами, мы каждый раз будем получать один из вариантов расклада. Более того, любому варианту расклада можно сопоставить некоторую перестановку из n единиц и двух нулей. Таким образом, получаем:
Р(n, 2) = (n + 2)!/(n!2!).
А теперь определитеколичество количество вариантов расклада, при котором в любой кучке есть хотя бы одна (две, три) спички?
В общем случае, если раскладываются n разных предметов по k ящикам так, чтобы в 1-й ящик (кучку, игроку в руки) попало предметов, во второй предмета, в k-й - предметов, при этом + + ...+ = n, то число вариантов расклада
