Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Статья "Теоретические основы комбинаторики"

Статья "Теоретические основы комбинаторики"

  • Математика

Поделитесь материалом с коллегами:

Государственное общеобразовательное учреждение

средняя общеобразовательная школа №353

Московского административного района Санкт-Петербурга














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

Элементы комбинаторики».












Учитель математики

ГОУ СОШ № 353

Мошнина Ирина Владимировна








Санкт – Петербург

2015 год

Содержание.




Введение

Стр. 3

Примеры комбинаторных задач

Стр. 3

Перестановки.

Стр. 5

Размещения

Стр. 6

Сочетания.

Стр. 7

Задачи по комбинаторике

Стр. 9

Литература

Стр. 15



Введение.

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

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Рассмотрим некоторые понятия, которые назовем «Элементами комбинаторики»:

1. Примеры комбинаторных задач.

2. Перестановки.

3. Размещения.

4. Сочетания.

Примеры комбинаторных задач.

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

Основные правила комбинаторики – это правило суммы и правило произведения.

Правило суммы используется тогда, когда надо выбрать что-нибудь «либо А, либо В»:

Если некоторый элемент А можно выбрать m способами, а элемент В – n способами, то выбор «либо А, либо В» можно сделать m+n способами.

Пример: Есть 7 слив и 4 персика, то один плод можно выбрать 7+4=11 способами.


Далее разъясняется и формулируется комбинаторное правило умножения, которое неоднократно используется при изучении последующего материала.

Для того чтобы разъяснить учащимся смысл этого правила, рассматривается такая задача:

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

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



hello_html_5cf03212.png



Ответ на поставленный вопрос в задаче можно получить, не выписывая сами числа и не строя дерево возможных вариантов. Рассуждать будем так. Первую цифру трехзначного числа можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать из оставшихся цифр уже тремя способами. Наконец, третью цифру можно выбрать (из оставшихся двух) двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 4*3*2, т.е. 24.

После этого формулируется комбинаторное правило умножения:

«Пусть имеется п элементов и требуется выбрать один за другим некоторые к элементов. Если первый элемент можно выбрать n1 способами, после чего второй элемент можно выбрать из оставшихся п2 способами, затем третий элемент – n3 способами и т.д., то число способов, которыми могут быть выбраны все к элементов, равно произведению n1 * n2 * n3 * ….* nk».

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

Целесообразно на этот вопрос потратить не менее 2 часов: на первом уроке показать, объяснить, а на втором устроить соревнование между командами.

Задачи:

  1. Сколько различных трехзначных чисел можно составить из цифр 1, 3, 5, если цифры в записи числа не повторяются?

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

  3. Сколько различных трехзначных чисел можно составить из цифр 1, 3, 5, если цифры в записи числа повторяются?

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

После решения этих задач можно предложить ребятам такие вопросы:

А. Чем похожи эти задачи?

Б. Какое условие поменялось и как это повлияло на решение и на результат?

С. Почему в 1 и 3 задаче чисел больше, чем во 2 и 4? Что повлияло на результат?

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

  2. Сколько различных четырехзначных чисел можно составить из цифр 0, 4, 5, 6 если цифры в записи числа не повторяются?

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

  4. Вася, Петя и Толик купили три билета на хоккейный матч на 1, 2, 3-е места первого ряда. Сколькими способами они могут занять имеющиеся места?

Решение.

способы

В

П

Т

П

Т

Т

П

В

Т

Т

В

В

П

П

В

ВПТ

ВТП

ПВТ

ПТВ

ТВП

ТПВ



Итого 6 способов.

  1. В вазе 5 пряников, 7 конфет и 4 шоколадки. Сколько вариантов выбора одного лакомства?

  2. Сколько вариантов покупки одной футболки, если продают 5 красных, 4 черных и 3 белых?

  3. Хоккейная комбинация. На поле пять игроков. Начал комбинацию игрок № 1, продолжили игроки с другими номерами, а забил гол игрок № 5. Каждый хоккеист
    ударил по шайбе только один раз.


Перестановки.


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

Понятие «перестановка» разъясняется на конкретном примере. Пусть имеются три книги. Обозначим их буквами а, в и с. Эти книги можно расставить на полке по-разному:

авс, асв, вас, вса, сав, сва.

Каждое из этих расположений называют перестановкой из трех элементов.

Затем дается определение и вводится соответствующая символика.

Перестановкой из п элементов называется каждое расположение этих элементов в определенном порядке.

Число перестановок из п элементов обозначается символом Рп (читается «Р из n»).

Выводу формулы числа перестановок предшествует рассмотрение конкретного примера.

Мы установили, что Р3 = 6. Для того чтобы найти число перестановок из трех элементов, можно не выписывать эти перестановки, а воспользоваться правилом умножения. Будем рассуждать так. На первое место можно поставить любой из трех элементов. Для каждого выбора первого элемента есть две возможности выбора второго из оставшихся двух элементов. Наконец, для каждого выбора первых двух элементов остается единственная возможность выбора третьего элемента. Значит, число перестановок из трех элементов равно 3*2*1= 6.

Таким образом, число всевозможных перестановок из п элементов вычисляется по формуле:

Рn=n!

где для произведения первых п натуральных чисел используют специальное обозначение: п! (читается n факториал»).

Например. 2! = 1 • 2 = 2; 5! = 1 • 2 • 3 • 4 • 5 = 120.

По определению, считают, что 1! = 1, 0!=1.

Задачи:

  1. Сколькими способами можно расставить на полке 5 книг?

Решение: количество способов расстановки пяти книг на полке будет равно числу перестановок из 5 элементов:

Р5=5!=1*2*3*4*5=120

Ответ: 120 способов.

  1. Сколькими способами можно расставить на полке 9 книг, если среди них три книги одного автора, которые при любых перестановках должны стоять рядом?

Решение: условно будем считать три книги одного автора единой книгой. Тогда количество способов расстановки семи книг на полке будет равно числу перестановок из 7 элементов:

Р7=7!=1*2*3*4*5*6*7=5040

Но в каждой такой перестановке можно выполнить Р3 перестановки книг одного автора, поэтому общее число способов будет 5040*3!=5040*6=30240.

Ответ: 30240 способами.

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

Решение: число способов равно числу перестановок из 8 элементов:

Р8=8!=1*2*3*4*5*6*7*8=40320.

Ответ: 40320 способов.

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

Решение: из цифр 0, 3, 5, 7 можно получить Р4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0, так как натуральное число не может начинаться с цифры 0. Число таких перестановок равно Р3. Искомое число четырехзначных чисел (без повторения цифр), равно Р43=4!-3!=24-6=18.

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

  1. Семь мальчиков, в число которых входят Вася и Толик, становятся в ряд. Найдите число возможных комбинаций, если Вася и Толик должны стоять рядом.

Решение: будем рассматривать пару Вася – Толик как один элемент. Расположение этой пары и пяти других мальчиков может быть выполнено Р6=6! Способами. В каждой из этих комбинаций Вася и Толик могут располагаться Р2=2! способами. Следовательно:

Р6 * Р2 = 6!*2! = 720 *2 = 1440.

Ответ: 1440 способов.

  1. Семь мальчиков, в число которых входят Вася и Толик, становятся в ряд. Найдите число возможных комбинаций, если Вася должен стоять в конце ряда.

Решение: Так как место Васи фиксировано, то число комбинаций зависит от расположения шести мальчиков.

Р6 = 6! = 1*2*3*4*5*6 =720.

Ответ: 720 способов построения в ряд.

  1. Найдите значение выражения

а) 18!/(14!3!), б) 7!8!/12!.

8. Четыре друга купили билеты в кино: на 1-е и 2-е места в первом ряду и на 1-е и 2-е места во втором ряду. Сколькими способами ребята могут занять эти 4 места в кинотеатре?


Размещения.

Пусть имеется 3 пустых ячейки и 4 шара: красный, синий, зеленый и белый. В пустые ячейки можно по-разному разместить три шара из набора. Если мы поместим красный шар в первую ячейку, синий шар во вторую ячейку, а зеленый в третью ячейку, то получим одну из возможных упорядоченных троек шаров:

красный

синий

зеленый

Выбирая по-разному первый, второй и третий шары, будем получать различные упорядоченные тройки шаров, например:

красный

зеленый

синий

синий

красный

зеленый

зеленый

синий

красный

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

Выпишем все возможные комбинации из четырех шаров по три:

(красный – к, синий – с, зеленый – з, белый – б)

В первой строке запишем все размещения, которые начинаются с элемента «к», во второй – с элемента «с», в третьей – с элемента «з», в четвертой – с элемента «б». Получим такую таблицу:

ксз

ксб

кзс

кзб

кбс

кбз

скз

скб

сзк

сзб

сбк

сбз

зкс

зкб

зск

зсб

збк

збс

бкс

бкз

бск

бсз

бзк

бзс

Из таблицы видно, что число комбинаций равно 24.

Но можно найти число размещений из четырех элементов по три, не выписывая самих размещений. Первый элемент можно выбрать четырьмя способами, так как им может быть любой из четырех элементов. Для каждого выбранного первого элемента можно тремя способами выбрать второй элемент из трех оставшихся. Наконец, для каждых первых двух элементов можно двумя способами выбрать из двух оставшихся третий элемент. В результате получаем, что 4*3*2=24.

Введем определение и выведем формулу для подсчета числа возможных размещений.

Определение. Размещением из n элементов по k (k<n) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из данных n элементов.

Число размещений из n элементов по k обозначают Аkn (читают «А из n по k»).

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

Выведем формулу для подсчета числа возможных размещений.

Первый элемент можно выбрать n способами. Так как после этого остается n-1 элементов, то для каждого выбора первого элемента можно n-1 способами выбрать второй элемент. Далее, для каждого выбора первых двух элементов можно n-2 способами выбрать третий элемент (из n-2 оставшихся). Наконец, для каждого выбора первых k-1 элементов можно n-( k-1) способами выбрать k-й элемент (из n-( k-1) оставшихся).

Значит,

Аkn= n(n-1)( n-2)*...*( n-( k-1)).

Аkn = n!/( n- k)!

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

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

Например, число размещений из шестнадцати элементов по пять равно произведению пяти множителей, первый из которых – число 16, а каждый следующий на 1 меньше предыдущего, т.е.

А516=16*15*14*13*12=524160.

Примеры.

1) Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета?

А48=8*7*6*5=1680.

2) Учащиеся школы изучают 10 различных предметов. Сколькими способами можно составить расписание уроков на один день, чтобы при этом было 5 различных предметов?

А510=10*9*8*7*6=30240

3) Бригадир должен отправить на работу бригаду из 5 человек. Сколько бригад по 5 человек в каждой можно составить из 12 человек?

А512=12*11*10*9*8=95040

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

А710 – А69 = 10*9*8*7*6*5*4 - 9*8*7*6*5*4 = 544320


Сочетания.

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

Два сочетания из n элементов по k считаются различными тогда и только тогда, когда они отличаются, по крайней мере, одним элементом.

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

Число всевозможных сочетаний из n элементов по k обозначается знаком Сkn.

hello_html_454e71a7.gif

hello_html_463db0c.gif

Эту формулу можно использовать и в случае, когда n = k, так как 0! = 1.

Примеры.

1. В классе 12 учеников. Сколькими способами можно выбрать 3 дежурных?

Каждый выбор отличается от другого хотя бы одним дежурным. Значит речь идет о сочетаниях из 12 элементов по 3:

С312 = hello_html_27a61675.gif =hello_html_m27dc1f5c.gif=220.

Ответ: 220 способов выбора дежурных.

2. На полке 12 компьютерных дисков: энциклопедия и 11 игр. Сколькими способами можно выбрать 3 диска, если:

а) энциклопедия нужна обязательно;

б) энциклопедия не нужна;

в) просто 3 диска?

Решение.

а) Так как энциклопедию уже выбрали, то остается выбрать 2 диска из 11:

С211=hello_html_780d17a1.gif

б) С311=hello_html_3725c07e.gif

в) С312=hello_html_271b72b.gif

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

С25* С35=hello_html_468d15dd.gifhello_html_m65c21465.gifhello_html_m28e87876.gif



Задачи по комбинаторике

1.Запишите все двузначные числа, в записи которых используются только цифры 3 и 7.

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

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

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

5.Шифр для сейфа составляется из трех разных цифр. Запишите все шифры, которые можно составить, используя цифры 1, 2 и 3.

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

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

Указание. Перебирая варианты, введите обозначения: Р — русский язык, М — математика, Ф — физкультура.

8.В магазине продаются полотенца трех видов: в полоску, в клетку и в горошек. Из скольких вариантов покупки придется выбирать, если нужны два разных полотенца?

Указание. Введите обозначения: П- полоска, К — клетка, Г — горошек.

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

10.Сколькими способами можно составить патруль из двух милиционеров, если на дежурство вышли четверо: Быстров, Свистунов, Умнов и Дубов?

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

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

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

14.Проведите прямую, отметьте на ней три точки и обозначьте их. Сколько получилось отрезков с концами в этих точках? Сколько лучей с началом в этих точках?

15.Школьники из Волгограда собрались на каникулы поехать в Москву, посетив по дороге Нижний Новгород.
Сколькими различными способами могут ребята осуществить свое путешествие, если из Волгограда в Нижний Новгород можно отправиться на теплоходе или поезде, а из Нижнего Новгорода в Москву — на самолете, теплоходе, поезде или автобусе? Решите задачу с помощью построения дерева.

16.В костюмерной имеются желтые и белые кофты, а также синие, красные и черные юбки. Сколько можно из них составить различных костюмов? Решите задачу с помощью построения дерева. (Введите обозначения: Б —белые, Ж — желтые кофты; С — синие, К — красные, Ч — черные юбки.)

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

Б. 18.. Отметьте и обозначьте три точки, не лежащие на одной прямой. Сколько можно построить ломаных с вершинами в этих точках? Начертите их, используя карандаши разных цветов.

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

20.Две волейбольные команды «Ласточка» и «Орленок» играют матч до трех побед. С каким счетом может закончиться их поединок, если в волейболе ничьих не бывает? Составьте таблицу всех возможных вариантов исхода поединка.

21.Дано число 3241. Запишите все числа, большие данного, которые можно получить с помощью перестановки цифр этого числа.

22.Хоккейная комбинация. На поле пять игроков. Начал комбинацию игрок № 1, продолжили игроки с другими номерами, а забил гол игрок № 5. Каждый хоккеист
ударил по шайбе только один раз.

23.Запишите все трехзначные числа, сумма цифр которых равна 3.

24.В школьной лотерее должно быть всего десять различных выигрышей. Есть ручки, блокноты, записные книжки, альбомы для рисования. Можно ли из этих предметов составить десять различных выигрышей, по два разных предмета в каждом?

25.Девять школьников, сдавая экзамены по математике, русскому и английскому языкам, получили отметки «4»и «5». Можно ли утверждать, что по крайней мере двое из них получили по каждому предмету одинаковые отметки?

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

27.В телеигре участвуют пять человек, из них трое выходят в финал. Сколько существует различных вариантов тройки финалистов?

29.Сколько существует трехзначных чисел, записанных цифрами 1 и 3 так, что сразу после единицы не стоит тройка?

30.Сколько существует двузначных чисел, у которых первая цифра больше второй?

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

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

34.Витя, Толя и Игорь купили вместе интересную книгу и решили читать ее по очереди. Выпишите все варианты такой очереди. Сколько есть вариантов, в которых Игорь на первом месте? Витя не на последнем месте?

35.Используя цифры 3, 4, 5, причем каждую только один раз составьте всевозможные трехзначные числа, которые делятся: а) на 2; б) на 5; в) на 3; г) на 6.

36.Выпишите всевозможные двузначные и трехзначные числа, которые можно составить из цифр 0, 1, 2, 3, используя каждую цифру в записи только один раз.

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

б) Для участия в эстафете 2 х 100 ж нужно выбрать двух мальчиков из пяти, обязательно указав, кто побежит первым, а кто — вторым. Перечислите все варианты выбора участников соревнования в этом случае. Сколько этих вариантов'

38..На районной олимпиаде по математике оказалось шесть победителей. Однако на областную олимпиаду можно отправить только двоих а) Сколько есть вариантов выбора двух кандидатов?

Указание: Дайте каждому победителю номер – от1 до 6.

б) Сколько есть вариантов, если один из шести ребят признан лучшим, и он обязательно будет участвовать в областной олимпиаде?

39.К переправе одновременно подошли пять человек. Лодочник сказал, что в его лодке поместятся только два пассажира.

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

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

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

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

Указание. Достаточно подсчитать число способов, которыми один курьер может выбрать два филиала из четырех.

41.Каждый из двух друзей может получить за контрольную по математике любую отметку от 2 до 5. Сколько существует вариантов получения ими отметок? Выпишите все эти варианты.

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

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

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

46.Поэт-модернист написал стихотворение, в котором первая строка — «Хочу пойти гулять куда-нибудь», а остальные строки все разные и получены из первой перестановкой слов.
Какое наибольшее количество строк может быть в этом стихотворении? Указание. В строке 4 разных слова, закодируйте их цифрами. Записав стихотворение в закодированном виде, «переведите» его на русский язык.

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

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

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

50.Для выступления на празднике руководитель школьного кружка бальных танцев отобрал шесть ребят: Аню, Таню и Нину, а также Володю, Диму и Сережу. а) Вальс будет исполнять одна пара. Сколько имеется вариантов выбора этой пары? б) Кадриль должны станцевать вместе две пары. Сколько есть вариантов выбора исполнителей этого танца? в)Мазурку будут исполнять одновременно три пары, Сколько имеется вариантов составления этих трех пар?

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

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

53.Егор и Андрей играют в настольный теннис до трех побед,(Ничьих в настольном теннисе не бывает.) а)Предположим, что первую партию выиграл Андрей, вторую и третью —- Егор* Сколько существует вариантов дальнейшего хода их поединка? Запишите каждый из них. б)Сколько существует вариантов развития поединка, при которых Андрей выиграет со счетом 3:2? Запишите каждый из них.в) Сколько всего существует вариантов хода их поединка?

54.Задача-исследование. 1) Аня и Галя карандашами пяти цветов — красным, синим, желтым, зеленым и фиолетовым —раскрашивают бумажные вымпелы для малышей, Аня делает двухцветные вымпелы, а Галя — трехцветные. Аня перебором подсчитала, что всего у нее 10 вариантов двухцветной раскраски. Галя подумала и, не перебирая варианты, сказа» ла5 что тогда вариантов трехцветной раскраски тоже 10. Запишите в строчку все 10 наборов из двух карандашей. Под каждым запишите дополняющий его до пяти цветов набор из трех карандашей . Может лм при этом какой-либо трехцветный набор повториться? оказаться неучтенным?

Докажите, что Галя права, продолжив рассуждение; когда Аня берет два каких-то карандаша, то Гале остаются некоторые три; если Аня переберет все возможные пары карандашей, то Галя .... Значит, ....

Четыре друга собрались на футбольный матч. Но им удалось купить только три билета. Сколькими способами они могут выбрать тройку счастливцев? Как удобнее перебирать:
тройки тех, кто пойдет, или тех, кто не пойдет?

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

б) В магазине продаются рубашки 4 цветов и галстуки 8 цветов. Сколько есть способов выбрать рубашку с галстуком?

Правило умножения

55.У Портоса есть сапоги со шпорами и без шпор, четыре разных шляпы и три разных плаща. Сколько у него вариантов одеться по-разному?

56.В кружке 6 учеников. Сколькими способами можно выбрать старосту кружка и его заместителя?

57.Четверо ребят должны дежурить в классе четыре дня подряд по одному дню каждый. Сколькими способами можно составить расписание их дежурств?

58.Концерт состоит из 5 номеров. Сколько имеется вариантов программы этого концерта?

59.а) Сколько можно составить четных двузначных чисел? б) Сколько существует четных трехзначных чисел?

Б60.Телефонная станция обслуживает абонентов, у которых номера телефонов состоят из 7 цифр и начинаются с 313. На сколько абонентов рассчитана эта станция?

61.Аппаратура телефонной сети, обслуживающей 300 000 абонентов, рассчитана на 6 цифр в номере. Хватит ли этой сети для обслуживания еще 700 000 абонентов?

62.В автохозяйстве 1001 автомобиль. Для их регистрации выделены номера К***ОД50 (вместо * ставится любая цифра от 0 до 9). Хватит ли этих номеров на все автомобили хозяйства?

63.Сколько существует шестизначных чисел, у которых:

а)третья цифра — 3;

б)последняя цифра — четная;

в)на нечетных местах стоят нечетные цифры;

г)на нечетных местах стоят четные цифры?

64.Для передачи текста по радио и телеграфу используется азбука Морзе, в которой каждая буква состоит из точек и тире. Например, буква Е обозначается точкой «.», а буква Э — набором из пяти знаков «..—..». Достаточно ли наборов от одного до пяти знаков для обозначения всех букв русского алфавита и всех цифр? Почему букву Е решили обозначить одним знаком, а букву Э — пятью?

65.Саша и Даша решали задачу: «В спортивном клубе 5 пловцов имеют лучшие результаты. Сколькими способами можно составить из них команду из двух человек для участия в соревнованиях?»

Саша рассуждал так: «Есть 5 способов выбрать первого участника команды, при этом остается 4 способа выбора второго участника. Применим правило умножения 5 х 4 = 20. Итого — 20 способов».

Даша занумеровала всех пловцов и выписала все возможные варианты команды. У нее получилось всего 10 вариантов: 12; 13; 14; 15; 23; 24; 25; 34; 35; 45. Кто из ребят прав?

66.В футбольном чемпионате принимают участие 15 команд. Сколько всего игр будет сыграно на этом чемпионате если: а) каждая команда с остальными участниками играет на «своем» и на «чужом» поле; б)каждая команда сыграет с каждой только один раз? В каком случае можно применить правило умножения, а в каком нельзя? Почему?

7 класс

67.На почте продается 40 разных конвертов и 25 разных марок. Сколько есть вариантов покупки конверта с маркой?

68.Сколько существует четырехзначных чисел, составленных из нечетных цифр? из четных цифр? из четырех разных цифр?

69.Сколько существует пятизначных чисел, которые делятся на 2? на 5? на 10?

70.Сколько существует вариантов выбрать спикера и вице-спикера парламента, если всего в парламенте 101 депутат?

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

72.В компьютере каждый символ кодируется последовательностью, состоящей из восьми цифр — нулей и единиц. Например, символ «пробел» закодирован так: 00101000. Какое наибольшее число символов может быть таким образом закодировано в компьютере?

73.В чемпионате по настольному теннису участвовало 40 спортсменов, и каждый с каждым сыграл по одной партии. Сколько всего сыграно партий?

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

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

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

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

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

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

77.Сколько существует четырехзначных чисел, в записи которых встречается хотя бы одна четная цифра?

78.В латинском алфавите 26 букв. Будем считать «словом» любую последовательность, состоящую не более чем из 5 букв. Сколько всего таких «слов»?

79.Сколько всего делителей у числа 2 • З2 • 53?

Перестановки

80.В конкурсе участвуют 12 школьников. Сколькими способами могут быть распределены места между ними?

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

82.Сколько существует пятизначных чисел, состоящих из нечетных цифр, если ни одна из цифр в записи числа не повторяется?

83.Анаграмма, как вы уже знаете, — это «слово», полученное из данного слова перестановкой его букв (но не обязательно имеющее смысл). Сколько существует различных анаграмм слова «график»? слова «интеграл»?

84.Из цифр 1, 2, 3, 4, 5 составляются пятизначные числа, в которых все цифры разные.

а)Сколько всего таких чисел?

б)Сколько из них делятся на 5?

в)Сколько из них не делятся на 5?

85.Верно ли, что:

а)10! = 10 х9! 6)10! = 2!х5! в) 12!/11! =12?

Б86.Сколько существует анаграмм слова «факториал»? слова «перестановка»? слова «комбинаторика»?

87.Делится ли 100! на 47? на 99? на 101?

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

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

90.Сколькими нулями оканчивается число 100! ?



Литература:

  1. Ю.Н. Макарычев, Н.Г. Миндюк. Алгебра: элементы статистики и теории вероятностей. Под редакцией С.А Теляковского. Москва. Просвещение, 2003 год.

  2. М.В. Ткачева, Н.Е. Федорова. Элементы статистики и вероятность. 7-9 класс. Москва. Просвещение, 2005 год.

  3. Л.П. Попова. Поурочные разработки по математике. К учебному комплексу Н.Я. Виленкина 5 класс. Москва. ВАКО, 2009 год.

  4. В.В. Выговская. Поурочные разработки по математике. К учебному комплексу Н.Я. Виленкина 6 класс. Москва. ВАКО, 2008 год.

  5. А.Н. Рурукин. Поурочные разработки по алгебре. К учебникам Ю.Н. Макарычева, Ш.А. Алимова 7 класс. Москва. ВАКО, 2008 год.

  6. А.Н. Рурукин. Поурочные разработки по алгебре. К учебникам Ю.Н. Макарычева, Ш.А. Алимова 8 класс. Москва. ВАКО, 2009 год.

  7. П.А. Ларичев. Сборник задач по алгебре. Москва. УЧПЕДГИЗ. 1961 год.

  8. Е.В. Смыкалова. Математика, дополнительные главы. 5 класс. Санкт-Петербург. СМИО Пресс 2006 год.

  9. Е.В. Смыкалова. Математика, дополнительные главы. 6 класс. Санкт-Петербург. СМИО Пресс 2008 год.

  10. Е.В. Смыкалова. Математика, дополнительные главы. 7 класс. Санкт-Петербург. СМИО Пресс 2008 год.

  11. Е.В. Смыкалова. Математика, сборник задач. 5 класс. Санкт-Петербург. СМИО Пресс 2007 год.

  12. Е.В. Смыкалова. Математика, сборник задач. 6 класс. Санкт-Петербург. СМИО Пресс 2007 год.

  13. Е.В. Смыкалова. Математика, сборник задач. 5 класс. Санкт-Петербург. СМИО Пресс 2007 год.

Выберите курс повышения квалификации со скидкой 50%:

Краткое описание документа:

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

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

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Рассмотрим некоторые понятия, которые назовем «Элементами комбинаторики»:

1. Примеры комбинаторных задач.

2. Перестановки.

3. Размещения.

4. Сочетания.

Автор
Дата добавления 23.06.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров832
Номер материала 310401
Получить свидетельство о публикации
Похожие материалы

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