Warning: session_start(): open(C:\Windows\temp\sess_741alm6pegbp1cb7u7ah6bmhc5, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 15 Warning: session_commit(): open(C:\Windows\temp\sess_741alm6pegbp1cb7u7ah6bmhc5, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 36 Warning: session_commit(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (C:\Windows\temp) in C:\www\lemma4.1php\login.php on line 36 Математика для Психологов

Пусть имеется группа из n элементов, и мы рассматриваем всевозможные способы расположения этих элементов, так называемые перестановки. Известно, что число возможных перестановок из n элементов равно n!=12...n . Для удобства принято полагать 0!=1 .
Например, рассмотрим число перестановок из трех элементов a,b,c. Определим это число с помощью построения дерева. Получаем шесть конечных ветвей, или шесть вариантов перестановки.Ассоциативная связь

Существует много комбинаторных задач, в которых невозможно указать какую-то простую форму для числа допускаемых задачей логических возможностей. Часто единственным способом служит построение дерева. Однако может быть полезным следующий общий принцип: если первый выбор можно сделать способами R , второй выбор можно сделать способами S , третий выбор можно делать T способами, то общее число перестановок равно RST . Например, пусть четыре студента могут получить одну из четырех оценок каждый. Если оценки не совпадают, то число вариантов 432=24 .

Рассмотрим более общую задачу: сколькими способами можно разместить k шаров в n корзин, так, чтобы в каждой корзине лежало не более одного шара, . Решим задачу сначала для n=4,k=2. Как видно из построения дерева логических возможностей, всего возможно 12 различных размещений.

Ассоциативная связь

Подобное построение легко провести для случая произвольных n и k :

первый шар может быть положен в любую из n корзин.

второй шар - в любую из оставшихся (n1) корзин,

третий шар - в любую из оставшихся (n2) корзин,

k -й шар в любую из оставшихся n(n1)(n2)...(nk1) корзин.

Всего получается

Ank=n(n1)(n2)...(n(k1)) 

- число размещений из n по k .

Следующий вопрос поставим так: сколькими способами можно выбрать из n различимых предметов k штук? Это число называется числом сочетаний из n элементов по k и обозначается Cnk . Снова обратимся к примеру с двумя шарами и четырьмя корзинами. Будем называть выбранными те корзины, в которых лежит шар. В случае размещений для нас существенно, какой шар оказался в данной корзине, в случае сочетаний – не существенно. Тогда из рисунка дерева видно, что некоторые возможности совпадают. Например, первая и четвертая. Это означает, что каждый случай выбора пары корзин считается столько раз, сколькими способами можно поменять местами шары в уже отмеченных корзинах. В нашем примере таких перемен мест (перестановок) всего две. Получили, что выбрать две корзины из четырех можно шестью способами.
Попробуем решить также с помощью дерева или рисунка следующую задачу. Сколькими способами можно выбрать из четырех пронумерованных корзин три?

Сначала подсчитаем число размещений трех шаров в четырех корзинах.
По формуле для Ank получаем: A43=432=24 .
Число удвоилось потому, что каждое из размещений двух шаров может быть дополнено добавлением третьего в одну из двух оставшихся свободными корзин.
Поскольку для нас не важны номера шаров, то многие возможности можно считать совпадающими. Подсчитаем, сколько раз выбраны одни и те же корзины, например, первая, вторая и четвертая.

Ассоциативная связь

В правой колонке нарисованы способы перестановки трех шаров по трем корзинам, всего получилось шесть способов. Понятно, что то же число получится, если рассматривать размещение трех шаров в любых трех фиксированных корзинах. То есть, каждый выбор трех корзин из четырех считается шесть раз в формуле числа размещений. Тогда общее число сочетаний из четырех элементов по три 246=4. 

.
Теперь вернемся к общему случаю. Сколькими способами можно выбрать k корзин из различимых n ? Как мы уже убедились, сначала надо вычислить число размещений k различимых шаров в n корзинах. Потом полученное число разделить на количество перестановок k различимых шаров, или, что то же самое, на количество размещений k шаров в k корзинах. Результат, как уже упоминалось, называется числом сочетаний из n элементов по k , и обозначается Cnk . Его можно записать в виде

Ассоциативная связь

Другие формы записи

Ассоциативная связь

Если поменять местами множители в знаменателе последнего равенства, то нетрудно видеть, что справедливо равенство Cnk=Cnnk 

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

Выпишем хорошо известные равенства для многочлена от двух переменных:

(p+q)0=1,(p+q)1=p+q,(p+q)2=p2+2pq+q2,(p+q)3=p3+3p2q+3pq2+q3. 

Рассмотрим многочлен

(p+q)n , называемый биномом. Ньютона. Что получится, если раскрыть скобки?
Начнем с выражения (p+q)4 . Опять используем дерево возможностей.

Ассоциативная связь

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

Как видно из рисунка общее количество концевых вершин, то есть множество возможностей, равно 16, или двум в четвертой степени, равной степени бинома. Среди этих возможностей много одинаковых, если нас интересует только окончательная степень у сомножителей. Например, если рассматривать ветки, оканчивающиеся произведением p2q2 , то нетрудно определить даже без непосредственного подсчета, сколько таких концевых веток оказалось в нашей «корзиночной модели». Для этого достаточно убедиться, что каждому такому произведению соответствует выбор каких-то двух корзин из четырех. В правой части рисунка изображены соответствующие этим веткам выборы корзин. Сколько способов выбора пары корзин из четырех, столько будет членов, содержащих квадраты и в биноме после раскрытия всех скобок. Аналогично, сколько существует способов выбора одной корзины из четырех, столько будет членов бинома, содержащих первую степень одного сомножителя и третью степень другого сомножителя (напомним, что имеет место равенство Cnk=Cnnk ).

В общем случае

(p+q)n=Cn0pn+Cn1pn1q+Cn2pn2q2+...+Cnn1pqn1+Cnnqn. 

Числовые значения коэффициентов в биноме Ньютона удобно находить с помощью построения треугольника Паскаля. Обоснованием этого служит следующая теорема.

Теорема. Cn+1k=Cnk+Cnk1 

Доказательство. Пусть у нас есть n+1 элемент. Выделим случайным образом один из них, назовем его x . Из этих n+1 элементов можно составить Cn+1k подмножеств, содержащих по k элементов. Разделим их на две группы A и B . Отнесем к группе A те из них, которые содержат x . К группе B отнесем те подмножества, которые не содержат x . Тогда каждое подмножество группы B получено сочетанием из n элементов (один, а именно x , исключен) по k . Следовательно, всего их Cnk . Каждое подмножество группы A образовано сочетанием из n элементов по k1 , так как в каждое еще включен x . Тогда их число Cnk1 . В сумме они образуют полное число Cn+1k - сочетаний из n+1 элемента по k .

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

Ассоциативная связь

В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Обозначим буквой n номер строки треугольника, а буквой k — номер числа в строке (нумерация начинается в обоих случаях с нуля). Тогда на пересечении строки и столбца с соответствующими номерами (в n -ой строке и на k -ом месте) стоит число Cnk .