«Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр. - презентация

1 «Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр (1844 г.) КОМБИНАТОРИКА

2

3 Комбинаторика – самостоятельная ветвь математической науки

4 КОМБИНАТОРИКА - это раздел математики, в котором изучаются простейшие «соединения»: перестановки, размещения, сочетания. (Большой Энциклопедический Словарь) - происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

5 «Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься.

6 n-факториал- это произведение всех натуральных чисел от до единицы до n. Обозначают n!=n·(n-1)·(n-2)·…·3·2·1. n-факториал- это произведение всех натуральных чисел от до единицы до n. Обозначают n!=n·(n-1)·(n-2)·…·3·2·1.

7 1! = 1, 2! = 2 · 1 = 2, 3! = 3 ·2·1 = 6, 4! = 4·3·2·1 = 24, 5! = 5·4·3·2·1 = 120. Необходимо знать, что 0!=1

8 Рассмотрим таблицу первых десяти значений n! n n!

9 Перестановки – Р n =1 ·2 ·3 ·… ·n Р n = n! Перестановки – соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; Р n =1 ·2 ·3 ·… ·n Обозначают Р n =n! Число n называется порядком перестановки.

10

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

12 Решение: Р 7 = 7!= 1 · 2 · 3 · 4 · 5 · 6 · 7 =5040, Ответ: 5040 способов.

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

14 Решение: P 4 = 4! = 1 · 2 · 3 · 4 = 24

15 Задача 3 Имеется 10 книг, среди которых есть трехтомник одного автора. Сколькими способами можно расставить эти книги на полке, если книги трехтомника должны находится вместе, но в любом порядке?

16 Решение: P 8 · Р 3 = 8! ·3! = Ответ:

17 Задача 4 Из цифр 0, 2, 4 и 5 образованы четырехзначные числа. Найдите количество всех таких чисел, если в них нет одинаковых цифр.

18 Решение: Из четырех цифр можно составить P 4 = 4! Р 3 =3! Р 4 – Р 3 =4!-3!=4·3!-3!=3·3!=18 Ответ: 18

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

20 а) начинаются с цифры 5 Решение: Р 4 = 4! = 24 Ответ: 24

21 б) не начинаются с цифры 1; Решение: Р 5 = 5! 4! 5! - 4! = 5·4! -4!=44!=4-4·3·2·1 =96. Ответ: 96

22 в) начинаются с 23; Решение: Р 3 = 3! = 3 ·2 ·1=6 Ответ: 6

23 г) не начинаются с 452; Решение: Р 2 = 2 · 1 = 2 Р 5 = 5! = 5 · 4 ·3 ·2 ·1 = 120 5!-2!=118 Ответ: 118

24 д) четные. Решение: 4! 4!+4!=2 ·4!=2 ·4 ·3 ·2 ·1=48 Ответ: 48

25 Спасибо за внимание

26

27 Размещения и сочетания

28 В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них в наряде старший? Задача 2. В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них в наряде старший?

29 12 способов выбрать старшего 11 способов выбрать его помощника · 12 · 11=132

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

31 1 способ. 4 ·3=12 всего 12 различных флажков

32 2 способ.

33 3 способ. (с,к)(к,с)(ж,с)(з,ж) (с,ж)(к,ж)(ж,к)(з,с) (с,з)(к,з)(ж,з)(з,к) всего 12 различных флажков

34 Составим из элементов множества всевозможные пары, чтобы в каждой паре элементы не повторялись

35 (а,b)(b,a)(c,a)(d,a) (a,c)(b,c)(c,d)(d,b) (a,d)(b,d)(c,b)(d,c)

36 Определение 1. Множество с заданным порядком располо­жения элементов называют упорядоченным множеством.

37 Определение 2. В комбинаторике конечные упорядоченные множества называются размещениями.

38 Размещением из n элементов по k, где k n, называют упорядоченное множество, содержащее k элементов. Вычисляется по формуле Размещением из n элементов по k, где k n, называют упорядоченное множество, содержащее k элементов. Вычисляется по формуле

39 Теорема. Число размещений из n элементов по k равно или, домножив числитель и знаменатель на (n-k)! получим, что

40

41 Вычислим число, где

42

43 n k

44

45

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

47

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

49

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

51 Решение задачи: Ответ: число способов равно числу размещений из 24 по 3, т.е способа.

52 Задача 7. В магазине есть пять сортов печенья, шесть сортов конфет, четыре сорта шоколада. Сколько различных подарков может предложить магазин, если в подарок входит два различных вида угощения (печенья, конфет, шоколада) различных сортов (по одному).

53 5·6=30 различных подарков, состоящих только из конфет и печенья 5·4=20 различных подарков, состоящих только из шоколада и печенья 4·6=24 различных подарков, состоящих только из конфет и шоколада =74 – число различных подарков

54 Определение. Рассмотрим конечные множества A 1, А 2, А 3,..., Ак, количество различных элементов в каж­дом из которых соответственно равно n 1, n 2, n 3,…n k, причем у них нет общих элементов. Тогда общее число различных элементов в их объединении равно сумме чисел элементов в каждом из множеств:

55 Определение. В комбинаторике конечные множества называют сочетаниями

56 Определение. Число всех способов выбрать k элементов из n данных элементов без учета порядка называют числом сочетаний из n элементов по k и обозначают.

57 Теорема. Число сочетаний из n элементов по k равно

58

59 a) при k=1:

60 б) при k=2:

61 в) при k=0:

62 Рассмотрим таблицу значений при

63 n k

64

65 n k

66

67

68 n k

69 ab a+b

70 336

71 10515

72

73 012345Σ 01 1= = = = = =2 5 n k

74

75

76 Теорема. Число всех подмножеств, образованных из элементов множества, состоящего из n элементов, равно

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

78 Решение задачи: Ответ: число способов равно числу сочетаний из 10 по 3, т.е. 120 способов.

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

80 Решение задачи: Ответ: число способов равно числу сочетаний из 10 по 4, т.е. 30 способов.

81 Спасибо за внимание.

82

83 Размещениями из n элементов по k с повторениями называются всевозможные соединения по k элементов, взятых из данных n элементов и отличающихся либо самими элементами, либо их порядком

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

85 Решение : На первое место мы можем поставить 3 числа, на второе тоже 3 и на третье – 3, значит

86 Перестановкой из n элементов называется упорядоченное множество, содержащее n заданных элементов, из которых некоторые повторяются раз

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

88 Решение : 7!=5040 3!=6 Ответ: 840 двузначных чисел.

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

90 Задача 3. На спектакле в Михайловском театре по время антракта Катя зашла в буфет и увидела на витрине четыре вида пирожных: эклеры, буше, наполеон и миндальные. Она купила 10 пирожных. Сколькими способами она могла это сделать?

91 Решение : Ответ: 715 способами Катя может купить 10 пирожных.

92 Порядок важен? нет Повторения есть? нет Сочетания да Сочетания с повторениями да Нужно выбрать все n элементов? нет Повторения есть? нет Размещения да Размещения с повторениями Да Повторения есть? нет Перестановки да Перестановки с повторениями

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

94 Решение: 6! Р 6 =6!=720 Ответ: 720

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

96 Решение : 4!=24 2!=2 Ответ: 6 слов.

97 Задача. Сколько существует треугольников, длина сторон которых 5, 6, 7, 8, 9?

98 Порядок важен? нет Повторения есть? да Сочетания с повторениями

99 Ответ: 35 треугольников.

100 Задача. Сколько слов можно получить из слова « барабашка »?

101 Порядок важен? да Нужно выбрать все n элементов? Да Повторения есть? да Перестановки с повторениями

102 Ответ: 210 слов.

103 Библиографическая справка Термины «перестановки» и «размещения» впервые употребил Якоб Бернулли в книге «Искусство предположений». Термин «сочетания»впервые встречается у Блеза Паскаля в 1665 году.

104 Решение задач: Задача 1: В соревнованиях участвуют 12 команд. Сколько существует вариантов распределения призовых (I, II, III) мест? Задача 2: Студенты Женя, Сергей, Коля, Наташа и Ольга побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие студенты могут занять очередь для игры в настольный теннис? Задача 3: В 9 классе учатся 7 учеников, в 10 – 9, а в 11 – 8 учеников. Для работы на пришкольном участке надо выделить двух учеников из 9 класса, трех – из 10 класса и одного – из 11 класса. Сколько существует способов выбора учеников для работы на пришкольном участке? Решение задач: Задача 1: В соревнованиях участвуют 12 команд. Сколько существует вариантов распределения призовых (I, II, III) мест? Задача 2: Студенты Женя, Сергей, Коля, Наташа и Ольга побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие студенты могут занять очередь для игры в настольный теннис? Задача 3: В 9 классе учатся 7 учеников, в 10 – 9, а в 11 – 8 учеников. Для работы на пришкольном участке надо выделить двух учеников из 9 класса, трех – из 10 класса и одного – из 11 класса. Сколько существует способов выбора учеников для работы на пришкольном участке?

105 Особая примета комбинаторных задач - вопрос, который начинался словами «Сколькими способами…?» Особая примета комбинаторных задач - вопрос, который начинался словами «Сколькими способами…?»

106 Исторические сведения Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей. Первые научные исследования по этой теме принадлежат итальянским ученым Дж. Кардано, Н. Чарталье ( ), Г. Галилею ( ) и французским ученым Б.Пискамо ( ) и П. Ферма. Комбинаторику, как самостоятельный раздел математики, первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 г. Он также впервые ввел термин «Комбинаторика».

107 Исторические сведения Дата рождения: 1 июля 1646 г. Место рождения: Лейпциг, Германия Дата смерти:14 ноября 1716 г. Место смерти: Ганновер, Германия Школа/традиция: рационализм Направление: Европейская философия Основные интересы: Метафизика, эпистемология, наука, математика. Лейбниц Готфрид Вильгельм

108