Базовые понятия и утверждения




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

Пример 1.Сборная команда легкоатлетов университета, в состав которой входят преподаватели Мишин и Петров, аспиранты Виктор, Иван, Борис и Андрей, а также студенты Тимур, Олег и Лев, принимает участие в межвузовской эстафете. По условиям соревнований на первом этапе соревнуются преподаватели, на втором - аспиранты, на третьем - студенты. Сколькими способами можно сформировать команду для участия в эстафете?

◄ Сформируем команду за три шага. Вначале выберем преподавателя для участия в первом этапе эстафеты, затем аспиранта для участия во втором этапе, и, наконец, студента для участия в третьем этапе. Представим все варианты формирования команды с помощью схемы (рис. 1.2). В первой строке схемы укажем варианты выбора преподавателя (М - Мишин, П - Петров), во второй строке - варианты выбора аспиранта (В - Виктор, И - Иван, Б - Борис, А - Андрей), в третьей - варианты выбора студента (Т - Тимур, О - Олег, Л - Лев).

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

 

Рис. 1.2.

Каждому варианту состава команды на схеме соответствует путь, идущий из верхней строки в нижнюю (например, М ® И ® Л). Поэтому число всех возможных вариантов формирования команды для участия в эстафете равно числу таких путей. Так как в первой строке две буквы, во второй - вчетверо больше, чем в первой, а третьей - втрое больше, чем во второй, то общее число путей равно произведению . Таким образом, имеем варианта формирования команды. ►

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

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

Объемом выборки называют число входящих в нее элементов (с учетом их повторения).

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

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

Вернемся к обсуждению примера. Проанализируем ситуацию, используя понятие выборки. Рассмотрим множество, элементами которого являются члены команды легкоатлетов. Чтобы сформировать команду, нужно отобрать из этого множества три элемента, т.е. составить выборку объема 3. В этой выборке элементы должны идти в определенном порядке: первым - преподаватель, вторым - аспирант, третьим - студент. Таким образом, команда - это выборка упорядоченная, и вопрос сколькими способами можно сформировать команду, можно заменить вопросом сколько имеется упорядоченных выборок объема 3, в которых первым элементом является преподаватель, вторым - аспирант, третьим - студент.

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

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

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

Пример 3.Сколько подмножеств имеет -элементное множество?

◄ Обозначим множество буквой и занумеруем его элементы номерами от 1 до : . Рассмотрим упорядоченные наборы из 0 и 1 длины . Между множеством таких наборов и множеством подмножеств (булеаном ) установим соответствие, сопоставив каждому подмножеству набор , в котором на -м месте стоит 1, если элемент входит в подмножество, и 0, если не входит. Например, если , то подмножеству соответствует набор . Пустому подмножеству соответствует набор из одних нулей, а самому - набор из одних единиц.

Соответствие, которое мы установили между подмножеством и множеством упорядоченных наборов из 0 и 1 длины является взаимно-однозначным, значит, мощности этих множеств совпадают (см. § 1.1). Таким образом, исходная задача свелась к определению числа упорядоченных наборов из 0 и 1 длины . Каждый такой набор, по сути, является упорядоченной выборкой объема из множества , которую можно построить за этапов. На первом этапе выбирается значение (0 или 1), на втором - (0 или 1) и т.д. Следовательно, на каждом этапе есть выбор из двух возможностей и по правилу произведения число наборов равно . Таким образом, -элементное множество имеет подмножеств. ►

Упражнение 1.4.У Олега десять книг, а у Ивана - двадцать. Сколькими способами можно осуществить обмен одной книги Олега на одну книгу Ивана?

Упражнение 1.5.Подсчитать число четных четырехзначных чисел, составленных из цифр , в десятичной записи которых соседние цифры различны.

Упражнение 1.6.Из города А в город В ведут четыре дороги. Сколькими способами можно съездить из А в В и обратно, если:

а) путешествие туда и обратно совершается по разным дорогам;

б) дороги туда и обратно выбираются независимо друг от друга?

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

Если - конечные попарно-непересекающиеся множества, то множество также конечно и

.

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

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

Каждое четырехзначное число, в десятичной записи которого все цифры различны, можно выписать за четыре шага: на первом шаге выбрать первую цифру числа, на втором - вторую и т.д. На первом шаге можно выбрать любую цифру, за исключением 0, т.е. имеется выбор из 9 возможностей. На втором шаге можно выбрать любую цифру, за исключением уже выбранной первой, значит, вновь имеем 9 возможностей. На третьем шаге число вариантов выбора сокращается до 8, а на четвертом - до 7. Следовательно, количество четырехзначных чисел, в десятичной записи которых все цифры различны, равно . Рассуждая аналогично, находим, что количество трехзначных чисел, удовлетворяющих условию, равно , количество двухзначных равно . Очевидно, что количество однозначных натуральных чисел равно 9.

Количество натуральных чисел, меньших 10000, в десятичной записи которых все цифры различны, найдем по правилу суммы: .►

Упражнение 1.7.Сколько имеется шестизначных чисел, в десятичной записи которых «четные» (0, 2, 4, 6, 8) и «нечетные» (1, 3, 5,7, 9) цифры чередуются?

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

2. Сочетания и размещения. Напомним, что выборка называется упорядоченной, если порядок следования элементов в ней имеет значение (две упорядоченные выборки, имеющие одинаковый состав, но отличающиеся порядком следования элементов, считаются различными).

Если порядок следования элементов в выборке не является существенным, то выборка называется неупорядоченной (две неупорядоченные выборки считаются различными только тогда, когда они отличаются составом).

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

Комбинируя эти свойства выборок, получают четыре основные разновидности выборок:

1) упорядоченная выборка объема без повторений называется размещением из n элементов по k;

2) неупорядоченная выборка объема без повторений называется сочетанием из n элементов по k;

3) упорядоченная выборка объема с повторениями называется размещением с повторением из n элементов по k;

4) неупорядоченная выборка объема с повторениями называется сочетанием с повторением из n элементов по k.

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

Проиллюстрируем введенные понятия на примере. Пусть множество состоит из трех элементов . Рассмотрим различные виды выборок объема 2. Имеем:

1) шесть упорядоченных выборок без повторений, т.е. размещений из 3 по 2:

, , , , , ;

2) три неупорядоченные выборки без повторений, т.е. сочетаний из 3 по 2:

, , ;

3) девять упорядоченных выборок с повторениями, т.е. размещений с повторениями из 3 по 2:

, , , , , , , , ;

4) шесть неупорядоченных выборок с повторениями, т.е. сочетаний с повторениями из 3 по 2:

, , , , , .

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

В качестве примера перечислим все перестановки множества :

, , , , , .

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

 

Рассмотрим формулы подсчета числа сочетаний и размещений.

Число размещений. Обозначим число размещений из n по k через (другое обозначение - ). Для подсчета числа используем правило произведения. При построении конкретного размещения первым элементом в нем можно взять любой из элементов множества , вторым элементом - любой из оставшихся в элементов и т.д. Поэтому

при .

При не существует размещений из по , следовательно, ; при полагаем .

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

Например, если в группе 20 человек, то список группы можно написать способами.

Число сочетаний. Обозначим число сочетаний из n по k через (другое обозначение - ). Поскольку в сочетании, в отличие от размещения, порядок следования элементов не учитывается, то из одного сочетания из n элементов по k путем упорядочивания элементов можно получить размещений. Значит,

, .

Из последней формулы следует

и .

При полагают , а при - (поскольку при не существует сочетаний из элементов по ).

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

.

Число сочетаний с повторениями. Для числа сочетаний с повторениями из n по k используется обозначение . Можно показать, что . Доказательство этой формулы опустим.

Рассмотрим несколько примеров использования комбинаторных формул.

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

б) Сколько пятибуквенных «слов» можно составить в алфавите из 9 букв, если буквы в словах могут повторяться?

◄ а) Прежде всего заметим, что под «словом» в комбинаторных задачах понимают любую конечную последовательность букв. Каждому пятибуквенному «слову» можно сопоставить упорядоченную выборку, элементами которой являются буквы алфавита: первый элемент выборки - первая буква в «слове», второй элемент - вторая буква в «слове» и т.д. В этих упорядоченных выборках элементы не повторяются (так как буквы в «словах» не должны по условию быть одинаковыми), следовательно, мы имеем дело с размещениями из 9 элементов по 5. Всего таких размещений .

б) Каждому пятибуквенному «слову» можно сопоставить упорядоченную выборку, элементами которой являются буквы алфавита: первый элемент выборки - первая буква в «слове», второй элемент - вторая буква в «слове» и т.д. В отличие от ситуации а), элементы в этих выборках могут повторяться (буквы в «словах» по условию могут быть одинаковыми), следовательно, мы имеем дело с размещениями с повторениями из 9 элементов по 5. Всего таких размещений . ►

Пример 6. В магазине продаются воздушные шары 7 цветов. Игорь решил купить для праздника 3 шара.

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

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

◄ В случае а) каждый выбор Игоря можно интерпретировать как неупорядоченную выборку без повторений из 7 цветов по 3, т.е. сочетание без повторений из 7 по 3. Число таких сочетаний .

Отличие случая б) от случая а) состоит в том, что Игорь может купить 2 или 3 шара одного цвета. Значит, каждый выбор Игоря можно интерпретировать как неупорядоченную выборку с повторениями из 7 цветов по 3, т.е. сочетание с повторениями из 7 по 3. Число таких сочетаний . ►

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

◄ Построение произвольной перестановки, удовлетворяющей условию задачи, разобьем на три шага: на первом выберем 3 последовательных места для карточек с цифрами 1,2,3; на втором расставим эти 3 карточки по выбранным местам; на третьем расположим остальные 7 карточек на оставшихся 7 местах.

На первом шаге имеется выбор из 8 возможных вариантов (выбрать места с 1 по 3 или места со 2 по 4 и т.д. или, наконец, места с 8 по 10). На втором шаге имеется выбор из вариантов. На третьем шаге имеется выбор из вариантов расположения оставшихся карточек на 7 свободных местах. Согласно правилу произведения, ответом на вопрос задачи является число

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

◄ Каждое число, удовлетворяющее условию задачи, можно выложить за два шага: на первом положить в ряд 3 карточки с четными цифрами, на втором - 3 карточки с нечетными цифрами. Число возможностей на первом шаге равно числу упорядоченных выборок объема 3 без повторений, элементами которых являются четные цифры, т.е. числу размещений из 4 по 3: . Число возможностей на втором шаге равно числу упорядоченных выборок объема 3 без повторений, элементами которых являются нечетные цифры, т.е. числу размещений из 5 по 3: . Согласно правилу произведения, общее число чисел, удовлетворяющих условию задачи, равно . ►

Пример 9.У Саши 10 марок, а у Вани - 20. Сколькими способами можно осуществить обмен 3 Сашиных марок на 3 Ванины?

◄ Для каждого обмена Саша должен отобрать 3 марки из 10. Он может это сделать способами, поскольку каждый результат отбора можно интерпретировать как неупорядоченную выборку без повторений 3 элементов из 10, т.е. сочетание из 10 по 3. В свою очередь Ваня может отобрать 3 марки для обмена способами. Каждому обмену можно однозначно сопоставить упорядоченную пару, первый элемент которой - набор марок, приготовленный для обмена Сашей, а второй - набор марок, приготовленный для обмена Ваней. Согласно правилу произведения, число таких пар, а значит, и число способов обмена равно произведению . ►

Упражнение 1.9. а) Сколькими способами можно разместить 5 занумерованных шаров по 9 пронумерованным коробкам, если в 1 коробку можно положить не более 1 шара?

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

Упражнение 1.10. Сколько разных шестибуквенных слов можно получить, переставляя буквы в слове «фартук»?

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

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

Упражнение 1.12. а) Сколькими способами Маша может выбрать 2 предмета из 8 для сдачи экзамена по выбору?

б) Маша должна сдать 2 экзамена за 8 дней. Сколькими способами она может составить расписание экзаменов, если нельзя сдавать больше одного экзамена в день?

Упражнение 1.13. В киоске продаются 10 видов рождественских поздравительных открыток. Тане нужно купить 8 открыток. Сколькими способами Таня сможет это сделать, если:

а) она решила купить открытки только разных видов;

б) она решила купить по две открытки четырех видов;

в) Тане все равно, какие открытки покупать;

г) одна из открыток понравилась Тане больше других, и она решила купить хотя бы одну такую открытку?

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

3. Некоторые комбинаторные соотношения. Числа называются также биномиальными коэффициентами, посколькуони фигурируют в функциональном тождестве, называемом формулой бинома Ньютона:

.

Доказательство формулы приведено во второй части параграфа.

Для чисел выполняется тождество . Действительно,

.

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

                         
                         
                         
                         
                         
                         
. . . . . . . . . . . . .

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

Упражнение 1.15. Доказать тождества

а) ; б) ;

в) ; г) .



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-26 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: