|
Постановка
проблемы. Можно ли сводить
комбинаторные задачи к алгебраическим?
Оказывается, что для большого класса комбинаторных
задач ответ можно получить как коэффициент многочлена,
который является результатом алгебраических операций над типовыми
для данного класса задач многочленами. |
|
Для операций над многочленами есть несколько мощных
компьютерных программ символьных вычислений, таких как Maple,
Mathematica (мы будем использовать более простую
программу Maxima, которая свободно
распространяется и имеет русифицированный интерфейс).
Работа с такими программами не требует специального
обучения, и мы будем описывать форматы команд по мере того, как они
будут использоваться в лабораторных работах.
Преимущество этих программ по сравнению, например, с
настольными калькуляторами в том, что для них не представляет труда
работать с целыми числами и многочленами практически неограниченной
длины! |
Цели
работы.
В этой
лабораторной работе мы найдём число "счастливых" трамвайных
(шестизначных) билетов с помощью перемножений многочленов в
программе Maxima. Для этого мы сначала
докажем, что число счастливых билетов равно числу билетов с суммой
цифр 27,
а потом вычислим это число.
|
|
Взаимно однозначное соответствие между
счастливыми билетами и билетами с суммой цифр
27.
|
Сопоставим шестизначному набору десятичных цифр
(трамвайному билету) A B C D E F,
где A,
B, C, D, E и F
–цифры, набор
A B C (9-D) (9-E) (9-F).
Например, "счастливому" билету
129345
сопоставляется билет 129654.
Понятно, что разным счастливым билетам
сопоставляются разные билеты с суммой
цифр 27,
и эта же формула даёт обратное соответствие.
Проверим, что сумма цифр билета
A B C (9-D) (9-E) (9-F)
действительно равна
27:
Действительно,
A + B + C
+ (9-D) + (9-E)
+ (9-F) = 27 + (A
+ B + C -
D - E
- F) = 27,
так как сумма A
+ B + C
равна сумме
D + E + F.
|
|
Понятие о производящей функции |
Рассмотрим произведение 6 многочленов
1+x+x2+x3+x4+x5+x6+x7+x8+x9:
(1+x+x2+x3+x4+x5+x6+x7+x8+x9)(1+x+x2+x3+x4+x5+x6+x7+x8+x9)..
(1+x+x2+x3+x4+x5+x6+x7+x8+x9).
Как получаются одночлены степени
27: x27?
Из каждой скобки выбирается по одному
одночлену так, чтобы сумма их степеней равнялась 27, например,
xx2x9x6x5x4.
Нетрудно заметить, что показатели перемножаемых одночленов совпадают
с цифрами набора с 129654,
который приводился выше как пример набора с суммой цифр
27. Таким образом
получается взаимно однозначное соответствие между такими
произведениями одночленов и шестизначными наборами с суммой цифр
27.
Количество таких произведений даёт
коэффициент при x27
в разложении
(1+x+x2+x3+x4+x5+x6+x7+x8+x9)6.
|
|
Проведение вычислений в программе Maxima |
Введём в окно ввода задание многочлена, как показано
ниже и нажмём Enter.
В окне появится вторая строчка (в её номер
войдёт буква "о").
Введём команду
expand(p(x)); и снова нажмём
Enter.
В рабочем окне появится разложение многочлена.
Коэффициент 55252
при
x27 даст
нам число счастливых билетов. |
|
(%i1)
p(x):=(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6;
(%o1)
p(x):=(1+x+x2+x3+x4+x5+x6+x7+x8+x9)6;
(%i2)
expand(p(x));
(%o2) x54+6x53+21x52+56x51+126x50+252x49+46x48+792x47+1287x46+
2002x45+2997x44+4332x43+6062x42+8232x41+10872x40+13992x39+17577x38+21582x37+
25927x36+30492x35+35127x34+39662x33+43917x32+47712x31+50877x30+53262x29+54747x28+
55252x27+54747x26+53262x25+50877x24+47712x23+43917x22+39662x21+35127x20+30492x19+
25927x18+21582x17+17577x16+13992x15+10872x14+8232x13+6062x12+4332x11+2997x10+
2002x9+1287x8+792x7+462x6+252x5+126x4+56x3+21x2+6x+1 |
|
|
|
Задания. |
|
1. С помощью полученного
разложения найдите число билетов с суммой цифр
2. Напишите номера этих билетов.
2. С помощью полученного
разложения выясните, билетов с какой суммой больше всего.
Объясните симметрию коэффициентов многочлена, полученного выше.
3. С помощью полученного
разложения найдите число билетов, у которых сумма первых двух
цифр равна сумме оставшихся. Для этого постройте взаимно
однозначное соответствие между этими билетами и билетами с
суммой цифр 18.
4*. С помощью полученного
разложения найдите число билетов, у которых первая цифра равна
сумме оставшихся.
5*. С помощью полученного
разложения найдите число билетов, у которых сумма первых трёх
цифр на 1
больше суммы оставшихся.
6*. Попробуйте дать
комбинаторное обоснование всем полученным выше коэффициентам.
7*. С помощью программы
Maxima решите задачу про число
"счастливых" билетов, состоящих только из нечётных цифр.
8**. По аналогии с
предыдущими, предложите свои задачи и их решения, используя
производящие функции (многочлены) и пользуясь программой
Maxima. |
| |
|
Работы учеников.
|
|
|
