Комбинаторика
.pdf
Треугольник Паскаля. Бином Ньютона Треугольник Паскаля
ПАСКАЛЬ, БЛЕЗ (1623–1662), французский религиозный мыслитель, математик и физик, один из величайших умов 17 столетия.
Его дарования проявились очень рано: в 12 лет он самостоятельно, пользуясь собственным словарем и схемами, которые рисовал в комнате для игр, пришел к некоторым геометрическим выводам и
доказал 32-й теорему Евклида о сумме углов треугольника. В 16 лет он написал замечательный Опыт о конических сечениях, содержащий теорему (называемую теперь теоремой Паскаля), согласно которой во всяком шестиугольнике, вписанном в эллипс, гиперболу или параболу, точки пересечения трех пар противоположных сторон лежат на одной прямой. Чтобы облегчить отцу трудоемкие финансовые расчеты (его отец работал в Палате по сбору налогов),
Блез придумал машину, способную складывать |
и |
вычитать, |
прообраз |
|
механического калькулятора. Сконструировав за |
несколько |
лет |
около 50 |
|
образцов арифметической машины, Блез в 1649 |
г. |
получил |
королевскую |
|
привилегию на свое изобретение – «Паскалево колесо». Машина в своем окончательном виде помещалась в небольшом продолговатом ящике и была проста в работе.
Паскаль написал несколько работ по теории вероятностей, что впоследствии оказало принципиальное влияние на развитие современной экономики и социологии. В историю физики Паскаль вошел, установив основной закон гидростатики и подтвердив предположение Торричелли о существовании атмосферного давления. В честь Паскаля названа единица
31
измерения давления системы СИ. Кроме того, его имя носит один из языков программирования Pascal, а также способ расположения биномиальных
коэффициентов в таблицу — треугольник Паскаля, |
которому он посвятил своё |
|||||||||
|
|
1 |
|
|
|
сочинение |
«Трактат |
об |
||
|
|
1 |
1 |
|
|
арифметическом |
|
|
||
|
1 |
2 |
1 |
|
|
треугольнике». |
|
|
|
|
|
1 |
3 |
3 |
1 |
|
|
|
|
|
|
1 |
4 |
6 |
4 |
|
1 |
|
Треугольник |
Паскаля |
– |
|
1 |
1 |
10 |
10 |
5 |
1 |
это |
числовая |
таблица |
||
треугольной формы. Она была известна ещё учёным Древней
Индии, но её заново открывали и изучали многие математики.
«Заметили ли вы какую-нибудь закономерность? А правило составления этого треугольника? Откуда берутся эти числа и где они встречаются?» Иногда треугольник Паскаля записывают иначе:
n |
|
|
|
|
|
|
|
|
0 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
2 |
1 |
2 |
1 |
|
|
|
|
|
3 |
1 |
3 |
3 |
1 |
|
|
|
|
4 |
1 |
4 |
6 |
4 |
1 |
|
|
|
5 |
1 |
5 |
10 |
10 |
5 |
1 |
|
|
6 |
1 |
6 |
15 |
20 |
15 |
6 |
1 |
|
7 |
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
Продолжите ещё два ряда в треугольнике Паскаля. Оказывается это коэффициенты разложения двучлена (a + b)n
32
Вычислим: C21 ,C22 ,C31 ,C32 ,C33 . Сравним с числами из таблицы. Не вычисляя, назовите чему равно C42 ,C43 ,C54 ,C62 ,C74
Бином Ньютона
Исаак НЬЮТОН (1643-1727 г.г.), английский математик, механик, астроном и физик, создатель классической механики, один из основоположников современной физики, сформулировал основные законы механики и был фактическим создателем единой физической программы описания всех физических явлений на базе механики; открыл закон всемирного тяготения, объяснил движение планет вокруг Солнца и Луны вокруг Земли, а также приливы в океанах, заложил
основы механики сплошных сред, акустики и физической оптики. Построил зеркальный телескоп.
Исаак Ньютон появился на свет в небольшой деревушке в семье мелкого фермера, умершего за три месяца до рождения сына. Младенец был недоношенным; бытует легенда, что он был так мал, что его поместили в овчинную рукавицу, лежавшую на лавке, из которой он однажды выпал и сильно ударился головой об пол.
Ньютон рос болезненным и необщительным, склонным к мечтательности. Его привлекала поэзия и живопись, он, вдали от сверстников, мастерил бумажных змеев, изобретал ветряную мельницу, водяные часы, педальную повозку. Трудным было для Ньютона начало школьной жизни. Учился он плохо, был слабым мальчиком, и однажды одноклассники избили его до потери сознания. Переносить такое унизительное положение было для самолюбивого Ньютона невыносимо, и оставалось одно: выделиться успехами в учебе. Упорной работой он добился того, что занял первое место в классе.
33
После серьезной подготовки Ньютон в 1660 г. поступил в Кембридж. Интерес к технике заставил Ньютона задуматься над явлениями природы. Он серьёзно занялся наукой. Многие из проведенных им экспериментов (а их насчитывается более тысячи) стали классическими и повторяются и сегодня в школах и институтах. Его труды намного опередили общий научный уровень того времени и были малопонятны его современникам.
В области математики он является автором бинома Ньютона и создателем (одновременно с Лейбницем, но независимо от него) метода флюксий — того, что ныне называется дифференциальным и интегральным исчислением.
Бином – двучлен. Бином Ньютона – формула, выражающая степень двучлена в виде суммы одночленов. Блез Паскаль доказал, что коэффициенты
разложения (a + b)n равны Сnk - числу сочетаний из n по k.
(a + b)n = a n + Cn1 a n− 1b + Cn2 a n− 2b2 + ... + Cnk an− k bk + ... + bn (*)
|
|
(a + b) |
2 |
= a |
2 |
+ 2ab + b |
2 |
|
|
|
|
|
|
|
|
(1,2,1) |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
(a + b) |
3 |
= a |
3 |
+ 3a |
2 |
b + 3ab |
2 |
+ b |
3 |
|
|
|
(1,3,3,1) |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
(a + b) |
4 |
= a |
4 |
+ 4a |
3 |
b + 6a |
2 |
b |
2 |
+ 4a b |
3 |
+ b |
4 |
(1,4,6,4,1) |
||||||||||||||||||
И. Ньютон доказал, что формула (*) разложения бинома в сумму выполняется не только для целых степеней, но и для отрицательных, и для дробных степеней. Поэтому таблица биномиальных коэффициентов – треугольник Паскаля, а формула разложения (*) – это бином Ньютона.
Свойства бинома Ньютона:
1)Число слагаемых на 1 больше степени
2)Коэффициенты находятся по треугольнику Паскаля
34
3)Коэффициенты симметричны
4)Если в скобке знак минус, то знаки + и – чередуются
5)Сумма степеней каждого слагаемого равна степени бинома
Упражнения
Раскрыть скобки:
а) (х + у)5 ; б) (c + d)6; в) (m – n)7; г) (a – b)8 ; д) (c + 1)4 ; е) (x + 2)5
Начальные сведения по теории вероятностей
События в материальном мире можно разбить на три категории – достоверные, невозможные и случайные.
Во многих играх используется игральный
кубик.
У кубика 6 граней, на каждой грани отмечено различное количество точек – от 1 до 6. Бросание кубика можно считать опытом, экспериментом,
испытанием, а полученный результат – исходом испытания или элементарным событием. Людям интересно угадывать наступление того или иного события, предсказывать его исход. Какие предсказания они могут сделать, когда бросают игральный кубик? Например, такие:
1)событие А – выпадает цифра 1, 2, 3, 4, 5 или 6;
2)событие В – выпадает цифра 7, 8 или 9;
3)событие С – выпадает цифра 1.
Событие – исход наблюдении или эксперимента. Событие А обязательно наступит.
Событие, которое в данном опыте обязательно наступит, называют достоверным событием.
Например, если стакан с водой перевернуть вверх дном, то вода выльется.
35
Событие В никогда не наступит, это просто невозможно.
Событие, которое в данном опыте наступить не может, называют невозможным событием.
А как вы думаете, событие С наступит или не наступит? На этот вопрос мы с полной уверенностью ответить не в состоянии, поскольку цифра 1 может выпасть, а может и не выпасть.
Событие, которое в данном опыте может, как наступать, так и не наступить, называют случайным событием.
Упражнения
Определите достоверные, невозможные и случайные события
A.– два попадания в цель при трёх выстрелах;
B.– выплата рубля семью монетами;
C.– наугад выбранное трёхзначное число не больше 1000;
D.– появление 17 очков при бросании трёх игральных кубиков;
E.– команда школы по волейболу будет чемпионом города
Определение:
Раздел математики, в котором изучаются случайные события и закономерности, которым они подчиняются, называется теорией вероятности.
Проделаем простейший опыт – подбросим монету и посмотри, что выпадет: герб или цифра (говорят – орёл или решка). Ваши предположения?
Оказывается, этот опыт проделывали многие учёные. Французский естествоиспытатель Ж. Бюффон в XVIII веке провел опыт с монетой 4040 раз, герб выпал 2048 раз. Математик К. Пирсон в XIХ веке провёл 24000 испытаний, герб выпал 12012 раз. Какой напрашивается вывод? Число выпадения герба и цифры примерно одинаково.
Впервые основы теории вероятностей были изложены последовательно французским учёным П. Лапласом.
36
ЛАПЛАС Пьер Симон (1749-1827), французский астроном, математик, физик, иностранный почетный член Петербургской АН. Автор классических трудов по теории вероятностей и небесной механике (динамика Солнечной системы в целом и ее устойчивость и др.)
Также теорией вероятности занимались: Б. Паскаль, французский математик А. Муавр, русские математики В.Я. Буняковский, П.Л. Чебышев, А.А. Марков и др.
Большое число вероятностных задач возникает при проведении экспериментов, при планировании, в статистике.
Классическое определение вероятности случайного события (дано П. Лапласом):
Вероятностью случайного события А называется отношение числа возможных благоприятных событий к числу всех возможных событий, где n – общее число равновероятных событий, m – число благоприятных событий .
p(A) = mn
Свойства вероятностей:
∙Вероятность достоверного события равна единице.
∙Вероятность невозможного события равна нулю.
∙Вероятность случайного события принимает значения от 0 до 1.
Упражнения.
1)Определить вероятность выпадения герба при бросании монеты. Р(А) = 12
2)Какова вероятность того, что при бросании двух игральных костей выпадут две «шестёрки»?
1
Р(А)= 36
37
(Число возможных вариантов выпадения очков первого кубика 6, второго – тоже 6, всего возможных исходов 6 × 6 = 36)
3) В ящике лежат 10 шариков: 3 белых, 2 красных, 5 синих.
Какова вероятность того, что вытащенный наугад шар красного
цвета?
Р(А) = 102 = 0,2
4)В денежно-вещевой лотерее на 1000 билетов приходится 120 денежных и 80 вещевых выигрышей. Какова вероятность какого-либо выигрыша на один билет?
5)Вероятность чего больше: вероятность выигрыша в «Спортлото» 5 из 36 или 6 из 49?
Пусть событие А - выигрыш в лотерею 5 из 36. Пусть событие В - выигрыш в лотерею 6 из 49.
Р(А) = |
5 |
≈ 0,1388 |
Р(В) = |
6 |
≈ 0,1224 |
|
49 |
||||
36 |
Т.е. Р(А) > Р(В)
Во многих задачах на определение вероятности большее затруднение вызывает подсчёт числа вариантов возможных благоприятных исходов. Здесь на помощь приходят знания комбинаторики.
Задача. В ящике лежат одинаковые на ощупь 20 шаров. Из них 12 белых и 8 чёрных. Наугад вынимают два шара.
Какова вероятность того, что они оба белые (событие А)?
Какова вероятность того, что они оба чёрные (событие В)?
Какова вероятность того, что они разного цвета (событие С)?
Решение. Число всех возможных событий равно числу сочетаний из 20 по 2. Число благоприятных исходов равно числу сочетаний из 12 по 2.
38
Р(А) = |
С2 |
= |
12!×2!×18! |
= |
12×11 |
= |
33 |
» 0,35 |
|||
12 |
|
|
|
|
|
||||||
С202 |
2!×10!×20! |
19 |
× 20 |
95 |
|||||||
|
|
|
|
|
|||||||
Подсчитайте самостоятельно, чему равно Р(В) и Р(С)
Задачи по теории вероятностей
1. Найти вероятность того, что при одном бросании игрального кубика выпадает: а) 4; б) 5; в) чётное число очков; г) число очков больше 4; д) число очков, не кратное 3.
2. Случайным образом выбрали двузначное число. Найдите вероятность того, что оно:
а) оканчивается нулём;[0,1] б) состоит из одинаковых цифр;[0,1]
в) больше 27 и меньше 46;[0,2] 3. Двузначное число составляют из цифр 0, 1, 2, 3, 4. Какова вероятность
того, что составленное число:
а) чётное[0,6]; б) нечётное[0,4]; в) делится на 5[0,2]; г) делится на 4?[0,3] 4. Из четырех тузов случайным образом поочередно вытащили две карты.
Найдите вероятность того, что:
а) обе карты – тузы черной масти;[1/6] б) вторая карта – пиковый туз;[1/4]
5.Номер телефона состоит из 5 цифр. Какова вероятность того, что все цифры наугад набранного номера разные?[0,3024]
6.В ящике находятся 90 стандартных и 10 нестандартных деталей. Какова вероятность того, сто среди 10 наугад вынутых деталей все стандартные?
39
Формулы комбинаторики
1. |
Факториал |
0! = 1 |
|
|
|
|
|
|
|
|
1! =1 |
|
n! = 1 ×2 × 3 × … |
|
|
|
|
2! = 2 |
|
|
× n |
|
|
|
|
3! = 6 |
|
|
|
|
4! = 24 |
2. |
Перестановки из n элементов |
5! = 120 |
|
Pn = n!
3. Размещения из n элементов по m (n>m)
Аnn = Pn = n!
Аnn− 1 = Аnn = n!
Аnm = n(n – 1)(n – 2)…(n – m + 1)
4. Сочетания из n элементов по m (n>m)
Сnm = Cnn − m
5. Треугольник Паскаля
n |
|
|
|
|
|
|
|
|
0 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
2 |
1 |
2 |
1 |
|
|
|
|
|
3 |
1 |
3 |
3 |
1 |
|
|
|
|
4 |
1 |
4 |
6 |
4 |
1 |
|
|
|
5 |
1 |
5 |
10 |
10 |
5 |
1 |
|
|
6 |
1 |
6 |
15 |
20 |
15 |
6 |
1 |
|
7 |
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
6.Бином Ньютона
(a + b)n = an + Cn1an− 1b + Cn2an− 2b2 + ...+ Cnk an− k bk + ...+ bn
(a + b)2 = a2 + 2ab + b2
(a + b)3 = a3 + 3a2 b + 3ab2 + b3
(a + b)4 = a4 + 4a3 b + 6a2 b2 + 4a b3 + b4
40