Г. А. Клековкин П. С. Богданов

РЕШЕНИЕ КОМБИНАТОРНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ СРЕДЫ MAXIMA

Учебное пособие

Математика и информатика

Государственное бюджетное образовательное учреждение высшего профессионального образования города Москвы «Московский городской педагогический университет»

Самарский филиал

Г. А. Клековкин

П. С. Богданов

Решение комбинаторных задач с использованием среды MAXIMA

Учебное пособие

Самара 2015

УДК 519.1 ББК 22.141 К48

Печатается по решению Ученого совета СФ ГБОУ ВПО МГПУ

Рецензенты:

доктор педагогических наук, профессор кафедры фундаментальной и компьютерной математики Вятского государственного гуманитарного университета С. И. Калинин;

доктор физико-математических наук, профессор, заведующий кафедрой алгебры, геометрии и методики обучения математике Стерлитамакского филиала Башкирского государственного университета П. Н. Михайлов

Клековкин Г. А., Богданов П. С.

К48 Решение комбинаторных задач с использованием среды MAXIMA: учебное пособие / Г. А. Клековкин, П. С. Богданов. — Самара: СФ ГБОУ ВПО МГПУ, 2015. — 88 с.

ISBN 978-5-9905895-3-7

В пособии рассмотрены примеры использования системы компьютерной математики Maxima при решении комбинаторных задач на выбор и упорядочивание элементов конечного множества, разбиение конечных множеств и разложение натуральных чисел на слагаемые. Даны инструкции и индивидуальные задания для трех лабораторных работ.

Предназначено для студентов вузов, обучающихся по направлению 050100 Педагогическое образование. Может быть использовано при проведении лабораторных работ в курсе «Дискретная математика», а также при разработке и проведении специальных курсов.

УДК 519.1 ББК 22.141

ISBN 978-5-9905895-3-7

© СФ ГБОУ ВПО МГПУ, 2015

© Г. А. Клековкин, П. С. Богданов, 2015

Содержание

Введение............................................................... 4

Основы работы в системе Maxima................................ 6

Лабораторная работа № 1 «Вычисление комбинаторных чисел, заданных формулами»...................................... 21

Лабораторная работа № 2 «Рекуррентные соотношения» ... 36

Лабораторная работа № 3 «Производящие функции»........ 59

Литература............................................................. 87

Введение

Учебно-методическое пособие предназначено для организации и проведения лабораторных занятий по теме «Перечислительная комбинаторика» в курсе дискретной математики.

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

К сожалению, решение многих численных комбинаторных задач, как чисто учебных, так и прикладных, с помощью любого из перечисленных способов может быть сопряжено с громоздкими вычислениями. Поэтому на практических занятиях решение задач нередко заканчивается записью нужных для получения численного результата формул, рекуррентных соотношений или производящих функций. В лучшем случае преподаватель на аудиторных занятиях совместно со студентами доводит «с помощью бумаги и ручки» до численного результата две-три задачи. Вместе с тем, практика показывает, что некоторые студенты остаются неудовлетворенными такими решениями. Поэтому данное пособие адресовано в первую очередь именно тем студентам, которые привыкли заканчивать решение точными вычислениями.

Новые возможности для автоматизации численных и символьных вычислений открывают системы компьютерной математики. Существует множество коммерческих и свободно распространяемых систем компьютерной математики общего назначения. До недавнего времени наибольшей популярностью у нас в стране пользовались коммерческие системы Maple, Mathematica и MathCad. Однако из-за высокой стоимости эти программы нашим индивидуальным пользователям практически недоступны. Поэтому среди них растет интерес к свободно распространяемым программам, прежде всего к системе Maxima.

Система Maxima обладает весьма широкими возможностями для численных и символьных вычислений в различных областях математики и

во многих отношениях не уступает таким коммерческим системам, как Maple или Matematica. При этом система имеет небольшой размер дистрибутива, легко устанавливается, существуют ее русифицированные графические интерфейсы. Еще одним важным достоинством системы Maxima является ее многоплатформенность, она доступна как пользователям операционных систем Linux, так и пользователям Windows. Наконец, она чрезвычайно проста для освоения.

Система Maxima, таким образом, может стать идеальным объектом изучения и инструментом численных и символьных вычислений для школьников старших классов и студентов вузов, ее также могут использовать в своей работе как профессиональные математики, так и специалисты, имеющие дело с приложениями математики, для проведения сложных расчетов и исследований.

В стране постепенно формируется банк учебной и методической литературы, необходимой для массового внедрения системы Maxima в школьное и вузовское преподавание математики. Почти все имеющиеся пособия похожи по структуре и содержанию, авторы дают описание возможностей системы, ее интерфейса, правил ввода в систему команд и различных типов данных, рассматривают примеры решения задач, главным образом из базового курса высшей математики.

В данном пособии даны примеры использования системы Maxima при решении задач перечислительной комбинаторики. Авторы пособия при этом предполагают, что читатель уже знаком с интерфейсом системы и имеет начальные навыки работы с ней, полученные в базовом курсе математики. Поэтому общие сведения о работе в системе Maxima даны в пособии в минимально необходимом объеме. Для уточнения и расширения этих сведений читатель всегда может обратиться либо к англоязычному справочнику системы, либо к существующим руководствам по работе с ней, которые имеются в сети Интернет. (Отметим прежде всего учебно-методические пособия Н. А. Стахина [3] и Е. А. Чичкарёва [4].)

В пособии приведены инструкции и индивидуальные задания к трем лабораторным работам, которые могут быть проведены в практикуме по дискретной математики либо в факультативном курсе по системам компьютерной математики: «Вычисление комбинаторных чисел, заданных формулами», «Рекуррентные соотношения» и «Производящие функции».

Используемая в пособии терминология и обозначения комбинаторных чисел даны в полном соответствии с учебным пособием Г. А. Клековкина [2]. При подборке задач для индивидуальных заданий главным образом использовалась книга Н. Я. Виленкина [1].

ОСНОВЫ РАБОТЫ В СИСТЕМЕ MAXIMA

Как было отмечено во введении, авторы предполагают, что читатель уже имел опыт выполнения численных и символьных вычислений в среде Maxima. Поэтому в данном пункте лишь кратко напоминаются некоторые правила работы в этой среде и описываются функции, с которыми наиболее часто приходится сталкиваться при проведении вычислений в комбинаторных задачах, традиционно входящих в курс дискретной математики. Описания даны применительно к графическому интерфейсу wxMaxima, существенно облегчающему работу при решении типовых математических задач.

Ввод команд и вывод результатов. После запуска Maxima появляется окно программы, в рабочем поле которого вводятся и записываются все команды, обрабатываемые системой. Команда в Maxima — это любая комбинация выражений и встроенных функций. Разделителем команд является символ «;» (точка с запятой). После ввода команды для ее обработки и вывода результата необходимо нажать клавиши <Ctrl>+<Enter>.

Пример:

Предусмотрена возможность ввода сразу нескольких команд в одной строке, для этого одна команда от другой отделяется символом «;». При этом формируется одна строка ввода и столько строк вывода, сколько команд было задано.

Пример:

В рассмотренных примерах система в ответе вывела значение выражения, хотя, казалось бы, мы не задали никакой команды. Это объясняется тем, что в системе Maxima по умолчанию является активной функция упрощения: если вводимое выражение можно упростить, то система обязательно это делает.

Для обозначения конца ввода команды вместо точки с запятой можно использовать знак $, позволяющий не выводить на экран результат вычисления (команда при этом будет исполняться). Это удобно тогда, когда визуализация результата не нужна, например, при загрузке файлов с помощью функции load.

В том случае, когда выражение надо отобразить, а не вычислить, перед ним ставится знак «'» (одинарная кавычка). Но этот прием не работает, когда выражение имеет явное численное значение.

Примеры:

Две одинарных кавычки, последовательно примененные к выражению во входной строке, приводят к замещению входной строки результатом вычисления вводимого выражения.

Из рассмотренных примеров видно, что после ввода каждой команде присваивается ее порядковый номер: (%i1), (%i2), .... Соответствующие порядковые номера присваиваются и результатам вычислений: (%o1), (%о2), .... Это позволяет при дальнейшей записи команд ссылаться на ранее записанные команды и результаты вычислений.

Примеры:

Операторы. Для обозначения арифметических операций в Maxima используются знаки: «+» — сложение, «-» — вычитание, «*» — умножение, «/» — деление. Возведение в степень можно обозначать тремя способами: ^, ^^, **. Извлечение корня степени n записывают, как степень ^(1/n).

Для обозначения приоритета операции, как обычно, при записи команд используются круглые скобки ( ).

Операторы сравнения: < (меньше), < = (меньше, равно), > (больше), > = (больше, равно).

Логические операторы: and (и), or (или), not (не).

Константы. В Maxima для удобства вычислений имеется ряд встроенных констант. При выполнении лабораторных работ будут использоваться константы:

Название

Обозначение

π (число пи)

%pi

е (экспонента)

i = √—1 (мнимая единица)

%i

Истина

true

Ложь

false

Числа. Все функции и операторы Maxima работают как с действительными, так и с комплексными числами. При записи действительных чисел числитель и знаменатель обыкновенных дробей разделяется при помощи символа «/», целая и дробная части десятичных дробей разделяются символом точка, перед отрицательными числами ставится знак минус. Комплексные числа записываются в алгебраической форме, т. е. в виде а + b * %i, где а и b — соответственно действительная и мнимая части числа.

Переменные. Для выполнения промежуточных расчетов и хранения их результатов применяются переменные, которым могут присваиваться определенные значения. В виде значения такой переменной может выступать любое математическое выражение.

При вводе названий переменных важен регистр букв, так как переменные x и Х — это две разные переменные (сказанное в равной мере относится к записи функций и констант). Присваивание значения переменной осуществляется с использованием оператора «:» (двоеточие). Примеры:

В первом примере пользователем было введено а:2; — то есть переменной а присваивалось значение 2; (%i1) означает, что в данной строке и далее предполагается пользовательский ввод. Второй пример показывает, что переменной можно присваивать значение другой переменной или функции.

Математические функции. В Maxima имеется набор встроенных математических функций. Для ввода математической функции записывается ее название, а затем в круглых скобках через запятую перечисляются аргументы. Напомним, что некоторые обозначения функций, принятые в Maxima, отличаются от обозначений, используемых в отечественной математической литературе. При выполнении лабораторных работ будут использоваться функции:

Название

Обозначение

Квадратный корень (√х)

sqrt(x)

Экспонента (ех)

ехр(х)

Натуральный логарифм (lnх)

log(x)

Синус (sin х)

sin(x)

Косинус (cosx)

cos(x)

Абсолютная величина (|х|)

abs(x)

Знак числа sign x =

signum(x)

Пример:

Пользовательские функции. Пользователь может создавать собственные функции с помощью оператора задания функции пользователя «: =» (двоеточие и равно). Для этого сначала указывается название функции и в скобках перечисляются названия аргументов, затем после знаков «: =» следует описание функции. После задания пользовательская функция вызывается точно так же, как и встроенные функции Maxima. Это значительно облегчает работу с ней, поскольку к ней можно обращаться по имени и легко и удобно вычислять значения в заданных точках.

Пример:

Любое имя можно очистить от присвоенного ему выражения функцией kill() и тем самым освободить занимаемую этим выражением память. Для этого нужно просто набрать kill(name), где name — имя уничтожаемого выражения; причем это может быть как имя, назначенное пользователем, так и любая ячейка ввода или вывода. Точно так же можно очистить разом всю память и освободить все имена, введя kill(all). В этом случае очистятся и все ячейки ввода-вывода, а их нумерация опять начнется с единицы.

Списки. Списки — базовые строительные блоки в Maxima, представляющие собой конечные упорядоченные последовательности элементов. Элементами списка могут быть числа, переменные, выражения, другие списки; в частности, список может содержать один элемент, быть пустым. Для задания списка нужно в квадратных скобках через запятую перечислить его элементы.

Примеры:

Если элементы списка могут быть заданы с помощью формулы, то для его формирования удобно использовать команду makelist().

Пример:

Здесь сформирован список с именем L5, состоящий из десяти элементов, значения которых находятся по формуле k(k+1)/2.

В программе Maxima имеется широкий набор функций для работы со списками и набор функций для работы с элементами списка. Их описание можно найти в [4], а также в справочной системе программы.

Массивы. Массивы — упорядоченные совокупности однородных объектов, помеченных индексами. Число индексов не должно превышать пяти.

Для создания массивов в Maxima существует функция array (name, dim_1, ... , dim_n) и ее модификации. Здесь пате — имя переменной, в которой хранится массив, dim_1, ... , dim_n — размеры n — мерного массива (n < 5). Напомним также, что нумерация элементов массива начинается с 0 и заканчивается на dim_i, где i = 1, ..., n.

Примеры:

В первом примере сформирован одномерный массив А длиной 10, во втором — двумерный массив AA, имеющий 3 строки и 3 столбца.

Массив может быть заполнен путем непосредственного задания значений всех его элементов. Примеры:

Вывод значений элементов массива, как видим, осуществляется в столбец. Функция listarray(name) позволяет преобразовать массив в список. Порядок включения элементов массива в список — по строкам.

Примеры:

Для доступа к элементам массива используется порядковые номера элемента по каждой из размерностей, указанные в квадратных скобках через запятую.

Примеры:

Во многих случаях двумерные массивы удобней задавать построчно в виде матрицы с помощью функции matrix (row_1, ... , row_n).

Пример:

Следующий пример демонстрирует задание двумерного массива В = ||bij|| размерности 4×4, элементы которого заданы с помощью формулы

Программирование в Maxima. Во встроенном языке системы заложены основные исполнимые операторы, которые есть в любом языке программирования. Напомним их синтаксис.

Условный оператор в общем виде может быть записан следующим образом:

причем часть «else if cond_2 then expr_2 else if ...» можно опустить. Данный оператор выполняет действия expr_1, если условие cond_1 верно, и так далее, то есть выполняет действие expr_k, если условие cond_k: верно. Если ни одно из условий не верно, то выполняется действие expr_0. Кроме того, можно опустить и часть «else expr_0». В этом случае при невыполнении всех условий cond_k в качестве результата работы оператора получим «false».

Примеры:

1. Неполная форма условного оператора:

2. Полная форма условного оператора:

3. Полная форма условного оператора с ветвлением:

4. Полный условный оператор, составленный с использованием логического оператора:

Оператор цикла может задаваться несколькими способами. Способ задания зависит от того, известно ли заранее, сколько раз необходимо выполнить тело цикла. Имеются следующие виды циклов:

Как видно из их записи, операторы отличаются лишь последней частью, а их начало одинаково:

— variable — означает имя переменной, которая будет меняться внутри цикла;

— initial_value — начальное значение такой переменной;

— increment — то, на сколько изменяется эта переменная на каждой итерации цикла.

В циклах первого вида «thru limit» означает, что цикл должен закончиться тогда, когда переменная variable достигнет значения limit. В циклах второго вида «while condition» означает, что все операторы цикла будут выполняться до тех пор, пока верно условие condition. В случае «unless condition» цикл будет выполняться, пока условие condition ложно.

body — тело цикла.

При нормальном завершении цикла на экран выводится done. Принудительный выход из цикла осуществляется при помощи оператора return, который может возвращать произвольное значение. Для вывода результатов работы цикла существует команда display().

Примеры:

В первом примере программа выводит все числа отрезка от 0 до 10, делящиеся на 2.

Из этого примера видим, что несколько операторов можно объединять в блоки с помощью круглых скобок. Внутри скобок операторы следует разделять запятой.

Во втором примере приводится цикл для вычисления суммы натуральных чисел от 1 до 100.

В третьем примере ищется список, составленный из максимальных элементов столбцов заданной матрицы. При решении данной задачи в программе нужно описать два массива:

— заданный двумерный массив (матрицу),

— одномерный массив, в который будут записываться максимальные элементы из каждого столбца. Пусть это матрица В размерности 5 × 5, а искомый массив — это b.

Зададим элементы матрицы, например, следующим образом:

Для нахождения максимального элемента в столбцах потребуется второй внутренний (вложенный) цикл. Внешний цикл с переменной j будет перебирать столбцы, а во внутреннем цикле с переменной i элементы столбца будут сравниваться между собой для поиска наибольшего.

Как в условных операторах, так и в циклах вместо простых операторов можно писать составные операторы, т. е. блоки. Для этого имеется функция block([v_l, ..., v_m], expr_1, ..., expr_n). Здесь в квадратных скобках указаны локальные переменные, т. е. те, которые не будут доступны вне блока, a expr_1, ..., expr_n — последовательность операторов, которые будут выполняться внутри блока. Список локальных переменных может быть пустым. В качестве результата работы данная конструкция возвращает значение последнего выполненного оператора.

Пример:

Рассмотрим программу для вычисления знакопеременной суммы

В данном случае пользователю не обязательно знать значение переменной sig, так как оно нужно лишь во время вычислений и не влияет на восприятие результата, поэтому данную переменную имеет смысл сделать внутренней.

В частности, имеем:

Функции для вычисления комбинаторных чисел. Для вычисления числа сочетаний и числа размещений в Maxima предусмотрены функции:

— combination(n, k) — находит число Сnk сочетаний из n элементов по к,

— permutation (n,k) — находит число размещений из n элементов по k.

(Обе функции подключаются с помощью команды load(functs)). Для вычисления числа сочетаний можно также использовать функцию binomial(x, у), которая определена на множестве всех действительных чисел. (Если х, у не являются целыми, то биномиальный коэффициент вычисляется как многочлен от x и у.)

Пример:

Число Pn перестановок из n элементов вычисляет функция factorial(n). Удобно, однако, пользоваться функцией n!. Эта функция задает факториал в наиболее общем виде как гамма-функцию х! = gamma(x+1) и определена для всех комплексных чисел, кроме целых отрицательных. Факториал от целых неотрицательных чисел автоматически упрощается ею до натурального числа.

Пример:

Функции stirlingl(n, k) и stirling2(n, k) позволяют находить числа Стирлинга первого и второго рода соответственно. Пример:

Кроме рассмотренных функций в системе Maxima имеются другие функции для вычисления комбинаторных чисел. В частности, функции:

— fib(n), которая вычисляет n-е число Фибоначчи;

— bern(n), которая выполняет вычисление n-го числа Бернулли для целого п;

— euler(n), которая выполняет вычисление n-го числа Эйлера для целого n.

Для решения рекуррентных соотношений используется пакет расширений solve_rec, который загружается с помощью команды load(solve_rec).

Пример:

Найдено общее решение линейного однородного рекуррентного соотношения второго порядка an+2 = 2аn+1 + 3аn.

Другие функции, которые потребуются при выполнении лабораторных работ. В ряде заданий лабораторной работы № 1 потребуется выполнять суммирование комбинаторных чисел данного вида. Для выполнения этой операции может быть использована команда sum (expr, i, i_0, i_k), которая суммирует заданное выражение в заданных пределах.

Примеры:

В лабораторной работе № 2 при нахождении частных решений линейных рекуррентных соотношений приходится решать системы линейных уравнений. Для этого в Maxima имеется команда linsolve ([expr_1, , expr_m], [x_1, x_n]).

В wxMaxima — это команда Solve Linear System в меню Уравнения панели инструментов. После вызова команды на экране появляется окно, в котором указывается число уравнений системы

(рис. 1), а после указания числа уравнений — рабочее окно (рис. 2), в которое вводятся уравнения системы и переменные, относительно которых ее требуется решить.

Пример:

Решить систему:

Вводя сначала число уравнений системы, а затем сами уравнения и переменные, относительно которых нужно решить систему, получим:

Рис. 1

Рис. 2

В тех случаях, когда характеристическое уравнение линейного однородного рекуррентного соотношения с постоянными коэффициентами имеет комплексные корни, возможно, придется пользоваться командами realpart() и imagpart(), которые соответственно выделяют действительную и мнимую части комплексного числа. Возможно также, что для упрощения найденного общего или частного решения рекуррентного соотношения потребуются команды меню Упростить панели инструментов.

При решении задач методом производящих функций в лабораторной работе № 3 в подавляющем большинстве случаев будут востребованы всего две команды:

— expand(), которая раскрывает скобки и, следовательно, позволяет перемножать многочлены;

— taylor(expr, x, а, n), которая выполняет разложение функции в ряд Тейлора в точке а (число n указывает степень члена ряда, на котором следует оборвать запись разложения).

Примеры:

Лабораторная работа № 1

Вычисление комбинаторных чисел, заданных формулами

В лабораторной работе № 1 формируются умения и навыки использования вычислительных возможностей системы Maxima при решении задач перечислительной комбинаторики на выборки элементов из заданного конечного множества [2, § 1.4, 1.5], на разбиения конечных множеств [3, § 1.12] и на перечисление подстановок [2, § 1.10]. Основное внимание уделено вычислению комбинаторных чисел, которые могут быть заданы в замкнутой форме.

1.1. Теоретическая справка

Выборки. Выборку к элементов из n элементов данного множества А = {a1,..., an} или кратко — (n, k)-выборку — можно однозначно задать списком элементов, включенных в эту выборку. Различают упорядоченные и неупорядоченные выборки. Упорядоченной называется выборка, в которой учитывается порядок размещения элементов. Если очередность следования элементов в выборке является несущественной, она называется неупорядоченной. Кроме того, выборки делят на выборки без повторений и выборки с повторениями.

Неупорядоченная (n, k)-выборка из множества A, все элементы в которой различны, называется сочетанием из n элементов по k, а неупорядоченная (n, k)-выборка, элементы в которой могут повторяться, — сочетанием из n элементов по k с повторениями.

Сочетание из n элементов по k — это k-элементное подмножество {ai1, ..., aik} множества A, а (n, k)-сочетание с повторениями -k-элементное мультимножество, для которого множество A является основанием. При решении некоторых задач сочетания с повторениями удобно рассматривать и как k-элементные подмультимножества мультимножества, содержащего элементы n типов; в этом случае число элементов каждого типа должно быть не меньше к.

Число сочетаний из n элементов по к равно

(1.1)

Число сочетаний из n элементов по k с повторениями равно

(1.2)

Упорядоченная (n, k)-выборка из элементов множества A, все элементы которой различны, называется размещением из n элементов по k, а упорядоченная (n, k)-выборка, элементы которой могут повторяться, — размещением к элементов из n с повторениями.

Оба вида размещений являются элементами множества Аk, т. е. картежами (ai1, ..., aik) длины k, составленными из элементов множества А. В случае размещений без повторений все элементы

в картеже различны, а в случае размещений с повторениями могут повторяться.

Число размещений из n элементов по к равно

(1.3)

Число размещений из n элементов

по к с повторениями равно

(1.4)

Размещения из n элементов по n называются перестановками из n элементов. Перестановками из n элементов с повторениями называются картежи, содержащие все n элементов мультимножества

Число перестановок из n элементов вычисляется по формуле

(1.5)

а число перестановок элементов мультимножества мощности n -по формуле

(1.6)

Разбиения множеств. Пусть А — непустое конечное множество. Подмножества A, ⊂ А образуют разбиение множества A, если А = A1 ∪ A2 ∪ ... ∪ Аk и Ai ⋂ Aj = 0 при i ≠ j. Подмножества A, называются блоками разбиения, а их число k — рангом разбиения. Список [n1; n2, ..., nk] мощностей |Ai| = ni блоков Ai называется спецификацией или типом разбиения, число ni — объемом блока Ai.

Различают упорядоченные и неупорядоченные разбиения. Для упорядоченных разбиений порядок подмножеств в разбиении считается существенным, а для неупорядоченных — нет. Разбиение конечного множества А можно однозначно задать списком его блоков i = 1,..., k и списками элементов, входящих в блоки.

Упорядоченное разбиение множества А на блоки Ai (i = 1,...,k) условимся обозначать, используя круглые скобки: (A1, A2,..., Ak), а неупорядоченное — фигурные: {A1, A2,..., Аk}.

Наряду с разбиениями множеств на блоки в некоторых перечислительных задачах одновременно рассматриваются упорядочивания элементов в блоках разбиения.

При перечислении разбиений обычно прибегают к комбинаторной схеме, которую называют «раскладкой предметов по ящикам». Любое упорядоченное разбиение n-множества А ранга к интерпретируется как раскладка n различных предметов по к различимым ящикам, а неупорядоченное разбиение — как раскладка n различных предметов по одинаковым (неразличимым) ящикам. Такие интерпретации особенно полезны при решении задач.

Основные вычислительные формулы для подсчета числа разбиений n-множества на к блоков приведены в таблице 1.

Таблица 1

Тип раскладки n предметов по к ящикам

Размещение предметов в ящике

Число способов

Ящики различимые, в i-м ящике ni предметов

Неупорядоченное

Ящики различимые, допускаются пустые ящики

Неупорядоченное

Ящики различимые, нет пустых ящиков

Неупорядоченное

Ящики различимые, имеется точно r пустых ящиков

Неупорядоченное

Ящики различимые, допускаются пустые ящики

Упорядоченное

Ящики различимые, нет пустых ящиков

Упорядоченное

Ящики неразличимые, В i-м ящике ni предметов

Неупорядоченное

Ящики неразличимые, нет пустых ящиков

Неупорядоченное

Ящики неразличимые, допускаются пустые ящики

Неупорядоченное

Ящики неразличимые, нет пустых ящиков

Упорядоченное

Комбинаторные числа

(1.7)

S(n, 0) = 0 при n > 0, S(n, n) = 1 при n > 0, S(n,k) = 0 при k > n, выражающие количество всех способов неупорядоченного разбиения n элементного множества на к непустых блоков, называются числами Стирлинга второго рода.

Числа B(n), обозначающие число всех неупорядоченных разбиений n-множества на непустые блоки, называются числами Белла. Они связаны с числами Стирлинга второго рода соотношением

(1.8)

при этом В(0) = 5(0,0) = 1.

Число всех неупорядоченных разбиений «-множество А на блоки Аi1, Ai2, ..., Ain, i = 1,2, ..., n, среди которых для каждого i имеется > 0 блоков с i элементами, т. е. Σ i ⋅ mi = n, равно

(1.9)

Перечисление подстановок. Подстановками называются биекции конечного множества на себя. Комбинаторные свойства подстановок любого n-множества удобно изучать на примере множества In = {1,... ,п}. Подстановки множества In называют подстановками n-й степени, множество всех подстановками n-й степени обозначают Sn.

Подстановка s ∈ Sn задается таблицей

(1.10)

в которой под числом k ∈ In указывается его образ ik = s(k). Тождественное отображение множества In на себя, т. е. отображение, при котором s (k) = k для каждого k ∈ In, определяется подстановкой е = ее называют тождественной подстановкой. Для любой подстановки (1.10) существует обратная ей подстановка

На множестве Sn определено умножение подстановок. Произведением st подстановок s и t называется их последовательное выполнение, т. е. st(i) = t(s(i)) для всех i ∈ In.

Подстановка n-й степени называется циклической или циклом, если она элемент i1 переводит в элемент i2, i2 — в i3 и m. Д., ik-1 -в ik, наконец, ik — в i1, а остальные элементы оставляет на месте (т. е. переводит в себя). Такая подстановка обозначается (i1, i2, ..., ik), при этом число k < n называется длиной цикла. Два цикла n-й степени, не имеющие общих перемещаемых элементов, называются независимыми. Результат умножения независимых циклов не зависит от порядка сомножителей. Это позволяет любую подстановку s ∈ Sn единственным образом представить в виде произведения попарно независимых циклов. При этом для элементов, которые переходят в себя, обычно вводят в рассмотрение циклы длины 1.

Если подстановка n-й степени s разлагается в произведение m1 циклов длины 1, m2 циклов длины 2 и т. д., mn циклов длины n, то говорят, что она имеет тип [1m1, 2m2, ..., nmn]. Число всех подстановок n-и степени типа [1m1,2m2,... ,nmn] обозначим через C(m1;m2, ...mn), а число всех подстановок n-й степени, имеющих в разложении точно к циклов, — через С(n,k). Имеют место формулы:

(1.12)

Для решения широкого класса комбинаторных задач вместо чисел С(n, к) удобней рассматривать числа

(1.13)

которые называются числами Стирлинга первого рода. Числа С(n, к) поэтому часто называют числами Стирлинга первого рода без знака. Очевидно, что S(n, 0) = 0 для n > 0, s(n,n) = 1 для всех n > 0 и s(n, к) = 0 для всех к > n.

Элемент i ∈ In называется неподвижным (инвариантным) при подстановке s, если s(i) = i. Подстановка, не содержащая неподвижных элементов, называется беспорядком. Количество беспорядков среди подстановок n-й степени равно

(1.14)

Для n = 0 принимают D0 = 1.

Подстановку, содержащую ровно к неподвижных элементов, называют подстановкой с к встречами. Число всех подстановок n-й степени с к встречами вычисляется по формуле

(1.15)

1.2. Примеры решения задач с использованием Maxima

1. Рассмотрим примеры применения команд combination(n,k), permutation(n,k) и factorial(n) при решении задач на выборки.

Задача 1.1. Найти число десятизначных чисел, у которых все цифры различны.

Решение. Существует 10 цифр и 10! способов их перестановки. Среди этих перестановок будут перестановки, начинающиеся с цифры 0, таких перестановок — 9!. Поэтому искомый ответ: 10! — 9!. Проведем вычисления:

Возможен и другой вариант выполнения вычислений:

Ответ: 3265920.

Задача 1.2. Из 10 студентов и 8 студенток для участия в математической олимпиаде формируют команду, состоящую из 5 человек. Сколькими способами это можно сделать, если в команде должно быть не более 3 юношей?

Решение. В команде может не быть юношей, может быть 1, 2 или 3. Поэтому по правилу произведения и правилу суммы команду можно составить - способами. Вычисления:

Ответ: 6636.

Задача 1.3. Найти число восьмизначных чисел с различными цифрами, кратных 5.

Решение. Число кратно 5, если оно оканчивается цифрой 0 или 5; расстановка остальных 7 цифр числа может быть произвольной. Поэтому имеется A79 восьмизначных чисел с различными цифрами, у которых последняя цифра 0, и A79 — A68 чисел, у которых последняя цифра 5. По правилу суммы число всех восьмизначных чисел с различными цифрами, кратных 5, равно 2A79 — A68. Вычисления:

Ответ: 342720.

Задача 1.4. Найти число восьмизначных чисел, у которых три цифры нечетные, а остальные четные.

Решение. Имеется 5 четных и 5 нечетных цифр. Поэтому любую цифру числа, кроме первой, можно выбрать пятью способами. Позиции для четных цифр можно выбрать C58 способами, в C47 случаях из них на первом месте будет стоять нуль. Значит, искомое число равно

Вычисления:

Ответ: 8203125.

Задача 1.5. В продаже имеются маркеры четырех цветов. Сколькими способами можно купить 15 маркеров так, чтобы в покупке было хотя бы по одному маркеру каждого цвета?

Решение. Если сразу взять по одному маркеру каждого цвета, то из имеющегося ассортимента останется выбрать еще 11 маркеров. Этот выбор может быть сделан C114 = C114+11—1 = C1114 способами. Вычисления:

Ответ: 364.

Задача 1.6. Сколько различных десятизначных чисел, кратных 9, можно составить из чисел 1, 2 и 3, если в каждом из них цифра 3 должна повторяться дважды?

Решение. Число кратно 9, если сумма его цифр делится на 9. Среди 10 цифр числа, удовлетворяющего условиям задачи, две цифры 3. Пусть среди остальных восьми цифр числа имеется к единиц, а значит, (8 — к) двоек (к < 8). Тогда на 9 делится число k + 2(8 — k) + 2 ⋅ 3 = 22 — k. Это возможно лишь при к = 4. Поэтому в каждое число, которое удовлетворяет заданным условиям, цифры 1 и 2 входят по четыре раза. Следовательно, искомых чисел . Вычисления:

Ответ: 3150.

2. Дадим примеры применения команда stirling2(n, к) для вычисления чисел Стирлинга второго рода S(n, к) в задачах на разбиения множеств. Из таблицы 1 видим, что эту команду можно также применять для перечисления числа:

— упорядоченных разбиений n-множества на к блоков, среди которых нет пустых: Т(n, к, 0) = к! S(n, к);

— упорядоченных разбиений n-множества на к блоков, среди которых r пустых:

Для вычисления числа ΣS(n, i) всех неупорядоченных разбиений n-множества на к блоков, среди которых допускаются пустые, и чисел Белла B(n) может быть использована команда sum (expr, i, i_ 0, i_1), которая суммирует заданное выражение в заданных пределах. Как проводить вычисления в остальных случаях, мы уже рассмотрели в предыдущем пункте.

Задача 1.7. Сколькими способами 12 различных открыток можно разложить в 8 одинаковых конвертов, если

а) в каждом конверте должна лежать хотя бы одна открытка;

б) допускаются пустые конверты?

Решение. а) Требуется найти число неупорядоченных разбиений множества из 12 элементов на 8 непустых блоков, т. е. найти S(12,8). Вычисления:

б) Теперь нужно вычислить сумму Σ(12, i). Имеем:

Ответ: а) 159027, 6)4189550.

Задача 1.8. Найти число всех способов раскладки 12 различных открыток в одинаковые конверты (пустые конверты не допускаются).

Решение. Задача сводится к вычислению числа Белла S (12). Вычисления:

Ответ: 4213597.

Задача 1.9. Сколькими способами 12 различных открыток можно разложить в 8 различных конвертов, если

а) в каждом конверте должна лежать хотя бы одна открытка;

б) допускаются пустые конверты;

в) должно остаться два пустых конверта?

Решение. а) Требуется найти число T(12,8,0) упорядоченных разбиений множества из 12 элементов на 8 непустых блоков, но T(12,8,0) = 8! 5(12,8). Имеем:

б) Требуется найти число T(12,8) упорядоченных разбиений множества из 12 элементов на 8 блоков, среди которых могут быть пустые, это число 812. Вычисляем:

в) Ищется число упорядоченных разбиений множества из 12 элементов на 8 блоков, среди которых ровно 2 пустых, т. е. число

Имеем:

Ответ: а) 6411968640, б) 68719476736, в) 26684824320.

Задача 1.10. Сколькими способами 12 различных открыток можно разложить в одинаковые конверты так, чтобы в двух конвертах лежало по одной открытке, в трех — по две открытки и одном — четыре?

Решение. Чтобы ответить на поставленный вопрос, нужно найти число неупорядоченных разбиений множества из 12 элементов, которые имеют тип [12, 20, 32, 41, 50, 60, ..., 120]. Это число равно

Вычисления дают:

Ответ: 138600.

3. Команда stirlingl(n,k) для вычисления чисел Стирлинга первого рода s(n, к) позволяет находить число С(n, к) всех подстановок n-й степени, имеющих в своем разложении точно к циклов. Нахождение числа C(m1, m2, ..., mn) всех подстановок n-й степени данного типа [1m1,2m2,... ,nmn] сводится к арифметическим вычислениям. Для вычисления числа беспорядков Dn можно использовать команду sum.

Рассмотрим примеры.

Задача 1.11. Найти число всех подстановок 12-й степени, в разложении которых

а) два одночленных цикла, два цикла длины 3 и один цикл длины 4;

б) ровно 5 циклов.

Решение. а) Требуется найти число подстановок 12-й степени, которые имеют тип

Это число равно

Вычисления дают:

б) Решение сводится к вычислению числа Вычисления дают:

Ответ: а) 3326400, б) 45995730.

Задача 1.12. Девять джентльменов при входе в ресторан сдают свои шляпы в гардероб. Сколькими способами рассеянный гардеробщик может выдать при выходе шляпы так, чтобы

а) ни один из джентльменов не получил свою шляпу;

б) только три джентльмена получили свои шляпы;

в) хотя бы один из джентльменов получил свою шляпу?

Решение. а) Задача сводится к вычислению числа беспорядков

Имеем:

б) Необходимо найти число

Вычисления дают:

в) Число всех способов, которыми гардеробщик может выдать шляпы, равно 8!, при этом только в D, случаях ни один из джентльменов не получит свою шляпу. Поэтому искомое число равно разности 8! — D,. Имеем:

Ответ: а) 133496, б) 22260, в) 229384.

1.3. Задачи для самостоятельного решения

Решить следующие задачи. При выполнении вычислений использовать систему Maxima.

1. Сколько среди перестановок цифр числа 123456789 таких, которые начинаются: а) с двух четных цифр, б) с двух цифр, меньших 6?

2. Сколько среди четырехзначных чисел таких, в записи которых: а) все цифры различные, б) все цифры различные и хотя бы одна цифра четная, в) все цифры различные и ровно одна цифра четная, г) хотя бы одна цифра четная?

3. Сколько семизначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 и 6, в записи которых: а) все цифры различные, б) нет цифры 0, в) дважды повторяется цифра 0, а остальные цифры различные?

4. Сколько различных анаграмм можно составить из букв слова «обобщение»?

5. Имеется колода из 52 карт. Сколькими способами можно вытянуть 10 карт, среди которых: а) 4 туза; б) хотя бы один туз; в) два туза, одна дама, одна бубновая карта; г) ровно пять карт одной масти?

6. Рота состоит из 3 офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно составить наряд, состоящий из одного офицера, двух сержантов и 20 рядовых?

7. В аквариуме плавают 12 гуппи, 10 меченосцев и 6 гурами. Надо пересадить в другой аквариум не менее 4, но не более 6 гуппи, не более 4 меченосцев и 2 гурами. Сколькими способами это можно сделать?

8. В цветочном магазине продается 8 видов цветов. Сколькими способами можно составить букет: а) из 15 цветов; б) из 15 цветов, если в нем должны быть представлены все виды цветов?

9. Сколькими способами из десяти супружеских пар можно выбрать комиссию из четырех человек так, чтобы она не содержала ни одной супружеской пары.

10. В почтовом киоске имеются открытки 12 сортов. Сколькими способами можно купить: а) 12 открыток, б) 8 открыток, в) 8 разных открыток?

11. Сколькими способами можно расставить 20 различных книг в книжном шкафу с шестью полками, если каждая полка может вместить все 20 книг?

12. Решить предыдущую задачу при условии, что на каждую полку должна быть поставлена хотя бы одна книга.

13. Переплетчик должен переплести 12 различных дипломных работ. Сколькими способами он может это сделать, если у него в наличии имеется бумага трех цветов?

14. Решить предыдущую задачу при условии, что в бумагу каждого цвета должен быть переплетен хотя бы один диплом.

15. Переплетчик, у которого в наличии имеется бумага красного, синего и зеленого цветов, должен переплести 12 различных дипломных работ. Сколькими способами он может это сделать, если два диплома собирается переплести в красную бумагу, три -в синюю, а остальные — в зеленую?

16. Компания, состоящая из 12 супружеских пар, разбивается на 6 групп по 4 человека для лодочной прогулки. Сколькими способами можно разбить их так, чтобы в каждой лодке оказалось два мужчины и две женщины?

17. Сколькими способами можно разместить 14 различных предметов в 4 ящиках, если: а) ящики различимы и могут быть пустыми, б) ящики различимы и не могут быть пустыми, в) ящики неразличимы и могут быть пустыми, г) ящики неразличимы и не могут быть пустыми?

18. Сколькими способами студенческую группу из 24 человек можно разбить на 4 команды для игры в волейбол?

19. Сколькими способами можно разложить 9 различных книг в три бандероли по три книги в каждой?

20. У преподавателя обучается 25 студентов. Преподаватель проводит тест, а затем предлагает студентам обменяться работами для взаимопроверки. Сколькими способами это можно сделать?

21. Неопытный официант подает 14 блюд, обслуживая 14 клиентов. Сколькими способами он может сделать так, чтобы: а) ни один клиент не получил свой заказ, б) только половина клиентов получила свои заказы?

22. Матрицей перестановок размерности называется матрица, в каждой строке и в каждом столбце которой только один элемент равен 1, а все остальные равны 0. Сколько существует матриц перестановок размерности 8×8, содержащих на главной диагонали только нули?

23. Сколькими способами можно переставить цифры в числе 123456789 так, чтобы: а) ни одна цифра не стояла на своем месте, б) ни одна четная цифра не стояла на своем месте, в) ровно три цифры остались на своих местах?

24. Найти число всех подстановок 10-й степени, в разложении которых: а) три одночленных цикла, два цикла длины 2 и один цикл длины 3; б) ровно 3 циклов.

1.4. Варианты индивидуальных заданий

Номер варианта

Задачи

1.

1,5, 11, 17, 20, 24

2.

2, 6, 12, 17,21,24

3.

3,7, 13, 17, 22, 24

4.

4, 8, 14, 17, 23,24

5.

5,9, 15, 17, 20, 24

6.

6, 10, 16, 17,21,24

7.

7, 1, 18, 17, 22, 24

8.

8, 2, 19, 17, 23,24

9.

9,3, 13, 17, 20, 24

10.

10, 4, 14, 17,21,24

Лабораторная работа № 2

Рекуррентные соотношения

В лабораторной работе № 2 формируются умения и навыки рекурсивных вычислений [2, § 2.1] и решения линейных рекуррентных соотношений [2, § 2.2, 2.3].

2.1. Теоретическая справка

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

Рекуррентное соотношение

Un+k = Ф(n: un,..., un+k-1), (2.1)

где n, k ∈ N0, называется рекуррентным соотношением или рекуррентным уравнением порядка к. Если найдены (заданы) к первых комбинаторных чисел u0, u1, ..., uk-1, то, используя соотношение (2.1), можно вычислить следующее комбинаторное число ик и вообще число un для любого n ∈ N0.

Приведем несколько примеров известных рекуррентных соотношений.

1. Рекуррентное соотношение первого порядка

(2.2)

для числа Pn перестановок из n элементов.

2. Рекуррентное соотношение первого порядка

(2.3)

для числа беспорядков Dn среди подстановок n-ой степени.

3. Линейное однородное рекуррентное соотношение второго порядка

(2.4)

для чисел Фибоначчи.

4. Рекуррентное соотношение

для числа сочетаний из n элементов по к.

5. Рекуррентное соотношение

s(n,n) = 1 при n > 0, s(n, 0) = 0 при n > 0 и s(n,k) = 0 при к > n для чисел Стирлинга первого рода. 6. Рекуррентное соотношение

S(n,n) = 1 при n > 0, S(n,0) = 0 при n > 0 и S(n,k) = 0 при к > n для чисел Стирлинга второго рода. 7. Нелинейное рекуррентное соотношение

для чисел Каталана. В вычислительной практике гораздо чаще используется более простое линейное однородное рекуррентное соотношение первого порядка

Решение рекуррентных соотношений. В некоторых случаях, наоборот, более целесообразно от рекуррентного задания комбинаторных чисел переходить к их заданию с помощью явных формул. Для этого рекуррентное соотношение рассматривают как уравнение и решают его при заданных начальных условиях.

Функция un = f(n) называется решением рекуррентного соотношения (2.1), если при ее подстановке в это соотношение оно для каждого n ∈ N0 обращается в верное числовое равенство.

Соотношение (2.1) связывает k + 1 значений функции f(n). Если известны к ее первых значений (начальные условия)

(2.5)

где f(0), f(1), ... , f(k — 1) — заданные числа, то можно найти f(k) и вообще f(n) для любого n. Поэтому решение f(n) можно также записать в виде

(2.6)

Другим начальным значениям будет соответствовать другое решение соотношения (2.1), такие решения называются его частными решениями.

Частное решение (2.6) задает числовую последовательность

Эту последовательность называют рекуррентной последовательностью порядка к, заданной соотношением (2.1), и также считают решением этого рекуррентного соотношения.

Частные решения объединяет функция

(2.7)

где C0, C1, ... , Ск-1 — произвольные числа. Решение (2.7) называется общим решением соотношения (2.1).

Общих универсальных методов решения рекуррентных соотношений не существует. Серьезные трудности могут возникнуть уже при решении линейных рекуррентных соотношений первого порядка.

Линейным рекуррентным соотношением первого порядка называется соотношение вида

(2.8)

где an, bn — заданные вещественные или комплексные функции аргумента n ∈ N0; причем an ≠ 0 для всех n ∈ N0.

Если bn — О для каждого n ∈ N0, то линейное однородное соотношение (2.8) называется однородным', в противном случае оно называется линейным неоднородным.

Линейное однородное рекуррентное соотношение первого порядка обычно решается методом последовательных подстановок. Использование этого метода сопряжено с вычислениями конечных сумм и произведений, порой достаточно громоздкими и сложными. При решении линейных неоднородных рекуррентных соотношений первого порядка, кроме того, приходится использовать метод вариации постоянных [2, § 2.2].

Наиболее разработана теория решения линейных однородных рекуррентных соотношений с постоянными коэффициентами [2, § 2.3, 2.4].

Линейным однородным рекуррентным соотношением порядка к с постоянными коэффициентами называется соотношение

(2.9)

где a1, a2, ... , ak — заданные числа (действительные или комплексные), причем ak ≠ 0.

Общее решение соотношения (2.9) определяется корнями его характеристического уравнения

(2.10)

Если характеристическое уравнение (2.10) соотношения (2.9) имеет к различных корней λ1, λ2, ... , λk, то общее решение этого соотношения имеет вид

В общем случае характеристическое уравнение (2.10) может иметь r различных корней: λ1 кратности k1, λ2 кратности k2, ... , λr кратности kr, Σki = k. Тогда в общем решении соотношения (2.9) каждый корень λi представлен слагаемым

i = 1,2,..., r, а само общее решение есть сумма таких слагаемых.

Нередко приходится сталкиваться с решением соотношений (2.9) с действительными коэффициентами, когда среди корней характеристического уравнения имеются комплексные, а решение соотношения требуется записать без использования степеней с комплексными основаниями. Если коэффициенты рекуррентного соотношения действительны, а характеристическое уравнение имеет комплексный корень a + bi кратности l, то его l-кратным корнем является и сопряженный ему корень а — bi. Эти корни в общем решении представляются суммой

При решении линейных однородных рекуррентных соотношений «с бумагой и ручкой» основные трудности возникают при решении алгебраического уравнения (2.10). Из-за громоздких вычислений затруднения, кроме того, могут возникнуть в решении систем линейных уравнений при нахождении частных решений соотношения (2.9), соответствующих заданным начальным условиям.

Рекуррентное соотношение

(2.11)

где a1, a2, ... , ak — заданные числа (действительные или комплексные), причем ak ≠ 0, а bn — заданная функция, называется линейным неоднородным рекуррентным соотношением порядка к с постоянными коэффициентами; а рекуррентное соотношение (2.9) — однородным рекуррентным соотношением, соответствующим неоднородному соотношению (2.11). Общее решение неоднородного линейного рекуррентного соотношения (2.11) является

суммой любого его частного решения g (n) и общего решения соответствующего ему однородного соотношения (2.9).

Основные трудности при решении линейных неоднородных рекуррентных соотношений связаны с отысканием их частных решений; они, как правило, ищутся методом вариации постоянных. Наибольший интерес представляют случаи:

1.bn = ßn.

Если ß не является корнем характеристического уравнения (2.10), то частное решение соотношения (2.11) ищется в виде g(n) = Cßn, если же ß — r-кратный корень уравнения (2.10), то в виде g (n) = Cnrßn.

2. bn = p(n), где p(n) = p0nr + p1nr-1 + ...+ pr — многочлен от n степени r.

Если 1 не является корнем характеристического уравнения (2.10), частное решение соотношения (2.11) находится в виде

если же 1 — корень уравнения (2.6), то в виде g (n)

где m — кратность корня 1

В этом случае обычно пользуются тем, что если соотношение

где a1, a2, ..., ak и функции An, Bn действительны, имеет решение g(n) = а(n) + ib(n), то его действительная часть а(n) и мнимая часть b(n) являются соответственно решениями соотношений

4. Если g(n), g(n) — частные решения линейных неоднородных рекуррентных соотношений

соответственно, то C1g(n) ± C2g(n) — частное решение рекуррентного соотношения

2.2. Примеры решения задач с использованием Maxima

1. Дадим примеры программ на встроенном макроязыке системы Maxima для вычисления комбинаторных чисел, заданных рекуррентными соотношениями.

Задача 2.1. На встроенном макроязыке системы Maxima написать программу для вычисления числа Pn перестановок из n элементов. Найти: а) Р10, б) Р15.

Решение. Из соотношения (2.2) следует, что для вычисления значения Pn используется лишь предыдущее Pn-1 и номер итерации n. Следовательно, чтобы найти значение Pn в функции потребуется написать цикл для всех к = 1, ...,n, а внутри цикла результат вычислений можно записывать в одну и ту же переменную на каждой итерации, так как это значение не влияет на вычисления, кроме тех, которые будут произведены на следующей итерации. Поэтому, учитывая, что Р0 = 1, приходим к функции:

Задача 2.2. На встроенном макроязыке системы Maxima написать программу для вычисления числа беспорядков Dn. Найти: a) D10, б) D15.

Решение. Рекуррентное соотношение (2.3) для числа беспорядков отличается от предыдущего (2.2) лишь нелинейным слагаемым (—1)n+1. Поэтому в теле цикла нужно учесть это слагаемое. Для вычисления (—1)п можно использовать два способа: условный оператор if и умножение на —1 на каждом шаге цикла. Однако более удобно воспользоваться встроенной функцией signum(x) для х = (—1)i. При этом функция для вычисления числа беспорядков Dn будет иметь вид:

Задача 2.3. На встроенном макроязыке системы Maxima написать программу для вычисления чисел Фибоначчи Fn. Найти: a)F10,6)F15.

Решение. Каждый член последовательности Фибоначчи Fn (2.4) зависит от двух предыдущих, поэтому при составлении программы потребуется задать два начальных условия F0 = 1, F1 = 1. Ориентируясь на предыдущие примеры, сделаем соответствующий «сдвиг» значений, позволяющий хранить в памяти два значения последовательности. Таким образом, легко получается следующая функция:

Примечание. Построенная функция позволяет вычислять n-й член последовательности Фибоначчи. Но если в этой функции менять начальные условия, то можно аналогичным образом вычислить члены других последовательностей, заданных рекуррентным соотношением (2.4). Можно также составить функцию, в которой в качестве параметров будут передаваться начальные значения последовательности:

Новая функция является более универсальной и позволяет вычислять члены последовательности (2.4) с другими начальными условиями. Например, для последовательности чисел Люка, которая определяется соотношением Ln+2 = Ln+1 + Ln, L0 = 1, L1 = 3, получим:

Задача 2.4. Написать программу для вычисления биномиальных коэффициентов Сkn. Найти: а) C1015, б) C1020.

Решение. Для программной реализации рекуррентного соотношения

при к > n будем использовать два цикла: внешний цикл по n и внутренний — по к.

Для n = 15, к = 10 и n = 20, к = 10 соответственно получим:

Задача 2.5. Написать программу для вычисления чисел s(n,k) Стирлинга первого рода. Найти: а) s(10,4), б) s(15,7).

Решение. Числа Стирлинга первого рода определяются соотношением s(n, к) = s(n — 1, к — 1) — (n — l)s(n — 1, k), s(n, n) = 1 при n > 0, s(n, 0) = 0 при n > 0 и s(n, k) = 0 при к > n. Вновь требуется использовать два цикла: внешний цикл по n и внутренний — по к.

Отсюда

Задача 2.6. Написать программу для вычисления чисел S(n,k) Стирлинга второго рода. Найти: а) 5(10,4), б) 5(15,7).

Решение. Числа Стирлинга 2-го рода определяются соотношением

Откуда

Ответ: а) S(10,4) = 34105, 6) S(15,7) = 408741333.

Задача 2.7. Написать программу для вычисления чисел cn Каталана. Найти: а) c10, б) c15.

Решение. Рекуррентное соотношение

для чисел Каталана лишь коэффициентом отличается от соотношения для числа перестановок (задача 2.1). Поэтому функция для их вычисления может быть записана так:

Вычисления при n = 10, n = 15 дают:

Ответ: а) c10 = 16796, б) c15 = 9694845.

Метод рекуррентных соотношений с успехом используется при решении задач на разбиение чисел на меньшие слагаемые. Типичными примерами таких задач являются задачи о размене и оплате. В пособии [2] (пункт 2.1.3) в качестве примера рассмотрена следующая задача.

Задача 2.8. Для оплаты некоторой коммунальной услуги надо перечислить через банкомат сумму в 2100 руб. Сколькими способами можно оплатить услугу банкнотами в 100, 500 и 1000 руб., если два способа, отличающиеся порядком, в котором банкноты отправляются в банкомат, считаются: а) различными, б) неразличимыми?

В пособии показано, что в общем случае число f(n) способов разбиения целого неотрицательного числа n на натуральные слагаемые n1, n2, ...,пк, среди которых допускаются одинаковые слагаемые и порядок слагаемых является существенным, удовлетворяет рекуррентному соотношению

где f(n) = 1, если n = 1, и f(n) = 0, если n < 0. В случае, когда порядок слагаемых является несущественным, число F(n; n1, n2,... ,пк) способов разбиения числа n на слагаемые n1, n2,..., пк удовлетворяет рекуррентному соотношению

при этом F(0; n1,...,nk) = 1.

Использование этих рекуррентных соотношений при решении задач с конкретными числовыми данными, как вы видели, сопряжено с громоздкими вычислениями. Поэтому дадим программные реализации соотношений, позволяющие избавить от этих рутинных и скучных вычислений в подобных задачах.

Решение. Прежде всего заметим, что в первом случае рекуррентная последовательность задается с помощью к предыдущих членов, а во втором — лишь двух, но зависящих более чем от одной переменной.

а) Здесь необходимо использовать массив, так как в общем случае не известно, чему равно к. Кроме того, можно задавать массив коэффициентов при сложении предыдущих членов, формула вычисления текущего члена последовательности в котором будет выглядеть следующим образом:

Наконец, требуется задать начальные значения f(1), f(2), ... , f(max(n1,n2, ...,nk)). Ясно, что f(j) = 0 при j < 0 и f(0) = 1. Тогда начальные значения f(1), f(2), ... , f(max(n1;n2, ...,nk)) можно вычислить по той же формуле f(n) = c1f(n — n1) + ... +ckf(n-nk).

С учетом сказанного имеем:

Здесь блок

отвечает за нахождение начальных значений, а блок

— за нахождение всех остальных членов последовательности. При этом входящие параметры функции — CA — массив коэффициентов при f(n — nj), заданный в порядке их следования.

Заметим, что задача о нахождении числа способов разложения числа n = 2100 на слагаемые n1 = 100, n2 = 500 и n3 = 1000 равносильна задаче о нахождении числа способов разложения числа n = 21 на слагаемые n1 = 1, n2 = 5 и n3 = 10. Поэтому, если используются 1-й, 5-й и 10-й элементы, то массив CA будет иметь вид (1,0,0,0,1,0,0,0,01), lenCA — количество элементов массива, причем если в массиве CA содержится 10 элементов, пронумерованных от 0 до 9, то lenСА=10, а n — номер члена последовательности f(j), который надо найти.

Запуская программу для численных данных, указанных в задаче, получим:

б) В случае, когда порядок слагаемых не учитывается, функция для вычислений будет выглядеть так:

Рассмотрим, как построена данная функция. Теперь порядок представления слагаемых разложения не важен. Первое граничное условие if k=1 then (if is(mod(n,IA[0])=0) then res: leise res: 0) отражает то, что количество способов представления слагаемого равно 0 или 1. Второе граничное условие показывает, что число меньшее нуля можно представить 0 способами (как следует из постановки задачи). Далее напрямую реализуется рекуррентное соотношение F(n; n1,..., nk) = F(n; n1,..., nk-1) +F(n — nk; n1, ..., nk.

Запуская функцию для n = 21 и n1 = 1, n2 = 5, n3 = 10, имеем:

Ответ: а) 268, б) 9.

Не менее эффективен метод рекуррентных соотношений в комбинаторных задачах на перечисление числа маршрутов заданной длины через вершины многоугольников, многогранников и графов.

Задача 2.9. Найти число замкнутых маршрутов длины n по сторонам равностороннего треугольника ABC со стороной 1. (Начальная и конечная точка маршрута — вершина А.) Провести вычисления для: а) n = 15, б) n = 20.

Решение. Пусть an — число маршрутов длины n из вершины А в вершину A, bn — число маршрутов длины n из вершины А в вершину В и cn — число маршрутов длины n из вершины А в вершину С.

Очевидно, что a0 = 1, a1 = 0 и числа an, bn, cn связаны системой рекуррентных соотношений

Эта система равносильна системе

Исключая из нее bn, находим рекуррентное соотношение, связывающее числа an:

Найденное рекуррентное соотношение отличается от соотношения Фибоначчи лишь постоянным коэффициентом 2 при an и начальными условиями a0 = 1, a1 = 0. Поэтому функцию для перечисления числа маршрутов длины n из вершины А в вершину А можно записать так:

Откуда при n = 15, n = 12 получим:

Ответ: а) a15 = 10922, 6) a20 = 349526.

2. Рассмотрим примеры использования пакета solve_rec для решения рекуррентных соотношений. Этот пакет расширений загружается с помощью команды load(solve_rec)$.

Задача 2.11. Найти общее решение линейного однородного рекуррентного соотношения:

Решение.

а) Характеристическое уравнение

соотношения — уравнение 5-й степени. Хотя соотношение составлено так, что корни характеристического уравнения являются «хорошими» (λ1,2 = 1, λ3,4 = 2, λ5 = —3), процесс их вычисления «вручную» достаточно трудоемок. Внося же соотношение в строку ввода, сразу находим:

б) Характеристическое уравнение λ2 + 4 = 0 соотношения с действительными коэффициентами имеет комплексно сопряженные корни 2i и —2i. Поскольку

то общее решение соотношения имеет вид:

Вычисления в Maxima выглядят следующим образом:

Система «выдала» результат в комплексном виде и при этом произвела не слишком удачное «упрощение» степени (in = (-1)n/2). Чтобы записать найденное решение без использования комплексного основания степени, пробуем представить его в тригонометрической форме с помощью функции trigrat:

Maxima, как видим, с задачей не справилась. Однако требуемый вид решения можно получить, если выполнить замену произвольных постоянных:

Ответ:

в) Здесь характеристическое уравнение соотношения имеет два двукратных комплексно сопряженных корня

Вычисления в Maxima выглядят следующим образом:

Вновь вводя новые обозначения

ответ можно записать в привычном виде.

Ответ:

Задача 2.12. Найти общее решение соотношения Фибоначчи Fn+2 — Fn+1 + Fn и частное решение, соответствующее начальным условиям F(0) = 1, F(1) = 1 (формулу Бине).

Решение. Данный простой пример выбран для того, чтобы показать, что система даже в хорошо известных случаях может выдавать результаты несколько в непривычном виде. Как известно, искомые решения имеют соответственно вид:

Посмотрим, как справиться с первой задачей система Maxima:

Здесь с точностью до обозначений результат тот же самый. Перейдем ко второй задаче. Используя команду Solve Linear System, решаем систему, соответствующую начальным условиям F(0) = 1, F(l) = 1:

Подставляя найденные значения k1, k2 в общее решение, получим:

Попытаемся выполнить преобразование полученного результата с помощью команд окна Упростить. Команда Simplify radical, позволяющая упрощать выражения с радикалами и степенными функциями с рациональными показателями, дает:

Найденный ответ, однако, после упрощения «вручную» нетрудно привести к привычному виду:

Задача 2.13. Найти частное решение линейного однородного рекуррентного соотношения un+3 = 3un+2 — 2un, если u0 = а, u1 = b,u2 = с.

Решение. Находим общее решение соотношения:

Из системы

находим k1, k2, k3, соответствующие начальным условиям u0 = а, u1 = b,u2 = с:

Подставляем найденные значения k1, k2, k3 в общее решение:

Задача 2.14. Найти общее решение линейного неоднородного рекуррентного соотношения:

Решение. Система Maxima прекрасно справляется с решением соотношений а) и б):

В случае в), однако, Maxima заявляет об ошибке:

Поэтому поступим следующим образом. Согласно формуле Эйлера

Рассмотрим рекуррентное соотношение

Мнимая часть частного решения этого соотношения будет удовлетворять исходному рекуррентному соотношению. Находим

С помощью команды Complex Simplification (Get Imaginary Part) выделим мнимую часть дроби

Следовательно, общее решение рекуррентного соотношения запишется так:

Уже на основании рассмотренных примеров можно заключить, что при решении линейных рекуррентных соотношений с постоянными коэффициентами система Maxima в одних случаях прекрасно справляется с поставленной задачей, в других — «берет на себя» рутинную часть вычислений, но полученный результат тре-

бует дальнейшей корректировки, в третьих — может быть хорошей помощницей, если пользователь располагает необходимой теоретической базой по решению данного вида соотношений.

Заметим также, что с помощью пакета solve_rec можно находить решения некоторых видов рекуррентных соотношений с данными функциональными коэффициентами, которые обычно тяжело решаются методом последовательных подстановок.

Задача 2.15. Найти решение рекуррентного соотношения

Решение. Нетрудно видеть, что дано рекуррентное соотношение для числа Dn беспорядков, а требуется найти явную формулу для его вычисления. Это линейное соотношение имеет функциональные коэффициенты.

Применение команды solve_rec дает:

Полученный ответ легко привести к привычному виду:

Задача 2.16. Найти общее решение рекуррентного соотношения

Решение. Имеем:

Ответ:

2.3. Задачи для самостоятельного решения

Задачи 1—10 решить методом рекуррентных соотношений. При выполнении вычислений составить программу на встроенном макроязыке системы Maxima.

1. Имеется лента, разбитая на клетки и уходящая вправо в бесконечность. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами он может добраться до n-й от начала ленты клетки? Провести вычисления для n = 30.

2. Лягушка прыгает по вершинам шестиугольника ABCDEF, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами она может попасть из вершины А в вершину А за n прыжков? Провести вычисления для n = 30.

3. Лягушка прыгает по вершинам шестиугольника ABCDEF, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами она может попасть из вершины А в вершину С за n прыжков? Провести вычисления для n = 30.

4. Лягушка прыгает по вершинам шестиугольника ABCDEF, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами она может попасть из вершины А в вершину С за n прыжков при условии, что в вершину D ей прыгать нельзя? Провести вычисления для n = 30.

5. Сколькими способами купюру в 500 рублей можно разменять монетами в 1, 2, 5 и 10 рублей?

6. Сколькими способами можно разбить число N на слагаемые, каждое из которых равно одному из чисел 1, 2, ... , n? (Порядок слагаемых не учитывается.) Провести вычисления для N = 30, n = 20.

7. Сколькими способами можно разбить число N на различные слагаемые, каждое из которых равно одному из чисел 1, 2, ... , n? (Порядок слагаемых не учитывается.) Провести вычисления для N = 30,п = 20.

8. Имеются марки достоинством в n1, n2, ..., nk руб. (стоимости n1, n2, ..., nk марок различны и запас марок каждого вида неограничен). Сколькими способами из них можно выбрать марки на сумму в N руб. и затем наклеить на бандероль, если два способа наклейки, отличающиеся порядком наклейки марок, считаются

различными? Провести вычисления для N = 30, n1 = 1, n2 = 2, n3 = 3, n4 = 5, n5 = 10.

9. Имеются марки достоинством в 1,2, ... , n руб. Сколькими способами из них можно выбрать марки разного достоинства на сумму в N руб. и затем наклеить на бандероль, если два способа наклейки, отличающиеся порядком наклейки марок, считаются различными? Провести вычисления для N = 30, n = 20.

10. Найти число замкнутых маршрутов длины n по ребрам тетраэдра ABCD, если ребро тетраэдра равно 1. (Начальная и конечная точка маршрута — вершина А.) Провести вычисления для: n = 12, n = 15.

11. Найти общее решение линейного однородного рекуррентного соотношения:

12. Найти решение линейного однородного рекуррентного соотношения:

13. Найти общее решение линейного неоднородного рекуррентного соотношения:

14. Найти решение линейного неоднородного рекуррентного соотношения:

2.4. Варианты индивидуальных заданий

Номер варианта

Задачи

1.

1, 11(a), 12(a), 13(a), 14(a)

2.

2, 11 (б), 12(6), 13(6), 14(6)

3.

3, 11(в), 12(в), 13(в), 14(в)

4.

4, 11 (г), 12 (г), 13 (г), 14 (г)

5.

5, 11 (д), 12 (д), 13 (д), 14(д)

6.

6, 11(e), 12(e), 13(e), 14(e)

7.

7, 11 (a), 12(a), 13(a), 14(a)

8.

8, 11 (м), 12 (м), 13 (м), 14 (м)

9.

9, 11 (и), 12 (и), 13 (и), 14 (и)

10.

10, 11 (к), 12 (к), 13 (к), 14 (к)

Лабораторная работа № 3

Производящие функции

В лабораторной работе № 3 рассматривается использование системы Maxima при решении перечислительных задач методом производящих функций. Даны примеры решения этим методом задач на выборки [2, § 3.4], разбиения конечных множеств [2, § 3.5] и разбиения натуральных чисел на слагаемые [2, § 3.6].

3.1. Теоретическая справка

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

Формальным степенным рядом над полем R действительных (над полем С комплексных) чисел называется выражение

(3.1)

или, кратко,

где коэффициенты an ∈ R, n ∈ N0 и х — некоторый произвольный символ, который принято называть переменной. Множество формальных степенных рядов над R обозначают R[[х]]. Формальный степенной ряд

(3.2)

и ряд (3.1) считаются равными, если an = bn для любого n ∈ N0. Если все коэффициенты ряда (3.1), за исключением конечного числа, равны нулю, то A(х) — многочлен над кольцом R. Поэтому множество многочленов R[x] — подмножество множества R[[х]].

На множестве R[[х]] определены операции сложения и умножения формальных рядов, а также операцию умножения формального ряда на действительное число.

Суммой А(x) + В(x) формальных рядов (3.1) и (3. 2) называется ряд

(3.3)

Нейтральным элементом относительно сложения рядов является нулевой ряд, т. е. ряд, все коэффициенты которого равны нулю: A(х) + 0 = 0 + A(х) = A(х). Для любого ряда (3.1) существует противоположный ему ряд

такой, что A(х) + (-A(х)) = (-A(х)) + A(х) = 0.

Произведением формального ряда A(х) на число k ∈ R называется ряд

(3.4)

Произведением Коши A(х)В(х) формальных рядов (3.1) и (3.2) называется ряд С(х) = c0 + c1х + ... + cnxn + ... такой, что

(3.5)

Нейтральным элементом относительно умножения является ряд 1 = 1 + 0х + 0х2 +

Ряд A-1(х) такой, что А(х)А-1(х) = 1, называется обратным к ряду A(х). Для того чтобы формальный степенной ряд (3.1) над

R был обратимым, необходимо и достаточно, чтобы его коэффициент a0 ≠ 0.

Для ряда (3.1) и обратимого ряда (3.2) существует единственный степенной ряд С(х) такой, что B(x)C(x) = А(х). Степенной ряд С(х) называется частным от деления ряда А(х) на ряд В(х) и обозначается A(x)/B(x).

Пусть даны ряд А(у) = a0 + аху + ... + апуп + ... и ряд В(х) = b1х + ... + bnxn + коэффициент b0 которого равен нулю. Формальный степенной ряд

называется подстановкой формального степенного ряда В(х) в формальный степенной ряд А (у).

Производной формального степенного ряда (3.1) над полем R действительных (С комплексных) чисел называется формальный степенной ряд

(3.6)

Производная n-го порядка степенного ряда А(х) определяется по индукции:

(3.7)

и обозначается

Для формального степенного ряда A(х) справедлив аналог формулы Маклорена:

(3.8)

где A(0) = a0, A(к)(0) = k!ak (k = 1,2,...).

Интегралом формального степенного ряда (3.1) называется формальный степенной ряд

(3.9)

Наряду с обычными формальными степенными рядами над R (над С) вводят экспоненциальные формальные степенные ряды. Так называются выражения вида

(3.10)

где коэффициенты ai ∈ R, n ∈ N0 и х — некоторый произвольный символ. Множество экспоненциальных формальных степенных рядов над R обозначают R*[[х]].

На множестве R*[[х]] обычным образом определяются операции сложения рядов и умножения ряда на действительное число:

Однако произведение Коши экспоненциальных рядов не является экспоненциальным рядом. Вместо него на R*[[х]] вводится произведение Блиссара. Произведением Блиссара экспоненциальных рядов

называется экспоненциальный ряд

такой, что

(3.11)

Формальное дифференцирование и интегрирование экспоненциального ряда (3.10) дает:

Пусть имеется некоторая последовательность действительных или комплексных чисел

(3.12)

Производящей функцией этой последовательности называется формальный степенной ряд

(3.13)

Экспоненциальной производящей функцией последовательности (3.1) называется формальный экспоненциальный ряд

При этом говорят, что производящие функции (3.13), (3.14) генерируют (порождают) последовательность (3.12).

Операции, определенные на множестве формальных степенных рядов, позволяют строить из данных производящих функций новые производящие функции.

Пусть даны последовательности

Операции сложения и умножения на скаляр, примененные к их производящим функциям

позволяют построить производящую функцию последовательности (αап + ßbn).

Произведение Коши С(х) = А(х) В(х) является производящей функцией последовательности (cn) = (Σакbп-к), которая называется сверткой Коши последовательностей (an) и (bn). Важный частный случай свертки Коши имеем при А(х) = xm, m ∈ N; свертка хmВ(х) = Σbn-mхn является производящей функцией последовательности (0, ..., 0, b0, b1, ...), которая начинается с m нулей. Поэтому умножение производящей функции на xm часто называют операцией сдвига (вправо на m позиций).

Если из производящей функции В(х) вычесть ее первые m членов и наиденную разность разделить на xm, то найдем производящую функцию Σ bnxn-m последовательности (bm, bm+1,... ), полученной из (bn) в результате отбрасывания m первых членов и сдвига остальных членов на m позиций влево.

Чтобы получить производящую функцию Σnanхn последовательности (nan), нужно продифференцировать производящую функцию А(х), а затем полученный результат умножить на Х. Если же проинтегрировать производящую функцию —, то получим производящую функцию Σan/nxn последовательности (an/n).

Произведение Блиссара экспоненциальных производящих функций

последовательностей (an), (bn) является экспоненциальной производящей функцией последовательности

которая называется сверткой Блиссара исходных последовательностей.

Построенные с помощью степенных рядов, в частности многочленов, и операций над ними, производящие функции являются одним из наиболее универсальных средств решения самых разнообразных перечислительных комбинаторных задач.

В таблице 2 приведены наиболее часто встречающиеся при решении комбинаторных задач последовательности и их производящие функции.

Таблица 2

Выборки. Производящей функцией для числа сочетаний из n элементов по к является многочлен

(3.15)

Многочлен

(3.16)

служит производящей функцией для числа сочетаний из n элементов с повторениями, если число повторений элемента не превышает к. В том случае, когда на число повторений не накладывается никаких ограничений, производящая функция является степенным рядом

(3.17)

При рассмотрении неупорядоченных выборок из совокупности элементов m типов a1,a2,... ,am можно выделить два основных случая:

1) число элементов каждого типа является неограниченным;

2) число элементов каждого типа ограничено, т. е. выбор идет из мультимножества A = {n1а1,n2a2, ..., nmam}.

На выборки из разных совокупностей, в свою очередь, могут накладываться некоторые дополнительные условия. Поэтому производящие функции F(x), с помощью которых изучаются эти выборки, имеют специфические особенности. При составлении производящей функции F(x) для вычисления числа n-выборок определенного вида в первом случае руководствуются следующими общими правилами:

1°. Число неупорядоченных n-выборок из совокупности элементов m типов, в которых представлено хотя бы по одному эле-

менту каждого типа, равно коэффициенту при xn в произведении

2°. В общем случае число неупорядоченных n-выборок из совокупности элементов a1, a2, ..., am равно коэффициенту при xn в произведении

F(x) = F1(x)F2(x)...Fm(x), (3.18)

где Fi(x) — многочлен или ряд, который строится с учетом ограничений, наложенных на выбор элемента ai. Именно, если из совокупности элементов ai, 1 < i < m необходимо выбрать:

а) ровно к элементов, то эту совокупность в произведении (3.18) следует представить множителем xk;

б) не менее k1, но не более k2 элементов, то эту совокупность в произведении (3.18) следует представить многочленом (xk1 + ... + xk2);

в) нечетное количество элементов, то эту совокупность представляет множитель (х + x3 + ... + x2k+1 + ... );

г) четное количество элементов, то эту совокупность представляет множитель (1 + x2 + ... + x2к + ... );

д) количество элементов, кратное r, то эту совокупность следует представить множителем (1 + хr + ... + хrk + ...) (понятно, что правило является обобщением предыдущего).

Правила 1°-2° можно применять и для подсчета числа неупорядоченных выборок в том случае, когда задано количество элементов каждого типа. Если, например, из мультимножества А = {п1а1, n2а2, ...,птат} необходимо выбрать n ⩽ n1 + ... + nm элементов, то производящей функцией для числа таких выборок является произведение многочленов

Использование экспоненциальных производящих функций позволяет перечислять упорядоченные выборки. Действительно,

— экспоненциальная производящая функция для числа размещений без повторений.

Экспоненциальной производящей функцией для числа Ank = пк размещений из n элементов по к с повторениями является функция F(x) = епх. В самом деле,

Рассмотрим упорядоченные n-выборки из совокупности элементов m типов a1, a2,..., am. Пусть для каждого 1 < i < m выбирается ni элементов ai и n1 + ... + nm = n. Если количество элементов любого типа является неограниченным, то выборка элементов ai может быть представлена членом а вся n-выборка — произведением

(3.19)

содержащим m сомножителей. Если это произведение представить в виде экспоненциального ряда, то коэффициент

даст число способов, которыми можно выбрать и упорядочить n элементов (по ni элементов типа ai).

Понятно, что в конкретной перечислительной задаче экспоненциальные ряды, представляющие в произведении (3.19) элементы типа ai, вновь будут иметь специфические особенности, обусловленные условиями задачи. Поэтому при составлении экспоненциальной производящей функции следует руководствоваться теми же правилами 1° и 2°, которые сформулированы для обычных производящих функций.

Разбиения множеств. Приведем производящие функции для основных видов разбиений множеств.

1°. Количество kn способов, которыми n-множество можно разбить на к попарно непересекающихся упорядоченных блоков, среди которых допускаются пустые блоки, ищется с помощью производящей экспоненциальной функции

(3.20)

коэффициент при x/n! у которой равен kn.

2°. Количество способов, которыми n-множество можно разбить на к попарно непересекающихся упорядоченных блоков, среди которых нет пустых, позволяет найти производящая экспоненциальная функция

(3.21)

3°. Число всех способов неупорядоченного разбиения n-множества на к непустых подмножеств, т. е. число S(n,k) Стирлинга 2-го рода, можно найти с помощью экспоненциальной производящей функции

(3.22)

Это число можно найти и с помощью обычной производящей функции

(3.23)

4°. Число всех неупорядоченных разбиений n-множества на непустые подмножества, т. е. число Белла В(n), ищется с помощью экспоненциальной производящей функции

(3.24)

Попутно отметим, что число неупорядоченных разбиений n-множества в к циклах или, что тоже самое, число подстановок степени n, в разложении которых ровно к циклов, есть число С(n, к) Стирлинга первого рода без знака. Для чисел s(n, к) Стирлинга первого рода

— обычная производящая функция, а

— экспоненциальная.

Разбиения чисел. Рассмотрим различные виды разложений натурального числа n на слагаемые, или, что то же самое, раскладок n неразличимых предметов в неразличимые и неразличимые ящики. Начнем с разложений, порядок слагаемых в которых является несущественным.

1°. Производящая функция для числа разложений натурального числа n на различные натуральные слагаемые, равные n1, n2, ... , пк, порядок которых не учитывается, равна

(3.25)

2°. Производящая функция для числа разложений натурального числа n на натуральные слагаемые, равные n1, n2, ... , пк, порядок которых не учитывается, имеет вид:

(3.26)

Обратите внимание, что теперь не требуется, чтобы все слагаемые в разложении были различными. Иными словами, находится число целочисленных неотрицательных решений системы

3°. Производящая функция для числа разбиений числа n на не более чем к слагаемых имеет вид

(3.27)

а ровно на к слагаемых — вид:

(3.28)

Когда слагаемые разбиения или их число не указаны, в качестве производящих функций приходится рассматривать произведения, содержащие бесконечное число сомножителей.

4°. Количество разложений числа n на различные слагаемые, которые не указаны и порядок которых не учитывается, можно представить функцией

(3.29)

Доказывается, что коэффициент при xk в F(x) равен коэффициенту при xk в многочлене

Производящие функции для числа разложений на различные четные и различные нечетные слагаемые имеют соответственно вид:

5°. Производящие функции для числа разложений числа n на произвольные слагаемые, на произвольные четные и произвольные

нечетные слагаемые имеют соответственно вид (порядок слагаемых не учитывается):

(3.30)

В заключение приведем производящие функции для разложений, в которых порядок слагаемых считается существенным. 1°. Производящая функция

— для числа способов представления натурального числа n в виде суммы к целых неотрицательных слагаемых, порядок которых учитывается:

— для числа способов представления натурального числа n в виде суммы к натуральных слагаемых, каждое из которых не меньше l и порядок которых учитывается:

— для числа способов представления натурального числа n в виде суммы к натуральных слагаемых, порядок которых учитывается:

2°. Количество способов, которыми натуральное число n можно представить в виде суммы к слагаемых, принимающих значения n1, n2, ... , nm (порядок слагаемых учитывается), представляется производящей функцией

3.2. Примеры решения задач с использованием Maxima

Нельзя не видеть, что при решении задач с конкретными числовыми данными методом производящих функций приходится сталкиваться с малоприятной и весьма громоздкой процедурой перемножения многочленов и степенных рядов. Для выполнения подобных вычислений система Maxima просто незаменима. При

этом в подавляющем большинстве случаев придется пользоваться всего двумя командами:

— expand, которая раскрывает скобки и, следовательно, позволяет перемножать многочлены.

— taylor, которая выполняет разложение функции в ряд Тейлора.

1. В этом пункте, используя систему Maxima, проведем вычисления в задачах, рассмотренных в учебном пособии [2].

Задача 3.1. В продаже в неограниченном количестве имеются яблоки, груши и апельсины. Сколькими способами можно произвести покупку:

а) 9 фруктов;

б) 9 фруктов, среди которых хотя бы по одному фрукту каждого вида;

в) 9 фруктов, среди которых ровно 3 апельсина;

г) 9 фруктов, среди которых не менее 3 апельсинов;

д) 9 фруктов, среди которых не более 3 апельсинов;

е) 9 фруктов, среди которых не менее 4 яблок, но не более 2 апельсинов;

ж) 9 фруктов, из которых можно составить три одинаковых набора фруктов?

Решение. Для каждого пункта на основе правил 1°-2° составим соответствующие производящие функции:

Для ответов на поставленные вопросы достаточно разложить найденные функции в степенные ряды и найти коэффициенты при x9. Используем для этого функцию taylor.

Ответ: а) 55, б) 28, в) 7, г) 28, д) 34, е) 15, м) 10.

Задача 3.2. В вазе лежит 5 яблок, 6 груш и 4 апельсина. Сколькими способами можно выбрать из них:

а) 9 фруктов;

б) 9 фруктов, среди которых хотя бы по одному фрукту каждого вида;

в) 9 фруктов, среди которых ровно 3 апельсина;

г) 9 фруктов, среди которых не менее 3 апельсинов;

д) 9 фруктов, среди которых не более 3 апельсинов;

е) 9 фруктов, среди которых не менее 4 яблок, но не более 2 апельсинов;

ж) 9 фруктов, из которых можно составить три одинаковых набора фруктов?

Решение. Для каждого пункта составим соответствующие производящие функции. При составлении необходимо учитывать, что число фруктов каждого вида ограничено, поэтому:

В этой задаче для вычислений используется функция expand:

Ответ: а) 24, б) 18, в) 6, г) 12, д) 18, е) 6, м) 3.

Задача 3.3. Найти количество шестизначных чисел, все цифры в которых нечетные, а цифры 1 и 3 встречаются не менее одного раза.

Решение. Имеется 5 нечетных цифр. Поэтому экспоненциальная производящая функция, позволяющая найти количество указанных шестизначных чисел, запишется следующим образом:

. Разложим ее в ряд Тейлора:

Поскольку для перечисления упорядоченных выборок используется экспоненциальная функция, найденный коэффициент при x6 нужно умножить на 6!:

Отсюда следует, что искомое количество шестизначных чисел равно 56 — 2 ⋅ 46 + 36 = 8225.

Задача 3.4. Имеется 5 карточек, на которых написана буква А, 4 карточки с буквой Б и 3 карточки с буквой В. Сколько различных «слов» можно составить с помощью этих карточек, в которых:

а) 6 букв;

б) 6 букв, среди которых хотя бы по одной букве каждого вида;

в) 6 букв, среди которых ровно 3 буквы А;

г) 6 букв, среди которых не менее 4 букв А;

д) 6 букв, среди которых не более 2 букв А;

е) 6 букв, среди которых четное число букв А, не менее 2 букв Б и не более 2 букв В?

Решение. Теперь производящие функции составляются с учетом того, что выбор каждой из букв ограничен:

Число искомых выборок будет равно произведению найденного коэффициента при x6 на 6!. Вычисления дают:

Ответ: а) 642, б) 510, в) 120, г) 72, д) 410, е) 195.

2. Перейдем к задачам на разбиение множеств.

Задача 3.5. Найти число способов, которыми 7 различных открыток можно разложить в 5 конвертов так, чтобы не было пустых конвертов. Рассмотреть случаи: а) все конверты одинаковые, б) все конверты различные.

в) Сколькими способами 7 различных открыток можно разложить по конвертам так, чтобы не было пустых конвертов?

Решение. а) Очевидно, что нужно найти S(7,5). Разложение функции

в ряд Тейлора дает:

Следовательно,

Этот же результат получим, если используем обычную производящую функцию (3.23):

б) Нужно найти коэффициент при x/5! в разложении функции (ех — 1)5. Имеем:

в) Требуется найти число Белла В (7). Вычисления дают:

Ответ: а) 140, б) 16800, 877.

Рассмотрим пример решения задачи на упорядоченные разбиения с ограничениями.

Задача 3.6. Сколькими способами 9 пассажиров могут сесть в 3 легковых автомобиля так, чтобы:

а) в каждый автомобиль сел хотя бы один пассажир;

б) в один автомобиль село нечетное число пассажиров, а в два других — четное;

в) в каждый автомобиль село по три человека?

(Порядок рассадки пассажиров в автомобиле считать несущественным.)

Решение. Учитывая, что в автомобиль может сесть не более четырех пассажиров, составим соответствующие производящие функции:

Выполним вычисления:

Ответ: а) 11130, б) 3150, в) 1680.

Следующая задача демонстрирует случай, когда экспоненциальные производящие функции используются для перечисления разбиений, в которых упорядочены элементы в блоках разбиения.

Задача 3.7. Сколькими способами 8 пассажиров могут сесть в 3 легковых автомобиля, если:

а) допускается, что в один из автомобилей пассажиры не сели;

б) в каждый автомобиль должен сесть хотя бы один пассажир?

Решение. а) Число всех упорядоченных разбиений n-множества на к упорядоченных блоков равно

Это число разбиений можно найти как коэффициент при в экспоненциальной производящей функции

В рассматриваемом случае:

б) Число всех упорядоченных разбиений n-множества на к упорядоченных блоков, каждый из которых не пуст, равно n!Ck-1n-1. Здесь экспоненциальная производящая функция -

В нашем случае:

Ответ: а) 1814400, б) 846720.

Решим с помощью производящих функций для чисел s(n,k) Стирлинга первого рода задачу 1.9 (б) из лабораторной работы № 1 :

Задача 3.8. Найти число всех подстановок 12-й степени, в разложении которых ровно 5 циклов.

С помощью первой функции получаем:

Коэффициент при x5 равен 45995730.

К этому же результату приходим, используя экспоненциальную производящую функцию:

В этом случае искомое число — коэффициент при

3. В заключение рассмотрим задачи на разбиение чисел.

Задача 3.9. Сколько комплектов букетов можно составить из 15 одинаковых роз, если букеты могут состоять из 1, 3, 5, 7, 9 роз и число цветов во всех букетах комплекта должно быть различным?

Решение. Согласно (3.25) составляем функцию

и перемножаем входящие в нее многочлены:

Ответ: 2.

Задача 3.10. Сколькими способами купюру в 1000 рублей можно разменять на купюры в 50, 100 и 500 рублей?

Решение. Теперь не требуется, чтобы все слагаемые в разложении были различными, поэтому для решения применяется производящая функция (3.26). Очевидно, что данная задача эквивалентна задаче о разложении числа 20 на слагаемые, равные 1, 2 и 10. Составим производящую функцию

Находим ее разложение в ряд Тейлора:

Ответ: 18.

Задача 3.10. Сколькими способами число 12 можно представить в виде суммы:

а) различных слагаемых;

б) различных четных слагаемых;

в) различных нечетных слагаемых. Порядок слагаемых не учитывается.

Решение. Производящие функции, соответствующие этим суммам, имеют вид:

Раскрывая скобки, получим:

Ответ: а) 15, б) 4, в) 3.

Задача 3.11 (о счастливых билетах). Трамвайные билеты имеют шестизначные номера. Билет считается «счастливым», если сумма его первых трех цифр равна сумме трех последних. Найти число всех счастливых билетов.

Решение. Существует взаимно однозначное соответствие между множеством счастливых шестизначных билетов и множеством номеров с суммой цифр 27. Для того чтобы установить такое соответствие, заменим в произвольном счастливом билете три последние цифры его шестизначного номера на цифры, дополняющие их до 9 (например, номер 713425 при такой замене перейдет в номер 713574, сумма цифр которого равна 27). Если сумма трех

первых цифр (и трех последних) прежнего номера была равна k, то после указанной замены сумма трех последних цифр нового номера станет равной 27 — k. Следовательно, общая сумма цифр нового номера равна 27.

Обратно, пусть в номере, сумма цифр которого равна 27, сумма трех первых цифр равна k, тогда сумма трех последних -27 — k. Заменяя в нем последние три цифры на цифры, дополняющие их до 9, получим «счастливый» номер.

Число способов, которыми число 27 можно представить в виде суммы 6 слагаемых, каждое из которых равно одному из чисел 0, 1, 2, ... , 9 (порядок слагаемых учитывается), можно найти с помощью производящей функции

Выполним возведение многочлена в степень:

Задача 3.12 (задача абитуриента). Поступающий в высшее учебное заведение должен сдать 3 экзамена. Он полагает, что проходной балл составит 13 баллов. Сколькими способами можно сдать экзамены, чтобы набрать проходной балл?

Решение. Проходной балл — 13 — разбивается на три слагаемых (число экзаменов), которые могут принимать значения 3, 4 и 5 (положительные отметки), причем порядок слагаемых имеет значение (экзамены разные). Поэтому

Разложим функцию в ряд Тейлора:

Ответ: 6.

3.3. Задачи для самостоятельного решения

Решить задачи методом производящих функций.

1. В урне имеются 5 красных, 4 синих и 3 белых шара. Сколькими способами можно выбрать из урны 8 шаров? Во скольких случаях среди выбранных шаров будут 3 красных и 2 синих шара?

2. В урне имеются 5 красных, 4 синих и 3 белых шара. Из урны выбирается 8 шаров. Во скольких случаях среди выбранных шаров:

а) хотя бы один шар будет белым;

б) ровно один шар будет белым;

в) будет четное число красных шаров и нечетное — синих?

3. В вазе лежат конфеты четырех сортов, по 4 конфеты каждого сорта. Сколькими способами сладкоежка можно съесть:

а) 8 конфет;

б) 8 конфет, среди которых хотя бы по одной конфете каждого сорта;

в) 8 конфет, среди которых ровно 4 конфеты одного, особо понравившегося сорта?

4. В продаже имеются карандаши красного, синего, желтого, зеленого и черного цветов. Сколькими способами можно купить 20 карандашей так, чтобы

а) количество карандашей красного цвета было не менее 5 и не более 10;

б) количество карандашей красного цвета было кратно 5, а синего цвета — кратно 3, количество желтых карандашей было не более 3, зеленых — не менее 3 и черных — не более 2?

5. Сколько десятизначных чисел можно составить из цифр 1, 2, 3, 4, если в числе должно быть:

а) 5 цифр 1 ;

б) не менее одной цифры 1, двух цифр 2, нечетное число цифр 3 и четное число цифр 4;

в) поровну четных и нечетных цифр?

6. Сколько десятизначных чисел можно составить из цифр 1, 2, 3, 4, 5, если в числе:

а) было 2 цифры 1 и 3 цифры 2;

б) цифра 1 встречалась не менее 2, но не более 5 раз, цифра 2 встречалась 2 раза, а цифра 3 — 1 раз;

в) было нечетное число нечетных цифр?

7. Сколько десятизначных чисел можно составить из цифр 1, 2, 3? Сколько среди них делится на 9?

8. Переплетчик должен переплести 12 различных книг в красный, синий и коричневый переплеты. Сколькими способами он может это сделать, если в каждый цвет должна быть переплетена хотя бы одна книга?

9. Сколько слов можно составить из букв слова «логарифм», в которых две гласные буквы и не менее двух согласных?

10. Сколько различных наборов из 6 шаров можно составить, имея в наличии 2 одинаковых красных шара, 3 одинаковых синих шара и 4 одинаковых белых шара?

11. В лифт вошли 8 человек. Сколькими способами они могут выйти на четырех этажах так, чтобы на каждом этаже вышел по крайней мере один человек?

12. Сколькими способами можно разделить 15 различных предметов между тремя людьми так, чтобы каждый получил: а) не менее 2-х и не более 10 предметов, б) по 5 предметов.

13. Сколькими способами четверо детей могут разделить между собой 10 белых грибов, 12 подберезовиков и 9 подосиновиков? Сколькими способами можно разделить эти грибы так, чтобы каждый получил хотя бы 7 грибов?

14. Девушка собирается отправить своему приятелю по почте 8 своих различных фотографий, используя для этого 5 конвертов. Сколькими способами она это может сделать, если: а) конверты различные, б) конверты одинаковые?

15. В хоккейной команде 24 игрока. Сколькими способами их можно разместить в гостинице в шести четырехместных номерах?

16. Сколькими способами 3 юноши и 5 девушек могут разбиться на две команды по 4 человека так, чтобы в каждой команде был хотя бы один юноша?

17. Сколькими способами можно расставить 10 различных книг в книжном шкафу с пятью полками, если каждая полка может вместить все 10 книг?

18. Сколькими способами можно разделить на команды по 6 человек для игры в волейбол группу из: а) 12, б) 24 спортсменов?

19. Сколькими способами 9 постояльцев можно заселить в четыре номера гостиницы, если в номер нужно разместить не менее двух, но не более четырех человек?

20. Пять пиратов делят между собой добычу, состоящую из 18 различных драгоценных украшений. Сколькими способами может произойти раздел, если:

а) он идет без каких-либо ограничений;

б) каждый пират должен получить хотя бы одно украшение;

в) точно два пирата останутся без добычи;

г) четыре пирата получают по 4 украшения, а пятый — 2;

д) каждый пират должен получить не менее трех украшений?

21. Найти число целочисленных неотрицательных решений уравнения x1 + 2х2 + ... +5хk = 10.

22. Найти число способов, которыми число 30 можно представить в виде суммы 3 слагаемых, каждое из которых равно одному из чисел 0, 1, 2, ... , 15 (порядок слагаемых учитывается).

23. Сколькими способами можно оплатить покупку в 220 рублей купюрами в 100 и 50 рублей и монетами в 5 и 10 рублей?

24. Десять ящиков занумерованы числами от 1 до 10. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров так, чтобы ни один ящик не оказался пустым?

25. Сколькими способами можно составить сумму в 25 рублей, если в наличии имеется 5 монет достоинством в 1 рубль, 4 монеты достоинством в 2 рубля, 3 монеты в 5 рублей и 2 монеты в 10 рублей?

26. Сколькими способами можно составить сумму в 25 рублей, если в наличии имеется по три монеты достоинством в 1, 2, 5 и 10 рублей?

27. Сколькими способами можно составить сумму в 25 рублей из монет достоинством в 1, 2, 5 и 10 рублей?

28. Сколькими способами число 20 можно разложить: а) на сумму слагаемых, б) на сумму четных слагаемых, в) на сумму нечетных слагаемых? (Порядок слагаемых не учитывается.)

29. Имеются рублевые, двухрублевые и десятирублевые марки. На конверт надо наклеить 6 марок на сумму 22 рубля. Сколькими

способами это можно сделать, если: а) учитывается порядок наклейки марок, б) порядок наклейки марок является несущественным?

30. Одновременно бросается 5 игральных костей. Во скольких случаях сумма выпавших очков окажется равной 21?

31. Найти число подстановок n-й степени, в разложении которых ровно к циклов.

Вариант

а

б

в

г

д

е

ж

3

и

к

n

8

10

6

7

5

9

8

10

6

7

k

3

7

1

4

4

5

5

3

5

3

3.4. Варианты индивидуальных заданий

Номер варианта

Задачи

1.

1, 11,21,31 (а)

2.

2, 12, 22,31 (б)

3.

3, 13,23,31 (в)

4.

4, 14, 24,31 (г)

5.

5, 15,25,31 (д)

6.

6, 16, 26,31 (е)

7.

7, 17, 27,31 (м)

8.

8, 18, 28,31 (з)

9.

9, 19, 29,31 (и)

10.

10, 20,30,31 (к)

Вместо заключения

Авторы пособия надеются, что выполнение лабораторных работ продемонстрировало читателю, что система компьютерной математики Maxima обладает хорошим набором функций для решения комбинаторных задач и хорошей скоростью выполнения вычислений. Надеемся также, что он убедился в том, что в качественных текстовых задачах Maxima может быть лишь помощником в выполнении необходимых численных вычислений, решение задач ему придется искать самому, опираясь на хорошее знание теоретического материала.

Литература

Основная

1. Виленкин Н. Я. Комбинаторика. — М/: Наука, 1969. — 328 с.

2. Клековкин Г. А. Введение в перечислительную комбинаторику. — М/: Спутник+, 2014. — 219 с.

3. Стахин Н.А. Основы работы с системой аналитических (символьных) вычислений Maxima (ПО для решения задач аналитических (символьных) вычислений): учебное пособие. — М.: 2008. — 86 с.

4. Чичкарёв Е. А. Компьютерная математика с Maxima: руководство для школьников и студентов. — М.: ALT Linux, 2009. — 233 с.

Дополнительная

5. Алфутова Н. Б. Алгебра и теория чисел: сборник задач для математических школ / Н. Б. Алфутова, А. В. Устинов. — 2-е изд., испр. и доп. — М.: МЦНМО, 2004. — 320 с.

6. Гаврилов Г. П. Задачи и упражнения по дискретной математике: учебное пособие / Г. П. Гаврилов, А. А. Сапоженко. — М.: ФИЗМАТЛИТ, 2004.-416 с.

7. Кузьмин О. В. Перечислительная комбинаторика: учебное пособие. — М.: Дрофа, 2005. — 110 с.

8. Программирование в Maxima: учебное пособие / А. Р. Есаян, В. Н. Чубариков, Н. М. Добровольский, А. В. Якушин. — Тула: Изд-во Тульского гос. пед. ун-та им. Л. Н. Толстого, 2012. — 351 с.

9. Эвнин А. Ю. Сборник задач по дискретной математике. — 4-е изд. перераб. и доп. — М.: ЛИБРОКОМ, 2011. — 264 с.

Учебное издание

Клековкин Геннадий Анатольевич

Богданов Павел Сергеевич

Решение комбинаторных задач с использованием среды MAXIMA

Учебное пособие

Компьютерная верстка и корректура И. В. Мыльникова

Самарский филиал ГБОУ ВПО города Москвы «Московский городской педагогический университет», 443041, г. Самара, ул. Братьев Коростелевых, 76.

Подписано в печать 13.03.15. Формат 60×90 1/16. Бумага офисная. Гарнитура Times New Roman. Печать оперативная. Усл. печ. л. 5,5. Тираж 200 экз. Заказ 1303. Отпечатано в типографии ООО «Абрис», 443041, г. Самара, ул. Агибалова, 78.