Сколько различных перестановок можно составить из букв слова оценка

Комбинаторика и элементы теории вероятностей и статистики в задачах ГИА
материал для подготовки к егэ (гиа) по алгебре (9 класс) по теме

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

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

Основные понятия и формулы

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

Размещения – это комбинации, формируемые из n различных элементов по m элементов в каждой и отличающиеся одна от другой либо составом, либо порядком следования элементов

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

Свойства сочетаний без повторений :

Комбинаторный принцип умножения если одну часть действия можно выполнить k способами, а другую – p способами, то все действие можно выполнить kp числом способов.

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

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

Решение: Из четырех цифр можно получить P 4 перестановок. Из них надо исключить те перестановки, которые начинаются с нуля. Таких перестановок P 3. Тогда: P 4 – P 3 =4! — 3! = 18

Ответ: 18 четырехзначных чисел

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

Решение: На первое место можно поставить цифры 1, 2, 3(3 способа), на второе, третье и четвертое место – 0,1,2,3 (4 способа). Применяя комбинаторный принцип умножения получим 3 4 4 4 = 192 числа ( 2 способ: 3 =3 4 3 =192)

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

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

Задача 4. Сколько перестановок можно получить из букв слова КОЛОКОЛА?

Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых:

буква К повторяется 2 раза;

буква О повторяется 3 раза;

буква Л повторяется 2 раза

буква А повторяется 1 раз.

Задача 4 . В секции занимается 8 человек. Сколькими способами можно составить команду из 4 человек?

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

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

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

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

Решение: Для каждого звукосочетания клавиши нажимаются одновременно, и с учетом комбинаторного правила сложения, получим

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

Решение: Первую ладью можно поставить на любое из 64 полей. При этом 14 полей оказываются под угрозой, значит, для второй ладьи остается любое из 64 -15 = 49 полей. Значит, общее число вариантов 64 49 = 3136

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

Решение: первую группу можно составить способами, вторую способами, третью способами. С учетом комбинаторного правила умножения число всех составов групп

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

Решение: Всего можно составить четырехзначных чисел, включая и те, которые начинаются с цифры 0. Исключив их, получим . Теперь из этого набора нужно исключить все четырехзначные числа, не содержащие цифру 3, т.е. состоящие из цифр 0, 1, 2,4,5.аналогично получим

Задача 10. На книжной полке помещается 30 томов. Сколькими способами их можно расставить так, чтобы при этом первый и второй тома не стояли рядом?

Решение: Всего на полке можно сделать перестановок. Убрав первый том, получим 29! перестановок книг. Первый том можно поставить рядом со вторым двумя способами

2 29! (вычтем их). Таким образом, способами

Задача 11. Найти число диагоналей n-угольника

Решение: Имеется n точек на плоскости. Всего можно провести

отрезков. Исключим n отрезков, которые являются сторонами многоугольника. Значит, всего диагоналей будет .

Задача12. В скольких точках пересекаются диагонали выпуклого n-угольника, если никакие три из них не пересекаются в одной точке?

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

Задача 13. Восемь авторов должны написать книгу из 16 глав. Сколькими способами возможно распределение материала между авторами, если два человека напишут по три главы, четыре – по две, два – по одной главе книги?

Решение: Искомое число таково способами

Задача 14. У одного мальчика 6 значков, а у другого – 5. Сколькими способами они могут обменять 2 значка одного на 2 значка другого?

Решение: Найдем сколькими способами каждый выдерет из своих значков по 2 для обмена: ; . Используя комбинаторное правило умножения получим 10 15=150 способов

Теория вероятностей – это раздел математики, в котором изучаются закономерности случайных событий

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

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

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

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

Свойство 1. Вероятность достоверного события равна единице
Свойство 2. Вероятность невозможного события равна нулю.
Свойство 3. Вероятность случайного события есть положительное число, заключенное между нулем и единицей.

Итак, вероятность любого события удовлетворяет двойному неравенству .

Вероятность появления хотя бы одного из двух несовместных событий равна сумме вероятностей этих событий: P(C) = P(A) + P(B)

Вероятность совместного появления двух независимых событий равна произведению вероятностей этих событий: P(C) = P(A) P(B)

Вероятность противоположного события : P( ) = 1 – P(A)

Задача 1. В урне 10 шаров: 6 белых и 4 черных. Вынули два шара. Какова вероятность, что оба шара белые?

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

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

Решение. Общее число возможных исходов равно числу способов, которыми можно отобрать 7 человек из 10, т.е.
.

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

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

Решение: Общее число исходов 6 6 = 36. Благоприятных исходов 9: (1;1),(1;3), (2;2), (3;1), (1;5), (2;4), (3;3), (4;2), (5;1). Значит, P =

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

Решение: Так как к каждой задаче предлагается 4 варианта ответов, то общее число возможных комбинаций ответов равно 4 5 = 1024. Благоприятными исходами являются

. Значит, искомая вероятность P =

Задача 5 . В мешочке лежат неразличимые на ощупь карточки с буквами К, О, С, М, О, С. Какова вероятность того, что, наудачу извлекая карточки и выкладывая их на столе, получится слово КОСМОС?

Решение: Занумеруем карточки числами от 1 до 6: К 1 О 2 С 3 М 4 О 5 С 6 . Общее число исходов равно количеству перестановок P 6 = 6! Благоприятными исходами будут следующие: К 1 О 2 С 3 М 4 О 5 С 6 , К 1 О 2 С 6 М 4 О 5 С 3, К 1 О 5 С 3 М 4 О 2 С 6 , К 1 О 5 С 6 М 4 О 2 С 3. Искомая вероятность равна P=

Задача 6. В окружность вписан правильный треугольник. Найти вероятность того, что точка, брошенная в круг, попадет в треугольник.

Решение: Пусть радиус окружности равен R, тогда сторона треугольника R . Тогда площади фигур равны: Sтр = ; Sокр= . Таким образом , искомая вероятность равна P = 0,41

Математическая статистика – это дисциплина, разрабатывающая математические методы систематизации и использования статистических данных для научных и практических выводов

Мода – значение признака, имеющее наибольшую частоту в статистическом ряду распределения.

Среднее арифметическое (среднее) – это сумма всех чисел ряда, деленная на их количество.

Медиана – это такое значение признака, которое разделяет упорядоченный ряд на две равные части. Если в ряду нечетное количество чисел, то это число, стоящее посередине ряда, если – четное, то среднее арифметическое двух средних по счету чисел.

Размах ряда – это разность наибольшего и наименьшего чисел упорядоченного ряда

Задача 1. Измеряя рост семи пришедших на урок учеников, учитель физкультуры получил ряд чисел: 152, 148, 152,154, 158,148, 152.Найдите разность между модой и медианой того ряда.

Решение: Упорядочим ряд 148, 148, 152,152, 152,154, 158. Мода ряда – 152. Медиана – 152. Значит,152 – 152 =0

Задача 2. Дима в четверти получил по 10 предметам среднюю оценку 4,2.По какому количеству предметов он должен улучшить оценку на 1 балл, чтобы его средняя оценка стала 5?

Решение: Сумма набранных баллов по всем предметам S= x 1 +x 2 +x 3 +…+x 10 = 4,2 10=42.

Тогда сумма баллов, набранная после исправления S 1 = y 1 +y 2 +…+y 10 =5 10=50. Следовательно, Дима должен улучшить свой результат на S-S 1 =50-42=8 баллов. Значит, он должен улучшить на 1 балл по 8 предметам.

Задача 3 . При каких значениях x медиана ряда чисел 1, 2, 3, 4, x будет равна 3?

Решение: После ранжирования данного ряда чисел в зависимости от значений x будет получен один из следующих рядов:

x, 1, 2, 3, 4, если x

1, x, 2, 3, 4, если 1

1, 2, x, 3, 4, если 2

1, 2, 3, x, 4, если 3

1, 2, 3, 4, x, если x>4

Найдем для каждого из этих рядов его медиану: 2, 2, x, 3, 3. Получаем, что медиана равна 3 при x>=3.

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

1. Автомобильные номера состоят из трех цифр. Найдите количество автомобильных номеров данной серии (буквы), все цифры, в которых четные. (При решении учесть, что номера «000» не существует.)
2. На карусели есть 8 посадочных мест, расположенных по кругу. Покататься пришли 6 детей. Сколькими способами их может рассадить карусельщик? Два способа считать одинаковыми, если один из них получается из другого поворотом карусели.
3. Найдите вероятность того, что в написании наудачу взятого двузначного числа встречается цифра 5.
4. По мосту производится бомбометание из двух самолетов. Вероятность попадания из первого самолета 0,8 ,второго – 0,6.Мост будет разрушен, если в него попадет хотя бы одна бомба. Какова вероятность того, что в результате одного бомбометания из двух самолетов мост будет разрушен?
5. По статистике автозавода ВАЗ, из 1000 машин 20 бракованных. Сколько бракованных машин следует ожидать, если завод собирается выпустить 300500 машин?
6. На произвольное поле шахматной доски поставили белого короля, затем на другое поле поставили черную ладью. Какова вероятность того, что ладья бьет короля? (Ладья бьет клетки своей вертикали и горизонтали)
7. Из колоды 36 карт вытаскивают две карты. Какова вероятность того, что среди них хотя бы один туз?
8. Из ста карточек, на которых написаны натуральные числа от 1 до 100, вытаскивают одну, затем еще одну. Какова вероятность того, что число, написанное на второй карточке, на 2 больше числа, написанного на первой?

Ответы: 1. 124; 2. 2520; 3. 1/5; 4. 0,92; 5. 6010; 6. 2/9; 7. 67/315; 8. 98/9900

Сколько различных перестановок можно составить из букв слова оценка

Сколько различных перестановок можно составить из букв слова оценка

Ответ:

1. 120 способов

2. 5 040 способов

3. 5 040 способов

4. Вазон

Пошаговое объяснение:

1. Число перестановок из 5:

Р5 = 5! = 1*2*3*4*5 = 120 способов

2. Число перестановок из 7:

Р7 = 7! = 1*2*3*4*5*6*7 = 5 040 способов

3. Число перестановок из 7:

Р7 = 7! = 1*2*3*4*5*6*7 = 5 040 способов

4. В букве А буква З слОН — Вазон

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

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

Варианты ответов

• 35
• 12
• 2520
• 120

Вопрос 3

Сколько существует способов рассадить 6 гостей по шести местам за праздничным столом?

Варианты ответов

• 720
• 36
• 12
• 360

Вопрос 4

Варианты ответов

• 1/4
• 11/4
• 25
• 16

Вопрос 5

Сколькими способами можно выбрать четыре человека на четыре должности из семи кандидатов?

Варианты ответов

• 28
• 840
• 24
• 52

Вопрос 6

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

Варианты ответов

• 25
• 10
• 35
• 120

Вопрос 7

Каждое расположение n элементов в определенном порядке называется

Варианты ответов

• размещением
• сочетанием
• перестановкой

Вопрос 8

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

Варианты ответов

• 30
• 5
• 100
• 120

Вопрос 9

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

Варианты ответов

• 10
• 60
• 20
• 30

Вопрос 10

Если объект А можно выбрать х способами, а объект В — у способами, то каким количеством способов можно выбрать объект «А и В» ?

Варианты ответов

• х
• ху
• х+у
• х-у

Вопрос 11

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

Варианты ответов

• 300
• 520
• 120
• 720

Вопрос 12

Из цифр 1, 2 и 3 составили такие комбинации: 12; 13; 21; 31; 32; 23. Как называются такие комбинации?

Варианты ответов

• сочетанием
• размещением
• перестановкой

Вопрос 13

Комбинаторика отвечает на вопрос

Варианты ответов

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

Вопрос 14

Если объект А можно выбрать х способами, а объект В — у способами, то каким количеством способов можно выбрать объект «А или В»?

Варианты ответов

• х+у
• ху
• х-у

Вопрос 15

Из цифр 1, 2 и 3 составили такие комбинации: 123; 133; 231; 213; 312; 321. Как называются такие комбинации?

Варианты ответов

• сочетанием
• размещением
• перестановкой

Вопрос 16

Из цифр 1, 2 и 3 составили такие комбинации : 12; 13; 23. Как называются такие комбинации?

Варианты ответов

• размещением
• перестановкой
• сочетанием

Вопрос 17

Комбинаторикой называют раздел математики, который изучает

Варианты ответов

• количественные характеристики массовых явлений
• закономерности массовых случайных событий
• различные комбинации элементов множеств

Вопрос 18

Любое множество, состоящее из k элементов, взятых из данных n элементов, называется……

Варианты ответов

• размещением
• перестановкой
• сочетанием

Вопрос 19

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

Варианты ответов

• размещением
• перестановкой
• сочетанием

Вопрос 20

Из цифр 1, 2 и 3 составляют всевозможные двузначные числа без повторения этих цифр в записи числа. Всего можно составить 6 таких чисел потому, что…

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

Рассмотрим множество, состоящее из n различных элементов. Требуется выбрать из них какие-нибудь k элементов и расположить эти k элементов в каком-либо порядке. Такие упорядоченные последовательности называются размещениями из n элементов по k элементов (упорядоченные – следовательно, последовательности и — различные размещения).

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

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

Любое подмножество (неупорядоченное), состоящее из k элементов, называется сочетанием из n элементов по k элементов.

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

Число сочетаний без повторений

Число сочетаний с повторениями

Количество способов переставить элементов в заданном множестве (количество перестановок) вычисляется по формуле

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

Выбор	Неупорядоченный	Упорядоченный
Без повтора
С повтором

Рассмотрим разницу между сочетаниями, размещениями с повторениями, без повторений на следующих примерах.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

ПРИМЕР 13.2.1 В коробке 6 шаров, пронумерованных от 1 до 6. Из коробки вынимаются друг за другом 3 шара и в этом же порядке записывают полученные цифры. Сколько трехзначных чисел можно таким образом записать?

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

ПРИМЕР 13.2.2. В коробке 6 шаров пронумерованных от 1 до 6. Из коробки вынимаются 3 шара и записывают число в порядке возрастания цифр. Сколько трехзначных чисел можно таким образом записать?

Решение: По условию задачи подмножества и дают число 123, т.е. не являются различными.

ПРИМЕР 13.2.3. Условие задачи 2.1 (шары возвращаются в коробку)

ПРИМЕР 13.2.4. Условие задачи 2.2 (шары возвращаются в коробку)

ПРИМЕР 13.2.5. Сколько различных перестановок можно составить из букв слова «комар»?

ПРИМЕР 13.2.6. Сколько различных перестановок можно составить из букв слова «задача»?

Решение: Если бы все шесть букв слова были различны, то число перестановок было бы 6! Но буква «а» встречается в данном слове три раза, и перестановки только этих трех букв «а» не дают новых способов расположения букв. Поэтому число перестановок букв слова «задача» будет не 6!, а в 3! раза меньше, то есть .

ПРИМЕР 13.2.7. В мастерской имеется материал 5 цветов. Поступил заказ на пошив флагов, состоящих из трех горизонтальных полос разного цвета каждый. Сколько таких различных флагов может сшить мастерская?

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

ПРИМЕР 13.2.8. Сколькими способами можно распределить 5 учеников по 3 параллельным классам?

Решение: Составим вспомогательную таблицу

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

ПРИМЕР 13.2.9. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй том не стояли рядом?

Решение: Произведем рассуждения “от обратного”. Тридцать томов на одной полке можно разместить 30! способами.

Если 1 и 2 тома должны стоять рядом, то число вариантов расстановки сокращается до , т.к. комбинацию из 1 и 2 тома можно считать за один том, но при этом они могут стоять как (1;2) или (2;1), т.е.

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

ПРИМЕР 13.2.10. Чемпионат, в котором участвуют 16 команд, проводится в два круга, т.е. каждая команда дважды встречается с любой другой. Определить, какое количество встреч следует провести.

Решение: По условию задачи из 16 команд для каждой встречи требуется отобрать 2 команды. В данном случае отбор производится без повтора и порядок отбора не важен, т.е. число вариантов — . Так как команды должны играть дважды число вариантов удваивается, т.е. .

ПРИМЕР 13.2.11. Автомобильная мастерская имеет для окраски 10 основных цветов. Сколькими способами можно окрасить автомобиль, если смешивать от 3 до 7 основных цветов?

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

ПРИМЕР 13.2.12. Турист прошел маршрут из пункта A в пункт B, из B в C и вернулся обратно. Сколько вариантов маршрута существует, если из пункта A в пункт B ведут 3 дороги, а из B в C — 4 и нельзя возвращаться той дорогой, по которой уже прошел?

Решение: Составим схему.

Из рисунка видно, что вариантов маршрута из А в B существует 3, и из B в C – 4, т.е. всего маршрутов .

На обратном пути вариантов маршрута из С в B существует 3 (один уже пройден), и из B в А – 2, т.е. всего возможных обратных маршрутов осталось . Тогда всего вариантов маршрута .

ПРИМЕР 13.2.13. Двенадцати ученикам выданы два варианта контрольной работы. Сколькими способами можно посадить учеников в два ряда по 6 человек, чтобы у сидящих рядом не было одинаковых вариантов, а у сидящих друг за другом был один и тот же вариант?

Решение: Рассуждения произведем несколькими способами

I способ) Первоначально 12 учеников разбивают на 2 группы по 6 человек. Это можно сделать способами.

Затем они могут распределиться по своим рядам согласно схеме

Поэтому всего способов распределения учеников будет .

II способ) Первоначально 12 учеников запускают в класс, указывая место, где каждый должен сидеть, например “второй ряд, третье место”. Так как посадочных мест также 12, то всего вариантов распределения 12!
Варианты контрольной работы могут распределиться

“I вариант – I ряд, II вариант – II ряд”

“II вариант – I ряд, I вариант – II ряд”,

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

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

ПРИМЕР 13.2.14. Сколько существует вариантов расположения шести гостей за круглым шестиместным столом?

Решение: Эта задача имеет разные решения и, соответственно разные ответы – в зависимости от того, что понимать под различным расположением гостей за столом. Поэтому исследуем возможные варианты.

Если считать, что нам важно, кто сидит на каком стуле, то это простая задача на перестановки и, следовательно, всего вариантов .

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

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

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

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

ПРИМЕР 13.2.15. Семнадцать студентов сдали экзамены по 4 предметам только на “хорошо” и “отлично”. Верно ли утверждение, что хотя бы у двух из них оценки по экзаменационным предметам совпадают?

Решение: Очевидно, что в данном случае речь идет о возможных вариантах вида

Предмет	1	2	3	4
Студент 1	4	4	5	5
Студент 2	5	4	4	5
Студент 3	5	5	5	5
…	…	…	…	…
Студент 17	4	4	5	4

Данный пример можно решить способом, изложенным в примере 13.1.8., и получить количество вариантов . Приведем другой наглядный способ решения, использующий так называемое “дерево решений”,который представляет все варианты (16 штук) получения экзаменационных оценок.

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

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

Если некоторый объект A может быть выбран из совокупности объектов m способами, а другой объект B может быть выбран nспособами, то:

Правило суммы: выбрать либо A, либо B можно m+n способами.

Правило произведения. Пара объектов (A,B) в указанном порядке может быть выбрана способами.

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

Решить комбинаторную задачу.

13.2.1.1. В группе 25 студентов. Сколькими способами можно выбрать старосту, заместителя старосты и профорга?

13.2.1.2. В группе 25 студентов. Сколькими способами можно выбрать актив группы, состоящий из старосты, заместителя старосты и профорга?

13.2.1.3. Сколькими способами можно составить список из 10 человек?

Отв.: 3628800

13.2.1.4. Сколькими способами из 15 рабочих можно создать бригады по 5 человек в каждой?

Отв.: 126126

13.2.1.5. Буквы азбуки Морзе образуются как последовательности точек и тире. Сколько букв можно составить, используя для кодировки каждой из букв: а) ровно 5 символов? б) не более пяти символов?

Отв.: а)32; б) 62

13.2.1.6. Кости для игры в домино метятся двумя цифрами. Кости симметричны, и поэтому порядок чисел не существенен. Сколько различных костей можно образовать, используя числа 0,1,2,3,4,5,6?

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

Отв.: 9864000

13.2.1.8. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

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

13.2.1.10. Команда компьютера записывается в виде набора из восьми цифровых знаков – нулей и единиц. Каково максимальное количество различных команд?

13.2.1.11. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?

Отв.: 725760

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

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

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

Отв.: 9000000

13.2.1.15. У одного студента есть 7 DVD дисков, а у другого – 9 дисков. Сколькими способами они могут обменять 3 диска одного на 3 диска другого?

Отв.: 105840

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

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

Отв.: 362160

13.2.1.18. В поезд метро на начальной станции вошли 10 пассажиров. Сколькими способами могут выйти все пассажиры на последующих 6 станциях?

Отв.: 60466176

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

13.2.1.20. В классе 25 учеников. Верно ли утверждение, что, по крайней мере, у трех из них день рождения в один и тот же месяц?

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

13.2.1.22. На официальном приеме 50 человек обменялись рукопожатиями. Сколько было сделано рукопожатий?

13.2.1.23. Сколько диагоналей у выпуклого двадцатиугольника?

Уважаемые студенты
На нашем сайте можно получить помощь по всем разделам математики и другим предметам:
✔ Решение задач
✔ Выполнение учебных работ
✔ Помощь на экзаменах

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

Выше были рассмотрены размещения множеств таких объектов, которые отличались один от другого. Чему будет равно число возможных перестановок множества объектов, если в этом множестве некоторые объекты одинаковы? Ясно, что если какие-то объекты множества невозможно отличить друг от друга, то число всех возможных перестановок объектов этого множества уменьшается. Так например, из трех букв А, В, С можно образовать 3! трехбуквенных слов, а из букв А, А, А – только одно.

Решим задачу 1. Сколько различных слов можно образовать из всех букв слова «атака»? Решение. Если бы буквы а различались между собой, то, как уже известно, существует 5! перестановок пяти различных букв. Сведем эту задачу к известной, а именно будем временно считать, что все буквы а разные. Обозначим неизвестное нам число перестановок х. Обозначим три буквы а так: а_1, а₂, а₃. Переставляя эти три буквы, получим 3! перестановок. Так как пять букв теперь все различны, то х*3!=5!, следовательно, х=.

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

Теорема 6. Перестановки объектов с повторениями. Пусть дано множество из n элементов, в котором n₁ элементов принадлежат к первому типу, n₂ элементов принадлежат к n₂ типу, n₃ элементов принадлежат к третьему типу, и так далее до n_к элементов к-го типа, причем элементы одного и того же типа не различимы между собой. Тогда общее число перестановок данного множества n элементов равно

n₁+n₂₊n₃+…+n_k=n.
Следствие 7. Число перестановок в случае двух типов объектов. Если множество из n элементов состоит из r элементов одного типа и n—r элементов другого типа, то число перестановок данного множества из n объектов равно
==
Доказательство. (а) Доказательство немедленно следует из теоремы 6, если мы положим n₁=r и n₂=n-r. Можно дать другое доказательство этой теоремы.

(б) Предположим, что надо расставить по порядку r одинаковых объектов, которые мы обозначим А, и n-r одинаковых объектов, отличных от предыдущих, которые мы обозначим В. Количество способов, которыми можно отобрать r мест для размещения объектов А из всех n мест, равно , после чего эти объекты можно расположить на выбранных местах одним способом. Далее, объекты типа В можно расположить на оставшихся n-r местах *1, или одним, способом. Следовательно, общее число размещений равно .

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

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

Решение. В данном слове 9 букв, в том числе одна буква «м», три – «с», четыре буквы «и» и одна «п». Следовательно, n₁=1, n₂=3, n₃=4 и n₄=1. По теореме 6 общее число перестановок из этих букв будет равно

=2520
Задача 3. Сколько различных перестановок можно образовать из всех букв слова «удобрения», если все гласные буквы должны идти друг за другом в следующем порядке: у, о, е, и, я?

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

Решение 2. Надо разместить 9 букв на 9 подряд идущих мест. Места для гласных можно выбрать способами, и, после того как это сделано, их можно поставить на выбранные места одним способом – в заранее указанном порядке. Согласные можно расставить на оставшихся 4-х местах 4! Способами. Следовательно, общее число перестановок этих букв равно

Задача 4. Дано n букв А и r букв Б. Сколько различных слов можно образовать из этих букв так, чтобы каждое слово содержало все n букв А?

Решение. Можно составить слово из n букв А и совсем не брать буквы Б, можно составить слово из n букв А и одной Б, можно из n букв А и двух Б, и т.д. Итого будем иметь r+1 взаимно исключающих друг друга случаев. Соответствующие количества слов будут:

n букв А, 0 букв Б —

n букв А, 1 буква Б —

n букв А, 2 буквы Б —

n букв А, 3 буквы Б —

n букв А, r букв Б —

Количество слов в каждом случае вычислено по формуле следствия 7.

Так как эти случаи взаимно исключают друг друга, то по правилу сложения имеем общее число слов равным такой сумме:

Замечание. Эта сумма равна, что можно показать последовательным применением правила Паскаля:
+=+=

Тест "Элементы комбинаторики"

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

Педагогика — еще материалы к урокам:

Предметы

• Алгебра
• Английский язык
• Биология
• География
• Геометрия
• ИЗО
• Информатика
• История
• Литература
• Математика
• Музыка
• МХК
• Начальная школа
• ОБЖ
• Обществознание
• Окружающий мир
• ОРКСЭ
• Педагогика
• Русский язык
• Технология
• Физика
• Физкультура
• Химия
• Экология