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

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

Первые комбинаторные задачи, по-видимому, были вызваны подсчетом различных комбинаций при игре в карты, кости и другие азартные игры, популярные в средние века. Одним из первых подсчетом числа различных комбинаций при игре в кости занимался итальянский математик Тарталья (1500– 1557). В 17 веке изучением теоретических вопросов комбинаторики занимались французские ученые Б. Паскаль (1623 – 1662) и П. Ферма (1601 – 1665). Исходным пунктом их исследований также были проблемы азартных игр. Дальнейшее развитие комбинаторики связано с именами Я. Бернулли (1654 – 1705), Г. Лейбница (1646 – 1716) и Л. Эйлера (1707 – 1783).Однако и в работах этих математиков в основном рассматривались приложения к различным играм (лото, пасьянсы и т.д.). Однако основные вопросы комбинаторики и их систематическое изучение связаны с развитием алгебры многочленов и теории вероятностей в 16 – 18 веках.

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

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

Правила комбинаторики.

1. Правило сложения: Если элемент можно выбрать m способами, а элемент – n способами, причем любой выбор элемента а отличен от любого выбора элемента b, то выбор « или » можноосуществить m + n способами.

2. Правило умножения: Если элемент можно выбрать m способами, и после каждого такого выбора элемента элемент можно выбрать n способами, то выборэлементов « и » можноосуществить m n способами.

Задачи

49. Имеется пять видов конвертов без марок и 4 вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма?

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

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

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

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

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

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

56. Есть 9 монет различного достоинства. Сколькими способами их можно разложить в два кармана?

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

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

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

60. На кафедре математики 9 преподавателей. Сколькими способами можно составить расписание консультаций на 9 дней, если каждый преподаватель проводит консультацию ровно один раз?

61.Семь членов профсоюзного комитета должны выбрать из своего состава председателя и секретаря. Сколькими способами это можно сделать?

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

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

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

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

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

67. Сколькими способами можно выбрать согласную и гласную буквы из слова «здание»? из слова «математика»? из слова «паркет»?

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

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

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

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

72. На железнодорожной станции имеется m светофоров. Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния: красный, желтый и зеленый?