|
|
Метод математической индукцииВ основе всякого математического исследования лежат дедуктивный или индуктивный методы. Дедуктивный метод рассуждений - это рассуждение от общего к частному, т.е. рассуждение, исходным моментом которого является общий результат, а заключительным моментом – частный результат. Индукция применяется при переходе от частных результатов к общим, т.е. является методом, противоположным дедуктивному. По своему первоначальному смыслу слово «индукция» применяется к рассуждениям, при помощи которых получают общие выводы, опираясь на ряд частных утверждений. Рассмотрим доказательство методом математической индукции на примере. Доказать, что для любого натурального n, справедливо равенство:
Доказательство. 1) Пусть n=1, тогда 2) Докажем, что данное равенство справедливо для (k+1). Пусть k – любое натуральное число и пусть утверждение справедливо для n=k, т.е. Докажем, что тогда утверждение справедливо и для следующего натурального числа n=k+1, т.е. что Действительно,
На основании принципа математической индукции заключаем, что исходное равенство истинно для любого nÎN.
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ 1. Понятие выборки Если из множества, содержащего n элементов, каким-то способом отобраны k элементов (k<n), то говорят, что из этого множества произведена выборка объема k. Если порядок расположения элементов выборки принимают во внимание, то выборки называют упорядоченными. Таким образом, две упорядоченные выборки считают различными, если они отличаются либо составом элементов, либо их расположением. В том случае, когда порядок расположения элементов не учитывают, выборки называют неупорядоченными. Следовательно, две неупорядоченные выборки считают различными, если в одной из них есть хотя бы один элемент, которого нет в другой. Например, для множества, состоящего из трех элементов a, b, c, существуют три различные неупорядоченные выборки объема (ab, bc, ac) и шесть различных упорядоченных выборок того же объема (ab, bc, ac, ba, cb, ca). Правила комбинаторики Комбинаторика – это раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Многие задачи комбинаторики могут быть решены при помощи следующих правил: Правило произведения: Пусть из некоторого конечного множества первый объект можно выбрать m1 способами, второй объект – m2 способами, …, п-й – тп способами, тогда произвольный набор перечисленных п объектов можно выбрать т1 · т2 · …· тп способами. Правило суммы: Пусть из некоторого конечного множества первый объект можно выбрать m1 способами, второй объект – m2 способами, …, п-й – тп способами, тогда любой из объектов можно выбрать т1 + т2 + …+тп способами. Примеры: 1. Сколько существует способов выбора одного карандаша из коробки, если в ней содержится 7 синих карандашей, 5 красных, 3 зеленых и 1 желтый? Решение. Синий карандаш можем выбрать 7 способами, красный – 5 способами, зеленый – 3 способами, желтый – 1 способом. Так как выбираем один объект, то воспользовавшись правилом суммы, получим: N = 7 + 5 + 3 + 1 = 16. Ответ. 16 способов. 2. Сколько существует пятизначных чисел, все цифры у которых различны? Решение. Х ХХ Х Х – пятизначное число. Первая цифра записи числа может быть записана 9 способами, так как для записи чисел используется 10 цифр 0,1,2,…,9 и ноль не может быть первой цифрой записи пятизначного числа. Вторая цифра может быть записана 9 способами, так как используются 8 оставшихся цифр и ноль, третья цифра – соответственно 8 способами, четвертая – 7 способами, пятая – 6 способами. Так как пятизначное число – это набор из 5 цифр, то для подсчета воспользуемся правилом произведения, получим: N = 9 × 9 × 8 × 7 × 6 = 27216. Ответ: 27216 существует пятизначных чисел, все цифры у которых различны. |
|
.
. Следовательно, утверждение верно при n=1.
.
.
.