РЕШУ УРОК — выпускные экзамены по математике

Задания

5.  Числа $E_n в степени k ,$ где n, k  — целые неотрицательные, определены равенствами

$E_n в степени k = левая круглая скобка k плюс 1 правая круглая скобка E_n минус 1 в степени k плюс левая круглая скобка n минус k правая круглая скобка E_n минус 1 в степени левая круглая скобка k минус 1 правая круглая скобка ,$

$E_n в степени 0 = 1$

$E_n в степени k = 0$

при $k больше или равно n.$

а)  Докажите, что $E_n в степени k = E_n в степени левая круглая скобка n минус k минус 1 правая круглая скобка .$

б)  Найдите отношение $дробь: числитель: E_11 в степени 5 , знаменатель: E_10 в степени 5 конец дроби .$

в)  Докажите, что для любых натуральных чисел p и n верно тождество

$p в степени n = E_n в степени 0 C_p в степени n плюс E_n в степени 1 C_p плюс 1 в степени n плюс \ldots плюс E_n в степени левая круглая скобка n минус 1 правая круглая скобка C_p плюс n минус 1 в степени n .$ $p в степени n = E_n в степени 0 C_p в степени n плюс E_n в степени 1 C_p плюс 1 в степени n плюс$
$плюс \ldots плюс E_n в степени левая круглая скобка n минус 1 правая круглая скобка C_p плюс n минус 1 в степени n .$

г)  Докажите, что $E_n в степени k$ совпадает с числом таких перестановок $a_1, a_2, \ldots, a_n$ чисел $1, 2, \ldots, n,$ для которых неравенство $a_i больше a_i плюс 1$ выполняется ровно для k значений $i принадлежит левая фигурная скобка 1, 2, \ldots, n минус 1 правая фигурная скобка .$

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

а)  Приведем рассуждение по индукции. База индукции очевидна. Индукционный переход:

$E_n плюс 1 в степени левая круглая скобка n минус k правая круглая скобка = левая круглая скобка n минус k плюс 1 правая круглая скобка E_n в степени левая круглая скобка n минус k правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка E_n в степени левая круглая скобка n минус k минус 1 правая круглая скобка =$
$= левая круглая скобка n минус k плюс 1 правая круглая скобка E_n в степени левая круглая скобка k минус 1 правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка E_n в степени k = E_n плюс 1 в степени k .$ $E_n плюс 1 в степени левая круглая скобка n минус k правая круглая скобка =$
$= левая круглая скобка n минус k плюс 1 правая круглая скобка E_n в степени левая круглая скобка n минус k правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка E_n в степени левая круглая скобка n минус k минус 1 правая круглая скобка =$
$= левая круглая скобка n минус k плюс 1 правая круглая скобка E_n в степени левая круглая скобка k минус 1 правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка E_n в степени k = E_n плюс 1 в степени k .$ $E_n плюс 1 в степени левая круглая скобка n минус k правая круглая скобка =$
$= левая круглая скобка n минус k плюс 1 правая круглая скобка E_n в степени левая круглая скобка n минус k правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка E_n в степени левая круглая скобка n минус k минус 1 правая круглая скобка =$
$= левая круглая скобка n минус k плюс 1 правая круглая скобка E_n в степени левая круглая скобка k минус 1 правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка E_n в степени k =$
$= E_n плюс 1 в степени k .$

б)  Увидим $E_11 в степени 5 = 6 E_10 в степени 5 плюс 6 E_10 в степени 4 = 12 E_10 в степени 5$ в силу соотношения симметрии предыдущего пункта, отсюда ответ  — 12.

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

Лемма. Имеем: $левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p плюс 1 в степени левая круглая скобка n плюс 1 правая круглая скобка =pC_k плюс p в степени n .$ Действительно,

$левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p плюс 1 в степени левая круглая скобка n плюс 1 правая круглая скобка =$
$= левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка левая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс C_k плюс p в степени n правая круглая скобка =$
$= левая круглая скобка n плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p в степени n =$
$= левая круглая скобка k плюс p минус n правая круглая скобка C_k плюс p в степени n плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p в степени n = pC_k плюс p в степени n .$ $левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p плюс 1 в степени левая круглая скобка n плюс 1 правая круглая скобка =$
$= левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка левая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс C_k плюс p в степени n правая круглая скобка =$
$= левая круглая скобка n плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p в степени n =$
$= левая круглая скобка k плюс p минус n правая круглая скобка C_k плюс p в степени n плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p в степени n =$
$= pC_k плюс p в степени n .$

Итак, докажем тождество по индукции:

$\sum_k = 0 в степени n E_n плюс 1 в степени k C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка =$
$= \sum_k = 0 в степени n меньше или равно левая круглая скобка k плюс 1 правая круглая скобка E_n в степени k C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n плюс 1 минус k правая круглая скобка E_n в степени левая круглая скобка k минус 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n минус 1 правая круглая скобка =$
$= \sum_k = 0 в степени левая круглая скобка n минус 1 правая круглая скобка E_n в степени k меньше или равно левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p плюс 1 в степени левая круглая скобка n плюс 1 правая круглая скобка = p\sum_k = 0 в степени левая круглая скобка n минус 1 правая круглая скобка E_n в степени k C_k плюс p в степени n ,$ $\sum_k = 0 в степени n E_n плюс 1 в степени k C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка =$
$= \sum_k = 0 в степени n меньше или равно левая круглая скобка k плюс 1 правая круглая скобка E_n в степени k C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n плюс 1 минус k правая круглая скобка E_n в степени левая круглая скобка k минус 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n минус 1 правая круглая скобка =$
$= \sum_k = 0 в степени левая круглая скобка n минус 1 правая круглая скобка E_n в степени k меньше или равно левая круглая скобка k плюс 1 правая круглая скобка C_k плюс p в степени левая круглая скобка n плюс 1 правая круглая скобка плюс левая круглая скобка n минус k правая круглая скобка C_k плюс p плюс 1 в степени левая круглая скобка n плюс 1 правая круглая скобка =$
$= p\sum_k = 0 в степени левая круглая скобка n минус 1 правая круглая скобка E_n в степени k C_k плюс p в степени n ,$

откуда и следует индукционный переход.

г)  Формулировка этого пункта дает другое, комбинаторное, описание чисел Эйлера. Идея доказательства знакома, поскольку аналогичные рассуждения часто используются при рассмотрении чисел сочетаний. Именно, мы покажем, что для количества $\tilde E_n в степени k$ перестановок указанного вида выполняются те же соотношения, которыми определялись числа Эйлера, поэтому $\tilde E_n в степени k =E_n в степени k .$

Ясно, что если при всех $i принадлежит левая фигурная скобка 1, 2, \ldots, n минус 1 правая фигурная скобка$ верно неравенство $a_i меньше a_i плюс 1,$ то $a_i=i,$ то есть имеется одна такая перестановка, поэтому $\tilde E_n в степени 0 =1=E_n в степени 0 .$

Пусть теперь $a_1, a_2, \ldots, a_n$   — перестановка с k инверсиями, под которыми мы понимаем такие пары $левая круглая скобка i; i плюс 1 правая круглая скобка ,$ что $a_i больше a_i плюс 1.$ Предположим, что $w=a_l.$

Рассмотрим перестановку $b_1, b_2, \ldots, b_n минус 1,$ получающуюся из исходной вычеркиванием элемента a_l, так что $b_j=a_j$ при $j меньше l$ и $b_j=a_j плюс 1$ при $j\geqslant} l.$ Ясно, что число инверсий в полученной таким образом перестановке $левая круглая скобка b_i правая круглая скобка$ равно либо $k минус 1,$ либо k. Предположим вначале, что это число есть $k минус 1.$ Следовательно, для некоторых $n минус k минус 1$ значений $j принадлежит левая фигурная скобка j_1, \ldots, j_n минус k минус 1 правая фигурная скобка$ верно неравенство $b_j меньше b_j плюс 1.$ Поэтому исходная перестановка $левая круглая скобка a_i правая круглая скобка$ может иметь k инверсий, если $l = 1, j_1 плюс 1, \ldots, j_n минус k минус 1 плюс 1,$ следовательно, число таких перестановок, получающихся добавлением числа n в $левая круглая скобка n минус 1 правая круглая скобка$ -⁠перестановку с $k минус 1$ инверсией, равно $левая круглая скобка n минус k правая круглая скобка \widetilde E_n минус 1 в степени левая круглая скобка k минус 1 правая круглая скобка .$ Рассуждая аналогично, получаем, что число n-⁠перестановок с k инверсиями, получающихся из $левая круглая скобка n минус 1 правая круглая скобка$ -⁠перестановок с k инверсиями, равно $левая круглая скобка k плюс 1 правая круглая скобка \widetilde E_n минус 1 в степени k ,$ таким образом,

$\widetilde E_n в степени k = левая круглая скобка n минус k правая круглая скобка \widetilde E_n минус 1 в степени левая круглая скобка k минус 1 правая круглая скобка плюс левая круглая скобка k плюс 1 правая круглая скобка \widetilde E_n минус 1 в степени k .$

Ответ: б) 12.

----------

Дублирует задание 2074.

Ключ