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

Курс по выбору «Комбинаторика» Урок № 5. Тема:    Размещения     Цель занятия: Познакомить учащихся  с понятием «размещения». Вывести  формулу для подсчёта числа размещений. Научить решать задачи  на размещения. Наглядность и раздаточный материал:  Презентация № 3 1. Повторение (по слайдам) 1) Факториал 2) Перестановки 3) Проверка домашнего задания 2. Размещения Задача. Имеется множество чисел N = {1,2,3,4,5}.  а) Сколько существует пятизначных чисел, все цифры которых различны?  Решение: Данные комбинации чисел будут перестановками,  Р5 = 5! = 120 б) Сколько существует трёхзначных чисел, все цифры которых различны?  Решение:  Это   уже   не   перестановки.   Первую   цифру   можно   выбрать   5 способами, вторую – четырьмя, третью цифру – тремя   способами, т.е. число трёхзначных чисел будет 5 4  3 =  60 в)   Сколько   существует   четырёхзначных   чисел,   все   цифры   которых различны?  Решение:   Это   также   не   перестановки.   Первую   цифру   можно   выбрать   5 способами,   вторую   –   четырьмя,   третью   цифру   –   тремя     способами, четвёртую – двумя способами, т.е. число четырёхзначных чисел будет  5 4  3  2 =  120 Имеется  n  различных   предметов.   Сколько   из   них   можно   составить  k­ расстановок?   При   этом   две   расстановки   считаются   различными,   если   они   либо отличаются   друг   от   друга   хотя   бы   одним   элементом,   либо   состоят   из одних и тех же элементов, но расположенных в разном порядке. Такие комбинации, отличающиеся друг от друга порядком элементов и составом,  называются размещениями.  ОПРЕДЕЛЕНИЕ:  Размещением  из n элементов  по k (k    n) называется любое   подмножество   данного   множества,   состоящее   из   любых   k элементов, взятых в определённым порядке из данных n элементов.  Число размещений из n элементов по k обозначают  k). Размещения – это упорядоченные подмножества данного множества.  По   правилу   произведения   число   упорядоченных  k­элементных подмножеств   множества  N,   состоящего   из   n   элементов,   находится   как nА   (читают А из n по k произведение чисел: n (n – 1) (n – 2) (n – 3)….( n – k + 1).  Или число размещений из n элементов по k вычисляется по формуле: Аk n  n !  kn ( )! Можно сказать что размещения из п элементов по п – это перестановки из п­элементов. Сравним число таких комбинаций, вычисленное по формуле размещений и по формуле перестановок: Аn n , т.е. Pn = n!    ! n ! n  nn ( )! n ! !0 Изучением   «размещений»   впервые   занимался   Якоб   Бернулли   во   второй части   своей   знаменитой   книги   «Искусство   предугадывания», опубликованной в 1713 г. Он же ввел соответствующий термин.   Яков (Якоб) Бернулли Математик,   физик,   астроном   и   механик Яков   Бернулли   (1654   —   1705)   родился   в Базеле (Швейцария).    Бернулли, Отец хотел, чтобы сын был священником, и поэтому   Я.   поступив   в Базельский университет, в основном изучал теологию   и   языки.   Он   владел   немецким, французским,   английским,   итальянским, латинским и греческим языками. Но больше всего его привлекала математика, которую он   изучал   тайком   от   отца.   Наиболее значительные   достижения   Якова   I   в   развитии   анализа   бесконечно   малых, теории рядов, вариационного исчисления и теории вероятностей. В 1687г., ознакомившись   с   первыми   работами  Г.Лейбница  по   дифференциальному исчислению (1684г.), Бернулли применил новые идеи к изучению свойств ряда кривых: логарифмические спирали, открытой им лемнискаты, цепной линии и др.   Определил   площадь   сферического   треугольника,   вычислил   площади конусоидальных   и   сфероидальных   поверхностей,   произвел   многочисленные квадратуры и спрямления. Книга Бернулли "Арифметические приложения о бесконечных  рядах  и  их  конечных  суммах" (1689­1704гг.)  явилась   первым руководством по теории рядов. Бернулли – это целая семья математиков. Совместно   с   братом  Иоганном   I,   Яков   положил   начало   вариационному исчислению. Выдвинул и частично решил изопериметрическую задачу и задачу о   брахистохроне,   или   кривой   быстрейшего   спуска,   поставленную   братом Иоганном.   В   труде   "Искусство   предложения"   Яков   I   в   1713г.   решил некоторые   задачи   комбинаторики;   открыл   числа,   позднее   названные   числа Бернулли; доказал так называемую теорему Бернулли ­ частный случай закона больших   чисел,   имеющего   большое   значение   в   теории   вероятностей   и   ее приложениях к статистике; построил математическую модель для описания серии   независимых   испытаний   (схема   Бернулли).   Благодаря   его   работам теория   вероятностей   приобрела   важнейшее   значение   в   практической деятельности. А 2 4 3. Решение задач Задача № 1. Сколько двузначных чисел можно составить из чисел 1,2,3,4? Это размещения из 4 элементов по 2.  Задача № 2.  Сколько всего 7­значных телефонных номеров, в каждом из которых цифры не повторяются? Это размещения из 10 элементов по 7.   Задача № 3. Сколькими способами могут занять 1, 2, 3 места 8 команд ­  участниц городского турнира по волейболу?  А  87654321  4321  21 )!24(   !4  !4 !2 336  12  3 8 !8  )!38( !8 !5  54321 Задача 4. Сколько двузначных чисел, цифры которых разные,  можно составить из чисел 0,1,2,3,4,5,6,7,8,9? Это размещения из 10 по 2, но нужно исключить те числа, первая цифра которых 0, таких чисел 9.  А 2 10 9 !10  10( )!2  9 9 !10 !8 10987654321   87654321  90 9 9 81 4. Тест 3 5. Домашнее задание к уроку 5. 1) В   классе   25   человек.   Сколькими   способами   можно   выбрать старосту и физорга? 2) Сколько   можно   сшить   различных   трёхцветных   флажков,   если имеются ткани пяти цветов? 3) Сколько   существует   различных   семизначных   телефонных номеров? (цифры могут повторяться)