Мультиноминальные коэффициенты

Первый курс Занятие второе

Вопрос 0. Разбор домашнего задания

6. В случае одной и двух четвёрок подряд легко найти соответствующие полные квадраты (2² и 12²), поэтому данные случаи не проверяем.
Рассмотрим число оканчивающееся на 3 четвёрки. Оно делится на 4, а 4 является квадратом, таким образом наше число имеет вид Разделим число Т на 4:

Если число четвёрок на конце больше трёх, то и остаток от деления на 4 будет 3, что соответствует невычету.

Упражнение: Найдите наименьшее число, квадрат которого имеет 3 четвёрки на конце подряд.

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

Вопрос 1. Метод математической индукции

Есть череда утверждений (их число не более, чем счётно), следующих одно из другого. Пусть среди них есть база – самое простое утверждение. Тогда можно доказать все утверждения сразу, проведя следующий приём:

Доказываем базу индукции (самое простое утверждение).

Полагаем, что верны n утверждений, доказываем, что верно n+1 (-ое) утверждение. Таким образом доказаны все утверждения.

Вопрос 1. Преобразования выражений с квадратичными иррациональнастями

Найти предел последовательности:

Упростим выражение:

Для решения нужно представить подкоренное выражение в виде квадрата:

В случае корней иных степеней нужно подбирать соответствующие степени. Выделим в выражении рациональную и иррациональную части:

Приравнивая рациональные и иррациональные части подкоренного выражения и квадрата суммы, получим:

Данную систему решаем методом подстановки:

Таким образом имеем базу индукции:

Предположим, что для n-1 корня данное утверждение (7) выполнено, тогда рассмотрим:

Получилось. Выходит, что для каждого n предел последовательности равен одному и тому же числу (6).

Задание 1.

Упростить выражения:

Ответы для самопроверки:

Вопрос 2: Введение в комбинаторику.

Число размещений с повторениями из n элементов по m мест равно n^m.

Доказательство: при каждом заполнении места, мы имеем дело с n вариантами выборов, а итоговое число комбинаций – произведение числа вариантов на каждом месте.

Пример: сколько можно составить десятизначных чисел из нечётных цифр в шестнадцатиричной системе счисления? Как изменится ответ, если будут использованы чётные цифры?

Решение:

В шестнадацатиричной системе счисления суть 8 чётных и 8 нечётных цифры. При использовании нечётных цифр мы получим 8¹⁰ чисел, а при использовании чётных – ибо если на первом месте стоит цифра ноль, то он незначащий, и число таким образом не десятизначное.

Число перестановок из n элементов равно n!.

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

Пример: сколькими способами я смогу расставить 20 книг на полке?

Чтобы получить число размещений (без повторений) из n элементов по k местам разделим n! на k!:

В данном случае число мест меньше числа вариантов, и в итоге идёт перемножение от n до ( n- k). Выразить это можно при помощи формулы (13).

Пример: у Деда Мороза 15 подарков, и ему нужно поздравить на празднике 10 детей; сколькими способами можно распределить подарки между детьми?

Число сочетаний можно получить, разделив число расстановок на число повторений: дело в том, что в случае сочетаний пары вида {a,b} и {b,a} не различаются. Число этих повторов k!:

Пример: Преподаватель, едя на экзамен попал в аварию, прибыв в зело плохом настроении, он решил завалить шестерых студентов из двадцати одного в группе. Сколькими способами он сможет выбрать своих жертв?

Рисунок 1: Пояснение к числу сочетаний и к числу размещений

Обобщение данной формулы: число разбиений (размещений без повторений) из n элементов по m групп численностью k_i каждая, причём :

Пример: Группа из 12 туристов собралась в поход, нужно выделить трёх человек на добычу воды и четырёх на сбор дров, сколькими способами это можно сделать?

Решение:

В условии задачи неявно присутствует ещё подгруппа путешественников: трое за водою, четверо за дровами, а ещё пятеро – никуда не идут. Таким образом, число распределений обязанностей .

Как это выводится? Мы распределяем части по группам, причём порядок расположения нам не важен, поэтому каждый раз мы делим на число повторений в данной группе.

Рисунок 2: Пояснение к числу разбиений

Число сочетаний можно также понимать как разбиение исходного множества на две подгруппы: выбранную и не выбранную. Такое представление наглядно показывает, что ибо при перемене выбранной и невыбранной подгруппы итоговое число сочетаний не изменится. Ведь нету зависимости числа разбиений от названия групп.

Разные задачи

Сколькими способами можно рассадить 5 девочек на одной лавке?

Число размещений без повторения.

Сколькими способами можно составить хоровод из 13 мальчиков?

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

Сколькими способами можно собрать бусы из 13 камешков?

В отличие от хоровода, если мы перевернём бусы, то это будут те же самые бусы, поэтому вариантов в 2 раза меньше.

В купе эл-ки нужно рассадить 6 человек. Сколькими способами можно сделать, если один из них предпочитает ехать против движения, два – по ходу движения, а трём – безразлично? Как изменится решение задачи, если для этого будет выделено два купе?

1. Сперва рассадим седоков с предпочтениями в направлении движения; для каждого направления – 3 сидения: для любителей сидеть по ходу движения, для любителей сидеть против, а затем оставшихся проезжих способами, итого это способов.

2. В данном случае у нас по 6 сидений в каждом направлении, тогда значения будут таковы: для любителей сидеть по ходу движения, для любителей сидеть против, а затем оставшихся проезжих способами, итого это способов.

В игре в классическую мафию участвуют 10 человек и ведущий, сидящие за столом. Все игроки пронумерованы, каждому игроку показывается карта с его ролью. Всего ролей 4: две мафии и дон, являющийся также мафией, но ищущий шерифа; шериф, ищущий мафию и 6 мирных жителей. Игроки 1 и 10 сидят у ведущего.

Найдите число расстановок стола таких что:

1. Мафии сидят в ряд;

2. Шериф окружён мирными жителями;

3. Мирный житель сидит между шерифом и мафиею;

4. Шериф и мафия сидят у ведущего;

Рисунок 3: Пояснение к расстановке игроков в мафию

Решения:

1. Из-за наличия ведущего средний игрок из ряда в мафию не может находиться на местах 1 и 10, то есть таких мест 8. На три места мафию можно разместить способами. Остальных игроков рассадим способами. Итого таких расстановок .

2. В отличие от предыдущего условия, шериф может сидеть на любом из мест, в случае расположения на крайних местах, его окружает один мирный житель, иначе – два. Данные случаи нужно рассмотреть отдельно. Если шериф сидит с краю, то мирного жителя можно выбрать способами, расположение остальных игроков ; общее число таких рассадок нужно умножить на два; если шериф расположен между мирными жителями, то мирных жителей можно выбрать способами, расположение блока шериф-мирные можно выбрать 8 способами и расположение остальных игроков способами, ответ: способами.

3. Рассадок мирного жителя, также как и в случае 1 настоящего перечня 8; шериф может быть справа и слева от мирного жителя, поэтому итоговое количество расстановок умножим на два. Мафию можно выбрать тремя способами, остальных игроков – способами. Итого:

4. Возможно два случая: шериф открывает стол (сидит на 1 месте), и мафия закрывает стол и наоборот, мафию можно выбрать 3 способами, остальных игроков способами.

Бином Ньютона

Биномиальными коэффициентами для степеней a^mb^m^- ⁿ при возведении будут коэффициенты .

Пример: найдите коэффициент при возведении

Мультиноминальные коэффициенты

Числа - коэффициенты при одночленах при возведении

Пример: найдите коэффициент при возведении

Домашнее задание

4. Найдите наименьшее число, квадрат которого имеет 3 четвёрки на конце подряд.

5. Найдите число раскладов стола при игре в мафию, при котором все положительные игроки (мирные жители и шериф) сидят в ряд. Сравните с числом раскладов стола, при котором в ряд сидят лишь мирные жители (смотри рисунок 3).

6. Найдите коэффициент при возведении

7. Найдите коэффициент при возведении

8. Найдите наибольшее число 6, идущих подряд с в записи натурального квадрата, разделите его на наибольшее число 1, идущих поряд.

Дата добавления: 2022-11-11; просмотров: 85; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!