alt text

Помогите, пожалуйста, доказать данные тождества.

задан 10 Дек '19 18:26

10|600 символов нужно символов осталось
2

Обозначения в виде квадратных и фигурных скобок желательно пояснять. Здесь можно догадаться, что речь о числах Стирлинга I и II рода, но для них могут быть и другие обозначения. Скажем, $%s(n,k)$% и $%S(n,k)$%. Равно как скобки могут означать что-то ещё. Также надо иметь в виду, что многие стандартные комбинаторные функции могут определяться разными способами, от чего может зависеть стратегия доказательства.

Начнём для удобства со второго пункта.

б) Здесь речь о числе разбиений $%n$%-элементного множества на $%n-2$% равноправные части ($%n\ge3$%). Легко видеть, что есть два типа таких разбиений: или в одной части три элемента, а в остальных по одной, или же есть две части по два элемента и остальные одноэлементные.

В первом случае выбираем $%C_n^3$% способами три элемента из одной части. Остальное однозначно. Во втором случае надо выбрать две пары. Сначала выбираем 4 элемента для них $%C_n^4$% способами. Ясно, что эти элементы можно тремя способами разбить на пары. В сумме получается $%C_n^3+3C_n^4=\frac{n(n-1)(n-2)(3n-5)}{24}$%.

а) Здесь всё обстоит похоже. Возьмём за основу определение через количество перестановок на $%n$% элементах с $%n-2$% циклами. Здесь либо один цикл имеет длину 3, а остальные одноэлементны, либо есть два цикла длиной 2, а остальные элементы подстановки неподвижны. В первом случае, после выбора трёх элементов цикла, его можно записать двумя способами как $%(abc)$% или $%(acb)$%. Поэтому $%C_n^3$% умножается на 2. Во втором случае разницы нет: выбираем 4 элемента и разбиваем их на пары. Итого $%2C_n^3+3C_n^4=\frac{n(n-1)(n-2)(3n-1)}{24}$%.

ссылка

отвечен 10 Дек '19 19:00

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,279
×60

задан
10 Дек '19 18:26

показан
120 раз

обновлен
10 Дек '19 19:00

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru