Сочетания в комбинаторике

В комбинаторике часто рассматривают задачи на отыскание количества подмножеств, содержащих по k элементов каждое, можно составить из m элементов данного множества Х?


Такие подмножества носят название сочетаний без повторений из элементов по k:  CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif. Выведем формулу, выражающую   CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif через m и k. Возьмем какое-нибудь k-подмножество А в m-множестве Х. Так как множество А содержит k элементов, то его можно упорядочить k! способами. При этом каждое упорядоченное k-множество, состоящее из элементов множества Х, может быть получено таким путем. Значит число упорядоченных k-множеств, составленных из элементов множества Х, в  k! раз больше числа неупорядоченных k-подмножеств в Х.


Например, из элементов множества А = {a, b, c, d} можно составить четыре трехэлементных подмножества: {a, b, с}; {a, b, d}; {a, c, d};           {b, c, d}. Число же упорядоченных трехэлементных подмножеств в 3! = 6 раз больше:


{a, b, с}; {a, b, d}; {a, c, d}; {b, c, d}


{a, c, b}; {a, d, b}; {a, d, c}; {b, d, c}


{b, a, с}; {b, a, d}; {c, a, d}; {c, b, d}


{b, c, a}; {b, d, a}; {c, d, a}; {c, d, b}


{c, a, b}; {d, a, b}; {d, a, c}; {d, b, c}


{c, b, a}; {d, b, a}; {d, c, a}; {d, c, b}.


Но число упорядоченных k-множеств равно АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif, а число
k-подмножеств мы обозначили через CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif. Поэтому АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif= k!Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gif CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif. Так как     АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage480.gif,то мы получаем формулу, выражающую число k-подмножеств в m-множестве: CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage481.gif


Если множество А состоит из m элементов, то его подмножества, содержащие k элементов, называются сочетаниями без повторений из m элементов по k элементов. Их число подсчитывают по формуле:                                         


                                                  CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage481.gif


Пример. Сколькими способами можно выбрать делегацию в 5 человек из группы, содержащей 12 человек?    


Поскольку порядок членов делегации не играет роли, то нам надо узнать, сколько можно  выбрать пятиэлементных подмножеств из множества, содержащего 12 элементов. Число таких подмножеств СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage483.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage484.gif=792.  


Задача. В шахматном турнире принимают участие 12 человек. Сколько будет сыграно партий, если любые два участника встретятся между собой один раз?


Решение: Имеем множество, состоящее из 12 элементов. Так как нам нужно определить количество партий, т.е. подмножеств, куда входят 2 элемента, то речь идет о сочетании без повторений из 12 элементов по 2 элементам. Это можно подсчитать следующим образом: СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage485.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage486.gif=66.   Таким образом, будет сыграно 66 партий.


Задача. На шахматном турнире, проводившемся в один круг, любые два участника встречались между собой один раз. Была сыграна 91 партия. Сколько человек участвовало в турнире?


Решение:  Нам дано множество из  х  элементов. Известно, что каждая партия – это подмножество, которое состоит из 2-х элементов. Всего таких подмножеств – 91. Значит можно составить уравнение: СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage487.gif=91.


Решим данное уравнение:  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage487.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage488.gif=91;   Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage489.gif=91.   Сократим на (х – 2)!. Получим квадратное уравнение хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage457.gif– х=182, откуда х=14. Значит, в турнире участвовало 14 человек.


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


Если записывать порядок, в котором продавец кладет пирожные в коробку, то получится кортеж длины 7 из 4 элементов – сортов пирожных. Однако два кортежа одного и того же состава, например (н, н, э, п, с, с, э) и (э, н, с, н, э, п, с), означают одну и ту же покупку: 2 наполеона, 2 эклера, 2 слоеных, 1 песочное. Поэтому два способа сделать покупку надо считать различными лишь в случае, когда соответствующие кортежи отличаются своим составом.


Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage490.gifИтак, мы пришли к следующей задаче: сколько различных составов могут иметь кортежи длины k из m элементов? По-другому эту задачу можно сформулировать так: на сколько классов эквивалентности разбивается вся совокупность кортежей длины k из m элементов (назовем два кортежа эквивалентными, если они имеют одинаковый состав)? Такие классы эквивалентности называют сочетаниями с повторениями из m элементов по k, а их число обозначают СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif.


Сочетаниями с повторениями из m элементов по k вычисляют по следующей формуле.


                                           СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage492.gif


Вернемся к нашей задаче. В ней поставлен вопрос: сколько различных составов могут иметь кортежи длины 7, составленные из 4 элементов данного множества? По-другому эту задачу можно сформулировать и так: на сколько классов эквивалентности разбивается вся совокупность кортежей длины 7 из 4  элементов? В таком случае речь идет о сочетаниях с повторениями:  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif=CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage495.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage496.gif=120 (способов).


Рассмотрим свойства чисел СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif, которые выражают различные соотношения между подмножествами множества Х.


1. Если  0Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage022.gifkОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage022.gifm, то верно равенство СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage497.gif. Докажем данное равенство, используя формулу сочетаний без повторений:


CОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage497.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage498.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage499.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif.


2. Для любых k и m, таких, что 0Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage022.gifkОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage022.gifm, верно равенство СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage500.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage501.gif.


Это равенство нетрудно получить также с помощью формулы сочетаний без повторений:


СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage500.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage502.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage503.gif;


СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage501.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage504.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage505.gif;


СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage500.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage501.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage503.gif+Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage505.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage506.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage507.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif.


Отметим, что при k=0 получаем равенство СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage508.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage509.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage510.gif. Так как СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage508.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage510.gif=1, то следует положить СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage509.gif=0. Аналогично СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif при k>m. Тогда доказанное выше равенство (2) оказывается верным и при k = m.


Данная формула позволяет вычислить значения СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif, зная СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage501.gif и СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage500.gif. Иными словами, с помощью этого тождества можно последовательно вычислить СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage479.gif сначала при m=0, затем при m=1, при m=2 и т.д. Вычисления удобно записывать в виде треугольной таблицы, которая получила название арифметического треугольника (или треугольника Паскаля):


1


1       1


1     2    1


                                                    1    3    3    1


1    4    6    4    1


………………………….


При составлении арифметического треугольника каждое число n-й сроки участвует в образовании двух чисел (n + 1)-й строки – стоящего слева и стоящего справа от него. Поэтому если сложить числа (n + 1)-й строки через одно, то в полученную сумму войдут по одному разу все числа n-й строки. Складывать числа через одно можно двумя способами – начав с первого числа строки или начав со второго числа. В обоих случаях получится одна и та же сумма, равная сумме чисел в n-й строке.


Доказанное свойство арифметического треугольника можно записать так:


СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage508.gif + СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage511.gif +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage512.gif + … =  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage513.gif + СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage514.gif +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage515.gif + …= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage510.gif + СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage516.gif +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage517.gif + … +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage518.gif.


Из него следует, что сумма чисел (n + 1)-й строки вдвое больше суммы чисел n-й сроки. Иными словами, при переходе к следующей строке арифметического треугольника сумма чисел в строке удваивается. Но в первой строке стоит только одно число 1, а потому для этой строки сумма равна 1. Поэтому в (n + 1)-й сроке сумма чисел равна 2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage519.gif:


3. СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage508.gif + СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage513.gif +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage511.gif + … +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage465.gif = 2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage519.gif.


4.     СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage520.gif СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage521.gif = Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage522.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif. СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage520.gif.


5.     СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage465.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage523.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage524.gif= СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage525.gif.


6.     СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage465.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage523.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage524.gif+ СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage526.gif = СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage527.gif.


7.     СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage508.gif + СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage511.gif +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage512.gif + …  = 2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage528.gif.


8.   СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage513.gif + СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage514.gif +  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage515.gif + …  = 2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage528.gif.


Рассмотрим задачу. Пусть дано множество М={a, b, c, d}. Подсчитаем количество всевозможных подмножеств данного множества, состоящего из 4 элементов: одноэлементных подмножеств  будет  СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage529.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage530.gif=4;  двухэлементных будет СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage531.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage532.gif=6; трехэлементных – СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage533.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage534.gif=4; четырехэлементных соответственно СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage535.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage536.gif=1 и еще одно пустое множество Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage004.gif. Всего получилось 4+6+4+1+1=16 подмножеств, что соответствует  2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage462.gif=16.


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












 
 

 



            2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage519.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage508.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage513.gif+ … +СОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage465.gif


Просмотров 22 461 Комментариев 0
Познавательно:
Скажи свое мнение:
Добавить комментарий
Имя:* E-Mail:*

Вопрос:
1+1=
Ответ:*