Рефераты → Математика → Из → Изучение основ комбинаторики и теории вероятностей

Изучение основ комбинаторики и теории вероятностей

Содержание


Введение...........................................................................................................................4


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


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


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


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


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


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


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


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


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


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


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


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


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

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


1.4.2. Частный случай теоремы о включениях и исключениях...........................23


1.4.3. Комбинаторные задачи с ограничениями.....................................................24


1.4.4. Задачи о смещениях (о беспорядках).......................................................25


1.4.5. Задача о караване.......................................................................................25


1.4.6.Комбинаторика разбиений.............................................................................26


1.4.7. Количество делителей числа N
..................................................................27


1.4.8. Раскладка предметов в несколько ящиков....................................................30


1.4.9. Задача: Флаги на мачтах..................................................................................31


1.4.10. Задача: Покупка билетов.............................................................................31


1.4.11. Рекуррентные соотношения в комбинаторике........................................32


1.5. Связь комбинаторики с другими разделами математики....................................34


1.5.1. Теория групп.......................................................................................................34


1.5.2. Теория вероятностей.....................................................................................35


1.5.3. Криптография..................................................................................................37


1.5.4. Экономика.........................................................................................................38


1.5.5. Теория информации...........................................................................................39


1.5.6. Теория графов.................................................................................................40


Глава 2. Методические разработки для элективного курса...................41


2.1. Анализ изложения темы в школьных учебниках............................41


2.2. Тематическое планирование..........................................................51


2.2.1. Введение.......................................................................................................51


2.2.2. Содержание программы спецкурса...........................................................55


2.2.3. Поурочное планирование...........................................................................56


2.3. Разработки занятий........................................................................58


2.4. Электронный учебник....................................................................93


Заключение..........................................................................................96


Список использованной литературы.....................................................97


Введение


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


Комбинаторика возникла в 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
множеств, содержащих, соответственно, 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
]равно . Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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








1 2 3 4 5

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


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



(1)


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


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


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


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


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


(2)


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


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


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


Рассмотрим задачу: Сколько разных числовых последовательностей, длины 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 элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений.


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


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


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


(4)


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


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


Pn
= n!,


где .


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


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


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


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


(5)


Для обоснования (5) сначала будем переставлять п
предметов в предположении, что они все различны. Число таких перестановок равно п!
Затем заметим, что в любой выбранной расстановке пере­становка n
1
одинаковых предметов не меняет комбинации, анало­гично перестановка n
2
одинаковых предметов также не меняет ком­бинации и т. д. Поэтому получаем выражение (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.


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


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


.(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% от всех играющих.


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


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


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


(7)


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


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


1. .


2. .


3. .


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



.


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


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


.


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


.


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


.


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


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


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


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


67


A=48 AB=27 B=35


Очевидно, что N =
67 - 48 - 35 + 27 = 11.


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


Пусть имеется множество из N
объектов произвольной природы. На этом множестве пусть задано п
свойств. Каждый объект может обла­дать либо не обладать некоторыми из этих свойств. Сами свойства обо­значим:.
Будем обозначать N() - количество объек­тов точно обладающих свойством и может быть какими-то другими, а N () - число объектов не обладающих ни свойством , ни свойством . Тогда число объектов, не обладающих ни одним из пере­численных свойств:



(8)


Продолжение примера. Пусть теперь 20 человек знают французс­кий, 12 - английский и французский, 11 - английский и немецкий и 5 - все три языка.


Тогда в соответствии с теоремой количество человек, не знающих ни одного из трех перечисленных языков (но может быть знающих ки­тайский язык), равно N
=
67 - 48 - 35 - 20 + 27 +12+11-5 = 9.


Решето Эратосфена


Выпишем все числа от 1 до N.
Сколько чисел делится на k
?Очевид­но, [N
/
k
],где [х
] обозначает целую часть числа х.
Тогда, легко подсчи­тать количество чисел, не делящихся в данном диапазоне на k
1
k
2
,
k
3
...


Пример. Сколько чисел от 1до 100 не делятся ни на 5, ни на 7?


Воспользуемся теоремой о включениях и исключениях. Под первым свойством чисел будем понимать делимость на 5, под вторым – делимость на 7. На 5 делятся 20 чисел. На 7 делятся 14 чисел. На 35 делятся 2 числа. Следовательно, не делятся на 5 и 7: 100 - 20 - 14 + 2 = 68 чисел.


1.4.2. Частный случай теоремы о включениях и исключениях


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


При произвольном п
имеем:



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


(9)


Полученное значение Dn
иногда называют формулой полного беспо­рядка или субфакториалом. Субфакториал Dn
можно представить и так:


.


где выражение в [...] стремится к е -1
при неограниченном возраста­нии.


Субфакториал имеет свойства, похожие на свойства обычного фак­ториала. Например,


- для обычного факториала,


-
для субфакториала.


Субфакториалы легко вычисляются по формуле


. Приведем некоторые начальные значения субфакториалов:
























п
1 2 3 4 5 6 7 8 9

Dn


п


0 1 2 9 44 255 1784 14273 128456

1.4.3. Комбинаторные задачи с ограничениями


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


а) Задача о львах и тиграх.
Имеется 5 львов и 4 тигра. Необходимо их расставить в ряд, но при этом известно, что тигр не может идти спокойно за тигром. Тогда расставляем львов с промежутками ( их бу­дет 6) и в них вставляем тигров. Таким образом, если тигры и львы обезличенные, то = 15. В общем случае при п
львах и к
тиграх имеем:


б)Задача о книжной полке.
Из n
книг, стоящих на полке, нужновыбрать к
таких, которые не стояли рядом на книжной полке. Отберем сразу к
книг, останется п-к.
Их расставим с промежутками (п-к+1
про­межуток). На эти места вставим к
книг. Общее решение:


(10)


в)Рыцари короля Артура.
12 рыцарей сидят за круглым столом. Нужно выбрать 5 из них, но таких, которые не сидели рядом за столом. Множество всех решений разбиваем на два подмножества в зависимо­сти от того, входит ли в команду избранных конкретный рыцарь илинет? Ответ: 15+21=36. Если за круглым столом сидит п
рыцарей, а нужно выбрать к,
которые не сидели рядом, то задача решается анало­гично и имеет смысл при п > 2к.


1.4.4. Задачи о смещениях (о беспорядках)


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


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


1.4.5. Задача о караване


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


Выделим запрещенные пары: (1, 2), (2, 3), (3,4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9). Для решения применим главную теорему комбинаторики. Для этого определим, что есть объект и что есть свойства. Под объек­тами будем понимать различные расстановки верблюдов. Всего их бу­дет N
=
9!. Под свойствами будем понимать наличие определенной пары в перестановке. Таким образом число свойств равно 8. Тогда количе­ство перестановок, не обладающих ни одним из 8 свойств:



В общем случае при п
верблюдах имеем



1.4.6.Комбинаторика разбиений


При анализе стратегий различных игр требуется подсчитывать ко­личество комбинаций при раскладе определенных предметов. Наибо­лее распространенная карточная игра - преферанс. В классическом варианте этой игры карты раскладываются на 3 кучки (по числу играю­щих) и 2 карты кладутся в "прикуп". Играют 32 картами, т. е. каждый игрок получает по 10 карт.


Определим количество вариантов расклада при игре в преферанс:



Для обоснования полученной формулы расставим все карты подряд и переставим их 32! способами. При каждой перестановке будем выде­лять первые 10 карт первому игроку, вторую десятку - второму, третью


- третьему, а последние 2 карты будем откладывать в "прикуп". После этого заметим, что перестановка 10 карт в руках каждого игрока не меняет варианта расклада, как и положения 2 карт в прикупе. Поэтому 32! разделим три раза на 10! и еще на 2!


При игре в древнюю китайскую игру НИМ раскладываются п
спичек на 3 кучки. Сколько вариантов раскладки этих спичек?


Для определения количества вариантов расклада выпишем подряд п
единиц и справа добавим к ним 2 нуля. Переставляя эти объекты всеми возможными способами, мы каждый раз будем получать один из вари­антов расклада. Более того, любому варианту расклада можно сопос­тавить некоторую перестановку из п
единиц и двух нулей. Таким обра­зом, получаем:


P
(n,2) = (n+2)!/(n!2!).


А теперь определите количество вариантов расклада, при котором в любой кучке есть хотя бы одна (две, три) спички?


В общем случае, если раскладываются п
разных предметов по к
ящи­кам так, чтобы в 1-й ящик (кучку, игроку в руки) попало п1
предметов, во второй п2
предмета, в к
-й- пк
предметов, при этом п1
+ п2
+
...+ пк
= п,
то число вариантов расклада



1.4.7. Количество делителей числа N


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


1-й карман
5 р., 4 р., 3 р., 2 р., 1 р., 0 р.


2-й карман
0 р., 1 р., 2 р., 3 р., 4 р., 5 р.


Итого существует 6 вариантов расклада. Если раскладывается п
предметов на 2 кучки, то существует п
+ 1 вариант.


Если раскладываются предметы нескольких типов на 2 кучки (ящи­ки, корзины, множества), то такой расклад выполняется независимо для каждого типа предметов и результаты перемножаются.


Пример. Имеются цветы трех видов: 10 васильков, 15 незабудок, 12 ромашек. Требуется разложить их на 2 букета. Васильки на 2 букета можно разложить 11 способами, незабудки - 16, ромашки - 13 способа­ми. Поскольку расклад каждого вида цветов выполняется независимо, то общее число вариантов расклада будет: .


Обобщим полученный результат. Пусть имеется п1
предметов 1-го типа, п2
-
2-го, ... п
k
—
k
-го.
Требуется разложить эти предметы на 2 кучки.


Тогда полное число вариантов расклада равно


Пусть имеется некоторое число N.
Требуется определить количе­ство делителей N.


Решение. Представим N
в канонической форме, т. е.



Тогда задача о нахождении числа делителей N
сводится к задаче рас­кладки степеней простых чисел на 2 делителя: т. е. решение будет:



Пример. N
=
600 = 23
31
52
. Число делителей равно (3+1)(1+1)(2+1) = 24.


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


Пример 1. Из n
различных чисел требуется отобрать к
таких, чтобы в выбранное множество не входили s
конкретных чисел. Общее число выборов из п
по к:



Выберем теперь s
конкретных чисел и остальные доберем


способами. Это будет число неблагоприятных комбинаций. Число бла­гоприятных комбинаций определится разностью



Пример 2. Из группы в 15 человек нужно отобрать бригаду, в которую должно входить не менее 5 человек. Сколько имеется вариантов выбора?


Подсчитаем число неблагоприятных комбинаций выбора, т. е. со­ставим варианты бригад из 1, 2, 3, 4 человек. Их количество равно:



А общее количество бригад равно 215
– 1. Разность дает число благо­приятных комбинаций.


Пример 3. Комиссия из 7 человек хранит свои материалы в сейфе. Сколько должно быть замков на сейфе и сколько должно быть ключей у каждого члена комиссии, чтобы сейф мог быть открыт, если соберутся вместе не менее 4 членов комиссии, но не мог быть открыт при меньшем числе членов комиссии?


Для решения последней задачи можно использовать так называе­мые "равновесные" коды. Равновесными кодами длины п
веса к
назы­ваются двоичные последовательности длины п,
содержащие ровно к
единиц ( и п - к
нулей). Число таких кодов определяется выражением: Р(к, п - к).
Выпишем, например, все коды длины 5 веса 3:


1) 11100 6) 10011


2) 11010 7) 01110


3) 11001 8) 01101


4) 10110 9) 01011


5) 10101 10) 00111


Легко заметить, что каждый столбец содержит 6 единиц и 4 нуля. Кроме того, если взять любые два столбца и поставить их рядом, то всегда найдется комбинация 00. Если же взять три любых столбца, то комбинации 000 не будет.


Если теперь считать номера строк 1), 2), ..., 10) номерами ключей, а каждый столбец рассматривать как способ выдачи ключей конкретно­му члену комиссии, то мы получим решение поставленной задачи при 5 членах комиссии и пороговом значении h
= 3. Если теперь построить таблицу кодов длины 7 веса 4, мы получим решение исходной задачи.


Полученное решение легко обобщить на произвольное число членов комиссии п
и произвольный порог h
.
Действительно, если построить таб­лицу равновесных кодов длины п
веса к,
то число ключей будет равно , а сейф может быть открыт, если соберется число членов комиссии равное h
= п - к
+ 1.


Так, например, пусть п =
4, h
=
3, т. е. число членов комиссии равно 4, а сейф должен открываться, если соберется не менее 3 членов комис­сии. В общем случае к = п -
h
+ 1.


Для конкретного примера k
= 4 – 3 + 1=2; т. е. нужно построить таблицу равновесных кодов длины 4 веса 2:


1) 1100 4) 0110


2) 1010 5) 0101


3) 1001 6) 0011


Из таблицы видно, что сейф должен иметь в этом случае 6 замков, а ключи должны распределяться в соответствии с таблицей равновесных кодов, т. е. первый член комиссии (первый столбец) получает 1, 2 и 3 ключ, второй член комиссии получает 1,4 и 5 ключ, третий член комис­сии получает 2,4 и 6 ключ и четвертый член комиссии получает 3, 5 и 6 ключ.


1.4.8. Раскладка предметов в несколько ящиков


Рассмотрим следующую задачу. Трое мальчиков собрали 40 яблок. Сколько имеется способов раздела яблок между ними?


Напишем 40 единиц и 2 нуля, выполняющих как и ранее функции раз­делителя, и затем начнем их переставлять всеми возможными способами. Каждой перестановке будет соответствовать некоторый способ раздела 40 яблок на 3 кучки. Каждому способу раздела будет соответ­ствовать некоторый код, содержащий 40 единиц и 2 нуля. Поэтому коли­чество способов раздела:


Р(40,2) = 42!/(2!40!) = 861.


Если мы раскладываем п1
предметов 1-го типа, п2
предметов вто­рого, ..., пк
предметов к-го
типа на s
кучек, тогда


.


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


1.4.9. Задача: Флаги на мачтах


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


Сначала будем считать, что все флаги одинаковые. Тогда:


.


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


Количество разных сигналов, получаемых путем развешивания фла­гов на мачтах, можно еще увеличить, если учитывать варианты, при которых вывешиваются не все флаги, а, например, s
флагов из имею­щихся п.
Тогда общее число расстановок будет


.


1.4.10. Задача: Покупка билетов


Перед кассой по продаже билетов стоит очередь из п
владельцев рублей и к
владельцев полтинников. Билет стоит полтинник. В каком количестве комбинаций очередь пройдет без задержки, если владелец полтинника, подойдя к кассе, получает билет, а владелец рубля - билет и полтинник на сдачу. В кассе предварительно нет полтинников. Ясно, что задача имеет смысл, если п < к.


Возьмем комбинацию, при которой очередь застрянет и запишем ее следующим образом:


(
s
-
рублей иs
-
полтинников)Р
........


Очередь застрянет на рубле, при этом до этого рубля в очереди дол­жно быть одинаковое количество владельцев рублей и полтинников. Добавим спереди полтинник (их станет к
+ 1) и проинвертируем всю комбинацию (заменим рубли на полтинники, а полтинники на рубли) до рубля, на котором очередь застряла (включая и его). Мы придем к ком­бинации, содержащей п
рублей и к
+ 1 полтинник, начинающейся с руб­ля. Можно взять п
рублей и к
+ 1 полтинник (теперь всегда число пол­тинников строго больше числа рублей) и начать комбинацию с рубля. Обратным преобразованием придем к комбинации, при которой очередь обязательно застрянет.


Таким образом, количество комбинаций, при которых очередь за­стрянет равно Р(п -
1, к
+ 1), а общее число комбинаций равно Р(п, к);
т. е., число благоприятных комбинаций, при которых очередь пройдет без задержки, будет равно


Р
(п
, к
) – Р
(п -
1, к
+ 1).


Например, при п =
4 и к = 5
число благоприятных комбинаций равно


Р
(4, 5) -Р
(3, 4) = 9!/(4!5!) - 7!/(3!4!) = 126 - 35 = 91.


1.4.11. Рекуррентные соотношения в комбинаторике


1. Задача о наклейке марок.


Имеются марки достоинством в 4, 6, 10 копеек. На конверт нужно наклеить марки так, чтобы сумма составляла 18 копеек. Сколькими способами можно это сделать?


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


F
(
N
) =
F
(
N
-
4) +
F
(
N
-
6) +
F
(
N
-
10)
,


где под F
(
N
)
понимается количество вариантов наклейки марок общей стоимостью N.
Подсчитаем значения F
(
N
)
для некоторых начальных N.


F
(
N
)
= 0 при N
<
0.
F
(0) =1. F
(1) = F
(2) = F
(3) = 0. F
(4) = 1. F
(5) = 0. F
(6) = 1.F
(7) = 0. F
(8) = 1. F
(9) = 0. F
(10) = 3. Тогда для N
= 18 получаем: F
(18) = F
(14) + F
(12) + F
(8) = F
(10)+ F
(8) + F
(4) + F
(8) + F
(6) + F
( 2) + F
(8) = 3 + 1 + 1 + 1 + 1 + 1 = 8.


2. Задача об уплате долга.


В кошельке имеются монеты достоинством в 1, 2, 3, 5, 10, 15, 20, 50 копеек (по одной штуке). Требуется уплатить долг в 73 копейки. Сколько существует вариантов выплаты долга?


Запишем рекуррентное соотношение в общем случае, когда монеты имеют достоинства в к1
к2
,
... и кт
копеек и требуется набрать сумму в N
копеек:


F
(
k
1
k
2
, ...,
km
;
N
) =
F
(
k
1
,
k
2
,
..., k
т-1
;
N
-
km
)
+ F
(
k
1
,
k
2
,
..., кт-1
;
N
).


Первый член правой части учитывает количество комбинаций, в ко­торых монета старшего достоинства использована, второй член - в ко­торых монета старшего достоинства не использована. Для рассматри­ваемого примера


F
(l, 2, 3, 5, 10,15, 20, 50; 73) = F
(l, 2, 3, 5,10, 15,20; 73)+F
(1,2, 3,5,10,15, 20; 23).


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


F
(l, 2,3,5,10,15,20; 23) = F
(l, 2,3,5,10,15; 3) + F
(l, 2,3,5,10,15; 23)


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


F
(l,2,3;3) + F
(l,2,3,5,10,15;23) =


=F
(1,2; 0) + F
(l,2;3 )+ F(l,2, 3, 5,10; 8) +F
(1,2, 3, 5,10; 23) = 1+F
(1; 1) + F
(1; 3)+F
(l, 2, 3, 5; 8) + F
(l, 2, 3, 5, 10; 23).


Очевидно, что F
(l, 2; 0) = 1; F
(l, 2; 3) = F
(l;l) = 1; F
(l; 3) = 0; F
(l, 2, 3, 5, 10; 23) = 0. Поэтому правая часть перепишется в виде: 1 + 1 + 0 + F
(l, 2,3,5; 8) + 0 = 2 + F
(l, 2, 3; 3) + F
(l, 2, 3; 8) = 2 + 2 + 0 = = 4. Таким образом, задача имеет 4 различных решения.


Подчеркнем еще раз, что в этой задаче порядок монет не важен.


4. Задача о размене гривенника (10 копеек).


Рассмотрим задачу, в которой сняты ограничения, как на порядок предметов, так и на их коли­чество: размен гривенника монетами достоинством в 1, 2, 3, 5 копеек. Сколько существует способов разменять гривенник?


Для этого случая рекуррентное соотношение имеет вид


S
(l, 2, 3, 5; 10) = S
(l, 2, 3; 10) + S
(l, 2, 3; 5) + S
(l, 2, 3; 0).


Таким образом все множество решений разбивается на подмноже­ства в зависимости от числа монет старшего достоинства, использо­ванных для размена. Находим все 20 способов размена:




























1.5. Связь комбинаторики с другими разделами математики


1.5.1. Теория групп


Рассмотрим группу вращений правильного n
-угольника. По­рождающим элементом этой группы является перестановка:


,


все остальные элементы группы могут быть получены возведением последовательно в степени 2, 3, ... п
этой перестановки. При этом hn
=
h0
. Количество таких перестановок (а, следовательно, и число эле­ментов группы) равно п.


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



1.5.2. Теория вероятностей


Для оценки вероятности появления какого-либо дискретного собы­тия широко применяются комбинаторные методы. Приведем некото­рые примеры.


а) Игрок в преферанс хочет рискнуть: объявить и сыграть "мизер". Для надежной игры ему требуется, чтобы в прикупе оказалась одна из двух семерок, например бубновая или трефовая. Он хочет оценить ве­роятность такого события. Вероятность события можно определить,разделив количество благоприятных вариантов на общее число возмож­ных вариантов. Подсчитаем количество вариантов, в которых одна из указанных семерок или сразу обе окажутся в прикупе. Положим бубно­вую семерку в прикуп, а остальные 21 карты распределим так: по 10 карт двум игрокам и одну в прикуп. Количество комбинаций будет рав­но: 21!/(10! 10!). Такое же количество комбинаций будет и в случае, когда в прикуп попадет трефовая семерка. Если мы сложим число вариантов в этих 2 случаях, то дважды учтем расклады, при которых обе семерки и бубновая, и трефовая попадут в прикуп, поэтому должны еще вычесть число этих вариантов. Окончательно получим число благоприятных ком­бинаций: 2(21!/(10! 10!) - 20!/(10! 10!) = 41·20!/(10! 10!). Подсчитаем те­перь общее число вариантов (учитываем, что 10 карт находятся у иг­рока, который хочет сыграть мизер). Общее число вариантов равно: 22!/(10!10!2!). Вероятность благоприятного события: Р =
0,177. Риск­нуть можно, но шансов на успех мало.


б)Из-за недостатка времени криптоаналитик может сделать только1000 попыток для расшифровки сообщения, ключ от которого ему неиз­вестен. Однако известно, что используется рюкзачный вектор, состоя­щий из 100 чисел, при этом сумма порождается 4 числами. Требуется оценить вероятность того, что за 1000 попыток вскрыть шифр, он это сумеет сделать.


Определим сначала общее число комбинаций, которые следовало бы перебрать криптоаналитику:=100!/(4!96!). Однако благоприятной комбинацией является только одна. Следовательно, вероятность вскры­тия шифра за одну попытку


Р =
24/94109400 = 0,000000255.


Вероятность того, что криптоаналитик вскроет неизвестный шифр за 1000 попыток:


Р
(1000) = 1 - (1 - 0,000000255)1000
= 0,0003.


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


1.Вероятность того, что все провода будут припаяны правильно.


2.Вероятность того, что из 8 проводов ровно 3 провода будут припа­яны правильно, а остальные неверно.


Для решения задачи сначала определим общее число перестановок 8 проводов. Оно равно 8! = 40320. Для решения 1-й части задачи отметим, что имеется всего одна благоприятная комбинация, поэтому веро­ятность распаять разъем правильно, не имея монтажной схемы, равна Р =
1/40320 = 0,0000248. Для решения второй части задачи число благоприятных комбинаций значительно больше и определяется как



Поэтому вероятность припаять правильно ровно 3 провода из 8 равна Р =
2464/40320 = 0,061.


1.5.3. Криптография


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


Рассмотрим, например, простейшую классическую криптографичес­кую систему, называемую системой Цезаря. В этой системе произво­дится замена букв по определенному правилу. Сначала в первой строке выписываются подряд все буквы алфавита. Затем формируется ниж­няя строка, составленная из тех же букв, расположенных в том же по­рядке, но со сдвигом на s
позиций. Для оценки затрат криптоаналитика по подбору шифра замены требуется вычислить количество вариантов ключей (т. е. сдвигов). Это число равно количеству букв п
в алфавите. Для латинского алфавита п =
26, для русского алфавита п =
33, поэтому криптоаналитик должен перебрать соответствующее число разных клю­чей, т. е. рассмотреть все шифры замены, получаемые всевозможны­ми сдвигами букв алфавита, т. е. 26 или 33 элемента группы сдвига.


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


Рюкзачная криптосистема с открытым распределением ключей име­ет дело с вектором А = (
a
1
,
a
2
,
..., ап
).
При шифровании сообщений открыто передаются значения сумм некоторых элементов а
i
, при этом криптоаналитику часто бывает известно количество элементов и их сумма (но не известны сами элементы). Для вскрытия шифра криптоа­налитик должен перебрать число ключей, равное числу сочетаний из п
по к.


1.5.4. Экономика


Рассмотрим следующую задачу. Некоторый банк имеет 5 милли­онов рублей, которые может выдать клиентам в виде кредитов. Пред­положим, что кредиты хотят получить 8 клиентов банка (заемщики). Правление решает выдавать кредиты, кратные 0,25 миллиона. Требу­ется определить, сколько различных способов выдачи кредита суще­ствует. Комбинаторика, конечно, не позволяет решить вопрос о том, каким клиентам и какой кредит следует выдать. Она только позволяет подсчитать количество вариантов. Для данного условия задачи найдем сначала количество квот (частей по 0,25 миллиона в каждой), содержа­щихся в 5 миллионах. Для этого разделим 5 на 0,25, получим 20. Выпи­шем теперь подряд 20 единиц и справа к ним припишем 7 нулей. Нач­нем переставлять цифры полученного кода всеми возможными спосо­бами. Одна из таких перестановок может выглядеть так: 111110111001001111111110011. Такой перестановке будет соответство­вать следующий вариант раздачи кредитов:


































1-й Заемщик получит 1,25 миллиона
2-й - 0,75 миллиона
3-й - 0,
4-й - 0,25 миллиона
5-й - 0,
6-й - 2,25 миллиона
7-й - 0,
8-й - 0,5 миллиона

Заметим, что каждой перестановке будет соответствовать некото­рый способ раздачи кредитов и каждому способу раздачи будет соот­ветствовать некоторый код, состоящий из 20 единиц и 7 нулей. Таким образом, число вариантов раздачи кредитов


Р
(20, 7) = 27!/(20!7!) = 888030.


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


1.5.5. Теория информации


Теория информации исследует математические описания и оценки качества передачи, хранения, извлечения и классификации информации. В 1948 году К. Шеннон (К.
Shannon
)
обосновал целесообразность ис­пользования количественной меры информации, что позволило ему сфор­мулировать фундаментальную теорему о нахождении скорости переда­чи информации по каналам связи, которую можно достичь при некото­ром оптимальном методе кодирования и декодирования, обеспечив при этом сколь угодно малую вероятность ошибки. Количественная мера информации энтропия
является мерой степени неопределенности слу­чайной величины. Пусть некоторая случайная величина , принимает значения х1
, х2
,..., хп
распределением вероятностей p
1
, р2
,...
, р
n
.
В этом случае энтропия случайной величины , определяется формулой


.


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


Учет вероятностей ошибок типа 01 и 10 и энтропийная оценка позволяют сравнивать различные методы кодирования и декодирова­ния по достоверности получаемых сообщений.


1.5.6. Теория графов


Теория графов относится к области дискретной математики и зани­мается изучением геометрических связей между объектами. Основ­ным объектом теории является граф, однако при решении многих задач в XX веке широко стали применяться другие термины: карта, сеть, ком­плекс, диаграмма, лабиринт. Теория графов тесно связана с различны­ми разделами математики: топологией, алгеброй, теорией вероятнос­тей, теорией чисел и, конечно, с комбинаторикой.


Приведем некоторые примеры задач теории графов, которые реша­ются комбинаторными методами.


1. Имеется п
участников шахматного турнира. Сколько партий дол­жно быть сыграно, чтобы каждый участник сыграл со всеми остальны­ми? Любой турнир между п
участниками (командами) может быть пред­ставлен в виде графа, при этом после окончания турнира граф является полным. Каждый участник (вершина графа) играет со всеми остальны­ми (их число п -
1), а поскольку число участников равно п,
то всего игр п(п -
1)/2.


2. Комбинаторные задачи сортировки часто изображаются в виде графов типа "дерево".


3. Не решенная аналитически задача Гамильтона об обходе всех вер­шин связного графа в точности по одному разу для определения числа шагов упорядоченного перебора использует комбинаторные оценки.


Глава 2. Методические разработки для элективного курса


2.1. Анализ изложения темы в школьных учебниках


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


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


Попытка построения вероятностно-статистической линии в базовом курсе математики основной школы предпринята в учебниках


Под редакцией Г.В Дорофеева и И.Ф Шарыгина


«Математика5», «Математика6», «Математика7», «Математика8» и «Математика 9».


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


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


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


6 класс
начинается с повторения таблиц и диаграмм. Повторяются уже изученные столбчатые диаграммы и более подробно рассматриваются круговые (для представления соотношения между частями целого).


Далее идут 2 параграфа по комбинаторике: логика перебора и правило умножения. Здесь рассматриваются задачи, которые решаются уже известным им способом перебора и предлагается упростить его, используя так называемое кодирование. Также рассматривается новый способ решения комбинаторных задач с помощью правила умножения.


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


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


В 8 классе
сначала повторяются статистические характеристики, изученные в 7 классе, и вводится новая характеристика – медиана. Рассматриваются таблицы частот. Приводятся примеры, показывающие связь с практикой, описываются различные жизненные ситуации. В 8 классе вводится классическое определение вероятности, данное Лапласом. Рассматриваются геометрические вероятности.


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


В учебнике рассматриваются 3 примера статистических исследований, это реальные примеры близкие школьнику. Это вопросы: «Как исследуют качество знаний школьников», «Удобно ли расположена школа?», «Куда пойти работать?». Учащийся видит применение знаний по статистике в реальных жизненных ситуациях.


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


Зубарева И.И., Мордкович А.Г. «Математика 5», «Математика 6»
.


В 5 классе
последняя глава «введение в вероятность» содержит 2 параграфа. В одном параграфе рассматриваются достоверные, невозможные и случайные события, приводятся задачи на определение характера события (достоверное, невозможное или случайное). Во втором параграфе рассматриваются комбинаторные задачи, решаемые методом перебора возможных вариантов.


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


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


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


Некоторые учебные комплекты пополнились дополнительными учебными пособиями, содержащими материал по стохастике.


Макарычев Ю.Н., Миндюк Н.Г.


«Алгебра: элементы статистики и теории вероятностей».


Под редакцией Теляковского С.А.


Это учебное пособие предназначено для учащихся 7-9 классов, оно дополняет учебники: Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И., Суворова С.Б. «Алгебра 7», «Алгебра 8», «Алгебра 9», под редакцией Теляковского С.А.


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


В 7 классе
(§1) материал объединен в параграф «статистические характеристики», который знакомит с простейшими статистическими характеристиками (среднее арифметическое, мода, медиана, размах). Упражнения к параграфу можно разделить на 2 группы. Первую группу составляют задания на отыскание рассматриваемых характеристик и истолкование их практического смысла. Ко второй группе относятся задания, которые требуют не только знания определений изучаемых статистических характеристик, но и умений проводить необходимые рассуждения, использовать ранее введенный алгебраический аппарат.


Материал, изучаемый в 8 классе
(§2) также объединен в один параграф «Статистические исследования», где рассматриваются вопросы организации статистических исследований и наглядного представления статистической информации (таблицы частот). Сначала повторяются основные статистические характеристики. Вводятся новые понятия: интервальный ряд, сплошное и выборочное исследования, выборка, генеральная совокупность, репрезентативность. Знакомство с новыми видами наглядной интерпретации результатов статистических исследований – полигонами и гистограммами


Наибольший объем материала приходится на 9 класс
(§3, §4).


§3 «Элементы комбинаторики» содержит 4 пункта:


1. Примеры комбинаторных задач
. На простых примерах демонстрируется решение комбинаторных задач методом перебора возможных вариантов. Этот метод иллюстрируется с помощью построение дерева возможных вариантов. Рассматривается правило умножения.


2. Перестановки
. Вводится само понятие и формула подсчета перестановок.


3. Размещения
. Понятие вводится на конкретном примере. Выводится формула числа размещений.


4. Сочетания
. Понятие и формула числа сочетаний.


§4 «Начальные сведения из теории вероятностей».


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


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


Методические рекомендации к данному учебнику даны в ряде статей Макарычева и Миндюка. А также некоторые критические замечания по данному учебному пособию содержатся в статье Студенецкой и Фадеевой, которая поможет не допустить ошибок при работе с данным учебником.


Ткачева М.В.


«Элементы статистики и вероятность».


Это учебное пособие для 7-9 классов и оно дополняет учебники Алимова Ш.А. «Алгебра 7,8,9».


1 Глава «Введение в комбинаторику» (7 класс) начинается с исторических комбинаторных задач о магических и латинских квадратах и другие. Затем рассматриваются различные комбинации из трех элементов: сочетания, перестановки и размещения, но строго термины не вводятся. Рассматривается таблица подсчета вариантов, которая подводит к правилу умножения. Также рассматриваются графы, но лишь как средство иллюстрации для подсчета возможных вариантов. Эта глава имеет и дополнительные параграфы – перестановки и разбиение на две группы, выдвижение гипотез.


2 Глава «Случайные события» (8 класс).


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


3 глава «Случайные величины» (9 класс).


Вводятся понятия случайной величины – дискретной и непрерывной. Рассматриваются таблицы распределения значений случайной величины и его графическое представление (полигоны). Далее рассматриваются такие понятия как генеральная совокупность и выборка, мода, медиана, размах. А завершается глава дополнительными параграфами, в которых рассматриваются отклонение от среднего, дисперсия, среднее квадратичное отклонение и правило трех сигм.


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

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


В конце учебника содержатся краткие методические рекомендации для учителя. Также методические рекомендации к первой главе данного учебного пособия можно найти в статье Ткачевой.


На данный момент одним из действующих учебников в школе является учебник Мордковича, к нему также имеются дополнительные главы для 7-9 классов:


Мордкович А.Г., Семенов П.В.


«События, вероятности, статистическая обработка данных».


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


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


Третий параграф – случайные события и их вероятность. Вводится классическое определение вероятности.


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


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


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


Тюрин Ю.Н., Макаров А.А. и др.


«Теория вероятностей и статистика».


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


В третьей главе вводятся основные статистические характеристики, а также такие понятия, как «отклонение» и «дисперсия».


Четвертая глава посвящена случайной изменчивости и содержит ряд примеров изменчивых величин (температура воздуха каждый день, рост или вес человека и т.п.). Затем в 5 главе переходят к изучению случайных событий и их вероятностей. Вероятность случайного события определяется здесь как числовая мера его правдоподобия. После определения вероятности рассматривается частота и эксперименты с монетой и игральной костью. Дальше вероятностная линия продолжается, и рассматриваются элементарные события, их равновозможность, противоположные события, диаграммы Эйлера, объединения и пересечения событий, сложение и умножение вероятностей.


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


Следующие несколько глав посвящены случайным величинам: примеры случайных величин, распределение вероятностей случайных величин, их числовые характеристики (математическое ожидание, дисперсия), случайные величины в статистике. Дается определение частоты, и теорема, утверждающая, что частота приближенно равна вероятности при большом числе опытов.


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


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


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


Бунимович Е.А., Булычев В.А.


«Вероятность и статистика. 5-9 классы».


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


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


В последнем пункте «сколько изюма в булке и сколько рыб в пруду?» рассматривается вопрос статистического оценивания и прогнозирования.


В данном пособии более удачным является введение понятия вероятности. Последовательность изложения вопросов по данной линии более логична, чем в остальных пособиях.


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


2.2. Тематическое планирование


2.2.1. Введение


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


Так как в школах тему “комбинаторика” преподают неразрывно с такими темами, как “теория вероятностей” и “случайные величины”, то в данной работе решено было разработать такой элективный курс, как "Изучение основ комбинаторики и теории вероятностей"
.


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


Курс рассчитан на учеников 10 - 11 классов, имеющих хорошую логическую математическую культуру мышления.


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


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


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


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


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


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


Основной целью

элективного курса

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


Задачи курса:


· получение знаний о комбинаторике и основных элементах теории вероятностей;


· рассмотреть решение комбинаторных задач;


· развитие представлений учащихся о случайных величинах и их характеристиках;


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


· овладение умениями решать задачи, связанные с конкретной жизненной ситуацией;


· расширение общекультурного кругозора и развитие логического мышления учащихся через межпредметные связи;


· формирование умение определять связь теории вероятностей с практическими потребностями;


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


Ожидаемые результаты


После изучения курса учащиеся должны знать:


- Знать основные понятия комбинаторики, теории вероятностей и математической статистики.


После изучения курса учащиеся должны уметь:


- Уметь вычислять вероятности событий, пользуясь различными определениями вероятности и формулами.


- Уметь представить событие в виде комбинации нескольких элементарных событий.


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


- Различать дискретные и непрерывные случайные величины.


- Уметь находить числовые характеристики случайных величин.


- Уметь решать простейшие задачи математической статистики.


- Уметь интерпретировать полученные результаты.


Содержание элективного курса:


1. Элементы комбинаторики. (8 часа)


2. Случайные события .(10 часа)


3. Случайные величины. (10 часа)


4. Практикум по решению задач . (3 часа)


5. Контрольная работа. (1 час)


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


2.2.2. Содержание программы элективного курса


Элективный курс “Основы комбинаторики и теории вероятностей” рассчитан на 32 часов: 25 часов – теоретических занятий, 3 часа – контроль знаний в виде теста, 3 часа – практикум по решению задач и 1 час – контрольная работа. Курсу отводится 1 час в неделю для изучения в двух полугодиях 10-го или 11-го класса.


Раздел 1.
Элементы комбинаторики (
8
ч).


Некоторые сведения из комбинаторики. Основные правила комбинаторики: правило суммы и правило произведения. Основные комбинаторные схемы: перестановки, размещения, сочетания. Упражнения по комбинаторике. Бином Ньютона и треугольник Паскаля.


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


Раздел

2

. Случайные события (10 ч).


Понятие вероятности.Классическое определение вероятности события. Статистическое понятие вероятности события. Геометрическое понятие вероятности.


Знать смысл, различать понятия вероятности.


Операции над вероятностями. Произведение и сумма событий. Теоремы умножения и сложения вероятностей, формула полной вероятности. Формула Байеса.


Знать смысл, различать и осознанно использовать следующие общие понятия:
свойства вероятности, основные теоремы теории вероятностей (сложение и умножение вероятностей), формулу полной вероятности и формулу Байеса.


Уметь:
решать задачи на применение формулы полной вероятности и формулы Байеса.


Раздел

3

.
Случайные величины. (
10

ч).


Случайные величины.Понятие случайной величины. Дискретные и непрерывные случайные величины. Примеры.


Цель:
различать и осознанно использовать понятия - дискретные и случайные величины.


Числовые характеристики.
Математическое ожидание, дисперсия случайной величины. Другие числовые характеристики (мода, медиана) и их смысл. Упражнения. Выполнение расчётных заданий.


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


Уметь:
вычислять характеристики дискретной случайной величины (математическое ожидание, дисперсию, среднеквадратическое отклонение), характеристики непрерывной случайной величины (математическое ожидание, дисперсию, моду, медиану, среднеквадратическое отклонение).


Раздел

4. Практикум по решению задач (3 ч).


Раздел

5. Контроль знаний (1 ч).


2.2.3. Поурочное планирование


Поурочное планирование на одно полугодие для 10 – 11 класса физико-математического профиля (32 часа).












































































































№ Тема урока Кол-во часов
1. Элементы комбинаторики(8 часов).
1.1. Логика перебора. 1
1.2. Правила суммы и умножения. 1
1.3. Перестановки, размещения, сочетания. 1
1.4. Размещения и сочетания и перестановки с повторениями 1
1.5. Свойства сочетаний. Применение формул комбинаторики для упрощения выражений. 1
1.6.

Формула бинома Ньютона. Свойства биномиальных


коэффициентов. Треугольник Паскаля.


 2
1.7. Проверка знаний (тестирование). 1
2. Случайные события(10 часов).
2.1. Алгебра событий. Элементарные события. Сложные события. 1
2.2. Частота случайного события. Определение вероятности. 2
2.3. Вероятностная шкала. 1
2.4. Вычисление вероятности с помощью формул комбинаторики. 1
2.5. Свойства вероятности и их применение к решению задач. 1
2.6. Условная вероятность. Формула Байеса. 1
2.7. Геометрические вероятности. 1
2.8. Независимые, однородные испытания. Схема Бернулли. 1
2.9. Проверка знаний (тестирование). 1
3. Случайные величины(10 часов).
3.1. Основные понятия. 1
3.2. Числовые характеристики случайной величины. Свойства математического ожидания, дисперсии. 2
3.3. Таблицы частот. 1
3.4. Функция распределения случайной величины. Плотность распределения непрерывной случайной величины. 2
3.5. Простейшие распределения случайных величин: биномиальное распределение, распределение Пуассона, равномерное распределение на [a; b], показательное, нормальное распределения и их применение. 2
3.6. Расчётно-графические задания. 1
3.7. Проверка знаний (тестирование). 1
4. Практикум по решению задач(3 часа).
5. Контрольная работа(1 час).

2.3. Разработки занятий


В данном параграфе представлены разработки занятий элективного курса «Основы комбинаторики и теории вероятностей» к разделу «Элементы комбинаторики». Разделу «Элементы комбинаторики» отводится 8 часов, из них один час – это проверка знаний в виде тестирования. Ниже представлены подробные конспекты данных уроков.


Урок № 1.

Логика перебора.


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


Тип урока:
комбинированный


Ход урока


1. Организационный момент и постановка цели урока (3 мин).


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


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


А представьте на миг, чтобы стало в школе, если бы не было расписания. Трудно пришлось бы всем: и детям, и учителям. Даже в одном классе и то вряд ли легко решили бы проблему. Для того чтобы решить эту проблему наиболее удобным способом и изучается комбинаторика.


2. Выполнение задания (35 мин).


Давайте рассмотрим такую задачу:


Задача 1.
Три друга, Антон, Борис и Виктор, приобрели два билета на футбольный матч. Сколькими способами можно распределить билеты на футбол?


Решение:
Здесь необходимо перебрать всевозможные пары мальчиков.


а) Антон и Борис; б) Антон и Виктор; в) Борис и Виктор.


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


Задача 2.
Три друга, Антон, Борис и Виктор, приобрели два билета на футбольный матч на 1-е и 2-е места первого ряда стадиона. Сколько существует способов занять эти два места на стадионе? Записать все эти варианты.


Решение:
Здесь мы можем использовать результаты предыдущей задачи. В ней мы не учитывали порядок, а теперь необходимо учитывать порядок, на каком месте будет сидеть тот или иной мальчик. Рассмотрим тот вариант, когда на матч пошли Антон и Борис, в этом случае возможно два варианта занять места на матче: 1-ое место – Антон, 2-ое место - Борис и наоборот 1-ое место Борис, а 2-ое Антон. То есть упорядочить два элемента мы можем двумя способами.


а) Антон и Борис;


1-ое место – Антон, 2-ое место – Борис или 1-ое место – Борис, 2-ое место – Антон.


б) Антон и Виктор;


1-ое место – Антон, 2-ое место – Виктор или 1-ое место – Виктор, 2-ое место – Антон.


в) Борис и Виктор.


1-ое место – Борис, 2-ое место – Виктор или 1-ое место – Виктор, 2-ое место – Борис.


Таким образом, мы получаем 6 вариантов.


Задача 3.
Антону, Борису и Виктору повезло, они купили 3 билета на футбол на 1-е, 2-е и 3-е места первого ряда стадиона. Сколькими способами могут занять мальчики эти места?


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


а) 1-ое место – Антон, тогда


2-ое место – Борис, 3-ье место – Виктор или 2-ое место – Виктор, 3-ье место – Борис.


б) 1-ое место – Борис, тогда


2-ое место – Антон, 3-ье место – Виктор или 2-ое место – Виктор, 3-ье место – Антон.


в) 2-ое место – Виктор, тогда


2-ое место – Антон, 3-ье место – Борис или 2-ое место – Борис, 3-ье место – Антон.


В результате получим 6 вариантов, то есть упорядочить 3 элемента мы можем шестью способами.


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


Задача 4.
Сколько двузначных чисел можно составить, используя цифры 1,2,3.


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


В процессе решения этой задачи может возникнуть такой вопрос, а может ли одна и та же цифра повторяться в числе два раза? (если не возникнет, то учитель может сам обратить на это внимание).


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


Рассмотрим задачу:


Задача 5.
В алфавите племени УАУА имеются только две буквы – «а» и «у». Сколько различных слов по три буквы в каждом можно составить, используя алфавит этого племени?


Решение:
В этой задаче одна и та же буква может встречаться в слове как один, так два или три раза. И нужно рассмотреть все варианты.


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


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



Теперь, проходя по веточкам дерева, по порядку выписываем нужные нам сочетания букв - «слова»:


ааа; аау; ауа; ауу; уаа; уау; ууа; ууу.


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


Задача 6.
В 5«А» классе в среду 4 урока: математика, информатика, русский язык, английский язык. Сколько можно составить вариантов расписания на среду?


Решение:
В данной задаче у нас имеется 4 предмета и необходимо выписать возможные варианты расписания на один день, учитывая те условия, что каждый урок должен обязательно присутствовать в расписании, и встречаться там всего один раз (для упрощения записи предлагается каждый предмет обозначит его заглавной буквой). Таким образом, нам необходимо подсчитать сколькими способами мы можем упорядочить 4 элемента. Пусть первым будет урок математики, тогда оставшиеся 3 предмета мы можем упорядочить 6-ью способами (из ранее рассмотренных задач). Аналогично для оставшихся трех предметов. Итого получим 24 способа упорядочить 4 предмета.


3. Домашнее задание (5 мин).


1. В 5А классе во вторник 5 уроков: физкультура, русский язык, литература, обществознание и математика. Сколько можно составить вариантов расписания на день, зная точно, что математика – последний урок?


2.Используя весь русский алфавит, составьте как можно больше двухбуквенных слов, используемых в русском языке. При условии, что при перестановке букв тоже получится слово русского языка. (В одном слове буквы не повторяются).


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


4. Подведение итогов урока (2 мин).


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


Урок № 2.

Правила сложения и умножения.


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


Тип урока:
комбинированный


Ход урока


1. Организационный момент и постановка цели урока(1 мин).


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


2.
Повторение ранее изученного материала (11 мин).


Рассмотрим следующую задачу:


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


Решение:
Мы можем записывать наше решение следующим образом : «1 вариант: первая полоса – красная, вторая – синяя, третья – белая.» и т.д. Но это очень долго и не удобно, записывая так, сложно сориентироваться все ли варианты мы записали, и не повторились ли мы где-нибудь. Поэтому очень удобно ввести кодирование, т.е. некоторое условное обозначение перебираемых в задаче объектов. В нашем случае мы заменим первой буквой каждый цвет полосы. Белый соответственно – «Б», красный – «К» и синий – «С».


Введя кодирование, запись решения задачи очень упрощается. Мы имеем множество из трех элементов {Б, К, С}. Нужно составить различные комбинации из трех элементов, при этом порядок элементов учитывается. Например, запись «БКС» будет обозначать, что первая полоса флага – белая, вторая – красная, третья – синяя. Подобные задачи мы уже решали методом непосредственного перебора и построением дерева возможных вариантов.


Задача 2.
При встрече 8 приятелей обменялись рукопожатиями. Сколько всего было сделано рукопожатий?


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


Каждому приятелю даем номер от 1 до 8, а рукопожатия закодируем следующим образом: например число 24 означает что 2-ой приятель пожал руку 4-му. При чем число 35 и 53 означают одно и тоже рукопожатие, и брать будем меньшее из них. Коды рукопожатий мы можем оформить следующей таблицей:


12, 13, 14, 15, 16, 17, 18,


23, 24, 25, 26, 27, 28,


34, 35, 36, 37, 38,


45, 46, 47, 48,


56, 57, 58,


67, 68,


78.


Таким образом, у нас получилось 1+2+3+4+5+6+7=28 рукопожатий.


3. Выполнение задания (30 мин).


После того как учащиеся научились составлять всевозможные наборы, рассмотрим задачу подсчета числа возможных вариантов.


Задача 1.
Группа туристов планирует осуществить поход по маршруту Антоново – Борисово – Власово – Грибово. Из Антоново в Борисово можно сплавиться по реке или дойти пешком. Из Борисово во Власово можно пройти пешком или доехать на велосипедах. Из Власово в Грибово можно доплыть по реке, доехать на велосипедах или пройти пешком. Сколько всего вариантов похода могут выбрать туристы? Сколько вариантов похода могут выбрать туристы при условии, что хотя бы на одном из участков маршрута они должны использовать велосипеды?


Решение:
Построим для этой задачи дерево возможных вариантов:


Пусть у нас «П»-обозначает путь пешком


«Р» - сплавиться по реке


«В» - доехать на велосипедах.



Ответ на второй вопрос также хорошо просматривается по дереву возможных вариантов.


Но эту задачу можно решить по-другому, с помощью рассуждений. Из Антоново в Борисово у нас 2 варианта каким образом продолжать путь, из Борисово во Власово тоже 2 варианта, т.е. на каждый вариант первого участка пути у нас есть по 2 варианта второго участка пути и того на данном этапе у нас будет 2*2=4 варианта выбора способа передвижения. На каждый из этих 4 вариантов существует по 3 варианта способа передвижения по третьему участку пути из Власово в Грибово, т.е. 4*3=12. Ответ в этой задаче мы получили умножением.


Такой способ подсчета называется правилом умножения, он возможен, если дерево возможных вариантов является «правильным»: из каждого узла выходит одно и тоже число веток на одном и том же ярусе.


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


Решение
:
Занумеруем тропы числами от 1 до 4 и построим дерево возможных вариантов:


Чтоб подняться у нас есть 4 тропы (4 варианта) и на каждый из них есть по 3 оставшихся тропы (3 варианта), чтоб спуститься, т.е. 4*3=12 маршрутов подхода к озеру. А теперь представим, что к озеру ведут не 4, а 10 троп. Сколько в этом случае существует маршрутов, если по-прежнему решено спускаться не по той тропе, по которой поднимались. Изобразить дерево возможных вариантов в такой ситуации очень сложно. Гораздо легче решить эту задачу с помощью рассуждений. Подняться к озеру можно по любой из 10 троп, а спускаться по любой из оставшихся 9 троп. Таким образом, всего получим 10*9=90 различных маршрутов похода.


Обе эти задачи мы решили, используя правило умножения,
которое звучит следующим образом: пусть необходимо выполнить к независимых действий, если первое действие мы можем выполнить п1
способами, после чего второе действие можем выполнить п2
способами и т.д. до k
-
го действия, которое можно выполнить п
k
способами, тогда выполнить все k
действия в указанном порядке можно п1
∙
п2
∙
…∙

п
k
способами. Обратить внимание, что, применяя правило умножения, мы учитываем порядок действий. То есть правило умножения применяется для подсчета упорядоченных наборов.


Рассмотрим две задачи:


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


Решение:
На роль капитана может быть выбран любой из 30 учащихся, а его заместитель – любой из 29 оставшихся учеников. Таким образом, получаем 30∙

29 = 870 способов.


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


Решение:
Нам не важно, кто капитан, а кто заместитель, нам нужны всего лишь два участника, поэтому получаем, что у нас каждая пара учащихся в произведении повторяется два раза. Поэтому ответом для второй задачи будет (30∙

29):2.


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


Задача 5.
Из класса нужно выделить одного дежурного, мальчика или девочку. Сколько существует способов для выбора дежурного, если в классе 22 девочки и 18 мальчиков?


Решение:
Выбрать одну девочку из 22 мы можем 22-мя способами, а одного мальчика из 18 можно 18-тью способами. Тогда выбрать одного дежурного мальчика или девочку можно (18+22) способами. Отсюда получаем, что существует 40 способов для выбора дежурного.


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


4. Домашнее задание(2 мин).


1. Пароль состоит из двух букв, за которыми следуют 4 цифры или из 4 букв, за которыми следуют 2 цифры. Сколько можно составить разных паролей, если из 33 букв русского алфавита используются только буквы: а, б, в, г, д, е, ж, и, к, л, м, н, п, р, с, т и все десять цифр? А сколько можно получить разных паролей, если из множества букв исключить дополнительно буквы а, е и с, а к 10 цифрам добавить символ *? C:wwwdoc2htmlworkbestreferat-249029-13972164196688сайтweb3.1.html


5. Подведение итогов урока (1 мин).


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


Урок № 3.

Перестановки, размещения, сочетания.


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


Тип урока:
комбинированный.


Ход урока


1. Организационный момент и постановка цели урока (5 мин).


Сегодня мы с вами познакомимся с такими понятиями как, размещение, перестановка, сочетание, закрепим такие понятия, как правило суммы, правило умножения, познакомимся с формулами для вычислений и научимся их применять для решения задач. Для начала мы проверим домашнее задание.


2. Выполнение задания (35 мин).


Размещения.


Определение.
Пусть имеется множество, содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов.


Рассмотрим задачу .


Задача 1.
Сколькими способами можно составить различные двузначные числа из четырех цифр 1,2,3,4 ?


Решение:
В этой задаче речь идет о размещениях из четырех элементов по два.


1 способ
. Перебор вариантов.


Рассмотрим все такие числа : 12 13 14 23 24 34


21 31 41 32 42 43


Всего таких чисел 12.


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


Если элемент a можно выбрать m способами, а элемент b – n способами, причем любой выбор элемента a отличен от любого выбора элемента b, то выбор “a или b” можно сделать m + n способами.


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


Если из некоторого множества А элемент ai
можно выбрать КA
способами, а элемент bj
из множества В – КB
способами, то совокупность (ai
; bj
) можно образовать КA
* КB
способами. Правило верно и для совокупностей, состоящих из большего, чем два числа элементов.


2 способ
. С применением правила произведения.


Первая цифра числа выбирается 4 способами из данных цифр, а вторая цифра числа выбирается 3 способами (из оставшихся трех цифр). По правилу произведения 4 * 3=12 (способов).


Формула для вычисления числа размещений.


Первый элемент размещения выбирается n способами, второй элемент ( n -1) способами, …, k-ый элемент (n -(k -1)) способами ,т.е. можно ввести формулу для числа вариантов


= (n –1)·(n – 2) …·(n – (k – 1))


или = , где - число размещений из n по k ,


( n! читается n - факториал); n!=1*2*3*….* n ; 0!= 1 по определению;


1!= 1.


3 способ
. Применение формулы для вычисления числа размещений.


= = = 3 · 4 =12 .


Задача 2
. Набирая номер телефона, абонент забыл две последние цифры. Сколько различных вариантов нужно набрать, чтобы дозвониться, если абонент помнит, что цифры различны?


Решение:
= = 9 · 10 = 90


Перестановки.


Определение
. Пусть дано множество N из n объектов. Всевозможные последовательности из всех n объектов называются перестановками.


Задача 1.
Сколькими способами можно рассадить n
человек на n
мест?


Решение:


1 способ
. Перебор вариантов.


1) n = 1. Число возможных вариантов 1.


2) n = 2. Возможные варианты: 12 и 21 , всего их 2.


3) n = 3. Возможные варианты: 123 213 312 132 231 321, всего их 6.


4) n = 4 Возможные варианты: 1234 2134 3124 4123


1324 2314 3214 4213


1432 2431 3421 4321


1243 2341 3142 4132


1342 2143 3241 4231


1423 2431 3412 4312. Всего их 24.


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


= n! т.к. == = = n!.


2 способ
. Применение формулы перестановок.


= 2!=1·2=2; =3!=1·2·3=6 ; =4!=1·2·3·4=24;


3 способ
. Применение правила произведения. (для n = 4)


1. на 1 место человека можно посадить четырьмя способами : 1, 2, 3, 4


2. на 2 место только тремя способами : пример 12 13 14


3. на 3 место только двумя способами : пример 123 124


4. на 4 место только одним способом : пример 1234


всего вариантов: 4·3·2·1=24


Задача 2.
Сколькими способами можно составить расписание одного учебного дня из 6 различных предметов ?


Решение:
= 6!=1·2·3·4·5·6=720


Задача 3.
Сколько различных «слов» можно составить из букв слова математика?


Решение:
В слове математика 10 букв, значит перестановок будет =10! Однако буква а повторяется 3 раза , буква т – 2 раза , буква м – 2 раза и их перестановки не дают новых вариантов, значит


= = =151200


Задача 4.
Для дежурства по классу в течение недели ( кроме воскресения) выделены 6 учащихся. Сколькими способами можно установить очередность дежурств, если каждый учащийся дежурит один раз?


Решение:
P=6!=720.


Задача 5.
Сколько шестизначных чисел, кратных пяти , можно составить из цифр 1,2,3,4,5,6, при условии , что цифры в числе не повторяются?


Решение:
Последняя цифра должна быть 5, предыдущие цифры могут быть составлены из оставшихся пяти цифр 1,2,3,4,6.


Р=5!=120 .

Сочетания.


Определение
. Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее k элементов , называется сочетанием из n элементов по k элементов.


Задача 1.
Сколько наборов из двух книг можно скомпоновать из четырех книг ?


Решение:


1 способ
. Перебор вариантов.


Возможны следующие наборы ( указываются номера книг)


1 2 1 3 1 4


2 3 2 4 3 4


всего 6 наборов.


Формула числа сочетаний.


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


= ,


Замечание: = – формула, связывающая сочетания с размещениями.


2 способ
. Применение формулы для вычисления числа сочетаний.


= = = 6 .


Задача 2.
Сколькими способами можно составить из 14 преподавателей экзаменационную комиссию из 7 членов?


Решение:
.


Задача 3.
Сколькими способами можно выбрать трех дежурных из группы в 20 человек?


Решение:
.


Задача 4.
В вазе стоят 10 белых и 5 красных роз. Сколькими способами можно выбрать из вазы букет , состоящий из двух красных и одной белой розы?


Решение:
(по правилу произведения)


· = =10 · = 100.


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


Решение:
в первом круге =153, во втором круге =153.


Всего 153 ·2 =306 встреч.


Задачи на применение формул комбинаторики.


Задача 1.
В классе 30 учащихся. Сколькими способами можно выделить для дежурства двух человек, если: а) один из них должен быть старшим; б) старшего быть не должно?


Решение:
а) = =29 · 30 =870; б) = =435.


Задача 2.
В хирургическом отделении работают 40 врачей. Сколькими способами из них можно образовать бригаду в составе: а) хирурга и ассистента; б) хирурга и четырех его ассистентов?
Решение:
а) 1 способ. = = 40 · 39 = 1560 ;

2 способ. 40 · =40 · = 40 · 39 = 1560 ;


б) 40 · = 40 · = = 3290040 .


3. Домашнее задание (3 мин).


1. Из коллектива работников в 25 человек нужно выбрать председа­теля, заместителя, бухгалтера и казначея. Каким количеством спосо­бов это можно сделать?


2.Сколько различных слов (пусть и не имеющих смысла) можно по­лучить путем перестановки букв в слове "ДУБЛЕНКА"?


3. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?


4. Подведение итогов урока (2 мин).


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


Всем спасибо за работу. До свидания.


Урок № 4.

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


Цели:
познакомиться с размещениями, перестановки и сочетаниями с повторениями, научиться применять новые формулы для решения задач.


Тип урока:
комбинированный


Ход урока


1. Организационный момент и постановка цели урока (5 мин).


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


2. Выполнение задания (10 мин).


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


Пусть даны элементы а1
,а2
, . . . ,аn
(а)


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


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


Каждый элемент может быть выбран n способами, поэтому : = ,где -обозначение размещений с повторениями .


Пример: размещения с повторениями из 4 элементов 1 , 2 , 3 и 4 по 3:


111; 112; 121; 211; и т.д.


= 4= 64.


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


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


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


(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.


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


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


Пример: сочетания с повторениями из четырех элементов 1,2,3,4, по два


11 12 13 22 32 14 24 33 34 44


( всего их 10)


= - формула сочетаний с повторениями.


= = = = 10.


3. Первичное закрепление(20 мин).


Задачи на применение формул комбинаторики.


Задача 1.
Сколько различных двухзначных чисел можно образовать из цифр 1,2,3,4?


Решение:
= = 16 .


Задача 2.
Сколько различных двухзначных чисел можно образовать из цифр 1,2,3, при условии, что все цифры различны?


Решение:
= = = 12 .


Задача 3.
Автомобильные номера состоят из тех букв (всего 30 букв) и четырех цифр (используется 10 цифр). Сколько автомобилей можно занумеровать таким способом, чтобы никакие два автомобили не имели одинаковые номера?


Решение:
Это размещение с повторениями. Применим правило произведения: = = .


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


Решение:
C:wwwdoc2htmlworkbestreferat-249029-13972164196688сайтweb3.14.html


C:wwwdoc2htmlworkbestreferat-249029-13972164196688сайтweb3.3.html Задача 5.
У школьника 2 авторучки, 4 карандаша и 1 резинка. Он раскладывает эти предметы на парте в ряд. Сколько вариантов раскладки?


Решение:
C:wwwdoc2htmlworkbestreferat-249029-13972164196688сайтweb3.14.html Р(2,4,1)=7!/(2!4!1!)=5*6*7/2=105.


Задача 6.
Рыбаки поймали 5 подлещиков, 4 красноперки и 2 уклейки, посолили и вывесили на солнце сушиться. Сколько вариантов развешивания рыбы на нитке?


Решение:
C:wwwdoc2htmlworkbestreferat-249029-13972164196688сайтweb3.14.html Р(5,4,2)=11!/(2!4!5!)=11*10*9*8*7*6/(2*2*3*4)=11*10*9*7=6930.


C:wwwdoc2htmlworkbestreferat-249029-13972164196688сайтweb3.4.htmlЗадача 7.
Сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?


Решение:
= = = = =120.


4. Проверка знаний (5 мин).


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


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


I вариант II вариант




5. Домашнее задание(3 мин).


Дома повторите то, что мы проходили на прошлом уроке, а также решите задачи:


1. На почте имеется 5 типов марок одинакового достоинства. На конверт нужно наклеить 3 марки. Сколько существует различных ком­бинаций наклейки марок на конверт, если порядок наклейки марок име­ет значение?


2.Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?


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


6. Подведение итогов урока (2 мин).


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


Урок № 5.

Свойства сочетаний и их применение для упрощения выражений.


Цели:
познакомиться со свойствами сочетаний,закрепить пройденный ранее материал, научиться решать неравенства, а также проверить оценку (контроль) знаний.


Тип урока:
комбинированный


Ход урока


1. Организационный момент и постановка цели урока (1 мин).


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


2. Повторение ранее изученного материала (3 мин).


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


Задачи.


1.Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?


2. На почте имеется 5 типов марок одинакового достоинства. На конверт нужно наклеить 3 марки. Сколько существует различных комбинаций наклейки марок на конверт, если порядок наклейки марок имеет значение?


3. Выполнение задания (20 мин).


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


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


1.


2.


3. .


4. .


5. .


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


.


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


Задача 1. Упростить выражение: .


Решение: = = = = 1.


Задача 2. Вычислить:


а) ,


б) .


Решение: а) = = = 1 .


б) = = 7 = 56 .


Задача 3. Решить уравнение:


= 20 .


Решение: = 20; = 20 , при этом x + 1 , а x .


= 20; = 20; x= 20;



х1
не подходит, а х2
подходит.


Ответ: х = 4 .


Задача 4. Решить неравенство .


Решение неравенства :;


; ОДЗ:








- + - +


0 2 7 x с учетом ОДЗ:


Ответ : 3;4;5;6;7.


4. Закрепление ранее изученного материала.


Самостоятельная работа (20 мин).


Найдите: Ответ: 0 .


Решить неравенство: < 24 . Ответ: 1;2;3.


Решить систему уравнений: Ответ: (18;8).


5. Подведение итогов урока(1 мин).


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


Всем спасибо за работу. До свидания.


Урок № 6.

Формула бинома Ньютона. Свойства биноминальных коэффициентов. Треугольник Паскаля.


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


Тип урока:
комбинированный


Ход урока


1. Организационный момент и постановка цели урока (1 мин).


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


2. Повторение ранее изученного материала (6 мин).


Перед тем, как приступить, повторим, что мы прошли на предыдущих уроках.


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


· напишите к ним формулы;


· выпишите свойства сочетаний.


3. Выполнение задания (35 мин).


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


Биномом Ньютона называют формулу представляющую выражение


при целом положительном n
в виде многочлена.


Знакомые формулы :



Бином Ньютона :


Можно проверить для n = 2: .


для n = 3 :.


Формулы выполняются.


Числа называются биномиальными коэффициентами.


Задача 1.



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


Биномиальные коэффициенты можно получить, пользуясь только сложением, следующим образом.


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


1 C00


1 1 C10 C11


1 2 1 C20 C21 C22


1 3 3 1 C30 C31 C32 C33


1 4 6 4 1 C40 C41 C42 C43 C44


1 5 10 10 5 1 C50 C51 C52 C53 C54 C55


1 6 15 20 15 6 1 C60 C61 C62 C63 C64 C65 C66


1 7 21 35 35 21 7 1 . . .


1 8 28 56 70 56 28 8 1 и т.д.


1 9 36 84 126 126 84 36 9 1


. . .


и т.д.


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


1)коэффициенты членов, равноудаленных от концов разложения, одинаковы.


2)сумма коэффициентов разложения (a + b)равна 2.


Например:


3) сумма коэффициентов стоящих на нечетных местах, равна сумме коэффициентов, стоящих на четных местах и составляет: 2.


Например: 1+ 15 + 15 + 1 = 2;


6 + 20 + 6 = 32 = 2.


Задача 1.
Найти рациональные члены в разложении


Решение:
24 = 14 +10.


Рациональным является член:


Задача 2.
Найдите коэффициенты при в разложении


Решение:


будет в слагаемых:


Итого: 3360 + 4320+ 405= 8085.


Ответ: 8085.


4. Домашнее задание(2 мин).


1. Найдите коэффициенты разложения:


а.


б.


5. Подведение итогов урока (1 мин).


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


Всем спасибо за работу. До свидания.


Урок № 7.

Практикум по теме «Формула бинома Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля».


Цели:
закрепить полученные знания по теме «Бином Ньютона и треугольник Паскаля».


Тип урока:
комбинированный


Ход урока


1. Организационный момент и постановка цели урока (1 мин).


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


2. Повторение ранее изученного материала (7 мин).


Перед тем, как приступить к решению заданий, напишите на листочках в течении 7 мин. Формулу бинома Ньютона, треугольник Паскаля, для n=5 и свойства биноминальных коэффициентов.


3. Выполнение задания (35 мин).


1. Раскройте скобки и упростите выражение.


а) (х + )6
; в) (х - )5
;


б) (2 + )5
; г) (- 3)4
.


2. Найдите показатель степени бинома


а) ( + )n
, если второй член разложения не зависит от х.


б) ( + х)n
, если третий член разложения не зависит от х.


3. Найдите член разложения бинома


а) ( +)n
, содержащий х в первой степени, если сумма всех биномиальных коэффициентов равна 512.


б) ( +)n
, содержащий х в первой степени, если сумма всех биномиальных коэффициентов равна 128.


4. В разложении бинома


а) ( + )n
третий биномиальный коэффициент в 4 раза больше второго. Найдите член разложения, содержащий .


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


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









№2






№3







 128 = 27
; n =7.








4. Домашнее задание(1 мин).


На следующем уроке у нас проверочная работа в виде теста. Дома повторите пройденный материал.


5. Подведение итогов урока (1 мин).


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


Всем спасибо за работу. До свидания.


Урок № 8.

Тест к разделу «Комбинаторика».


Цели:
проверить знания по данному разделу и подготовиться к итоговой контрольной работе.


Тип урока:
проверка знаний


Ход урока


1. Организационный момент и постановка цели урока (3 мин).


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


Тест может быть роздан на листочках, а может выполняться на компьютерах, если есть такая возможность.


2. Выполнение задания(40 мин).


1.В розыгрыше первенства страны по футболу принимает участие 16 команд. Сколькими способами могут быть распределены золотая и серебряная медали?


Выберите букву правильного ответа.


А) 256; Б) 31; В) 240; Г) 16.


2. Из Перми до Чайковского можно добраться теплоходом, поездом, автобусом, самолётом; из Чайковского до Ижевска - теплоходом или автобусом. Сколькими способами можно осуществить путешествие по маршруту Пермь - Чайковский - Ижевск?


Выберите букву правильного ответа.


А) 6; Б) 8; В) 12; Г) 32.


3. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?


А) 41; Б) 240; В)17; Г) 1024.


4. Из семи заводов организация должна выбрать три для размещения трех различных заказов. Сколькими способами можно разместить заказы?


Выберите букву правильного ответа.


А) 256; Б) 21; В) 210; Г) 343.


5. Риэлтерская фирма предлагает на продажу 5 больших квартир и 4 малогабаритных квартиры. Банк намеревается купить 4квартиры, причём среди них не должно быть более двух малогабаритных. Сколько вариантов выбора имеет банк?


Выберите букву правильного ответа.


А) 105; Б) 75; В) 20; Г) 160.


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


Выберите букву правильного ответа.


А) 38650; Б) 1739100; В) 42110; Г) 2903040.


7. Автокомбинат имеет 7 автомобилей малой грузоподъёмности и 10 большегрузных автомобилей. Нужно выбрать 3 автомобиля малой грузоподъёмности для обслуживания трёх торговых организаций и 5 большегрузных автомобилей для работы на стройке. Сколькими способами автокомбинат может осуществить свой выбор?


Выберите букву правильного ответа.


А) 19448; Б) 211680; В)8820; Г) 25401600


8. Имеется пять кусков материи разных цветов. Сколько из этих кусков можно сшить различных флагов, если флаги состоят из трёх горизонтальных полос, причём две соседние полосы должны быть разного цвета? Задача III.


Выберите букву правильного ответа.


А) 40; Б) 10; В) 240; Г) 160.


9. Сколько существует различных вариантов рассадки n человек за круглым столом, причём один вариант отличается от другого тем, что хотя бы у одного человека при разных вариантах разные соседи слева.


Выберите букву правильного ответа.


А) n!; Б) (n-1)!; В) (n-2)!; Г) n.


10. Сколько различных раскладов можно получить, раздавая колоду из 52-х карт четырём игрокам?


Выберите букву правильного ответа.


А); Б); В) ; Г).


11. Сколько различных раскладов можно получить, раздавая колоду из 52-х карт четырём игрокам, при условии, что каждый игрок получает одного туза?


Выберите букву правильного ответа.


А); Б) ; В) ; Г) .


12. У Деда Мороза в мешке 7 различных подарков, которые можно произвольным образом распределить среди 5-ти детей. Сколькими способами можно это сделать?


Выберите букву правильного ответа.


А) 35; Б) 21; В) 16807; Г) 78125.


13. Сколькими способами можно разложить 5 разноцветных шаров по 3-м ящикам?


Выберите букву правильного ответа.


А) 256; Б) 10; В) 243; Г) 20.


14. Директор фирмы составил список из 5-ти человек, которых он может назначить на вакантную должность своего заместителя, и список из 4-х человек, которых он может назначить на вакантную должность главного бухгалтера. В оба списка вошёл сотрудник Иванов. Других пересечений этих списков не оказалось. Сколько вариантов заполнения двух вакантных должностей имеет директор?


Выберите букву правильного ответа.


А) 126; Б) 19; В) 20; Г) 21.


15. У одного человека есть 7 книг, а у другого — 9 книг. Сколькими способами они могут обменять три книги одного на три книги другого?


Выберите букву правильного ответа.


А) 119; Б) 50803200; В) 2940; Г) 63.


16. Бригада строителей состоит из 16-ти штукатуров и 4-х маляров. Сколькими способами бригаду можно разделить на две бригады, чтобы в одной из них было 10 штукатуров и 2 маляра, а в другой 6 штукатуров и 2 маляра?


Выберите букву правильного ответа.


А) 48048; Б) 59764; В) 3406; Г) 4406.


17. Упростить выражение: .


Выберите букву правильного ответа.


А) 1; Б) 16; В) 457; Г) 6000.


18. Вычислить:


б) .


Выберите букву правильного ответа.


А) 1; Б) 12; В) 84; Г) 56.


19. Решить уравнение:


= 20 .


Выберите букву правильного ответа.


А) 570; Б) 4; В) 25; Г) 9.


20. Найдите четвертый член разложения.


Выберите букву правильного ответа.


А) 35a3
b4
; Б) 15a5
b2
; В) 35a4
b3
; Г) 15a2
b5
.


21. Найдите показатель степени бинома


а) ( + )n
, если второй член разложения не зависит от х.


Выберите букву правильного ответа.


А) 8; Б) 9; В) 10; Г) 16.


22. Найдите член разложения бинома


а) ( +)n
, содержащий х в первой степени, если сумма всех биномиальных коэффициентов равна 512.


Выберите букву правильного ответа.


А) 256x; Б) 31x; В) 84х; Г) 16x.


Ответы:
1.В), 2. Б), 3. Г), 4. В), 5. А), 6. Г), 7. Б), 8. А), 9. Б), 10. А), 11. Б), 12. Г), 13. В), 14. Б), 15. В), 16. А), 17. А), 18. Г), 19. Б), 20. В), 21. А), 22.В).


3. Подведение итогов урока(2 мин).


На сегодняшнем уроке мы с вами провели проверочную работу, на следующем уроке мы перейдём к новому разделу «Случайные события»


2.4. Электронный учебник


Данное электронное пособие было разработано для того, чтобы изучение темы «Основы комбинаторики» было более успешным.


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


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


В теоретической части рассматриваются такие основные элементы клас­сической комбинаторики как размещения, перестановки и сочетания, а также основные правила комбинаторики и свойства сочетаний.



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



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


Также в электронном приложении разработан тест, который позволит ученику проверить свой уровень знаний по теме «Основы комбинаторики». В тесте представлено 15 заданий. Задания подобраны так, чтобы охватить весь теоретический материал учебника, и направлены именно на подсчеты количества возможных вариантов. В каждом задании только один правильный вариант ответа. Все задания представлены в закрытой форме.



Заключение


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


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


В процессе работы над дипломом было разработано поурочное планирование элективного курса. Также были разработаны подробные конспекты восьми занятий к разделу «Элементы комбинаторики».


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


Таким образом поставленные цель и задачи были достигнуты.


Список использованной литературы


1. Бунимович Е.А. Вероятностно-статистическая линия в базовом школьном курсе математики // Математика в школе. – 2002. - №3.


2. Бунимович Е.А., Булычев В.А. Вероятность и статистика 5-9 кл.: пособие для общеобразовательных учебных заведений. – М.: Дрофа, 2002.


3. Бунимович Е.А., Суворова С.Б. Методические указания к теме «Статистические исследования». / Математика в школе.- 2003.- №3


4. Виленкин Н.Я. Комбинаторика//– М.: Наука, 1969. – 328 с.: ил.


5. Виленкин Н.Я. Популярная комбинаторика//– М.: Наука, 1975. – 209 с.


6. Ерош И.Л. Дискретная математика. Комбинаторика//– СПбГУАП.СПб.,2001. – 31с.


7. Зубарева И.И., Мордкович А.Г. Математика. 5 кл.: учебник для общеобразоват. Учреждений. – М.: Мнемозина, 2003.


8. Зубарева И.И., Мордкович А.Г. Математика. 6 кл.: учебник для общеобразоват. Учреждений. – М.: Мнемозина, 2003.


9. Изучение теории вероятностей и статистики в школьном курсе математики. Программа для курсов повышения квалификации учителей [текст]/ Булычев В.А., Бунимович Е.А.// Математика в школе. – 2003.-№4.


10. Макарычев Ю.Н. Алгебра: элементы статистики и теории вероятностей: учебное пособие для учащихся 7-9 классов общеобразовательных учреждений / Ю.Н.Макарычев, Н.Г.Миндюк. Под ред. С.А.Теляковского – М.: Просвещение. – 2003.


11. Макарычев Ю.Н., Миндюк Н.Г. Изучаем элементы статистики. // Математика в школе. – 2004. – №5.


12. Макарычев Ю.Н., Миндюк Н.Г. Элементы комбинаторики. // Математика в школе. – 2004. – №6.


13. Макарычев Ю.Н., Миндюк Н.Г. Начальные сведения из теории вероятностей в школьном курсе алгебры. // Математика в школе. – 2004. – №7.


14. Математика: Учеб. Для 5 кл. общеобразоват. учреждений / Г.В.Дорофеев, И.Г.Шарыгин, С.Б.Суворова и др.; Под ред. Г.В.Дорофеева, И.Г.Шарыгина. – М.: Просвещение, 2000.


15. Математика. 6 класс: Учеб. для общеобразоват. учеб. заведений / Г.В.Дорофеев, И.Г.Шарыгин, С.Б.Суворова и др.; Под ред. Г.В.Дорофеева, И.Г.Шарыгина. – М.: Дрофа, 1997.


16. Математика. Арифметика. Алгебра. Анализ данных. 7 класс: Учеб. для общеобразоват. учеб. заведений / Г.В.Дорофеев, С.Б.Суворова, Е.А.Бунимович, Л.В. Кузнецова, С.С.Минаева; Под ред. Г.В.Дорофеева. – М.: Дрофа, 1997.


17. Математика. Алгебра. Функции. Анализ данных. 8 класс: Учеб. для общеобразоват. учеб. заведений / Г.В.Дорофеев, С.Б.Суворова, Е.А.Бунимович, Л.В. Кузнецова, С.С.Минаева; Под ред. Г.В.Дорофеева. – М.: Дрофа, 1999.


18. Математика. Алгебра. Функции. Анализ данных. 9 класс: Учеб. для общеобразоват. учеб. заведений / Г.В.Дорофеев, С.Б.Суворова, Е.А.Бунимович, Л.В. Кузнецова, С.С.Минаева; Под ред. Г.В.Дорофеева. – М.: Дрофа, 2000.


19. Мордкович А.Г, Семенов П.В. События. Вероятности. Статистическая обработка данных: дополнительные параграфы к курсу алгебры 7-9кл. общеобразоват. Учреждений. – М.: Мнемозина, 2003.


20. Студенецкая В.Н., Фадеева О.М. Новое пособие по теории вероятностей для основной школы. // Математика в школе. - 2004. - №7


21. Студенецкая В.Н., Фадеева О.М. Статистика и теория вероятностей на пороге основной школы. // Математика в школе. - 2004. - №6.


22. Ткачева М.В. Анализ данных в учебнике Н.Я. Виленкина и других. // Математика в школе. – 2003. - №5


23. Ткачева М.В. Элементы статистики и вероятность: учебное пособие для учащихся 7-9 классов общеобразовательных учреждений / М.В.Ткачева, Н.Е.Федорова. – М.: Просвещение, 2004.


24. Ткачева М.В., Василькова Е.Н., Чуваева Т.В О готовности учащихся к изучению стохастики // Математика в школе. – 2003. - №9.


25. Ткачева М.В., Федорова Н.Е. Элементы стохастики в курсе математики VII-IXклассов основной школы.[текст] // Математика в школе. - 2003.-№3


26. Тюрин Ю.Н. Теория вероятностей и статистика [текст] / Ю.Н.Тюрин, А.А.Макаров, И.Р.Высоцкий, И.В.Ященко – М.:МЦНМО: АО «Московские учебники», 2004.


27. http://festival.1september.ru/


28. http://www.edu.yar.ru/russian/pedbank/
Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Изучение основ комбинаторики и теории вероятностей

Слов:19576
Символов:158818
Размер:310.19 Кб.