Методические рекомендации для проведения курса «Комбинаторика» (стр. 4 )

Решение: Здесь две буквы “м” и две буквы “а”. Значит, по формуле (6) число перестановок равно

3. 3 Сочетания.

а) Сочетания без повторений.

В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях.

k-сочетаниями из n элементов называют всевозможные k-расстановки, составленные из этих элементов и отличающихся друг от друга составом, но не порядком элементов. Число k-сочетаний, которые можно составить из n элементов, обозначается через .

Формула для числа сочетаний легко получается из формулы для числа размещений. Составим сначала все k-сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все k-размещения из n элементов, причем каждое только по одному разу. Но из каждого k-сочетания можно сделать k! перестановок, а число этих сочетаний равно . Значит, справедлива формула

  (7)

Задача. Сколькими способами можно поставить на шахматную доску восемь коней?

Решение. Для решения этой задачи, необходимо выбрать из 64 клеток шахматной любые 8 клеток. А это можно сделать   способами.

б) Сочетания с повторениями.

Общая формулировка задач:

Имеются предметы различных типов, сколько k – комбинаций можно сделать из них, если не принимать во внимание порядок элементов в комбинации (различные комбинации должны отличаться хотя бы одним предметом)?

При решении задач данного типа надо в каждом сочетании расположить элементы по типам (сначала все элементы первого типа, потом второго типа и т. д.). А затем перенумеровать все элементы в сочетании, но к номерам второго типа прибавить 1, третьего типа прибавить 2 и т. д. Тогда из каждого сочетания с повторениями получится сочетание без повторений, состоящие из чисел 1,2,…,n+k-1, причем в каждое сочетание входит k элементов. Обозначается сочетание с повторениями через  и вычисляется по формуле:

  (8)

Рассмотрим пример: «Задача о пирожных»

В кондитерском магазине продавали 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Решение: Данная задача не является задачей на размещения с повторениями, так как порядок, в котором укладываются пирожные в коробку, несуществен. Поэтому эта задача - на сочетания, но так как в комбинации могут входить повторяющиеся элементы, то эта задача на сочетания с повторениями. Воспользуемся формулой (8) для решения задачи, т. е. способов.

в) Свойства  числа сочетания.

Числа   обладают  рядом замечательных свойств:

(k>>>1/2n) (сумма числа сочетаний для любого целого числа n≥0) ( рекуррентная формула числа сочетаний для любого k, n; 0≤k≤n)

Эти свойства можно будет доказать различными способами: можно воспользоваться формулой (7), а можно получить доказательства комбинаторным путем: сначала подсчитать число комбинаций некоторого вида и разбить эти комбинации на классы без общих элементов, затем найти, сколько комбинаций входит в каждый класс, и, складывая полученные числа, снова получаем число всех комбинации данного вида.

§ 4.Треугольник Паскаля.

Треугольник Паскаля, является таблицей числа сочетаний. С помощью таблицы 1.2 можно последовательно вычислять , сначала при n=0, затем при n=1, при n=2 и т. д.

Таблица 1.2  «Треугольник Паскаля».

n\k	0	1	2	3	4	5	6	7	8	9	10
0	1	1
1	1	1	2
2	1	2	1	4
3	1	3	3	1	8
4	1	4	6	4	1	16
5	1	5	10	10	5	1	32
6	1	6	15	20	15	6	1	64
7	1	7	21	35	35	21	7	1	128
8	1	8	28	56	70	56	28	8	1	256
9	1	9	36	84	126	16	84	36	9	1	512
10	1	10	45	120	210	252	210	120	45	10	1

Чтобы вычислить , зная тождество (свойство 6): , необходимо сложить 2 соседних числа одной строки и получить – число, стоящее в следующей строке под правым слагаемым. Например, если (при n=4, k=2), то =6.

  Таблицу называют треугольником Паскаля по имени французского математика Блэза Паскаля (1623-1662), в трудах которого она встречается. Это название исторически неточно, так как таблицу уже знали арабские математики Каши и Хайям, жившие в XIII веке, а из европейских ученых с этой таблицей был знаком итальянский механик и математик Николо Тарталья (1500-1557). Поэтому эту таблицу называют арифметическим треугольником.

§ 5. Бином Ньютона

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

Но коэффициенты 1,2, 1 – это числа, стоящие в третьей строке таблицы, т. е.; а 1, 3, 3, 1 – числа, стоящие в четвертой строке той же таблицы, т. е..