Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Конкретная математика

(Лекции 2004, фрагменты)

Санкт-Петербург

09.05.2004

Докажем, что число счастливых 2n-значных трамвайных билетов равно

.

Билет считается счастливым, если сумма первых n цифр его номера равна сумме n последних цифр, например, билет с номером 764395 – счастливый шестизначный билет.

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

Доказательство (леммы).

Рассмотрим равенство (1+z+…+z⁹)ⁿ= , тогда а_i определяет количество n-значных чисел, сумма цифр которых равна i.

Нам нужно вычислить .

Имеем (1+z+…+z⁹)ⁿ(1+z^-1+…+z^-9)ⁿ= ´ = ,

тогда b₀= .

(1+z+…+z⁹)ⁿ(1+z^-1+…+z^-9)ⁿ= = .

Известно, что = .

Пусть z=e^ij=cosj+isinj, тогда b₀= = = .

Преобразуем =

=

= = .

Таким образом,

b₀= = = .

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

Правило суммы. Если объект А может быть выбран m способами, а объект В другими n способами, то выбор “либо А, либо В” может быть осуществлен m+n способами.

Правило произведения. Если объект А может быть выбран m способами и после каждого из таких выборов объект В в свою очередь может быть выбран n способами, то выбор “А, и В” в указанном порядке может быть осуществлен m×n способами.

Примеры. На основе этих правил в курсе математического анализа легко были получены формулы для числа k-перестановок и числа k-сочетаний из n объектов, а именно

= n(n-1)…(n-k+1)

=

Упражнение. Докажите, что число k-перестановок из n объектов с повторениями равно n^k.

Задача. Доказать, что число k-сочетаний из n объектов с повторениями равно .

Решение (Л. Эйлер): Пусть X={1,2,…n} и рассмотрим любое из k-сочетаний с повторениями с₁с₂…с_k этих n чисел (считаем, что в сочетании с₁с₂…с_k элементы выписаны в неубывающем порядке). Естественно, что в каждом сочетании вследствие возможности неограниченных повторений любые рядом стоящие элементы могут быть одинаковыми. Ввиду этого обстоятельства строим с помощью соотношений

d₁=c₁+0; d₂=c₂+1;…; d_i=c_i+i-1;…; d_k=c_k+k-1

последовательность элементов d₁d₂…d_k следовательно, при любых элементах c_i элементы d_i всегда различны. Ясно, что отображение с₁с₂…с_k в d₁d₂…d_k биективно. Число последовательностей из элементов d_i равно числу k-сочетаний без повторений из элементов от 1 до n+k-1, т. е. .