ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:

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

⇐ Предыдущая 45 46 47 48 495051 52 53 54 Следующая ⇒

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

Используя цифры 7, 4 и 5, мы образовывали различные двузначные числа: 77, 74, 75, 47, 44, 45, 57, 54, 55. В записи этих чисел цифры повторяются.

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

Дадим определение размещения в общем виде.

Определение. Размещение с повторениями из к элементов по т элементов - это кортеж, составленный из т элементов k-элементного множества.

Из определения следует, что два размещения из k элементов по т элементов отличаются друг от друга либо составом элементов, либо порядком их расположения.

Например, два двузначных числа из перечисленных выше (а это размещения из трех элементов по два) отличаются друг от друга либо составом элементов (74 и 75), либо порядком их расположения (74 и 47). Относительно размещений часто возникает вопрос: «Сколько всевозможных размещений по т элементов каждое можно образовать из k элементов данного множества?» Например, сколько всевозможных двузначных чисел можно записать, используя цифры 7, 4 и 5?

Число всевозможных размещений с повторениями из k элементов по т элементов обозначают и подсчитывают по формуле = k^m.

Выведем эту формулу.

Пусть в множестве X содержится k элементов. Будем образовывать из них различные кортежи по т элементов. Такие кортежи образуют множество X ´ X ´... ´ X, содержащее т множителей. По правилу произведения

п(Х ´ Х ´ ... ´ Х) = = =k^т.

Следовательно, = k^m.

Пользуясь этой формулой, легко подсчитать, сколько двузначных чисел можно записать, используя цифры 7, 4 и 5. Так как речь идет о размещениях с повторениями из трех элементов по два, то = 3² = 9.

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

Определение. Размещение без повторений из к элементов по т элементов - это кортеж, составленный из т неповторяющихся элементов множества, в котором к элементов.

Число всевозможных размещений без повторений из к элементов по т элементов обозначают и подсчитывают по формуле

= k(k – 1)×…×(k – m + 1).

Выведем эту формулу.

Пусть в множестве X содержится к элементов. Будем образовывать из них различные размещения без повторений из т элементов. Тогда выбор первого элемента таких кортежей можно осуществить к способами; если первый элемент выбран, то выбор второго элемента можно осуществить k-1 способом (так как после выбора первого элемента кортежа в множестве X остается k-1 элемент). Третий элемент размещения можно выбрать k-2 способами и т.д., т- й элемент можно выбрать k-(т-1) способами. Но выбор упорядоченного набора из т элементов можно осуществить k(k-1)... (k-т+1) способами. Значит, =

Например, число двузначных чисел, записанных с помощью цифр 7, 4 и 5 так, что цифры в записи числа не повторяются, есть число размещений без повторений из трех элементов по два: = 3 × (3 - 1) = 3 × 2 = 6.

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

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

=3×(3-1)×(3-2) = 3×2×1 = 6.

Эти числа таковы: 745, 754, 475, 457, 547, 574.

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

Число перестановок без повторений из k элементов обозначают Р_k и подсчитывают по формуле Р_k = k!, где k! = 1×2×3×... ×k и к\ читают «к факториал». Считают, что 1! = 1,0!= 1. Например, 5! = 1-2-3-4-5 = 120; 7! = 1-2-3-4-5-6-7 = 5040.

Из элементов множества X = {7, 4, 5} можно образовывать не только кортежи различной длины, но и различные подмножества, например двухэлементные. В комбинаторике их называют сочетаниями без повторений из трех элементов по два элемента.

Определение. Сочетание без повторения из к элементов по т элементов - это т-элементное подмножество множества, содержащего к элементов.

Два сочетания из k элементов по т элементов отличаются друг от друга хотя бы одним элементом.

Число всевозможных сочетаний без повторений из к элементов по т элементов обозначают Как находить это число?

Обратимся сначала к примеру. Образуем различные двухэлементные подмножества из элементов множества Х= {7,4, 5}. Их будет три: {7, 4}, {7, 5}, {4, 5}. Из элементов каждого такого подмножества можно образовать 2! кортежей длины 2:

(7,4) (7,5) (4,5)

(4,7) (5,7) (5,4)

Все полученные кортежи являются размещениями без повторения из трех элементов по два и их число равно = 3 × 2 = 6. Но, с другой стороны, это число равно произведению 2! × Значит, = 2!×, откуда =

Докажем справедливость этой зависимости в общем виде, т.е., что =

Пусть в множестве X содержится k элементов. Образуем из них сочетания без повторений по т элементов. Они будут представлять собой m -элементные подмножества множества X. Всего таких подмножеств будет .

Из элементов каждого m -элементного подмножества можно образовать т! перестановок, т.е. кортежей длины т. В итоге получим т! кортежей длины т, образованных из k элементов множества X. Их число равно . Таким образом, = т! × , откуда = .

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

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

4)Сколько всего двузначных чисел?

5)Сколько всего двузначных чисел, в записи которых цифры не повторяются?

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

В первой задаче двузначные числа образуются из 10 цифр, причем цифры в записи числа могут повторяться (в задаче нет условия о том, что цифры в записи числа не повторяются). Используя теоретико-множественную терминологию, можно сказать, что в ней речь идет об упорядоченных наборах (кортежах) из 10 элементов по 2 с повторениями. В комбинаторике такие кортежи называются размещениями с повторениями из 10-ти элементов по 2. Их число можно найти по формуле = 10² = 100. Но среди этих кортежей есть такие, у которых на первом месте стоит цифра 0 и которые не могут рассматриваться как запись двузначного числа. Таких кортежей 10, их надо вычесть из 100. Таким образом, двузначных чисел всего 90.

Конечно, эту задачу можно было решить проще, применив правило произведения: первую цифру из записи двузначного числа можно выбрать девятью способами, вторую десятью, а упорядоченную пару 9×10 = 90 способами.

Во второй задаче также рассматриваются кортежи длины 2, образованные из 10 элементов (цифр), но элементы в них не повторяются. Такие кортежи в комбинаторике называются размещениями без повторений из 10-ти элементов по 2. Их число можно найти по формуле = 10×(10-1) = 90, но из этого числа надо вычесть кортежи, у которых на первом месте стоит цифра 0, и они не могут представлять запись двузначного числа. Таких кортежей 9. Поэтому двузначных чисел, в записи которых цифры не повторяются, 90 - 9 = 81.

Другой характер имеют комбинации, о которых идет речь в третьей задаче. Действительно, если для записи чисел в первых двух задачах важен порядок следования цифр (так, 23 и 32 - это различные числа), то в третьей задаче он роли не играет (отрезок АВ и отрезок ВА - это один и тот же отрезок). Комбинации в этой задаче являются двухэлементными подмножествами, образованными из 10-ти данных элементов (точек). Такие подмножества в комбинаторике называются сочетаниями без повторений из 10 элементов по 2. Их число можно

найти по формуле: = - = ₌ 45

Упражнения

1. Заполните следующую таблицу

Виды комбинаций	Формула
На «языке» комбинаторики	На теоретико-множественном «языке»
Размещение с повторениями из k элементов по m элементов	Кортежи длины m с повтор. элементами, взятыми из множества, в котором k элементов	=
Размещение без повторений из k элементов по m элементов
Перестановки без повторений из k элементов
Сочетания без повторений из k элементов по m элементов

2. Покажите, что в нижеприведенных задачах рассматриваются размещения из k элементов по т; определите значения k и т и найдите число размещений:

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

б) В классе изучаются 7 предметов. В среду 4 урока, причем все разные. Сколькими способами можно составить расписание на среду?

в) В соревновании участвуют 10 человек. Сколькими способами могут распределиться между ними места?

г) Сколько всевозможных трехзначных чисел можно записать, используя цифры 3, 4, 5 и 6?

3. Покажите, что в следующих задачах рассматриваются сочетания из k элементов по т, определите значения k и т и найдите число
для каждой задачи:

а) Сколькими способами можно выбрать из 6 человек комиссию, состоящую из трех человек?

б) Сколькими способами можно выбрать 4 краски из 10 различных красок?

10. Два человека обменялись своими фотокарточками. Сколько было всего фотокарточек?

11. Два человека пожали друг другу руки. Сколько было рукопожатий? А если 15 человек пожали друг другу руки, то сколько будет рукопожатий?

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

13. 15 человек сыграли друг с другом по одной партии в шахматы. Сколько было сыграно партий?

14. На плоскости отметили 7 точек. Каждые две точки соединили отрезком. Сколько получилось отрезков?

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

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

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

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

г) Четыре друга собрались на футбольный матч. Но им удалось купить только три билета. Из скольких вариантов им надо выбрать тройку счастливцев? Как осуществить выбор, чтобы у всех ребят были равные шансы попасть на матч?

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

е) Задача Леонарда Эйлера. Трое господ при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Сколько существует вариантов, при которых каждый из них получит чужую шляпу?

ж) Имеется ткань двух цветов: голубая и зеленая, и требуется обить диван, кресло и стул. Сколько существует различных вариантов обивки этой мебели?

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

а) Аня, Боря, Вера и Гена - лучшие лыжники школы. На соревнования надо выбрать из них троих. Сколькими способами можно это сделать?

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

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

г) На прямой взяли 4 точки. Сколько всего получилось отрезков, концами которых являются эти точки?

д) За свои рисунки ученик получил две положительные отметки, Какими они могут быть?

е) В соревнованиях участвуют 5 футбольных команд. Каждая команда играет один раз с каждой из остальных команд. Сколько матчей будет сыграно?

⇐ Предыдущая 45 46 47 48 495051 52 53 54 Следующая ⇒

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных