16. Понятия размещения. Числа всех размещений из n элементов по k элементов.

Пусть дано множество, содержащее n элементов. Размещениями из n элементов по k элементов будем называть упорядоченные подмножества, состоящие из k элементов множества  (множества, состоящего изn элементов). Число размещений из n элементов по k элементов обозначается  (читается “А из n по k”). Одно размещение из n элементов по k элементов может отличаться от другого как набором элементов, так и порядком их расположения. Под размещение можно понимать любое упорядоченное множество, состоящее из n элементов, взятых из данного множества. Обозначается: =n(n-1)(n-2) …(n-m+1) – число размещений без повторения. Размещением из n элементов по k с повторениями – кортежи, содержащая m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования, причем элементы в комбинациях могут повторяться от 1 до m раз.

Дано множество X={a,b,c,d}. составить все размещения  из этого четыре элементного множества по два с повторениями. Эта записывается в виде:  Ā _n^k. Найти число кортежей дины k, которые можно составить из элементов множества, содержащего n элементов. – число размещений с повторения из n элементов по k

17. Треугольник паскаля и его свойства. Бином ньютона, его свойства и некоторые приложения.

Числовой треугольник Паскаля — неисчерпаемый источник всевозможных математических радостей.

В верхней строчке треугольника располагается одинокая единица. В остальных строках каждое число является суммой двух своих соседей этажом выше — слева и справа. Если какой-то из соседей отсутствует, он считается равным нулю. Т Обозначим буквой n номер строки треугольника, а буквой k — номер числа в строке (нумерация начинается в обоих случаях с нуля). Чаще всего число в n-ой строке и на k-ом месте в этой строке обозначается C^k_n, реже — (nk). Числа в n-ой строке треугольника являются биномиальными коэффициентами, то есть коэффициентами в разложении n-ой степени бинома Ньютона:

(a+b)n=∑k=0nC^k_nakbn−k.

Сумма всех чисел в n-ой строке равна n-ой степени двойки: ∑k=0nC^k_n=2ⁿ.

∑k=0nCkn=2ⁿ.

Эта формула получается из формулы бинома, если положить a=b=1.

Можно доказать явную формулу для вычисления биномиального коэффициента:

C^k_n=n!k!(n−k)!.

1) В треугольнике Паскаля каждое число кроме крайних единиц равно

сумме двух соседних в предыдущей строке.

2) Сумма чисел n-ой строки равна 2ⁿ, где n принадлежит целым числам.

3) Сумма чисел любой строки в два раза больше суммы чисел в предыдущей сроке.

4) Числа, равноудаленные от концов любой строки равны между собой.

Формула бинома Ньютона позволяет любой двучлен (бином) возвести в натуральную степень

Свойства бинома Ньютона:

1) Бином ньютона содержит n+1 слагаемых.

2) Биноминальные коэффициетнты, равноудаленные от концов равны между собой.

3) Формулу бинома Ньютона можно записать символически:

n

(a + b)n = S Cnk.an-k.bk

k=0

4) Любой член можно выразить формулой: Tk+1=Cnk.an-k.bk

5) Сумма биноминальных коэффициентов равна 2n.

Приложение. Метод математической индукции.

Некоторое утверждение будет верно при любом n N, если:

1) Оно верно при n=1;

2) Предположим, что оно верно при n=k и докажем, что оно верно

при n=k+1.