Основные функции комбинаторики Понятие комбинаторной задачи.

Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем. Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716) - всемирно известный немецкий учёный, занимался философией, математикой, физикой, организовал Берлинскую академию наук и стал её первым президентом. В математике он вместе с И. Ньютоном разделяет честь создателя дифференциального и интегрального исчислений.

 В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний: , , ,

 - строит таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

 В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории.Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.

 В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

 В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. "Искусство предположений" появилось после смерти автора и не было автором завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:

для числа перестановок из n элементов,

для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениямими,

для числа размещений с повторениями и без повторений.

 

 Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные комбинаторные объекты относятся к основным комбинаторным конфигурациям . В математике в XIX веке появился сначала термин "геометрическая конфигурация" в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).

 В 1896 году американский математикЭлиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье "Tactical memoranda", понимая под этим термином систему n множеств, содержащих, соответственно, a1, a2, … , an элементов. Тактическую конфигурацию Мур задаёт квадратной матрицей порядка n, в которой элемент akk, стоящий на главной диагонали, равен числу ak (числу элементов в k-ом множестве); элемент aij (i j) равен числу элементов i-ого множества, инцидентных j -ому множеству. К тактическим конфигурациям Мур относит сочетания, размещения, системы решений задачи Киркмана о 15 школьницах, подгруппы некоторых групп. Он демонстрирует широкий спектр задач из геометрии, теории групп, которые приводят к тактическим разложениям или используют тактические разложения. Мур обогатил список известных комбинаторных конфигураций построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. Мур построил системы S[k, l, m], m k l ( m, k, l - натуральные числа), содержащие такие k -сочетания (блоки) из m элементов, что каждое l -сочетание входит точно в одно k -сочетание. Число k -сочетаний в системе S[k, l, m] равно . Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.

 Термин "тактика" ввёл в математику английский математикДжеймс Джозеф Сильвестр (1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел. Мысли Сильвестра о тактике разделял его друг Артур Кэли.

 Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования. В конце XVIII века учёные, принадлежащие комбинаторной школе Гинденбурга, попытались построить общую комбинаторную теорию, используя бесконечные ряды. Исследователи этой школы изучили большое количество преобразований рядов: умножение, деление, возведение в степень, извлечение корней, обращение рядов, разложение трансцендентных функций. Использование производящих функций в комбинаторике можно отнести к (уже) классическим традициям.

 В XX веке комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж.-К. Рота (1964), а затем Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач способствовали обогащению комбинаторных методов исследования и дальнейшей интеграции комбинаторики в современную математику.

Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов называется комбинаторикой.

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

 Этот раздел математики тесно связан с рядом других разделов дис­кретной математики: теорией вероятностей, теорией графов, теорией чисел, теорией групп и т. д.

Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования.

Сейчас комбинаторные методы применяются как в самой математике, так и вне её – теория кодирования, планирование эксперимента, топология, конечная алгебра, математическая логика, теория игр, кристаллография, биология, статистическая физика, экономика и т.д.

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

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

Но внедрение вероятностно-статистической линии в школьный курс столкнулось с некоторыми трудностями, в первую очередь, это методическая неподготовленность учителей и отсутствие единой методики и школьных учебников.

Современная концепция школьного математического образования ориентирована, прежде всего, на учет индивидуальности ребенка, его интересов и склонностей. Этим определяются критерии отбора содержания, разработка и внедрение новых, интерактивных методик преподавания, изменения в требованиях к математической подготовке ученика. И с этой точки зрения, когда речь идет не только об обучении математике, но и формировании личности с помощью математики, необходимость развития у всех школьников вероятностной интуиции и статистического мышления становится насущной задачей. Причем речь сегодня идет об изучении вероятностно-статистического материала в обязательном основном школьном курсе «математике для всех» в рамках самостоятельной содержательно-методической линии на протяжении всех лет обучения.

Согласно данным ученых-физиологов и психологов в среднем звене школы заметно падение интереса к процессу обучения в целом и к математике в частности. На уроке математики в основной школе, в пятых-девятых классах, проводимых по привычной схеме и на традиционном материале, у ученика зачастую создается ощущение непроницаемой стены между изучаемыми объектами и окружающим миром. Именно вероятностно-статистическая линия, изучение которой невозможно без опоры на процессы, наблюдаемые в окружающем мире, на реальный жизненный опыт ребенка, способна содействовать возвращению интереса к самому предмету «математика», пропаганде его значимости и универсальности.

Знакомство школьников с очень своеобразной областью математики, где между однозначными «да» и «нет» существует еще и «быть может» (причем это «может быть» поддается строгой количественной оценке), способствует устранению укоренившегося ощущения, что происходящее на уроке математики никак не связано с окружающим миром, с повседневной жизнью. Учащиеся видят непосредственную связь математики с окружающей действительностью, реальной жизнью.

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

Цель дипломной работы: на основе изучения школьной литературы и имеющегося материала, разработать элективный курс по «Основам комбинаторики и теории вероятностей» для старших классов физико-математического профиля.

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

· Необходимо определить содержание материала по каждому из направлений: комбинаторика, статистика, теория вероятностей.

· Проанализировать связи между этими направлениями и определить последовательность или параллельность их изучения.

· Определить содержание каждых из названных разделов. 

Для реализации данных задач используются следующие средства:

· Изучение школьных учебников и методической литературы по данной теме.

· Изучение стандартов образования по данной теме.

· Анализ школьной литературы.

Дипломная работа состоит из двух частей, это как теоретическая часть, так и

методические разработки элективного курса.

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

Во второй главе представлен анализ изложения данной темы в школьных учебниках и дополнительной школьной литературе, а так же поурочное планирование на два полугодия для 10 – 11 класса физико-математического профиля (32 часов) с разработанными конспектами к теме данного диплома – «Комбинаторика».

Глава 1. Теоретическая часть

1.1. Историческая справка

 

Разрозненные комбинаторные задачи человечество решало с незапамятных времён. К концу XVI века накопились знания, относящиеся к:

1. свойствам фигурных чисел,

2. построению магических (и иных числовых) квадратов,

3. свойствам биномиальных коэффициентов.

Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем.Готфрид Вильгельм Лейбниц(1.07.1646 - 14.11.1716) - всемирно известный немецкий учёный, занимался философией, математикой,    физикой, организовал Берлинскую академию наук и стал её первым президентом. В математике он вместе с И. Ньютоном разделяет честь создателя дифференциального и интегрального исчислений. В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов, выводит свойства сочетаний:

                                          ,                                     

                                            ,                                     

                                                 ,                                        

- строит таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории. Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. "Искусство предположений" появилось после смерти автора и не было автором завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:

· для числа перестановок из n элементов,

· для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениями,

· для числа размещений с повторениями и без повторений.

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные комбинаторные объекты относятся к основным комбинаторным конфигурациям. В математике в XIX веке появился сначала термин "геометрическая конфигурация" в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).

Термин "тактика" ввёл в математику английский математик Джеймс Джозеф Сильвестр(1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел. Мысли Сильвестра о тактике разделял его друг Артур Кэли.

В 1896 году американский математик
Элиаким Гастингс Мур (1862-1932) ввёл              термин тактическая конфигурация в статье  "Tactical memoranda", понимая под этим термином систему nмножеств, содержащих, соответственно, a₁, a₂, … , a_n элементов. Тактическую конфигурацию Мур задаёт квадратной матрицей порядка n, в которой элемент a_kk, стоящий на главной диагонали, равен числу a_k (числу элементов в k-ом множестве); элемент a_ij (i j) равен числу элементов i-ого множества, инцидентных j -ому множеству. К тактическим конфигурациям Мур относит сочетания, размещения, системы решений задачи Киркмана о 15 школьницах, подгруппы некоторых групп. Он демонстрирует широкий спектр задач из геометрии, теории групп, которые приводят к тактическим разложениям или используют тактические разложения. Мур обогатил список известных комбинаторных конфигураций построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. Мур построил системы  S[k, l, m], m k l ( m, k, l - натуральные числа), содержащие такие k -сочетания (блоки) из m элементов, что каждое l -сочетание входит точно в одно k -сочетание. Число k -сочетаний в системеS[k, l, m]равно . Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.

Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования. В конце XVIII века учёные, принадлежащие комбинаторной школе Гинденбурга, попытались построить общую комбинаторную теорию, используя бесконечные ряды. Исследователи этой школы изучили большое количество преобразований рядов: умножение, деление, возведение в степень, извлечение корней, обращение рядов, разложение трансцендентных функций. Использование производящих функций в комбинаторике можно отнести к (уже) классическим традициям.

В XX веке комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж.-К. Рота (1964), а затем Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач способствовали обогащению комбинаторных методов исследования и дальнейшей интеграции комбинаторики в современную математику.

Предмет комбинаторики

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

В Математическом Энциклопедическом Словаре говорится, что комбинаторика - один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике.

В Большой Советской Энциклопедии говорится, что комбинаторика - это раздел математики в котором изучаются некоторые операции над конечными множествами.

 Основные понятия и теоремы комбинаторики

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

 Основные правила комбинаторики

При вычислении количества различных комбинаций используются правила сложения и умножения. Сложение используется, когда множе­ства не совместны. Умножение - когда для каждой комбинации перво­го множества имеются все комбинации (или одинаковое число комби­наций) второго множества.

Пример. Из 28 костей домино берутся 2 кости. В каком числе комбинаций вторая кость будет приложима к первой?

На первом шаге имеется два варианта: выбрать дубль (7 комбина­ций) или не дубль (21 комбинация). В первом случае имеется 6 вариан­тов продолжения, во втором - 12.

Общее число благоприятных комбинаций равно: .

А всего вариантов выбора 2 костей из 28 равно 378; т. е. при боль­шом числе экспериментов в 7 случаях из 9 (294/378 = 7/9) при выборе 2 костей одна кость окажется приложимой к другой.

 Размещения с повторениями

Размещение с повторением также в комбинаторике называется кортежем.

Рассмотрим задачу: сколько разных числовых последовательностей, длины 5, можно со­ставить из 10 цифр?

Перенумеруем разряды:

1

2

3

4

5

В первый разряд можно поставить одну из 10 цифр. Независимо от того, какая цифра поставлена, во второй разряд можно также поставить одну из 10 цифр и т. д. Всего получается 10⁵ различных чисел.

Для двоичной системы счисления (используются только две цифры: 0 или 1) получаем 2⁵ различных числовых последовательностей. Для системы с основанием к и числом разрядов п соответственно получаем:

                                                                                                                    (1)

n -число позиций (разрядов); k-число элементов в каждой позиции (цифр).

В общем виде задача ставится следующим образом: имеется k ти­пов предметов (количество предметов каждого типа неограниченно) и п позиций (ящиков, кучек, разрядов). Требуется определить, сколько раз­ных комбинаций можно составить, если в позициях предметы могут повторяться? Ответ дается формулой (1).

Пример. Сколько разных числовых последовательностей может содержать 10-разрядное слово в троичной системе счисления? В первый разряд можно поста­вить один из трех символов (0, 1 или 2), во второй разряд - также один из трех символов и т. д. Всего получаем З¹⁰ чисел.

В некоторых случаях имеются ограничения на количество разных предметов, которые можно помещать на позиции. Пусть, например, имеется п позиций и на каждую i-ю позицию можно поставить k _i пред­метов. Сколько в этом случае существует разных расстановок предме­тов по позициям?

Легко обосновывается формула:

                                                                                  (2)

Пример. В эстафете 100+200+400+800 метров на первую пози­цию тренер может выставить одного из 3 бегунов, на вторую - одного из 5, на третью - одного из 6, на четвертую - единственного бегуна (на каждую позицию выставляются разные бегуны). Сколько вариантов рас­становки участников эстафетного забега может составить тренер?

В соответствии с формулой (2) получаем, что число вариантов рав­но: .

 Размещения без повторений

Рассмотрим задачу: Сколько разных числовых последовательностей, длины 5, можно за­писать с помощью десяти цифр при условии, что в числовых последовательностях не использу­ются одинаковые цифры?

Перенумеруем разряды:

1

2

3

4

5

В первый разряд можно поставить одну из 10 цифр (0,1,2,3,4,5,6,7,8,9). Независимо от того, какая цифра помещена в первый разряд, во втором можно поставить только одну из 9 цифр, в третий - одну из 8 цифр и т. д. Всего существует  различных числовых последовательностей, в каждой из которых нет двух одинаковых цифр.

В общем случае, если имеется k позиций и п разных предметов, при­чем каждый представлен в единственном экземпляре, то количество разных расстановок:

                                                              ( 3)

В формуле (3) s  означает факториал числа s , т. е. произведение всех чисел от 1 до s . Таким образом, s = s .

Пример 1. Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга. Сколько вариантов выбора руко­водящего состава группы? Старосту выбрать можно одним из 25 способов. Поскольку выбранный староста не может быть своим за­местителем, то для выбора заместителя старосты остается 24 ва­рианта. Профорга выбирают одним из 23 способов. Всего вариан­тов: .

Пример 2. На дискотеку пришло 12 девушек и 15 юношей. Объявлен "бе­лый" танец. Все девушки выбрали для танцев юношей (и никто из них не отказался). Сколько могло образоваться танцующих пар?

Таким образом, размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений .

 Перестановки без повторений

В предыдущих параграфах комбинации отличались как составом предметов, так и их порядком. Однако если в последней задаче юношей было бы тоже 12, то все комбинации отличались бы только порядком. Рассмотрим, сколько различных комбинаций можно получить, перестав­ляя п предметов.

Положим в (3) , тогда получим

                                                                                                           (4)

Пример. К кассе кинотеатра подходит 6 человек. Сколько суще­ствует различных вариантов установки их в очередь друг за другом? Расставим 6 человек произвольным образом и начнем их переставлять всеми возможными способами. Число полученных перестановок в со­ответствии с формулой (4) будет равно 6! = 720.

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

P_n = n!,

где .

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

 Перестановки с повторениями

Иногда требуется переставлять предметы, некоторые из которых неотличимы друг от друга. Рассмотрим такой вариант перестано­вок, который называется перестановками с повторениями.

Пусть имеется п₁ предметов 1-го типа, n ₂ предмета 2-го, п_к пред­метов -го типа и при этом п₁+ п₂+...+ п_к = п. Количество разных перестановок предметов

                                                          (5)

Для обоснования (5) сначала будем переставлять п предметов в предположении, что они все различны. Число таких перестановок равно п! Затем заметим, что в любой выбранной расстановке пере­становка n ₁   одинаковых предметов не меняет комбинации, анало­гично перестановка n ₂ одинаковых предметов также не меняет ком­бинации и т. д. Поэтому получаем выражение (5).

Пример. Найдем количество перестановок букв слова КОМ­БИНАТОРИКА. В этом слове 2 буквы «к», 2 буквы «о», 1 буква «м», 1 буква «б», 2 буквы «и», 1 буква «н», 2 буквы «а», 1 буква «т» и 1 буква «р».

Таким образом, число перестановок букв этого слова равно:

Р(2, 2, 1, 1, 2, 1, 2, 1, 1) = 13!/(2! 2! 2! 2!)= 13!/16.

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

Если требуется выбрать к предметов из п,и при этом порядок выби­раемых предметов безразличен, то имеем

.                                                                                                       (6)

 Сочетаниями называют комбинации, составленные из n различных элементов по k элементов, которые отличаются хотя бы одним элементом.

Формула (6) может быть получена следующим образом. Выберем по очереди к предметов из п. Число вариантов будет равно . В этих расстановках к выбранных предмета имеют свои определенные позиции. Однако нас не интересуют в данном случае позиции выбран­ных предметов. От перестановки этих предметов интересующий нас вы­бор не меняется. Поэтому полученное выражение нужно разделить на

Пример 1. Из группы в 25 человек нужно выбрать троих для рабо­ты в колхозе. Если выбирать их последовательно, сначала первого, по­том второго, потом третьего, то получим  варианта. Но так как нас не интересует порядок выбора, а только состав выбранной бри­гады, поэтому полученный результат нужно разделить еще на 3!

Пример 2. В середине 60-х годов в России появились две лоте­реи, которые были названы "Спортлото": лотерея 5/36 и 6/49. Рассмотрим одну из них, например, 6/49. Играющий покупает билет, на котором имеется 49 клеточек. Каждая клеточка соответ­ствует какому-либо виду спорта. Нужно выделить (зачеркнуть) 6 из этих клеточек и отправить организаторам лотереи. После розыгрыша лоте­реи объявляются шесть выигравших номеров. Награждается угадав­ший все шесть номеров, пять номеров, четыре номера и даже угадав­ший три номера. Соответственно, чем меньше угадано номеров (видов спорта), тем меньше выигрыш.

Подсчитаем, сколько существует разных способов заполнения кар­точек "Спортлото" при условии, что используется лотерея 6/49. Ка­залось бы, заполняя последовательно номер за номером, получим: . Но ведь порядок заполнения не имеет значения, тогда получаем:

     Эту же задачу можно решить и другим способом. Выпишем все но­мера подряд и под выбираемыми номерами поставим 1, а под осталь­ными - 0. Тогда различные варианты заполнения карточек будут отли­чаться перестановками. При этом переставляются 6 предметов одного вида (единицы) и 49 - 6 = 43 предмета другого вида (нули), т. е. опять

       Если все участники заполняют карточки по-разному, то в среднем один из примерно 14 миллионов угадает все 6 номеров. А сколько чело­век в среднем угадают 5 номеров?

Выберем один из угаданных номеров ( ) и заменим его на один

из не угаданных ( ). Итого:  человек из 14 миллионов

угадают 5 номеров. А сколько угадают 4 номера? Выберем из 6 уга­данных два и затем из 43 не угаданных тоже два и перемножим число вариантов выбора. Тогда получим:  человек.

Аналогично найдем, что 3 номера угадают 246820 человек, т. е. при­мерно 1,77% от всех играющих.

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

Пример. Требуется купить 7 пирожных. В магазине имеются пирожные следующих видов: эклеры, песочные, слоеные и наполеоны. Сколько вариантов выбора? Решение: выбранные пирожные заменяем единицами, и добавляем три нуля (разделителя). Каждой перестановке однозначно соответствует некоторый выбор. Например, одному из ва­риантов покупки будет соответствовать такой код: 1101110101. Пиро­жные покупаются следующим образом. Количество единиц слева до первого нуля соответствует покупке эклеров, между первым и вторым нулем - покупке песочных, между вторым и третьим - покупке слое­ных, единицы после третьего нуля соответствуют числу покупаемых наполеонов. В случае приведенного кода покупается 2 эклера, 3 песоч­ных, 1 слоеное и 1 наполеон. Количество вариантов покупки пирожных равно числу перестановок из 7 объектов одного типа (единиц) и 3 объек­тов второго типа (нулей).

Пусть имеются предметы п разных типов (без ограничения числа предметов каждого типа) и требуется определить, сколько комбинаций можно сделать из них, чтобы в каждую комбинацию входило к предме­тов. Каждую комбинацию шифруем с помощью 0 и 1, причем 1 соот­ветствуют предметам, а 0 выполняют функцию разделителей. Тогда записав к единиц и добавив п - 1 нуль, мы получим комбинацию, при которой выбираются к предметов первого типа и ни одного предмета остальных типов. Переставляя всеми способами эти к единиц и п - 1 нуль, мы будем каждый раз получать некоторую расстановку, состоя­щую из к предметов. Тогда

                                                                           (7)

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

Приведем некоторые свойства чисел сочетаний, которые часто ис­пользуются при преобразованиях формул комбинаторики.

1. .

2. .

3. .

Первое свойство совершенно очевидно. Давайте проверим:

               

.

Второе легко доказывается, если оба члена правой части представить по формуле (6).

Третье свой­ство можно доказать методом математической индукции. Для приме­ра, при п = 2 имеем:

.

 Для п = 3 получаем:

.

Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством

.

 Основные комбинаторные задачи

Главная теорема комбинаторики (Теорема о включениях и исключениях)

Пример. На предприятии работает 67 человек. Из них 48 знают английский, 35 - немецкий и 27 - оба языка. Сколько человек не знают ни английского, ни немецкого?

Результат можно получить следующим образом. Построим диаграм­му, на которой изобразим прямоугольник, соответствующий общему числу работающих (67) и две пересекающиеся области А и В по 48 и 35 человек (знающих английский и немецкий языки). На диаграмме об­щая часть этих двух областей соответствует 27 - количеству работаю­щих, которые знают оба