Комбинаторика




                              Реферат на тему:



                                       Выполнил ученик 10 класса «В»
                                       средней школы №53
                                       Глухов Михаил Александрович



                             г. Набережные Челны
                                   2002 г.
                                 Содержание
|Из истории                                                   |3    |
|комбинаторики_________________________________________       |     |
|Правило                                                      |4    |
|суммы___________________________________________________     |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Правило                                                      |4    |
|произведения_____________________________________________    |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Пересекающиеся                                               |5    |
|множества________________________________________            |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Круги                                                        |-    |
|Эйлера_____________________________________________________  |     |
|Размещения без                                               |6    |
|повторений________________________________________           |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Перестановки без                                             |7    |
|повторений_______________________________________            |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Сочетания без                                                |8    |
|повторений__________________________________________         |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Размещения и сочетания без                                   |9    |
|повторений______________________________                     |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Перестановки с                                               |9    |
|повторениями_______________________________________          |     |
|Примеры                                                      |-    |
|задач____________________________________________________    |     |
|Задачи для самостоятельного                                  |10   |
|решения________________________________                      |     |
|Список используемой                                          |11   |
|литературы___________________________________                |     |


                          Из истории комбинаторики
       Комбинаторика занимается различного вида соединениями, которые можно
  образовать из элементов конечного множества. Некоторые элементы
  комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели
  вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара
  вычислял некоторые виды сочетаний и перестановок. Предполагают, что
  индийские ученые изучали соединения в связи с применением их в поэтике,
  науке о структуре стиха и поэтических произведениях. Например, в связи с
  подсчетом возможных сочетаний ударных (долгих) и безударных (кратких)
  слогов стопы из n слогов. Как научная дисциплина, комбинаторика
  сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.)
  французский автор А. Также посвящает сочетаниям и перестановкам целую
  главу.

  Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о
  числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах.
  П. Ферма знал о связях математических квадратов и фигурных чисел с
  теорией соединений. Термин "комбинаторика" стал употребляться после
  опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном
  искусстве", в которой впервые дано научное обоснование теории сочетаний и
  перестановок. Изучением размещений впервые занимался Я. Бернулли во
  второй части своей книги "Ars conjectandi" (искусство предугадывания) в
  1713 г. Современная символика сочетаний была предложена разными авторами
  учебных руководств только в XIX в.
       Все разнообразие комбинаторных формул может  быть  выведено  из  двух
  основных утверждений, касающихся конечных  множеств  –  правило  суммы  и
  правило произведения.

                                Правило суммы

       Если конечные множества не пересекаются, то число  элементов  X  U  Y
  {или} равно сумме числа элементов множества X и числа элементов множества
  Y.
       То есть, если на первой полке стоит X книг, а на второй Y, то выбрать
  книгу из первой или второй полки, можно X+Y способами.


       Примеры задач


       Ученик  должен  выполнить  практическую  работу  по  математике.  Ему
  предложили на выбор 17 тем по алгебре и 13 тем  по  геометрии.  Сколькими
  способами он может выбрать одну тему для практической работы?

       Решение: X=17, Y=13
       По правилу суммы X U Y=17+13=30 тем.

       Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото  и  10
  билетов автомотолотереи. Сколькими способами можно выбрать один билет  из
  спортлото или автомотолотереи?

       Решение: Так как денежно-вещевая лотерея в выборе  не  участвует,  то
  всего 6+10=16 вариантов.

       Правило произведения


       Если элемент X можно выбрать k способами, а элемент Y-m способами  то
  пару (X,Y) можно выбрать k*m способами.
       То есть, если на первой полке стоит  5  книг,  а  на  второй  10,  то
  выбрать одну книгу  с  первой  полки  и  одну  со  второй  можно  5*10=50
  способами.


       Примеры задач



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

       Решение: Имеется 12 книг и 3 цвета, значит  по  правилу  произведения
  возможно 12*3=36 вариантов переплета.
       Сколько существует  пятизначных  чисел,  которые  одинаково  читаются
  слева направо и справа налево?
       Решение: В таких числах последняя цифра будет такая же, как и первая,
  а предпоследняя - как и вторая.  Третья  цифра  будет  любой.  Это  можно
  представить в виде XYZYX, где Y и Z -любые цифры, а X - не  ноль.  Значит
  по правилу произведения количество цифр одинаково  читающихся  как  слева
  направо, так и справа налево равно 9*10*10=900 вариантов.
  Пересекающиеся множества

       Но бывает,  что  множества  X  и  Y  пересекаются,  тогда  пользуются
  формулой[pic], где X и Y - множества, а [pic] - область пересечения.

       Примеры задач

       20 человек знают английский и  10  -  немецкий,  из  них  5  знают  и
  английский, и немецкий. Сколько Человек всего?
       Ответ: 10+20-5=25 человек.
       Также часто для наглядного решения задачи применяются  круги  Эйлера.
  Например:
       Из 100 туристов, отправляющихся в заграничное  путешествие,  немецким
  языком владеют 30 человек, английским - 28, французским - 42.  Английским
  и немецким одновременно владеют 8 человек, английским и французским - 10,
  немецким и французским - 5, всеми тремя языками - 3. Сколько туристов  не
  владеют ни одним языком?
        Решение: Выразим условие этой задачи  графически.  Обозначим  кругом
  тех, кто знает английский, другим кругом - тех, кто знает французский,  и
  третьим кругом - тех, кто знают немецкий.
       Всеми тремя языками владеют три туриста, значит, в общей части кругов
  вписываем число 3. Английским и французским языком владеют 10 человек,  а
  3 из них владеют еще  и  немецким.  Следовательно,  только  английским  и
  французским владеют 10-3=7 человек.
       Аналогично получаем, что только английским и немецким  владеют  8-3=5
  человек, а немецким и французским 5-3=2  туриста.  Вносим  эти  данные  в
  соответствующие части.
       Определим  теперь,  сколько   человек   владеют   только   одним   из
  перечисленных языков. Немецкий знают  30  человек,  но  5+3+2=10  из  них
  владеют и  другими  языками,  следовательно,  только  немецкий  знают  20
  человек. Аналогично получаем, что одним английским владеют 13 человек,  а
  одним французским - 30 человек.
       По условию задачи всего 100  туристов.  20+13+30+5+7+2+3=80  туристов
  знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из
  данных языков.


                         Размещения без повторений.
       Сколько можно составить телефонных номеров из 6 цифр каждый, так
  чтобы все цифры были различны?
       Это пример задачи на размещение без повторений. Размещаются здесь 10
  цифр по 6. А варианты, при которых одинаковые цифры стоят в разном
  порядке считаются разными.
       Если X-множество, состоящие из n элементов, m?n, то размещением без
  повторений из n элементов множества X по m называется упорядоченное
  множество X, содержащее m элементов называется упорядоченное множество X,
  содержащее m элементов.

  Количество всех размещений из n элементов по m обозначают
  [pic]
  n! - n-факториал (factorial анг. сомножитель) произведение чисел
  натурального ряда от 1 до какого либо числа n
  n!=1*2*3*...*n 0!=1
  Значит, ответ на вышепоставленную задачу будет
  [pic]
  Задача
  Сколькими способами 4 юноши могут пригласить четырех из шести девушек на
  танец?
  Решение: два юноши не могут одновременно пригласить одну и ту же девушку.
  И варианты, при которых одни и те же девушки танцуют с разными юношами
  считаются, разными, поэтому:
  [pic]
  Возможно 360 вариантов.
                         Перестановки без повторений
       В случае n=m (см. размещения без повторений) из n элементов по m
  называется перестановкой множества x.
       Количество всех перестановок из n элементов обозначают Pn.
       Pn=n!
       Действительно при n=m:
       [pic]
                                Примеры задач
       Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2,
  3, 4,5, если цифры в числе не повторяются?
       Решение:
1) Найдем количество всех перестановок из этих цифр: P6=6!=720
2) 0 не может стоять  впереди  числа,  поэтому  от  этого  числа  необходимо
  отнять количество перестановок,  при  котором  0  стоит  впереди.  А  это
  P5=5!=120.
       P6-P5=720-120=600

                                   Квартет
                             Проказница Мартышка
                                    Осел,
                                   Козел,
                             Да косолапый Мишка
                           Затеяли играть квартет
                                      …
                            Стой, братцы стой! –
                        Кричит Мартышка, - погодите!
                              Как музыке идти?
                           Ведь вы не так сидите…
       И так, и этак пересаживались – опять музыка на лад не идет.
                    Тут пуще прежнего пошли у низ раздоры
                                  И споры,
                             Кому и как сидеть…
       Вероятно, крыловские музыканты так и не перепробовали всех  возможных
  мест. Однако способов не так уж и много. Сколько?

       Здесь идет перестановка из четырех, значит, возможно
       P4=4!=24 варианта перестановок.
                          Сочетания без повторений
       Сочетанием без повторений называется такое  размещение,  при  котором
  порядок следования элементов не имеет значения.
       Всякое подмножество X состоящее из m элементов, называется сочетанием
  из n элементов по m.
       Таким  образом,  количество  вариантов  при  сочетании  будет  меньше
  количества размещений.
       Число сочетаний из n элементов по m обозначается [pic].
       [pic].

                                Примеры задач

       Сколько трехкнопочных комбинаций существует на кодовом замке (все три
  кнопки нажимаются одновременно), если на нем всего 10 цифр.
       Решение:
       Так как кнопки нажимаются одновременно, то выбор этих трех  кнопок  –
  сочетание. Отсюда возможно [pic]вариантов.
       У одного человека 7 книг по математике, а у второго  –  9.  Сколькими
  способами они могут обменять друг у друга две книги на две книги.
       Решение:
       Так как надо  порядок следования книг не имеет значения, то выбор 2ух
  книг -  сочетание.  Первый  человек  может  выбрать  2  книги  [pic][pic]
  способами. Второй человек может выбрать 2 книги [pic].  Значит  всего  по
  правилу произведения возможно 21*36=756 вариантов.
       При игре в  домино  4  игрока  делят  поровну  28  костей.  Сколькими
  способами они могут это сделать?
       Первый игрок делает выбор из 28 костей.  Второй  из  28-7=21  костей,
  третий 14, а четвертый игрок забирает  оставшиеся  кости.  Следовательно,
  возможно [pic].
  Размещения и сочетания с повторениями
       Часто в задачах по комбинаторике  встречаются  множества,  в  которых
  какие-либо компоненты повторяются. Например: в задачах на числа –  цифры.
  Для таких  задач  при  размещениях  используется  формула  [pic],  а  для
  сочетаний [pic].
                                Примеры задач
       Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?
       Решение. Так как  порядок  цифр  в  числе  существенен,  цифры  могут
  повторяться, то это будут размещения с повторениями из пяти элементов  по
  три, а их число равно [pic].

       В кондитерском  магазине  продавались  4  сорта  пироженных:  эклеры,
  песочные,  наполеоны  и  слоеные.  Сколькими  способами  можно  купить  7
  пироженных.
       Решение: Покупка не зависит  от  того,  в  каком  порядке  укладывают
  купленные пироженные  в  коробку.  Покупки  будут  различными,  если  они
  отличаются  количеством  купленных  пирожных  хотя   бы   одного   сорта.
  Следовательно, количество различных покупок равно числу сочетаний четырех
  видов пироженных по семь - [pic].
       Обезьяну посадили за пишущую машинку с 45 клавишами, определить число
  попыток, необходимых для того,  чтобы  она  наверняка  напечатала  первую
  строку романа Л.Н. Толстого «Анна  Каренина»,  если  строка  содержит  52
  знака и повторений не будет?
       Решение:  порядок  букв  имеет  значение.  Буквы  могут  повторяться.
  Значит, всего есть [pic] вариантов.

                         Перестановки с повторениями
       [pic][pic], где n-количество  всех  элементов,  n1,n2,…,nr-количество
  одинаковых элементов.

                                Примеры задач
       Сколькими способами можно переставить буквы слова «ананас»?
       Решение: всего букв 6. Из них одинаковы  n1«а»=3,  n2«н»=2,  n3«с»=1.
  Следовательно, число различных перестановок равно [pic].

                     Задачи для самостоятельного решения

        Сколько перестановок можно сделать из букв слова «Миссисипи».
                                                                 Ответ: 2520
          Имеется пять различных стульев и семь рулонов обивочной ткани
   различных цветов. Сколькими способами можно осуществить обивку стульев.
                                                                Ответ: 16807
        На памятные сувениры в «Поле Чудес» спонсоры  предлагают  кофеварки,
   утюги, телефонные аппараты, духи. Сколькими способами 9 участников  игры
   могут получить эти сувениры? Сколькими способами могут  быть  выбраны  9
   предметов для участников игры?
                                                              Ответ: 49, 220
        Сколькими способами можно расставить на шахматной доске 8 ладей так,
   чтобы на одна из них не могла бить другую?
                                                                Ответ: 40320
        Сколько может быть случая выбора 2 карандашей  и  3  ручек  из  пяти
   различных карандашей и шести различных ручек?
                                                                   Ответ:200
        Сколько способов раздачи  карт  на  4  человека  существует  в  игре
            «Верю - не верю» (карты раздаются полностью, 36 карт).
                                                               Ответ: [pic].
        В течении 30 дней сентября было 12 дождливых  дней,  8  ветреных,  4
   холодных, 5 дождливых и ветреных, 3 дождливых и холодных,  а  один  день
   был и дождливым, и ветреным, и  холодным.  В  течение  скольких  дней  в
   сентябре стояла хорошая погода.
                                                                   Ответ: 15
        На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать
   одну овцу  и  одну  свинью?  Если  такой  выбор  уже  сделан,  сколькими
   способами можно сделать его еще раз?
                                                             Ответ: 480, 437
        Сколькими способами можно выбрать гласную и согласную буквы из слова
   «здание»?
                                                                    Ответ: 9
        Сколько существует четных пятизначных чисел,  начинающихся  нечетной
   цифрой?
                                                                Ответ: 25000
        В книжный магазин  поступили романы Ф. Купера «Прерия»,  «Зверобой»,
   «Шпион», «Пионеры», «Следопыт» по одинаковой цене.  Сколькими  способами
   библиотека может закупить 17 книг на выбранный чек?
                                Ответ:: 2985
                       Список используемой литературы
        Савина Л.Н., Попырев А.В.  «КОМБИНАТОРИКА»  издательство  Елабужский
   государственный педагогический институт 1999г
        Халамайзер А. Я. «Математика? – Забавно!» издание автора 1989г
                                  Интернет
        ссылка на сайт удаленаcontact:\www.mathclub.zala.ru/0921.phpl
-----------------------
Если множеств больше, например 5 языков, то  также  складывается  количество
человек  знающих  английский,  немецкий,  французский  и  т.д.,   отнимается
количество  человек,  знающих  2  языка  одновременно,  прибавляется  по  3,
отнимаются по 4 и т.д.