ГЛАВА IV. ПЕРЕЧИСЛЕНИЕ

§ 40. Введение

В начале § 8 мы показали, как понятие производящей функции может быть использовано в задачах о перечислении. Но такой процесс применим только в случае неупорядоченных -выборок; в случае же упорядоченных -выборок пришлось бы ввести такие производящие функции, которые приводят к некоммутативной алгебре. Хотя это и возможно, но даже прямое перечисление оказывается более эффективным. Эта глава посвящается вопросу о разумных способах перечисления.

Когда количество перечисляемых элементов велико, часто отказываются от составления полного списка и вводят некоторые характеристики, с помощью которых его можно получить. Следует иметь в виду, что процесс перечисления часто связан с пересчетом Метод «латинской композиции», или «сцепления», который мы приводим здесь, — не единственный метод перечисления; существуют и другие, например перечисление с помощью понятия «груды», как в работе Пэра [34]. Другой метод предложен Фоулксом (см. [2], стр. 281); в нем используется разложение на максимальные сильно связные подграфы, встречающиеся во многих задачах.

За недостатком места мы лишены возможности изложить все эти методы.