Задание 3 "Системы счисления, перестановки и анаграммы"
Переставляя всеми возможными способами числа 1, 2, ..., n,
мы получим все перестановки этих чисел. Например, есть 6 перес-
тановок чисел 1, 2 и 3: 123, 132, 213, 231, 312, 321.
3.1. Сколько имеется перестановок чисел 1, 2, 3 и 4? Выпишите
их все.
3.2. Покажите, что имеется n!=1*2*...*n перестановок чисел 1,
2, ..., n.
Как разложить n! в произведение простых множителей?
Посмотрим, в какой степени 2 входит в такое разложение. За-
пишем число n в двоичной системе счисления. Теперь будем отбра-
сывать по цифре справа и получающиеся числа складывать. Полу-
чившаяся сумма и даст ответ.
Пример. 10! = 2^8*..., так как 10 = <1010> и сумма
< 101>
< 10>
< 1>
<---->
<1000> = 8
равна 8 (в угловых скобках - запись в двоичной системе счисле-
ния).
3.3. Докажите это правило в общем случае.
Чтобы узнать, в какой степени простое число p входит в разложе-
ние n! на простые множители, можно так же использовать запись
числа n в p-ичной системе счисления.
3.4. Выпишите разложение 100! на простые множители.
Переставляя всеми возможными способами буквы некоторого сло-
ва, мы получим все его анаграммы. Например, есть 6 анаграмм
слова МАМА: ААММ, АМАМ, МААМ, АММА, МАМА, ММАА.
3.5. Сколько имеется анаграмм
(а) слова АААБББ, (б) слова ААААББ ?
Выпишите их все.
Возьмем m белых карточек, занумерованныхот 1 до m, и n черных
карточек, занумерованных от 1 до n. Всего имеется (m+n)! перес-
тановок этих карточек. Возьмем произвольно одну из таких перес-
тановок. На белой карточке напишем букву Б, а на черной - букву
Ч. Получим анаграмму слова, состоящего из m букв Б и n букв Ч.
Одна и та же анаграмма может возникнуть у нас m!*n! способами,
поэтому различных анаграмм этого слова имеется
(m+n)!
С(m,n) = -------
m! n!
3.6. Проверьте этот подсчет на примере 2 белых карточек Б1, Б2
и 3 черных карточек Ч1, Ч2, Ч3. Две перестановки этих 5 карто-
чек запишите в один столбик, если они дают одну анаграмму (нап-
ример, перестановки Б1,Ч3,Ч1,Б2,Ч2 и Б2,Ч2,Ч1,Б1,Ч3 будут в од-
ном столбике). Сколько будет столбиков?
Как разложить C(m,n) в произведение простых множителей?
Посмотрим, в какой степени 2 входит в такое разложение. За-
пишем числа m и n в двоичной системе счисления, сложим их в
двоичной записи и посмотрим, сколько было переносов в старшие
разряды. Это число переносов и даст ответ.
Пример. C(5,7) = 2^3*..., так как 5=<101>, 7=<111> и при
сложении ...
< 101>
< 111>
<---->
<1100> = 12
было 3 переноса в старшие разряды.
3.7. Докажите это правило в общем случае.
Чтобы узнать, в какой степени простое число p входит в разложе-
ние C(m,n) на простые множители, можно так же использовать за-
пись чисел m и n в p-ичной системе счисления.
3.8. Выпишите разложение C(50,50) на простые множители.
3.9. Напишите программу на том языке программирования, который
Вы учите, дающую разложение числа C(m,n) на простые множители.
3.10. Сколько примерно цифр в десятичной записи
(а) 100! ; (б) C(50,50) ?
3.11. Сколько в квадратной таблице 0 <= m < 2^k, 0 <= n < 2^k
нечетных чисел C(m,n) ? Будем показывать нечетные числа единич-
кой, а четные - нулем. Вот картинка для k=2:
\n 0 1 2 3
m\ -------
0| 1 1 1 1
1| 1 0 1 0
2| 1 1 0 0
3| 1 0 0 0
Сделайте картинку для k=4. Пусть d(k) - количество нечетных чи-
сел в квадратной таблице 0 <= m < 2^k, 0 <= n < 2^k. Укажите
формулой зависимость d(k) от k. При каком наименьшем k это ко-
личество d(k) составляет меньше 1% от всего количества чисел
C(m,n) в этом квадрате?
3.12. Пусть f(k) - количество нечетных чисел на "диагонали"
m+n=k. Как f(k) связано с двоичной записью числа k? Обратите
внимание на количество единичек в двоичной записи числа k.
О задачах
Прежде всего отметим, что для того, чтобы решать задачи, не
требуются никакие книжки, нужно только желание. Младшие учас-
тники кружка могут ограничиться вычислениями, а старшие могут
задуматься и над доказательствами, и делать программу.
Заметим, что C(m,n) - это число сочетаний из m+n по m (или
по n, все равно). Геометрическая трактовка - число путей, веду-
щих из точки (0,0) в точку (m,n), когда сдвигаться можно только
вправо на 1 или вверх на 1. В частности, C(7,7) - число крат-
чайших путей ладьи из левого нижнего угла шахматной доски в
правый верхний угол. Действительно, если сдвиг вправо на 1
обозначить буквой А, а вверх на 1 - буквой Б, то такой путь из
(0,0) в (m,n) записывается некоторой анаграммой из m букв А и n
букв Б. Алгебраическая трактовка C(m,n) - биномиальный коэффи-
циент из m+n по m (или по n). Таблица чисел C(m,n) - это повер-
нутый на 45 градусов треугольник Паскаля.
Вместо чета-нечета (остатков от деления на 2) можно брать
остатки от деления на простое число p. Вместо чисел C(m,n) мож-
но рассматривать числа C(k,l,m) - триномиальные коэффициенты.
Число C(k,l,m) обозначает количество анаграмм слова, состоящего
из k букв А, l букв Б и m букв В.
В истории треугольника Паскаля "по модулю p", которую здесь
просто невозможно пересказать, нужно отметить замечательную
книгу Е.Б.Дынкина и В.А.Успенского "Математические беседы", вы-
шедшую в серии "Библиотека математического кружка" в 1952 году.
Один из первых номеров журнала "Квант" (N 6 за 1970 г.) содер-
жал статью "Арифметика биномиальных коэффициентов", авторы
Д.Б.Фукс и М.Б.Фукс. Создатель системы Mathematica для символь-
ных и численных вычислений S.Wolfram, по образованию физик, в
начале 80-х годов занимался клеточными автоматами и способство-
вал популяризации задачи про количество нечетных элементов в
строке треугольника Паскаля с номером k. Ну а далее должен быть
помянут A.Granville, о нем будет рассказано при обсуждении за-
дачи.
Про системы счисления можно узнать во многих книжках и у
многих людей. Совет школьникам - про все поначалу непонятное
спрашивайте своих друзей, учителей, ищите в книжках в библиоте-
ке. Кто ищет - тот всегда найдет.
Отмечу как очень полезную книжку С.Л.Табачникова "Многочле-
ны", вышедшую в 1996 году в издательстве "Фазис", хотя в ней
про системы счисления написано немного.
(С) С.И.Соболев, 1999-2002