38661

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

Дипломная

Математика и математический анализ

Сколькими способами они могут занять очередь Решение Метод перебора: ДАК ДКА АДК АКД КДА КАД. Дерево возможных вариантов: Ответ: 6 способами. Правило суммы: Если объект А может быть выбран n способами а объект В m способами то выбор объектов А или В может быть осуществлён m n способами. Правило произведения: Если объект А может быть выбран n способами и при каждом способе выбора объекта А объект В может быть выбран m способами то выбор объектов А и В можно произвести m ∙ n способами.

Русский

2013-09-28

1.46 MB

411 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра высшей математики

Выпускная квалификационная работа

По специальности 050201.65 «Математика»

(с дополнительной специальностью 050202.65 «Информатика»).

«Избранные комбинаторные задачи»

Выполнила: студентка 5 курса

физико-математического факультета

отделения «математика-информатика»

Бакаева Ольга Викторовна

Научный руководитель: кандидат

физико-математических наук,

доцент кафедры высшей математики

Гордиенко Наталья Андреевна

Воронеж 2013

Содержание

1. Введение

3

2. Элективный курс на тему «Избранные комбинаторные задачи»

2.1. Занятие 1. Вводное занятие. Метод перебора и дерево возможных вариантов

  5

2.2. Занятие 2. Правило суммы и правило произведения

13

2.3. Занятие 3. Перестановки без повторений

20

2.4. Занятие 4. Размещения без повторений

27

2.5. Занятие 5. Сочетания без повторений

35

2.6. Занятие 6. Контрольная работа №1

42

2.7. Занятие 7. Перестановки с повторениями

45

2.8. Занятие 8. Размещения с повторениями

51

2.9. Занятие 9. Сочетания с повторениями

57

2.10. Занятие 10. Задачи на картах

63

2.11. Занятие 11. Задачи на шахматной доске

71

2.12. Занятие 12. Контрольная работа №2

75

3. Заключение

78

4. Список литературы

80

5. Приложения

5.1. Приложение 1. Историческая справка

82

5.2. Приложение 2. Учебный план элективного курса

86

1. Введение

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

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

Целесообразность их введения в школьный курс математики неоднократно отмечалась в работах С.Н. Бернштейна, А.Н. Колмогорова, А.Я. Хинчина, Б.В. Гнеденко.

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

Актуальность решения комбинаторных задач и обусловила выбор темы данной выпускной квалификационной работы.  

Задачи работы обусловлены её целями:

  1.  раскрыть теоретическое содержание данной темы;
  2.  на практическом примере продемонстрировать использование методов решения комбинаторных задач.

Задачи выпускной квалификационной работы:

  1.  изучить комбинаторные характеристики натурального ряда;
  2.  рассмотреть примеры решения различных комбинаторных задач.

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

Основная часть занятий состоит из теоретической (объяснение нового материала с примерами) и практической части.

В элективном курсе рассматриваются следующие темы:

  •  перестановки без повторений и с повторениями;
  •  размещения без повторений и с повторениями;
  •  сочетания без повторений и с повторениями;
  •  задачи на картах;
  •  комбинаторные задачи на шахматной доске.

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

  1.  Новосёлов С.И. «Специальный курс элементарной алгебры» : изд.7 – М; Высшая школа, 1965. – 551с.
  2.  Виленкин Н.Я. «Комбинаторика» – М.; Наука, 1969. – 328с.  
  3.  Виленкин Н.Я. «Задачник-практикум по теории вероятностей с элементами комбинаторики и математической статистики» – М.; Просвещение, 1979. – 111с.
  4.  Окунев Л.Я. «Комбинаторные задачи на шахматной доске» – Л.; 1935. – 87с.
  5.  Гнеденко Б. В. «Очерк по истории теории вероятностей» – М.; УРСС, 2001. – 88с.

2. Элективный курс на тему «Избранные комбинаторные задачи»

2.1. Занятие 1. Вводное занятие. Метод перебора и дерево возможных вариантов

Цели:

  •  дать понятие науки «Комбинаторика»;
  •  познакомить учащихся с историей данной науки;
  •  изучить метод перебора и дерево возможных вариантов.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Работа по теме.

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

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

С комбинаторными задачами люди столкнулись в глубокой древности. В Древнем Китае увлекались составлением магических квадратов. В Древней Греции занимались теорией фигурных чисел.

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

После первых работ, выполненных в XVI веке итальянскими учеными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым  рассмотрел комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666г. Работу «Об искусстве комбинаторики». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру.

Существует несколько методов решения комбинаторных задач:

1.   метод перебора;

2.   правило суммы;

3.   правило произведения;

4.   таблицы;

5.   графы (деревья);

6.   формулы.

Мы изучим метод перебора, правило суммы, правило произведения и формулы.

Метод перебора

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

а)   рассматривать все возможные случаи;

б)   найти те, которые удовлетворяют условию данной задачи;

Задачи для решения с учителем

Задача 1

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

Решение

Для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:

11, 14, 17, 41, 44, 47, 71, 74, 77.

Таким образом, их трех данных цифр можно составить всего 9 различных двузначных чисел.

Эту задачу можно решить и другим способом. Его название – дерево возможных вариантов. Для этой задачи построена специальная схема.

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

Далее отводим от звездочки 3 отрезка, так как в условии задачи даны 3 цифры – 1, 4, 7. Ставим эти цифры на концах отрезков. Они будут обозначать число десятков в данном числе. Далее от каждой цифры проводим по 3 отрезка. От цифры 1 три отрезка, от цифры 4 три отрезка и от цифры 7 также проводим три отрезка. На концах этих отрезков записываем также цифры 1, 4, 7. Они будут обозначать число единиц. Рассмотрим, какие числа получились: 11, 14, 17, 41, 44, 47, 71, 74, 77. То есть всего получилось 9 чисел. Такой метод называется деревом возможных вариантов.

Ответ: 9 чисел.

Задача 2

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

Решение

Метод перебора:

333, 335, 353, 355, 533, 535, 553, 555.

Дерево возможных вариантов:

Ответ: 8 чисел.

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

Задача 3

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

Решение

Метод перебора:

Р М Ф,  Р Ф М,  М Р Ф,  М Ф Р,  Ф Р М,  Ф М Р.

Дерево возможных вариантов:

Ответ: 6 вариантов.

Задача 4

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

Решение

Метод перебора:

509, 590, 905, 950.

Дерево возможных вариантов:

Ответ: 4 числа.

Задача 5

Данила, Андрей и Коля собрались потренироваться в бросании мяча в баскетбольную корзину. У них только один мяч, и им надо договориться, кто за кем будет бросать мяч в корзину. Сколькими способами они могут занять очередь?

Решение

Метод перебора:

Д-А-К, Д-К-А, А-Д-К, А-К-Д, К-Д-А, К-А-Д.

Дерево возможных вариантов:

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

Задача 6

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

Решение

Метод перебора:

ЗК-СЮ, ЗК-КЮ, ЗК-ЧЮ, ЖК-СЮ, ЖК-КЮ, ЖК-ЧЮ.

Дерево возможных вариантов:

Ответ: 6 костюмов.

Задача 7

Выписаны в порядке возрастания все трехзначные числа, в записи которых используются только цифры 0, 2, 4, 6. Какое число следует за числом 426?

Решение

Самый младший разряд числа 426 (то есть разряд единиц) увеличить нельзя – там стоит цифра 6. Разряд десятков увеличить можно – нужно цифру 2 заменить на следующую за ней цифру 4. После этого в разряд единиц нужно поставить минимальную цифру – 0. Получилось число 440.

Ответ: 440.

3.   Домашнее задание.

Темы докладов для учеников.

1.   Джироламо Кардано.

2.   Никколо Тарталья.

3.   Бином Ньютона;

4.   Блез Паскаль.

5.   Пьер Ферма.

6.   Треугольник Паскаля.

7.   Леонард Эйлер.

8.   Галилео Галилей.

9.   Готфрид Лейбниц.

10. Комбинаторная геометрия.

Задача 1

Сколько всего четырехзначных чисел можно составить из цифр 0 и 3?

Решение

Метод перебора:

3 000, 3 300, 3 030, 3 003, 3 300, 3 303, 3 330, 3 333.

Дерево возможных вариантов:

Ответ: 8 чисел.

Задача 2

Сколько слов четырёхбуквенных слов можно составить из букв Ы, А, Л?

Решение

Метод перебора:

АЫЛ, АЛЫ, ЛЫА, ЛАЫ.

Дерево возможных вариантов:

Ответ: 4 слова.

2.2. Занятие 2. Правило суммы и правило произведения

Цели:

  •  изучить сущность правила суммы и правила произведения;
  •  рассмотреть примеры решения задач, используя эти правила.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

Правило суммы: Если объект А может быть выбран n способами, а объект В m способами, то выбор объектов А или В может быть осуществлён m + n способами.

Правило произведения: Если объект А может быть выбран n способами, и при каждом способе выбора объекта А, объект В может быть выбран m способами, то выбор объектов А и В можно произвести mn способами.

Задачи для решения с учителем

Задача 1

([4], стр. 17) На книжной полке стоят 20 книг по алгебре, 12 – по теории вероятностей, 7 – по математическому анализу и 25 – по литературе. Сколькими способами можно выбрать книгу по математике?

Решение

Найдём количество способов, которыми можно выбрать книгу по алгебре, или по теории вероятностей, или по математическому анализу. Книгу по алгебре можно выбрать 20 способами, по теории вероятностей – 12 способами и по математическому анализу – 7 способами. По правилу суммы находим, что выбрать книгу по математике можно  способами.

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

Задача 2

([4], стр. 18) Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет спортлото или автомотолотереи?

Решение

Один билет спортлото можно сделать 6-ю способами, а автомотолотереи – 10-ю способами. Используя правило суммы, получаем

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

Задача 3

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

Решение

Для того, чтобы подняться на холм есть 5 способов. Учитывая условие, в котором говорится, что спускаться и подниматься нужно по разным тропинкам, спуск с холма можно совершить 4-мя способами. Используя правило произведения, получаем

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

Задача 4

В первой группе класса «А» первенства города по футболу участвуют 17 команд. Разыгрываются медали: золотые, серебряные и бронзовые. Сколькими способами они могут быть распределены?

Решение

Эта задача решается на основе правила произведения. Золотые медали может получить любая из 17 команд. Иными словами, здесь у нас 17 возможностей. Но если золотые медали уже получены какой-то командой, то остаётся лишь 16 претендентов на серебряные медали, то есть 16 возможностей. Повторения быть не может, так как одна и та же команда не может завоевать и золотые, и серебряные, и бронзовые медали.

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

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

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

Задача 5

([4], стр. 18) В отряде 5 разведчиков, 4 связиста и 2 санитара. Сколькими способами можно выбрать одного солдата так, чтобы он был или разведчиком или санитаром? Сколькими способами можно составить разведгруппу из трёх человек, чтобы в неё вошли разведчик, связист и санитар?

Решение

Разведчика можно выбрать 5-мя способами, а санитара – 2-мя, тогда по правилу суммы одного солдата можно выбрать  способами.

Используя предыдущие рассуждения и то, что связиста можно выбрать 4-мя способами, по правилу произведения получим, что разведгруппу можно составить способами.

Ответ: 7 способами, 40 способами.

Задача 6

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

Решение

Белую ладью можно поставить на любую из 64 клеток. Независимо от своего расположения она бьет 15 полей (включая поле, на котором она стоит). Поэтому остается 49 полей, на которые можно поставить черную ладью. Таким образом, всего есть 3 136 разных способов.

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

Задача 7

Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение

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

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

Задача 8

([4], стр. 19) В магазине имеется 5 сортов конфет. Сколько различных покупок, содержащих не более трёх сортов  конфет, можно сделать в этом магазине (покупки считаются одинаковыми, если они состоят из одинаковых сортов конфет)?

Решение

Исходя из условия задачи, ясно, что мы должны найти количество покупок, состоящих либо из 3-х, сортов, либо из 2-х. либо из одного. По правилу произведения покупку из 3-х сортов конфет можно сделать способами, из 2-х – способами, а из одного – 5-ю способами. По правилу суммы подсчитываем общее количество способов:

 

Ответ: 85 покупок.

Задача 9

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

Решение

Действие, которое должно быть выполнено особым способом, необходимо выполнять первым. Итак, на место водителя можно посадить только одного из трех человек (умеющего водить машину), т.е. существуют 3 способа занять первое место. Второе место может занять любой из 6 человек, оставшихся после того, как место водителя будет занято и т.д. Используя принцип умножения, получаем произведение:

2 260.

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

Задача 10

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

Решение

Нечетных цифр пять: 1, 3, 5, 7, 9. Очевидно, однозначных чисел можно составить 5. Количество двузначных, трехзначных и четырехзначных чисел можно найти по правилу умножения:

двухзначных – ;

трехзначных – ;

четырехзначных – .

Используем правило сложения:

Ответ: 780 чисел.

  1.  Домашнее задание.

Задача 1

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

Решение

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

 

Ответ: 24 числа.

Задача 2

([4], стр. 18) В магазине имеется 6 сортов шоколадных конфет и 4 сорта карамели. Сколько различных покупок конфет одного сорта можно сделать в этом магазине? Сколько можно сделать различных покупок, содержащих один сорт шоколадных конфет и один сорт карамели?

Решение

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

Ответ: 10 покупок; 24 покупки.

Задача 3

Сколько различных слов (необязательно осмысленных), не менее, чем из 4-х разных букв, можно образовать из букв слова УЧЕНИК?

Решение

Слово УЧЕНИК состоит из 6-ти букв. По правилу произведения четырёхбуквенных слов, пятибуквенных и шестибуквенных слов. По правилу суммы всего можно составить  1 800 слов, состоящих не менее, чем из 4-х букв.

Ответ:  1 800 слов.

Задача 4

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

Решение

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

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

2.3. Занятие 3. Перестановки без повторений

Цели:

  •  сформулировать определение перестановок;
  •  изучить вычисление факториала;
  •  рассмотреть примеры решения комбинаторных задач, используя формулу перестановок.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

В математике и в ее приложениях нередко рассматриваются  множества (мы ограничиваемся лишь конечными множествами) упорядоченные, элементы которых задаются «в определенном порядке». Так, например, алфавит есть упорядоченное множество из 33-х букв: в алфавите буквы выписываются в определенном порядке. Так, в русском алфавите буква Б следует за А, В следует за Б и т. д., буква А (первая) не следует ни за какой буквой, а за буквой Я (последняя) не следует ни одной буквы.

Пусть дано n элементов.

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

Две перестановки считаются различными, если они отличаются порядком элементов в своих наборах. Например, перестановки из цифр 1, 3, 5 будут отличаться: 135, 153, 315, 351, 513, 531.

Теорема. Число всевозможных перестановок, которые могут быть образованы из n элементов, выражается формулой:

Факториал числа n (лат. factorialis — действующий, производящий, умножающий) — произведение всех натуральных чисел от 1 до n включительно.

Пример

([1], стр. 532) Ниже выписаны всевозможные перестановки из четырех элементов:

1 2 3 4

2 1 3 4

3 1 2 4

4 1 2 3

1 2 4 3

2 1 4 3

3 1 4 2

4 1 3 2

1 3 2 4

2 3 1 4

3 2 1 4

4 2 1 3

1 3 4 2

2 3 4 1

3 2 4 1

4 2 3 1

1 4 3 2

2 4 1 3

3 4 1 2

4 3 1 2

1 4 2 3

2 4 3 1

3 4 2 1

4 3 2 1

Задачи для решения с учителем

Задача 1

Сколькими способами 4 мужчины могут расположиться на четырехместной скамейке?

Решение

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

Задача 2

([1], стр. 534) Сколько различных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, причем:

a) каждая цифра в обозначении числа встречается один раз;

б) цифра 0 не должна занимать первое место?

Решение

Если не принимать во внимание условие б), то из 10 цифр можно составить 3 628 800 различных чисел, в которых каждая цифра содержится один раз. Из общего количества полученных чисел  чисел начинаются цифрой 0. Следовательно, искомое количество чисел равно:

3 265 920.

Ответ: а) 3 628 800 чисел;  б) 3 265 920 чисел.

Задача 3

Сколько среди четырехзначных чисел, составленных из цифр 3, 5, 7, 9 (без повторения цифр), есть такие, которые: 1) начинаются с цифры 3; 2) кратны 5?

Решение

  1.  Так как на первом месте стоит цифра 3, то оставшиеся цифры мы можем выбрать  способами;
  2.  Как мы знаем, числа кратные 5 оканчиваются либо 0, либо 5. В нашем случае предлагаются составить числа из цифр 3, 5, 7 ,9. Так как последней должна быть цифра 5, то первые 3 цифры можно выбрать  способами.

Ответ: 1) 6 чисел;  2) 6 чисел.

Задача 4

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

Решение 

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

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

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

Задача 5

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

Решение

Ответ: 120 маршрутов.

Задача 6

Сколько шестизначных чисел (без повторения цифр) можно составить из цифр: 1) 1, 2, 5, 6, 7, 8;      2) 0, 2, 5, 6, 7, 8?

Решение

1)  

2)  

Ответ: 1) 720 чисел; 2) 600 чисел.

Задача 7

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

Решение

604 800.

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

Задача 8

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

Решение

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

 

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

Задача 9

([3], стр. 36) Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?

Решение

Если бы они стояли на месте, то получилось бы 5 040 перестановок. Но так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц,  надо считать одинаковыми. Но из каждой перестановки можно получить ещё шесть новых путём вращения. Значит, число 5 040 надо разделить на 7. Мы получаем 5 040 : 7 = 720 различных перестановок девушек в хороводе. На рисунке схематично показано расположение девушек в хороводе. И если это изображение симметрично отразить, то мы увидим новые перестановки. Учитывая этот факт, ответом на задачу является 720 : 2 = 360.

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

Задача 10

([4], стр. 24) Сколько ожерелий из 6 бусинок  каждое можно составить из бусинок разных размеров?

Решение

Рассуждая, как в прошлой задаче, получаем:

 

Ответ: 30 ожерелий.

  1.  Домашнее задание.

Задача 1

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

Решение

2 903 040.

Ответ: 2 903 040 способами.

Задача 2

В субботу в 5 «А» классе 5 уроков: физкультура, русский язык, литература, ИЗО, математика. Сколько можно составить вариантов расписания на день, зная, что математика – последний урок?

Решение

Ответ: 24 варианта.

Задача 3

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

Решение

Чётные числа из этих цифр получатся, если на последнем месте будет 0. Таким образом, получаем:  

Ответ: 120 чисел.

Задача 4

На библиотечной полке стоят 30 книг, причем 27 - книги разных авторов и еще 3 книги одного автора. Сколькими способами можно расставить эти книги так, чтобы книги одного автора стояли рядом друг с другом?

Решение

Временно объединим три книги одного автора в один объект, всего получим 28 объектов - 27 книг и 1 объект из трех книг. Для них число перестановок будет равно Р28. Теперь три книги переставим между собой Р3 способами. По правилу произведения получаем, что число способов расставить книги нужным образом равно:

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

2.4. Занятие 4. Размещения без повторений

Цели:

  •  сформулировать определение размещения без повторений;
  •  рассмотреть примеры решения комбинаторных задач, используя формулу размещений без повторений.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

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

Два размещения считаются разными, если они различаются наборами элементов или расположением элементов в наборе.  

Пример

([1], стр. 536) Ниже выписаны всевозможные размещения, составленные из четырех элементов по 3

1 2 3

1 2 4

1 3 4

2 3 4

1 3 2

1 4 2

1 4 3

2 4 3

2 1 3

2 1 4

3 1 4

3 2 4

2 3 1

2 4 1

3 4 1

3 4 2

3 1 2

4 1 2

4 1 3

4 1 3

3 2 1

4 2 1

4 3 1

4 3 1

Теорема. Число различных размещений, взятых из n элементов по k, выражается формулой:

Некоторые свойства размещений:

1., если k > n.

2.

3.

4.

5.

Задачи для решения с учителем

Задача 1

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

Решение

Значит, ответ на выше поставленную задачу будет

151 200.

Ответ: 151 200 номеров.

Задача 2

Сколько четырехбуквенных слов можно образовать из букв слова САПФИР? Сколько среди них таких, которые не содержат буквы Р? Сколько таких, которые начинаются с буквы С и оканчиваются буквой Р?

Решение

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

 

2)  Необходимо исключить букву Р из рассмотрения. Количество слов, не содержащих эту букву:

 

3)  На первое место поставить букву С можно только одним способом. На последнее место поставить букву Р можно тоже только одним способом. Остаются 4 буквы, которые необходимо разместить по двум местам:

Ответ: 360 слов; 120 слов; 12 слов.

Задача 3

Для запирания сейфов применяют секретные замки, которые открываются лишь тогда, когда набран определённый код. Этот код набирают с помощью одного  или нескольких дисков, на которых нанесены цифры (или буквы). Пусть на диск нанесены цифры от 0 до 9, а код состоит из 5 цифр, причём цифры в коде не повторяются. Сколько неудачных попыток может быть сделано человеком, не знающим секретного кода?

Решение

Используя формулу, получаем:

30 240.

30 240 вариантов кода, из которых только один верный. Значит, человек, не знающий кода, может сделать 30 239 неудачных попыток.

Ответ: 30 239 попыток.

Задача 4

([1], стр. 537) Сколько различных натуральных чисел можно составить из цифр 0, 1, 2, 3, 4, если в обозначении каждого числа каждая из данных цифр входит не более одного раза?

Решение

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

пятизначных чисел.

Количество различных четырехзначных чисел, которые можно составить из цифр 0, 1, 2, 3, 4, равно   за вычетом количества тех размещений, которые начинаются нулем, т. е.

 

Аналогично количество различных трехзначных, двузначных и однозначных чисел будет равно соответственно

и 4

В результате:

Ответ: 260 чисел.

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

Задача 5

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

Решение

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

 

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

 

C другой стороны, фиксированная фишка может занимать одно из трех мест. Тогда общее число комбинаций равно

Ответ: 60 комбинаций; 36 комбинаций.

Задача 6

Сколько диагоналей имеет выпуклый 38-угольник?

Решение

Диагонали многоугольника соединяют несмежные вершины, поэтому задача сводится к поиску количества пар несмежных вершин. Число всевозможных пар  – , но из этого числа, необходимо вычесть повторяющиеся пары (АВ и ВА), то есть разделить общее число пар на 2, а также вычесть пары соседних вершин, их 38. В итоге получим

 

Ответ: 665 диагоналей.

Задача 7

([4], стр. 24) Сколькими способами можно переставить буквы слова ЛОГАРИФМ так, чтобы 2-е, 4-е и 6-е места были заняты согласными буквами?

Решение

В слове ЛОГАРИФМ 5 согласных букв, поэтому на 2-е, 4-е и 6-е места можно занять  способами, а оставшиеся 5 мест  способами. Используя правило произведения, получаем

7 200.

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

Задача 8

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

Решение

Исходя из условия, можно сделать вывод, что выбранные слова будут состоять либо из одной, либо из 2-х, либо из 3-х, либо из 4-х букв.

2 080.

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

Задача 9

Сколько трёхзначных чисел, не превышающих 500, можно составить из цифр 0, 1, 3, 5, 7, 9  (цифры в числах не повторяются)?

Решение

Из данных 6 цифр можно составить  трёхзначных чисел. Из них необходимо исключить все те числа, которые начинаются с 0, т.е. . Так как, составленные числа не должны превышать 500, то мы должны исключить те, которые начинаются на цифры 5, 7, 9. Всего их получится . В итоге получаем:

Ответ:  40 чисел.

Задача 10

Сколькими способами можно посадить за круглый стол 7 мужчин и 7 женщин так, чтобы 2 женщины не сидели рядом.

Решение

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

  1.  Домашнее задание.

Задача 1

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

Решение

2 520.

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

Задача 2

([4], стр. 23) Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского на любой другой из этих пяти языков?

Решение

20.

Ответ: 20 словарей.

Задача 3

([4], стр. 24) Имеется 4 чашки, 5 блюдец, 6 чайных ложек (все чашки, блюдца и ложки различные). Сколькими способами может быть накрыт стол для чаепития на трёх человек, если каждый получит одну чашку, одно блюдце, одну ложку?

Решение

172 800.

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

Задача 4

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

Решение

Ответ: 60 чисел.

2.5. Занятие 5. Сочетания без повторений

Цели:

  •  сформулировать определение сочетания без повторений;
  •  рассмотреть примеры решения комбинаторных задач, используя формулу сочетаний без повторений.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

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

Два сочетания считаются разными, если они различаются наборами элементов.  

Пример

([1], стр. 536) Ниже выписаны всевозможные сочетания, составленные из 5 элементов 1, 2, 3, 4, 5 по 3:

123, 124, 125, 134,135, 145

234, 235, 245

345

Теорема. Число различных сочетаний, взятых из n элементов по k, выражается формулой:

Некоторые свойства размещений:

1. , если k > n.

2.

4.

5.

Задачи для решения с учителем

Задача 1

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

Решение

Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание. Таким образом,

Ответ: 120 комбинаций.

Задача 2

На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если:

а) словарь ему не нужен;

б) словарь нужен ему обязательно?

Решение

а)  

б)  

Ответ: 165 способами; 55 способами.

Задача 3

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

Решение

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

 

Ответ: 200 случаев.

Задача 4

Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Решение

Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:

Далее независимо аналогичным образом выберем мужчин на вторую специальность:

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

  1.  1 женщина и 2 мужчин (выбираем женщину  способами)
  2.  1 мужчина и 2 женщины (выбираем мужчину  способами).

В итоге получаем 1 680 способов.

Ответ: 1 680 способов.

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

Задача 5

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

Решение

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

Поэтому   искомое  число

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

Задача 6

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

Решение

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

Ответ:  диагоналей.

Задача 7

([4], стр. 23) Даны натуральные числа от 1 до 30. Сколькими способами можно выбрать три числа так, чтобы их сумма была чётной?

Решение

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

1 575 = 2 030.

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

Задача 8

([4], стр. 24) У одного человека имеется 7 книг, а у другого – 9. Сколькими способами они могут обменять друг у друга  две книги на две книги?

Решение

Используя правило произведения, получаем:

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

Задача 9

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

Решение

Сначала выбираем одну точку и 7 на первой прямой:  После чего выбираем одну точку на второй прямой и 2 на первой:  Используя правило сложения, получаем:

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

Задача 10

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

Решение

Из 20 человек можно выбрать 5 человек  различными способами. Принимая во внимание условие, что начальник, его заместитель и главный инженер одновременно уезжать не должны, исключаем из всевозможных групп те, в которых данное условие выполняется:  В результате получается:

15 054 – 136 = 14 918.

Ответ: 14 918 групп.

  1.  Домашнее задание.

Задача 1

([4], стр. 24) В состав сборной включены 2 вратаря, 5 защитников, 6 полузащитников и 6 нападающих. Сколькими способами тренер может выставить на поле команду, в которую входит вратарь, 3 защитника, 4 полузащитников и 3 нападающих?

Решение

6 000.

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

Задача 2

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

Решение

Чтобы выбрать из 20-ти мужчин 3, существует  способов. Остается 17, из которых выбирается 5 мужчин –  способами. Остается 12 мужчин, как раз в оставшуюся группу. Используя правило произведения, получаем: .

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

Задача 3

Сколькими способами можно выбрать из слова ДУБЛИКАТ две согласных и одну гласную букву?

Решение

Одну гласную букву можно выбрать 3-мя способами, а 2 согласных – .

Используя правило произведения, получаем:

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

Задача 4

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

Решение

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

  1.   Занятие 6. Контрольная работа №1

Вариант 1

Задача 1

Сколько трёхзначных чисел можно составить из цифр 0, 3, 5, 6, не превышающих 530? Выпишите эти числа. Решить, используя дерево возможных вариантов или метод перебора.

Задача 2

В ресторанном меню есть выбор из 5-ти первых блюд,  3-х салатов, 7-ми вторых блюд, 3-х десертов. Сколькими способами можно составить заказ, если он должен содержать первое блюдо, второе блюдо, салат и десерт?

Задача 3

Электрик должен проверить проводку в 6 домах. Сколькими способами он может это сделать?    

Задача 4

В парке аттракционов работает детская карусель с 6-ю разными животными. Сколькими способами можно расположить животных на карусели?

Задача 5

Сколько различных слов (необязательно осмысленных), не менее чем из 4-х различных букв, можно образовать из букв слова ЛАДОНЬ, причём каждая буква может быть выбрана только один раз?

Задача 6

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

Задача 7

Сколько хорд можно провести через 6 точек, лежащих на одной окружности?

Задача 8

Из 15 членов туристической группы нужно выбрать 3-х дежурных, одного повара и ещё 2-х человек, которые должны развести костёр. Сколькими способами это можно сделать?

Задача 9

([4], стр. 24) В классе 30 учеников. Ежедневно для дежурства выделяются 2 ученика. Можно ли составить расписание дежурств так, чтобы никакие 2 ученика не дежурили вместе дважды в течение учебного года?

Вариант 2

Задача 1

Сколько трёхзначных чисел можно составить из цифр 0, 1, 4, 8, не превышающих 411? Выпишите эти числа. Решить, используя дерево возможных вариантов или метод перебора.

Задача 2

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

Задача 3

Почтальон должен отнести письма в 5 домов. Сколькими способами он может это сделать?

Задача 4

Сколько различных слов (необязательно осмысленных), не менее чем из 4-х разных букв, можно образовать из букв слова КРОВАТЬ, причём каждая буква может быть выбрана только один раз?

Задача 5

Сколькими способами можно расположить 7 кружек на круглой вращающейся поставке?

Задача 6

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

Задача 7

На тренировках занимаются 10 баскетболистов. Сколько различных стартовых пятерок может образовать тренер? 

Задача 8

Сколько диагоналей можно провести в пятиугольнике?

Задача 9

Из 15 сотрудников фирмы 4-м выделяется премия в 1000р., 3-м премия в 1500р. и 2-м премия в 2000р. Сколькими способами это можно сделать, при условии, что сотрудник может получить только одну премию.

Ответы к контрольной работе №2

Вариант 1

  1.  21;
  2.  315;
  3.  720;
  4.  60;
  5.  430;
  6.  80;
  7.  15;
  8.  300 300;
  9.  435, можно.

Вариант 2

  1.  22;
  2.  80;
  3.  120;
  4.  942;
  5.  360;
  6.  720;
  7.  252;
  8.  5;
  9.  6 306 300.

  1.   Занятие 7. Перестановки с повторениями

Цели:

  •  сформулировать определение перестановок с повторениями;
  •  рассмотреть примеры решения комбинаторных задач, используя формулу перестановок с повторениями.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Выступление ученика с докладом.
  3.  Работа по теме.

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

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

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

Пример

Ниже выписаны все перестановки, в которых элементы a, b и с повторяются 2, 2 и 1 раз соответственно.

aabbc

aabcb

aacbb

ababc

abacb

abbac

abbca

abcab

abcba

acabb

acbab

acbba

baabc

baacb

babac

babca

bacab

bacba

bbaac

bbaca

bbcaa

bcaba

bcaba

bcbaa

caabb

cabab

cabba

cbaab

cbaba

cbbaa

Теорема. Число различных перестановок с повторениями из n элементов, в которых элементы 1, 2, …, n повторяются соответственно  раз, выражается формулой:

Задачи для решения с учителем

Задача 1

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

Решение

2 520.

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

Задача 2

Сколько перестановок можно сделать из букв слова «МИССИСИПИ»?

Решение

Всего букв 9. Из них одинаковы «и» = 4, «с»=3, «м»=1, «п»=1. Следовательно, число различных перестановок равно

2 520.

Ответ: 2 520 перестановок.

Задача 3

У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней она дает сыну по 1 фрукту. Сколькими способами это может быть сделано.

Решение

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

Задача 4

([4], стр. 26) Для премий на математической олимпиаде выделено 3 экземпляра одной книги, 2 экземпляра другой и 1 экземпляр третьей книги. Сколькими способами могут быть вручены премии, если в олимпиаде участвовало 20 человек (каждому из участников вручается только одна книга)?

Решение

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

2 325 600.

Ответ: 2 325 600 способами.  

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

Задача 5

([4], стр. 26) Сколькими способами можно расставить на книжной полке библиотеки 6 книг  по теории вероятностей, 3 книги по теории игр и 2 книги по математической логике, если книги по каждому предмету одинаковые?

Решение

4 620.

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

Задача 6

([4], стр. 26) Сколькими способами можно переставить буквы слова ПЕРЕШЕЕК так, чтобы 4 буквы «Е» не стояли подряд?

Решение

Всего букв 8. Из них одинаковы «е» = 4, «п» = 1, «р» = 1, «ш» = 1, «к» = 1. Следовательно, число различных перестановок равно . Но из них необходимо исключить те, в которых 4 буквы «Е» стоят подряд. Таких перестановок . В итоге получаем:

1 680 – 120 = 1 560.

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

Задача 7

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

Решение

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

Задача 8

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

Решение

15 120.

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

Задача 9

([4], стр. 23) Сколькими способами можно распределить поровну 12 различных учебников между четырьмя студентами?

Решение

369 600.

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

Задача 10

([4], стр. 24) Доказать, что число перестановок при n > 1 всегда является чётным.

Решение

Это очевидно, исходя из определения факториала. Произведение всех чисел от 1 до n называется факториалом, то есть  При нахождении перестановок, где n > 1, в произведении всегда будет цифра 2, а при умножении на неё полученное число будет чётным.

  1.  Домашнее задание.

Задача 1

([4], стр. 26) Сколько букв алфавита можно составить из 5 сигналов в каждой букве, если 3 сигнала – импульсы тока, а 2 – паузы?

Решение

Ответ: 10 букв.

Задача 2

([4], стр. 26) Найдите число различных перестановок в слове СТАТИСТИКА; в слове ПАРАБОЛА.

Решение

  1.  Всего букв 10. Из них одинаковы «т» = 3, «с» = 2, «и» = 2, «а» = 2, «к» = 1. Следовательно, число различных перестановок равно

75 600.

  1.  Всего букв 8. Из них одинаковы «а» = 3, «п» = 1, «р» = 1, «б» = 1, «о» = 1, «л» = 1. Следовательно, число различных перестановок равно

6 720.

Ответ: 75 600 перестановок; 6 720 перестановок.

Задача 3

Сколькими способами можно переставить буквы слова СЕРЕБРО так, чтобы 2 буквы «Е» не стояли подряд?

Решение

Всего букв 7. Из них одинаковы «е» = 2, «р» = 2, «с» = 1, «б» = 1, «о» = 1. Следовательно, число различных перестановок равно . Но из них необходимо исключить те, в которых 2 буквы «Е» стоят подряд. Таких перестановок  . В итоге получаем:

1 260 – 720 = 540.

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

  1.   Занятие 8. Размещения с повторениями

Цели:

  •  сформулировать определение размещения с повторениями;
  •  рассмотреть примеры решения комбинаторных задач, используя формулу размещений с повторениями.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

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

Два размещения с повторениями считаются разными, если они различаются наборами элементов или расположением элементов в наборе.  

Пример

([1], стр. 539) Ниже выписаны всевозможные размещения с повторениями из 4 элементов 1, 2, 3, 4 по 3:

111  112  121  211  113  131  311  114  141  411  222  221  212  223  232

322  224  242  422  333  331  313  133  332  323  134  343  433  444  441

414  144  442  424  244  123  124  213  214  132  334  443  434  344  312

314  142  143  412  413  241  243  421  423  431  432  342  341  321  324

231  234  122  233

Теорема. Число всевозможных размещений с повторениями из n элементов по k выражается формулой:

Задачи для решения с учителем

Задача 1

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

Решение

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

Ответ: 125 чисел. 

Задача 2

На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры?

Решение

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

Задача 3

([4], стр. 26) Сколько четырёхзначных чисел имеется в пятеричной системе счисления?

Решение

Алфавит пятеричной системы счисления состоит из цифр: 0, 1, 2, 3, 4. На первое место в четырёхзначном числе можно поставить цифру 4-мя способами, так как 0 на первом месте стоять не может. Остальные места можно занять  способами. Воспользуемся правилом произведения и получим:

4 900.

Ответ: 4 900 чисел.

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

Задача 4

Каких чисел от 1 до 1 000 000 больше: тех, в  записи которых встречается единица, или тех, в которых она не встречается?

Решение

Подсчитаем  количество  чисел  от 1 до 999999 (число 1 000 000  содержит единицу, его сразу отбросим), в записи которых нет единиц. Каждую цифру можно выбрать 9 способами (любая цифра кроме 1), поэтому все 6 цифр (по правилу  произведения)  можно  выбрать способами (если  в  числе  до значащих  цифр  стоят  нули,  мы  их  просто  отбрасываем).  При  этом  один вариант (000000)  нужно  убрать,  так  как  число 0  не  рассматривается. Получаем всего

531 440 чисел.

Так как всего чисел 1 000 000, то видно, что чисел без единицы среди чисел от 1 до 1 000 000  больше, чем тех, в записи которых единица есть.  

Ответ: Чисел без единицы больше, чем чисел с единицей.

Задача 5

([4], стр. 26) Сколькими способами можно разложить в два кармана 9 монет разными достоинствами?

Решение

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

Задача 6

([4], стр. 26) Трое юношей и две девушки выбирают место работы. Сколькими способами они могут это сделать, если в городе есть три завода, где требуются рабочие в литейные цехи (туда берут лишь мужчин), две ткацкие фабрики (туда приглашают женщин) и две фабрики, где требуются мужчины и женщины?

Решение

Юноши могут устроиться в какое-то из 5-и мест  способами, а девушки только в какое-то из 4-х мест  способами. Используем правило произведения и получаем:

Ответ: 141 способом.

Задача 7

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

Решение

Чтобы число было чётным, в конце должна стоять либо цифра 2, либо цифра 4, то есть последнее место можно занять 2-мя способами. Первые четыре места можно занять  способами. Используя правило произведения, получаем:

1 250.

Ответ: 1 250 чисел.

Задача 8

([4], стр. 26) Автомобильные номера состоят из одной, двух или трёх букв и четырёх цифр. Найдите число таких номеров, если используются 24 буквы русского алфавита и 10 цифр (0, 1 , …, 9).

Решение

14 424.

Ответ: 14 424 номеров.

Задача 9

Из колоды в 36 карт случайным образом вытаскивают 2 карты.  Подсчитайте количество наборов, в которых есть как карта пиковой масти, так и карта «красной» масти (бубновой или червовой).

Решение

Для выбора пиковой масти есть 9 вариантов, для выбора красной 18. В итоге:

Ответ: 162 набора.

Задача 10

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

Решение

Первая цифра равна сумме остальных. Последние 2 цифры одинаковые.

211, 422, 633, 844.

Ответ: 4 числа. 

  1.  Домашнее задание.

Задача 1

Имеется 5 различных каруселей и 7 различных цветов. Сколькими способами можно осуществить покраску каруселей?

Решение

16 807.

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

Задача 2

Сколько трехзначных чисел можно составить из цифр 5, 6, 8, 7, 1, 2?

Решение

Ответ: 216 чисел.

Задача 3

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

Решение

На первый ряд можно посадить учеников с первым вариантом контрольной работы способами, на второй ряд учеников со вторым вариантом  способами. Учитывая, что на первый ряд также можно посадить учеников со вторым вариантом, а на второй – с первым, получаем:

1 036 800.

Ответ: 1 036 800 способами.

  1.   Занятие 9. Сочетания с повторениями

Цели:

  •  сформулировать определение сочетания с повторениями;
  •  рассмотреть примеры решения комбинаторных задач, используя формулу сочетаний с повторениями.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

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

Два сочетания с повторениями считаются разными, если они различаются наборами элементов.  

Пример

Ниже выписаны всевозможные сочетания с повторениями, составленные из 4 элементов 1, 2, 3, 4 по 3:

111, 121, 131, 141, 212,

222, 232, 242, 333, 313,

323, 343, 353, 414, 424,

434, 124, 125, 134, 135,

145, 234, 235, 245, 444.

Теорема. Число различных сочетаний с повторениями, взятых из n элементов по k, выражается формулой:

Задачи для решения с учителем

Задача 1

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

Решение

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

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

Задача 2

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

Решение

Ответ: 21 результат.

Задача 3

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

Решение

24 310.

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

Задача 4

([4], стр. 26) Сколько можно построить различных прямоугольных параллелепипедов, если длина каждого его ребра может выражаться любым целым числом от 1 до 10?

Решение

Ответ: 220 параллелепипедов.

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

Задача 5

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

Решение

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

Задача 6

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

Решение

Каждая из 16 команд должна сыграть по одному матчу с каждой из оставшихся 15 команд. То есть, всего

Ответ: 240 матчей.

Задача 7

В кассе вокзала на поезд № 91 осталось 5 купейных билетов и 8 плацкартных. Сколько существует способов купить билеты для компании из 4 человек (места имеют значение)?

Решение

Всего в кассе имеется 13 билетов. Первый билет можно купить 13-ю способами, останется 12 билетов. Значит, следующий билет можно купить 12-ю способами, третий - 11-ю способами, четвертый - 10-ю. Следовательно,

17 160.

Ответ: 17 160 способов.

Задача 8

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

Решение

55 440.

Ответ: 55 440 вариантов.

Задача 9

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

Решение

65 536.

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

Задача 10

Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили два различных числа? Сколько среди них будет правильных дробей?

Решение

Различных  дробей  из 6  чисел: 3, 5, 7, 11, 13, 17  можно  составить штук ( способами выбираем два числа из 6, и двумя способами составляем из них дробь: сначала одно число – числитель, другое  знаменатель и наоборот). Из этих 30 дробей ровно 15 будут правильные, т.е., когда числитель меньше знаменателя (способами  выбираем  два  числа  из 6,  и единственным образом составляем дробь так, чтобы числитель был меньше знаменателя).

Ответ: 30 дробей; 15 дробей.

  1.  Домашнее задание.

Задача 1

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

Решение

293 930.

50 388.

Ответ: 293 930 способами; 50 388 способами; 45 способами.

Задача 2

Алфавит племени тумба-юмба состоит из букв А, У, С. Словом является любая последовательность из 4 букв. Сколько слов в языке этого племени?

Решение

Ответ: 15 слов.

Задача 3

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

Решение

Ответ: 32 числа.

2.10. Занятие 10. Задачи на картах

Цели:

  •  рассмотреть примеры решения комбинаторных задач на картах, используя изученные формулы.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

Задачи для решения с учителем

Задача 1

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых нет туза.

Решение

Все пять карт выбираются из 32 возможных карт (исключая тузов).

201 376.

Ответ: 201 376 набора.

Задача 2

Из колоды в 36 карт вытаскивают случайным образом 4 карты. Подсчитайте количество наборов, в которых есть карта каждой масти.

Решение

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

6 561.

Ответ: 6 561 набор.

Задача 3

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых есть ровно три туза.

Решение

Три туза можно выбрать 4 способами, а для выбора двух оставшихся можно взять любые две, кроме тузов.

1 984.

Ответ: 256 наборов.

Задача 4

Из колоды в 36 карт случайным образом вытаскивают 5 карт.  Подсчитайте количество наборов, в которых количество дам равно количеству карт червовой масти, если никаких карт, кроме дам и червей, в наборе нет.

Решение

В наборе обязательно есть дама червей. Для выбора дам есть 2 варианта. Для выбора двух оставшихся карт червовой масти остаётся 8 карт (кроме дамы червей). В итоге:

Ответ: 84 набора.

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

Задача 5

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых как количество десяток, так и количество чёрных карт больше половины.

Решение

Комбинации можно разделить на 4 группы:

1) в наборе четыре десятки и одна чёрная карта (16 способов);

2) в наборе три десятки, из них две чёрных, одна красная, а две остальные карты имеют разный цвет (способов);

3) в наборе три десятки, из них две чёрных, одна красная, а две остальные карты чёрные ( способов);

4) в наборе три десятки, из них одна чёрная, две красные, а две остальные карты чёрные ( способов).

Ответ: 752 набора.

Задача 6

Из колоды в 36 карт вытаскивают случайным образом 2 карты. Подсчитайте количество наборов, в которых есть, по крайней мере, одна красная карта  (карта бубновой или червовой масти).

Решение

Комбинации можно разделить на 4 группы:

1) в наборе одна красная и одна чёрная карта;

2) в наборе две красных карты.

Ответ: 477 наборов.

Задача 7

Из колоды в 36 карт вытаскивают случайным образом 4 карты. Подсчитайте количество наборов, в которых есть и чёрные карты (трефовой или пиковой масти), и красные карты (бубновой или червовой масти).

Решение

Найти искомое число можно вычитанием из общего числа наборов число наборов, в которых есть только красные или только чёрные карты.

=58 599.

Ответ: 58 599 наборов.

Задача 8

Из колоды в 36 карт вытаскивают случайным образом 3 карты. Подсчитайте количество наборов, в которых имеется туз бубей и одна дама любой масти.

Решение

Для выбора дамы есть 4 варианта. Для выбора оставшейся карты есть 31 вариант (кроме туза бубен и дам).

Ответ: 124 набора.

Задача 9

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

Решение

Все пять карт выбираются из 28 возможных карт (исключая королей и дам).

3 276.

Ответ: 3 276 наборов.

Задача 10

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых нет ни одной картинки (туза, короля, дамы или валета).

Решение

Все пять карт выбираются из 20 возможных карт (исключая «картинки»).

15 504.

Ответ: 15 504 набора.

Задача 11

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых 3 карты бубновой масти, а остальные чёрные (пиковой или трефовой масти).

Решение

Три карты бубновой масти выбираются из 9 возможных, а оставшиеся две чёрных из 18 возможных.

12 852.

Ответ: 12 852 набора.

Задача 12

Из колоды в 36 карт вытаскивают случайным образом 6 карт. Подсчитайте количество наборов, в которых нет карт пиковой масти, а карт остальных мастей поровну.

Решение

Две карты одной масти выбираем из 9 возможных карт, а три пары карт одной масти комбинируются между собой.

1 679 616.

Ответ:  1 679 616 наборов.

Задача 13

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых есть все виды картинок.

Решение

Все комбинации разобьём на два вида:

1) у которых пятая карта не является картинкой;

2) у которых пятая карта является картинкой.

1 280 + 768 = 2 048.

Ответ: 2 048 наборов.

Задача 14

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых количество карт красных мастей больше половины.

Решение

Все комбинации разобьём на три вида:

1) у которых три красных карты;

2) у которых четыре красных карты;

3) у которых пять красных карт.

139 536 + 55 080 + 8 568 = 203 184.

Ответ: 203 184 набора.

  1.  Домашнее задание.

Задача 1

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых все карты чёрные.

Решение

Все пять карт выбираются из 18 возможных карт чёрного цвета.

8 568.

Ответ: 8 568 наборов.

Задача 2

Из колоды в 36 карт вытаскивают случайным образом 4 карты. Подсчитайте количество наборов, в которых все карты бубновой масти.

Решение

Все пять карт выбираются из 9 возможных карт бубновой масти.

Ответ: 126 наборов.

Задача 3

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых все карты красные и есть валет бубен.

Решение

Все пять карт выбираются из 17 возможных карт красной масти (исключая валета бубен).

2 280.

Ответ:  2 280 наборов.

Задача 4

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых количество дам больше половины и больше числа королей (короли в наборе есть).

Решение

Все комбинации разобьём на три вида:

1) у которых три дамы и два короля;

2) у которых три дамы и один король;

3) у которых четыре дамы и один король.

Ответ: 476 наборов.

2.11. Занятие 11. Задачи на шахматной доске

Цели:

  •  рассмотреть примеры решения комбинаторных задач на шахматной доске.

Ход занятия

  1.  Сообщение темы и целей.
  2.  Проверка домашнего задания.
  3.  Выступление ученика с докладом.
  4.  Работа по теме.

Задачи для решения с учителем

Задача 1

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

Решение

=174 226 200.

Ответ: 174 226 200 способами.

Задача 2

Из полного набора шахмат вынули 4: фигуры или пешки. В скольких случаях среди них окажется: а) 2 коня; б) не менее двух коней?

Решение

а) 2 268.

б) 2 2682 381.

Ответ: а) в 2 268 случаях; б) в 2 381 случае.

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

Задача 3

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

Решение

Белую ладью можно поставить на любую из 64 клеток. Независимо от своего расположения она бьет 15 полей (включая поле, на котором она стоит). Поэтому остается 49 полей, на которые можно поставить черную ладью. Таким образом, всего есть 3 136 разных способов.

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

Задача 4

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

Решение

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

а) если белый король стоит в углу (углов всего 4), то он бьет 4 поля (включая то, на котором стоит), и остается 60 полей, на которые можно поставить черного короля;

б) если белый король стоит на краю доски, но не в углу (таких полей – 24), то он бьет 6 полей, и для черного короля остается 58 возможных полей;

в) если же белый король стоит не на краю доски (таких полей – 36), то он бьет 9 полей, и для черного короля остается 55 возможных полей.

Таким образом,

3 612

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

Задача 5

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

Решение

40 320.

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

Задача 6

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

Решение

a) 1 568.

б) 1 806.

в) 1 736.

Ответ: а) 1 568 способами; б) 1 806 способами; в) 1 736 способами.

Задача 7

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

Решение

5 040.

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

Задача 8

Сколькими способами можно расставить n ладей на шахматной доске  так, чтобы никакие 2 из них не стояли на одной горизонтали или одной вертикали, если:

а) все ладьи одинакового цвета;

б) все ладьи разного цвета;

в) k ладей белого цвета, а остальные – чёрного.

Решение

а) 1-я строка: n способов, 2-я строка: (n – 1) способов и т.д.

В результате n! способов.

б) .

в)

Ответ: a) n! способами; б)  способами; в)  способами.

  1.  Домашнее задание.

Задача 1

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

Решение

а) 1 848. 

б) 1 288

Ответ: а) 1 848 способами; б) 1 288 способами.

2.12. Занятие 12. Контрольная работа №2

Вариант 1

Задача 1

([4], стр. 22) Четверо студентов сдают экзамен. Сколькими способами могут быть поставлены им оценки, если известно, что никому из них не будет поставлена неудовлетворительная оценка?

Задача 2

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

Задача 3

Назовем симпатичными числа, в записи которых используют только нечетные числа. Сколько существует четырехзначных симпатичных чисел? 

Задача 4

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

Задача 5

Найдите число различных перестановок в слове КЛАССИКА.   

Задача 6

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых как количество шестёрок, так и количество чёрных карт больше половины.

Задача 7

Из колоды в 36 карт случайным образом вытаскивают 5 карт.  Подсчитайте количество наборов, в которых количество дам равно количеству карт червовой масти, если никаких карт, кроме дам и червей, в наборе нет.  

Задача 8

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

Задача 9

Из полного набора шахмат вынули 4: фигуры или пешки. Во скольких случаях среди них окажется: а) 2 ладьи; б) не менее двух ладей?

Вариант 2

Задача 1

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

Задача 2

Найдите число различных перестановок в слове ЗАПЕКАНКА.

Задача 3

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

Задача 4

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

Задача 5

Из колоды в 36 карт вытаскивают случайным образом 3 карты. Подсчитайте количество наборов, в которых есть, по крайней мере, одна чёрная карта  (карта трефовой или пиковой масти).

Задача 6

Из колоды в 36 карт вытаскивают случайным образом 5 карт. Подсчитайте количество наборов, в которых количество карт чёрных мастей больше половины.

Задача 7

Сколькими способами можно разложить в 2 кармана 11 конфет разных сортов? 

Задача 8

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

Задача 9

Из полного набора шахмат вынули 5: фигуры или пешки. Во скольких случаях среди них окажется: а) 3 ладьи; б) не менее трёх ладей?

Ответы к контрольной работе №2

Вариант 1

  1.  81;
  2.  120;
  3.  625;
  4.  48;
  5.  5 040;
  6.  752;
  7.  58 905;
  8.  293 930;
  9.  а) 2 268; б) 2 381.

Вариант 2

  1.  48;
  2.  30 240;
  3.  245;
  4.  32;
  5.  7 956;
  6.  203 184;
  7.  2 048;
  8.  19 448;
  9.  а) 1 512; б) 1 540.

Заключение

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

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

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

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

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

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

Таким образом, в данной выпускной квалификационной работе были рассмотрены все виды комбинаций с повторениями и без повторений: размещения, перестановки и сочетания.

Материал, представленный в выпускной квалификационной работе, может быть использован на уроках и элективных курсах в 9 и 11 классах средней школы (при подготовке к ГИА и ЕГЭ), а также на практических занятиях по алгебре на первом курсе и теории вероятности на 4 курсе.

Список литературы

  1.  Новосёлов С.И. «Специальный курс элементарной алгебры» : изд.7 – М; Высшая школа, 1965. – 551с.
  2.  Дж. Кемени и др. «Введение в конечную математику» : изд. 2 – М.; Мир, 1965. – 484с.
  3.  Виленкин Н.Я. «Комбинаторика» – М.; Наука, 1969. – 328с.  
  4.  Виленкин Н.Я. «Задачник-практикум по теории вероятностей с элементами комбинаторики и математической статистики» – М.; Просвещение, 1979. – 111с.
  5.  Окунев Л.Я. «Комбинаторные задачи на шахматной доске» – Л.; 1935. – 87с.
  6.  Стенли Р. «Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции» – М.; Мир, 2005. – 768с.
  7.  Халамайзер А. Я. «Комбинаторика и бином Ньютона» – М.; Просвещение, 1980. – 32с.
  8.  Холл М. «Комбинаторика» – М.; Мир, 1970. – 424с.  
  9.  Ежов И.И. «Элементы комбинаторики» – М.; Наука, 1977. – 80с.  
  10.  Гнеденко Б. В., Журбенко И.Г. «Теория вероятностей и комбинаторика» //Математика в школе. – 2007. - №6. – с.67-70.
  11.  Дихтярь М., Эргле Е. «Исторические комбинаторные задачи и комбинаторные модели»  //Математика. – 2007. – №14. – с.23-24.
  12.  Тишин В.В «Дискретная математика в примерах и задачах» — СПб.; БХВ-Петербург, 2008. – 352с.
  13.  Ермаков В.И., Ерохина Т.А. и др. «Практикум по дискретной математике» – М.; Российская  Экономическая Академия, 2007. – 91с. 
  14.  Аляев Ю.А., Тюрин С.Ф. «Дискретная математика и математическая логика» – М.; Финансы и статистика, 2006. – 368с.
  15.  Афанасьев В.В., Суворова М.А. «Школьникам о вероятности в играх. Введение в теорию вероятностей для учащихся 8-11 классов» Ярославль; Академия развития, 2006.  192с.
  16.  Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. «Комбинаторика» – М.; ФИМА, МЦНМО, 2006. – 400с.
  17.  Гнеденко Б. В. «Очерк по истории теории вероятностей» – М.; УРСС, 2001. – 88с.
  18.  http://ru.wikipedia.org
  19.  http://combinatorica.narod.ru/second.htm
  20.  http://www.matburo.ru/

5. Приложения

5.1. Приложение 1. Историческая справка

[18] История комбинаторики освещает развитие комбинаторики – раздела конечной математики, который исследует в основном различные способы выборки заданного числа m элементов из заданного конечного множества: размещения, сочетания, перестановки, а также перечисление и смежные проблемы. Начав с анализа головоломок и азартных игр, комбинаторика оказалась исключительно полезной для решения практических задач почти во всех разделах математики. Кроме того, комбинаторные методы оказались полезными в статистике, генетике, лингвистике и многих других науках.

Древний период

Комбинаторные мотивы можно заметить в символике китайской книги перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из n возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна .

Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000. 

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

Средневековье

В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.

В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра подсчитывал число размещений с перестановками в огласовках имени Бога и обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний.

Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

Новое время

Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии – как для разработки шифров, так и для их взлома.

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика»  Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница, Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

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

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

  •  задача о ходе коня;
  •  задача о семи мостах, с которой началась теория графов;
  •  построение греко-латинских квадратов;
  •  обобщённые перестановки.

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

Современное развитие

В начале XX века начала развиваться комбинаторная геометрия: были доказаны теоремы Минковского–Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука–Улама и Люстерника–Шнирельмана. Во второй четверти ХХ века были поставлены проблема Борсука и проблема Нелсона–Эрдёша–Хадвигера. В 1940-х годах оформилась теория Рамсея.

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

5.2. Приложение 2. Учебный план элективного курса

№ занятия

Тема

Количество часов

1

Вводное занятие. Метод перебора и дерево возможных вариантов

2

2

Правило суммы и правило произведения

2

3

Перестановки без повторений

2

4

Размещения без повторений

2

5

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

2

6

Контрольная работа №1

2

7

Перестановки с повторениями

2

8

Размещения с повторениями

2

9

Сочетания с повторениями

2

10

Задачи на картах

2

11

Задачи на шахматной доске

2

12

Контрольная работа №2

2

Всего:

32

Содержание элективного курса

Занятие 1. Вводное занятие. Метод перебора и дерево возможных вариантов.

История комбинаторики. Метод перебора. Дерево возможных вариантов.

Занятие 2.  Правило суммы и правило произведения.

Правило суммы. Правило произведения.

Занятие 3. Перестановки без повторений.

Перестановки без повторений.

Занятие 4. Размещения без повторений.

Размещения без повторений. Свойства размещений без повторений.

Занятие 5. Сочетания без повторений.

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

Занятие 6. Контрольная работа №1.

Занятие 7. Перестановки с повторениями.

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

Занятие 8. Размещения с повторениями.

Размещения с повторениями.

Занятие 9. Сочетания с повторениями.

Сочетания с повторениями.

Занятие 10. Задачи на картах.

Применение формул комбинаторики к решению задач на картах.

Занятие 11. Задачи на шахматной доске.

Применение формул комбинаторики к решению задач на шахматной доске.

Занятие 12. Контрольная работа №2.

Содержание контрольной работы №1

  1.  Метод перебора. Дерево возможных вариантов.
  2.  Правила суммы и произведения.
  3.  Перестановки без повторений.
  4.  Размещения без повторений.
  5.  Сочетания без повторений.

Содержание контрольной работы №2

  1.  Перестановки с повторениями.
  2.  Размещения с повторениями.
  3.  Сочетания с повторениями.
  4.  Задачи на картах.
  5.  Задачи на шахматной доске.

Темы докладов для учеников

1.   Джироламо Кардано.

2.   Никколо Тарталья.

3.   Бином Ньютона;

4.   Блез Паскаль.

5.   Пьер Ферма.

6.   Треугольник Паскаля.

7.   Леонард Эйлер.

8.   Галилео Галилей.

9.   Готфрид Лейбниц.

10. Комбинаторная геометрия.

Вопросы для самостоятельной работы учащихся

  1.  История комбинаторики.
  2.  Метод перебора.
  3.  Дерево возможных вариантов.
  4.  Правило суммы.
  5.  Правило произведения.
  6.  Перестановки без повторений.
  7.  Размещения без повторений. Свойства размещений без повторений.
  8.  Сочетания без повторений. Свойства сочетаний без повторений.
  9.  Перестановки с повторениями.
  10.   Размещения с повторениями.
  11.   Сочетания с повторениями.

Литература

  1.  Новосёлов С.И. «Специальный курс элементарной алгебры» : изд.7 – М; Высшая школа, 1965. – 551с.
  2.  Дж. Кемени и др. «Введение в конечную математику» : изд. 2 – М.; Мир, 1965. – 484с.
  3.  Виленкин Н.Я. «Комбинаторика» – М.; Наука, 1969. – 328с.  
  4.  Виленкин Н.Я. «Задачник-практикум по теории вероятностей с элементами комбинаторики и математической статистики» – М.; Просвещение, 1979. – 111с.
  5.  Окунев Л.Я. «Комбинаторные задачи на шахматной доске» – Л.; 1935. – 87с.
  6.  Стенли Р. «Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции» – М.; Мир, 2005. – 768с.
  7.  Халамайзер А. Я. «Комбинаторика и бином Ньютона» – М.; Просвещение, 1980. – 32с.
  8.  Холл М. «Комбинаторика» – М.; Мир, 1970. – 424с.  
  9.  Ежов И.И. «Элементы комбинаторики» – М.; Наука, 1977. – 80с.  
  10.  Гнеденко Б. В., Журбенко И.Г. «Теория вероятностей и комбинаторика» //Математика в школе. – 2007. - №6. – с.67-70.
  11.  Дихтярь М., Эргле Е. «Исторические комбинаторные задачи и комбинаторные модели»  //Математика. – 2007. – №14. – с.23-24.
  12.  Тишин В.В «Дискретная математика в примерах и задачах» — СПб.; БХВ-Петербург, 2008. – 352с.
  13.  Ермаков В.И., Ерохина Т.А. и др. «Практикум по дискретной математике» – М.; Российская  Экономическая Академия, 2007. – 91с. 
  14.  Аляев Ю.А., Тюрин С.Ф. «Дискретная математика и математическая логика» – М.; Финансы и статистика, 2006. – 368с.
  15.  Афанасьев В.В., Суворова М.А. «Школьникам о вероятности в играх. Введение в теорию вероятностей для учащихся 8-11 классов» Ярославль; Академия развития, 2006.  192с.
  16.  Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. «Комбинаторика» – М.; ФИМА, МЦНМО, 2006. – 400с.
  17.  Гнеденко Б. В. «Очерк по истории теории вероятностей» – М.; УРСС, 2001. – 88с.
  18.  http://ru.wikipedia.org
  19.  http://combinatorica.narod.ru/second.htm
  20.  http://www.matburo.ru/


1

4

7

7

4

1

4

1

1

4

7

7

5

5

3

3

3

5

3

5

5

3

5

3

5

Р

М

ФФ

Ф

М

Р

Р

М

Ф

М

Ф

Р

М

Р

Ф

5

99Ф

9

0

0

5

0

5

0

9

Д

А

КФ

К

А

Д

Д

А

К

А

К

Д

А

Д

К

ЗК

ЖК

ЧЮ

КЮ

СЮ

СЮ

КЮ

ЧЮ

0

39Ф

3

0

0

33

0

0

0

3

3

0

3

3

3

А

Л9Ф

Л

Ы

А

Ы

Ы

Ы

А

Л


 

А также другие работы, которые могут Вас заинтересовать

31902. Расчет регулируемого электропривода 840.5 KB
  Предварительная мощность двигателя Предварительная мощность двигателя рассчитывается по нагрузочной диаграмме и тахограмме рабочей машины по формуле: где коэффициенты учитывающие соответственно пульсирующий характер питающего напряжения; возможный режим ослабления магнитного потока двигателя; динамические нагрузки двигателя в переходных процессах. Окончательный выбор двигателя и редуктора По вычисленному расчетному значению мощности выбирам двигатель согласно условию: при . Д810Uн=220В Рнд=29кВт...
31906. Интернет-продвижение коммерческой организации (на примере ООО «Элстрой-НН») 533 KB
  5 1 Деятельность коммерческих В2Ворганизаций в условиях развития сети Интернет10 Интернет как новая коммуникативная среда.10 Продающие возможности сети Интернет.14 Роль Интернета в сфере В2Вторговли.32 Исследование отношения пользователей к различным видам Интернетрекламы.
31908. ЛЕКСИЧЕСКАЯ СЕМАНТИКА 3.24 MB
  Ее ключевыми элементами являются: 1 Принцип интегральности описания языка в силу которого лексемам в явном виде приписываются все свойства релевантные для правил а правила учитывают все формы поведения лексем не упомянутые непосредственно в словаре.
31909. Внутрішнє представлення цілочисельних даних в IBM РС 58.65 KB
  Виконати переклад заданих викладачем чисел з десяткової в двійкову систему числення. Дати їх внутрішнє (машинне) представлення в залежності від діапазону в знакових і беззнакових форматах типів Shortint (signed char), Byte (unsigned char), Integer (int), Word (unsigned int). Машинне представлення даних має бути дане в двійковій і шестнадцятирічній системах числення.
31910. Свобода совісті – явище духовної культури 103.5 KB
  Неоднозначність впливу релігії на різні сфери суспільного життя. Релігія в житті українців. Релігія і вільнодумство і атеїзм. Історичне підгруддя і реалії сьогодення. Свобода совісті як форми запобігання і вирішення соціальних конфліктів на релігійному ґрунті.