Число сочетаний из n элементов по m элементам

Число различных m-элементных подмножеств множества, состоящего из п элементов, называют числом сочетаний длины т из п элементов и обозначают . Итак, = n!/(m!(n-m)!) - число различных m-элементных подмножеств множества, состоящего из п элементов.
Следствие. Пусть |Х| = п. Тогда число всех различных подмножеств множества X равно
Задача. В группе 25 человек. Сколько существует способов выбора из них делегации из трех человек для участия в профсоюзной конференции?
Решение. Ясно, что выбор делегации - это выбор 3-элементного подмножества из множества студентов группы. Поэтому число способов выбора равно = 25!/(3!∙22!)= 2300.
Задача. В кондитерской продаются пирожные пяти видов: бисквитные, корзиночки, песочные, эклеры, трубочки. Сколькими способами можно купить 12 пирожных?
Решение. Каждая покупка однозначно определяется набором неотрицательных чисел {x1, x2, x3, x4, x5}, где xi - число покупаемых пирожных i-ого вида. Тогда наша задача равносильна задаче о числе решений уравнения x1 + x2 + x3 + x4 + x5 = 12 при условии, что xi Z,xi > 0 для i {1,2,3,4,5}. Сделаем замену xi + 1 = ni. В результате получили задачу, равносильную первоначальной, о нахождении числа решений уравнения n1+n2 + n3 + n4 + n5 = 17,
где для любого i число ni N. Нарисуем прямую и отметим на ней 17 точек. Каждому решению нашего уравнения сопоставим картинку, состоящую из точек и черточек, которая строится следующим образом. Если ( , , , , ) - решение, то отсчитаем слева направо отмеченных точек и за последней из них поставим черту. Затем отсчитаем точек и за последней из них также поставим черту, и так далее. Договоримся последнюю черточку не рисовать. Например, решению (2, 1, 4, 6, 4) соответствует рисунок
• • | • | • • • • | • • • • • • | • • • •
Ясно, что соответствие между решениями и картинками - биективное. Но каждая картинка определяется выбором 4-х промежутков, где ставится черта, из имеющихся 16. В нашем примере по решению (2, 1, 4, 6, 4) мы выбрали 4-элементное подмножество промежутков {2, 3, 7, 13}. Число способов выбора 4-элементных подмножеств множества, состоящего из 16 элементов, равно = 16!/(4!∙12!) = 1820
Задачи, сводящиеся к нахождению числа решений уравнения x1 + x2 + . . . + xm = n, xi Z, xi ≥ 0Vi называют задачами на сочетания с повторениями длины п из т видов.
Теорема 1.30. Число сочетаний с повторениями длины п из т видов равно . При доказательстве используется та же схема, что и при решении предыдущей задачи.

Powered by Drupal - Design by artinet