Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/05/09.pdf Дата изменения: Fri Dec 23 19:25:25 2005 Дата индексирования: Tue Oct 2 00:09:36 2012 Кодировка: Windows-1251 Поисковые слова: воздушные массы

ЧТО

ТАКОЕ

КОМБИНАТОРИКА

9
Для тех, кто еще не устал, можно добавить следующее. Если забыть о способе решения и думать лишь об аналогии с задачей о покупке пирожных, то придется, пожалуй, принять несмотря на все сказанное ранее, что 'повторяются' все-таки пираты! В общем, неразбериха что надо. Мораль проста: начинающим не рекомендуется связываться с термином 'сочетания с повторениями' без особой надобности. Можно ведь говорить о числе решений уравнения (6) в целых xi 0 . Это кристально ясное выражение, не дающее повода для 'кривотолков'. Задачи о дележе (II постановка) и о покупке пирожных внешне различны. Но стоит написать уравнение (6), как сразу становится очевидным, что это одна и та же задача. Иногда вместо количества решений уравнения (6) в целых xi 0 говорят о количестве разбиений числа m на n неотрицательных слагаемых. Это хуже. При наличии нулевых слагаемых не очень уместно говорить о разбиениях (можно ли считать, что 3 = 3 + 0 + 0 + 0 означает 'разбиение' числа 3 на 4 слагаемых?), но главное в другом. Разбиения 8 = 5 + 3 и 8 = = 3 + 5 это два разных разбиения или это по существу одно и то же разбиение? Можно понимать и так и этак, стало быть, нарушается Главное Правило Комбинаторики. В то же время вряд ли кто-нибудь усомнится в том, что x1 = 5, x2 = 3 и x1 = 3, x2 = 5 это разные решения уравнения x1 + x2 = 8. На сей счет в математике устойчивые традиции. Стоит ли уделять столько внимания терминологии ведь в конечном счете она несущественна? В конечном, пожалуй, и впрямь несущественна. Но для начинающих 'начальный счет' куда важнее 'конечного'.
(Окончание следует)

ная совсем простенькая на вид задача сама по себе не так уж проста. Но после того как найдено число решений уравнения (6) в целых xi 0 , тут и в самом деле почти нечего делать разве что обозначить через xi количество покупаемых пирожных i-го сорта (i = 1, , n). Искомое число равно (7). Конечно, речь могла идти не о пирожных, а о чем-либо другом. Важно лишь, что ищется число неупорядоченных наборов из m элементов, причем каждый элемент принадлежит какому-либо из n типов. Так как элементы одного типа считаются неразличимыми, то допускаются, таким образом, 'повторения' элементов в наборе.

'Повторения с повторениями'
Размещения, перестановки, сочетания и сразу, как грибы после дождя, размещения с повторениями, перестановки с повторениями, сочетания с повторениями С непривычки можно растеряться, тем более, что повторения не всегда понимаются одинаково. Стоит, пожалуй, вернуться к этим терминам и еще немного о них поговорить. Так сказать, повторение на тему повторений. Вот, к примеру, такой вопрос. Перестановки частный случай размещений, и формула для числа перестановок частный случай формулы для числа размещений. С другой стороны, перестановки с повторениями вроде бы частный случай размещений с повторениями, но формула для числа перестановок с повторениями отнюдь не является частным случаем формулы для числа размещений с повторениями. В чем тут дело? Когда речь идет о повторениях элементов в наборе (упорядоченном или нет), возможны две противоположные ситуации: а) нет никаких ограничений на число повторений элементов (кроме того, что общее число элементов набора равно заданному числу); б) каждый элемент должен повторяться в наборе заданное число раз. Встречаются и варианты, промежуточные между этими двумя, но сейчас они нам не нужны. Размещения с повторениями и сочетания с повторениями объединяет то, что имеется в виду а), тогда как число перестановок с повторениями опреде3 Квант ? 5

ляется в ситуации б). Конечно, размещения и перестановки (с повторениями или без) близки в другом отношении как упорядоченные наборы, тогда как сочетания (с повторениями или без) наборы неупорядоченные. Кстати, для неупорядоченных наборов постановка б) бессодержательна (ответ, очевидно, равен 1). Насколько полезна и удобна вся эта 'повторительная' терминология? Для очень простого (по виду и m смыслу) выражения n название 'число размещений с повторениями из n по m' является, пожалуй, излишне длинным и торжественным. Но в ясности ему не откажешь. Перестановки с повторениями термин ясный и удачный. В случае сочетаний с повторениями с ясностью не все благополучно. Вернемся к задачам из предыдущего пункта. При покупке пирожных проблем не возникает (кроме финансовой); ясно, что здесь повторяются пирожные одного сорта. Задача дележа рассматривалась в двух постановках I (пираты с признаками морали) и II (аморальные пираты). В случае I возникали сочетания, в случае II сочетания с повторениями. А что, собственно, повторяется в варианте II? Монеты? Они, естественно, 'повторяются', поскольку идентичны. Но они ведь были идентичными и в варианте I. Пираты? Но каждый из них у нас в единственном экземпляре. Правда, можно кодировать дележ, сопоставляя каждой монете имя владельца; тогда пираты (вернее, их имена) будут повторяться. Но, опять-таки, в этом смысле они 'повторялись' и в I постановке однако там были сочетания без повторений. Если исходить из метода решения, следует признать, что повторяются промежутки между монетами как места для перегородок. При II постановке, в отличие от I, один промежуток может повториться для нескольких перегородок. Прямо скажем, промежуток между монетами вещь куда менее ощутимая, чем монета или пирожное. Два пирата, которым при дележе достались лишь 'промежутки между монетами', вряд ли станут выяснять, один и тот же у них промежуток или разные скорее, они станут выяснять отношения с другими членами шайки.