Элементы комбинаторики. Формулы комбинаторики
Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.
Основная формула комбинаторики
Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .
Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .
Пример 2.
Сколько
трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если
цифры могут повторяться?
Решение:
n 1 =6
(т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7
(т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5,
6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4,
6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.
В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.
Пример 3.
Сколько всех четырехзначных чисел
можно составить из цифр 1, 5, 6, 7, 8?
Решение.
Для каждого разряда
четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.
Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .
Число размещений из n элементов по m
Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.
Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:
Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.
Пример 5
. Сколько существует двузначных
чисел, в которых цифра десятков и цифра единиц различные
и нечетные?
Решение:
т.к. нечетных цифр
пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на
две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:
Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.
Число сочетаний из n элементов по m
Число сочетаний обозначается C n m и вычисляется по формуле:
Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?
Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:
Перестановки из n элементов
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.
Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).
Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.
Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?
Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.
Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.
Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).
Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.
И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.
Пример 9.
На родительском собрании
присутствует 20 человек. Сколько существует различных вариантов состава
родительского комитета, если в него должны войти 5 человек?
Решение:
В этом примере нас
не интересует порядок фамилий в списке комитета. Если в результате в его
составе окажутся одни и те же люди, то по смыслу для нас это один и тот же
вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний
из 20 элементов по 5.
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.
Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5,
6, если цифры могут повторяться?
2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?
5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?
6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?
Сталин присвоил звание маршала даже Тухачевскому. Но разве хоть кто-нибудь считает Тухачевского стратегом?
То, что Жукову Сталин присваивал ордена и звания, ни о чем не говорит. В число сталинских наркомов, министров, маршалов и генералов попадали и подлецы, и проходимцы, и садисты, и развратники, и воры, и очковтиратели. Тут вам и Ежов, и Ягода, и Блюхер, и Бухарин, и Радек, и Хрущев и еще целая ватага.
ВПЕРЕД НА СЫЧЕВКУ!
Когда речь заходит о войне, мы вспоминаем Сталинград, а вспомнив Сталинград, вспоминаем Жукова. Это он, величайший полководец ХХ века, был творцом одной из самых блистательных операций Второй мировой войны, а, возможно, и всей мировой истории. Сталинград - подтверждение неоспоримой истины: где Жуков, там победа! Сталинград - доказательство гениальности Жукова: бросил взгляд на карту, и сразу нашел решение!
Прокричим же троекратное «Ура» гению, а потом зададим вопрос о достоверности сведений. Давайте докопаемся до истоков. Давайте установим, откуда стало известно, что план Сталинградской стратегической наступательной операции предложил Жуков?
Источник найти легко: это сам Жуков такое рассказал. Это он сам себя объявил автором плана операции, правда, признавая, что был и соавтор - А. М. Василевский. Описано это так:
«Днем 12 сентября я вылетел в Москву и через четыре часа был в Кремле, куда вызвали и начальника Генштаба А. М. Василевского…
Верховный достал свою карту с расположением резервов Ставки, долго и пристально ее рассматривал. Мы с Александром Михайловичем отошли подальше от стола в сторону и очень тихо говорили о том, что, видимо, надо искать какое-то иное решение.
А какое «иное» решение? - вдруг, подняв голову, спросил И. В. Сталин.
Я никогда не думал, что у И. В. Сталина был такой острый слух. Мы подошли к столу…
Весь следующий день мы с А. М. Василевским проработали в Генеральном штабе… Перебрав все возможные варианты, мы решили предложить Сталину следующий план действий…» («Воспоминания и размышления». М. АПН. 1969. С.401-402)
Из сказанного следует, что у истоков Сталинградской стратегической наступательной операции стояли трое: Сталин, Жуков и Василевский. Заслуга Сталина в том, что слух у него острый. Услыхал Сталин, что Жуков с Василевским шепчутся, заинтересовался, тут-то Жуков с боевым товарищем и подбросили Верховному главнокомандующему гениальную идею…
Жуков рассказывал, что Сталин сомневался в успехе, боялся рисковать, предлагал операцию проводить, но не такого масштаба, а скромнее. Но Жуков Сталина уломал, и все вышло как надо.
О Сталинграде устами своих литературных негров Жуков вещает подробно и много: «Ставка 12 июля создала новый Сталинградский фронт…» «К концу июля в состав Сталинградского фронта входило…» «Большую организаторскую работу провели обком и горком партии Сталинграда по формированию и подготовке народного ополчения…»
Все это так, все это интересно, но обратим внимание на мелочь: в июле 1942 года Жукова не было в Сталинграде и быть не могло. Он находился совсем на другом направлении, весьма далеко от Сталинграда. У каждого, кто интересуется войной, есть возможность восстановить хронологию работы Жукова на фронте день за днем, с первого до последнего дня войны. Иногда - с точностью до часов и минут. С 11 октября 1941 до 26 августа 1942 года Жуков командовал войсками Западного фронта, который воевал совсем на другом направлении в тысяче километров от Сталинграда.
Противовоздушная оборона Сталинграда осуществлялась войсками сталинградского корпусного района ПВО во взаимодействии с истребительной авиацией 8 воздушной армии. Зенитная артиллерия – до 10 полков занимала круговую оборону объектов в городе. Истребительная авиация – три полка перехватывала и уничтожала вражеские самолеты на подступах к городу. 23 августа более 400 бомбардировщиков группами до 18 самолетов совершили около 2000 самолетовылетов на южную часть и центр города. Зенитная артиллерия и авиация сбили в этот день 120 самолетов. Летчики 102 иад ПВО провели более 25 групповых воздушных боев. Шесть истребителей ведомые И.П. Моториным вступила в бой с 65 самолетами, уничтожили 5 немецких ассов, командир эскадрильи Николай Александрович Козлов уничтожил в небе Сталинграда 12 самолетов противника, один из них тараном. В феврале 1943 года ему было присвоено звание – Герой Советского Союза, всего за годы войны сбил 23 стервятника. Герой Советского Союза Н.А. Козлов проживает в поселке «Заря» недалеко от Москвы, ведет активную военно-патриотическую работу. После 23 августа количество налетов авиации возросло, 102 иад ПВО получила на усиление 86 самолетов.
Воины ПВО вели борьбу не только против авиации, но нередко и против танков противника. Вышедшая 23 августа 1942 года значительная группировка фашистских танков и мотопехоты к северным подступам Сталинграда была встречена зенитным артиллерийским полком полковника В.С. Германа. Без поддержки своей пехоты полк, состоявший на 1/3 из двадцатилетних девушек, в течение двух дней отразил более двадцати вражеских атак, враг к городу не прошел. В этих боях зенитчики уничтожили и подбили 83 танка, 15 автомашин с пехотой, истребили и рассеяли свыше трех батальонов автоматчиков, сбили 15 самолетов противника.
В ходе битвы за Сталинград назревал качественно новый этап в войне с гитлеровской Германией и ее сателлитами. Героическая оборона Сталинграда создала условия для перехода наших войск в контрнаступление. Принципиальное решение о нем было принято в Ставке в самый разгар оборонительных сражений 13 сентября 1942 года после докладов генералов Г.К. Жукова, назначенного 26 августа на специально учрежденный пост – Заместителя Верховного Главнокомандующего и А.М. Василевского, ставшего 26 июня Начальником Генерального штаба. «Перебрав все возможные варианты, - вспоминал Маршал Советского Союза Г.К. Жуков, - мы решили предложить И.В. Сталину следующий план действий: «Активной обороной продолжать изматывать противника, второе – приступить к подготовке контрнаступления, чтобы нанести противнику в районе Сталинграда такой удар, который резко изменил бы Стратегическую обстановку на юге страны в нашу пользу». Спустя два месяца, 13 ноября, после огромной подготовительной работы Ставка утвердила конкретный план стратегического контрнаступления под Сталинградом.
Девятнадцатого ноября 1942 года Севернее Сталинграда предутреннюю тишину донских степей, покрытых первым снегом, разорвали мощные залпы свыше семи тысяч орудий и минометов. Вслед за этим устремились вперед танки и пехота Юго-западного (командующий генерал Н.Ф. Ватутин) и правого крыла Донского (командующий К.К. Рокоссовский) фронтов. Прорвав оборону противника, они развивали наступление на Калач. На другой день южнее Сталинграда мощный удар по врагу нанесли перешедшие в наступление войска Сталинградского фронта. Теперь наступление развивалось на 400 – километровом фронте. А уже к исходу 23 ноября произошло знаменательное событие. Советские войска, наступавшие из районов севернее и южнее Сталинграда, встретились у хутора Советского. Кольцо окружения группировки немецко-фашистских войск замкнулось. В котле оказалось 22 дивизии и более 160 отдельных частей, входивших в состав 6-й и частично 4-й танковой немецких армий, всего 330 тысяч человек с многочисленной техникой.
Гитлеровское командование предприняло ряд отчаянных попыток деблокировать окруженную группировку. Особенно опасным в этом отношении был удар армейской группы «Гот» 12 декабря 1942 года из района Котельниково. Это лишь часть сил из группировки армии «Дон» под командованием фельдмаршала Манштейна, получившего от Гитлера строгий приказ во что бы то ни стало выручить окруженные немецко-фашистские войска. В армейскую группу «Гот» входили 13 дивизий, в том числе переброшенные из Германии и Франции, ряд частей из резерва Главного командования, В ее составе впервые на советско-германском фронте применялись танки «Тигр», фашистам удалось продвинуться вперед. В сложившейся обстановке советские войска сосредоточили свои усилия на отражении наступления Манштейна, на укреплении внутреннего и внешнего фронта окружения, временно приостановили операцию по уничтожению окруженной группировки противника.
Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.
Схема перебора всегда будет одинакова:
-
- во-первых, надо установить ПОРЯДОК на элементах, подлежащих
перечислению (в частности, определить, какой из них будет первым,
а какой последним);
Во-вторых, научиться переходить от произвольного элемента к
HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1
строить такой элемент x2, что x1
H аиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать за- ново. Пока запишем схему перебора в таком виде:
X:=First;
while X<>Last do Next(X);
где First - первый элемент; Last - последний элемент; Next -
процедура получения следующего элемента.
1.1. Последовательности
Hапечатать все последовательности длины N из чисел 1,2,...,M.
First = (1,1,...,1) Last = (M,M,...,M)
Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:
Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)
Теперь можно написать общую процедуру Next:
Если такого i найти не удается, то следующей последовательности
нет - мы добрались до последней (M,M,...,M). Заметим также, что
если бы членами последовательности были числа не от 1 до M, а от
0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так: Program Sequences;
type Sequence=array of byte;
var M,N,i:byte;
X:Sequence;
Yes:boolean;
procedure Next(var X:Sequence;var Yes:boolean);
var i:byte;
begin
i:=N;
{поиск i}
while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end;
if i>0 then begin inc(X[i]);Yes:=true end
else Yes:=false
end;
begin
write("M,N=");readln(M,N);
for i:=1 to N do X[i]:=1;
repeat
for i:=1 to N do write(X[i]);writeln;
Next(X,Yes)
until not Yes
end.
Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по
одному разу). First = (1,2,...,N)
Last = (N,N-1,...,1) Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!).
Для составления алгоритма Next зададимся вопросом: в каком случае
i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i). Мы должны найти наибольшее i, при котором это
так, т.е. такое i, что X[i] Procedure Next;
begin
{найти i: X[i] Теперь можно написать программу: Program Perestanovki;
type Pere=array of byte;
var N,i,j:byte;
X:Pere;
Yes:boolean;
procedure Next(var X:Pere;var Yes:boolean);
var i:byte;
procedure Swap(var a,b:byte); {обмен переменных}
var c:byte;
begin c:=a;a:=b;b:=c end;
begin
i:=N-1;
{поиск i}
while (i>0)and(X[i]>X) do dec(i);
if i>0 then
begin
j:=i+1;
{поиск j}
while (j1.2. Перестановки
