![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Размещения с повторением
Любой упорядоченный набор Пример. Для множества Задача. Все буквы, цифры, знаки в ЭВМ кодируются двоичными последовательностями определенной длины, компоненты которой равны 0 или 1. Например: Максимальное число символов (букв, цифр,......), которые могут быть представлены с помощью Обратная задача. Сколько различных чисел (знаков) может быть записано двоичными словами длиной 4, 8, 16: Или имеется алфавит из 64 слов. Сколько необходимо разрядов, чтобы закодировать в двоичной системе. Бином Ньютона. Это формула, представляющая выражение (a + b) n при положительном целом n в виде многочлена: Заметим, что сумма показателей степеней для a и b постоянна и равна n. П р и м е р 1. (См. формулу куба суммы двух чисел). Числа Их можно вычислить, применяя только сложение, если пользоваться следующей схемой. В верхней строке пишем две единицы. Все последующие строки начинаются и заканчиваются единицей. Промежуточные числа в этих строках получаются суммированием соседних чисел из предыдущей строки. Эта схема называется треугольником Паскаля: Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая - для n = 2; третья - для n = 3 и т.д. Поэтому, если необходимо, например, разложить выражение: (a + b)7, мы можем получить результат моментально, используя таблицу: Свойства биномиальных коэффициентов. 1. Сумма коэффициентов разложения (a + b) n равна 2 n. Для доказательства достаточно положить a = b = 1. Тогда в правой части разложения бинома Ньютона мы будем иметь сумму биномиальных коэффициентов, а слева: 2. Коэффициенты членов, равноудалённых от концов разложения, равны. Это свойство следует из соотношения: 48 До сих пор мы рассматривали задачи, в которых на порядок элементов в комбинациях не накладывалось никаких ограничений или дополнительных условий. Либо (как в сочетаниях) порядок вообще не учитывался. Рассмотрим задачи с ограничением. Задача 1. Укротитель хищных зверей хочет вывести на арену 5 львов и 4 тигра, при этом нельзя, чтобы два тигра шли друг за другом. Сколькими способами он может расположить зверей? Обозначим львов буквой Л. Для тигров имеется 6 мест. _____Л1_____Л2_____Л3____Л4_____Л5______ Львов можно расположить Общее число способов Для задачи в общем виде, если имеется:
Это возможно лишь при условии, что 49 Задача 1. На книжной полке стоят 12 книг. Сколькими способами можно выбрать 5 из них так, чтобы никакие две из них не стояли рядом. Зашифруем выбор 0 и 1: каждой оставленной книге поставим в соответствие 0, каждой выбранной - 1. Таким образом, имеем 5 единиц и 7 нулей и задача сводится к предыдущей. В общем виде: Если стоит Задача 2. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует с соседом. Надо выбрать 5 рыцарей (например в экспедицию, чтобы освободить заколдованную принцессу), причем так, чтобы среди них не было враждующих. (рис. 8.3) Сколькими способами это можно сделать?
Отличие от предыдущей задачи состоит в том, что рыцари сидят не в ряд, а по кругу. Но ее легко свести к случаю, когда рыцари сидят в ряд. Для этого возьмем рыцаря, например сэра Ланселота, и разомкнем круг. Все выбираемые комбинации распадаются на два класса: в одном участвует сэр Ланселот, в другом - нет. Подсчитаем сколько комбинаций входит в каждый класс. 1. Если сэр Ланселот отправился в поход, то его соседи справа и слева не должны участвовать. Остаются 9 рыцарей из которых надо выбрать 4. Надо проследить, чтобы среди выбранных не было врагов, то есть чтобы никакие двое не сидели рядом. Цепь разорвана следовательно: 2. Так как сэр Ланселот не участвует в экспедиции, то его можно исключить, остается 11 рыцарей, из которых выбирается 5.
В общем случае, если по кругу расположены Это доказывается точно так же, как и выше. Все комбинации элементов разбиваются на два класса в зависимости от одного из них (сэра Ланселота). В первом варианте будет Доказательство:
Задачи Общая постановка этих задач:
|