сколькими способами можно выбрать на шахматной доске два квадрата белый и черный
Сколькими способами можно выбрать на шахматной доске два квадрата белый и черный
II. Размещения из n элементов по k
III. Сочетания из n элементов по k
Задачи занятия №3
Размещения
а) У туриста есть пять способов подняться на гору. Для каждого из этих способов существует по пять возможностей спуститься вниз. Соответственно, способов подняться на гору, а затем спуститься с нее, существует ровно 5·5 = 25.
б) В отличие от пункта а, теперь для каждого из пяти способов подняться на гору есть лишь по четыре возможности спуститься: по той же дороге, по которой турист поднимался, спускаться уже нельзя. Так что в этом случае есть 5·4 = 20 возможных маршрутов.
a) Выбрать капитана можно четырьмя способами. При каждом из четырех способов выбора капитана есть по три способа выбрать первого помощника из оставшихся пиратов. А при каждом способе выбора капитана и помощника выбрать боцмана можно двумя способами. Поэтому всего возможностей распределить должности будет 4·3·2=24.
b) Решение аналогично решению пункта а. 6·5·4=120.
с) Решение аналогично решению двух предыдущих пунктов. Вычислять произведение чисел 20·19·18·17 проще всего так: 20·19·18·17 = (20·18)·(18-1)·(18+1) = 360·(18²-1) = 360·(324-1) = 360·323 = 116280 (здесь мы пользовались формулой для разности квадратов). Последнее умножение в этой цепочке можно проделать в столбик, а можно продолжить преобразования и привести выражение к такому виду, чтобы все действия можно было выполнить в уме (попробуйте проделать это самостоятельно). Вычислить 18² можно при помощи формулы для квадрата суммы: 18² = (20-2)² = 20²-2·20·2+2² = 400-80+4 = 324.
Посчитаем это количество. Отметим, что в каждой ячейке нижней строки нашей таблицы может стоять любой номер от 1 до 6 (каждый из шаров может попасть в любую лузу). Поэтому число способов ее заполнить равно 6·6·…·6 = 6 15 (произведение состоит из 15 сомножителей).
Точное значение числа 6 15 находить не обязательно, но можно вычислить, что оно равно 470184984576. Попробуйте это сделать, используя умножение не более шести раз. Все действия выполняйте в уме или в столбик: калькулятором пользоваться запрещается!
Сначала выберем черное поле. Как известно, на шахматной доске 8·8=64 клетки, и ровно половина из них черные. Значит, выбрать черное поле можно 32 способами.
В каждой вертикали и в каждой горизонтали есть по четыре белые клетки. Значит, на одной вертикали или на одной горизонтали с любой выбранной черной клеткой лежат 8 белых клеток. Так как всего белых клеток на доске 32, то не лежащих на одной горизонтали или вертикали с нашей черной клеткой среди них будет 32-8 = 24. Тем самым есть 32 способа выбрать черную клетку, и для каждого из этих способов по 24 возможности выбрать белую клетку. Значит, всего возможностей выбрать пару разноцветных клеток, не лежащих на одной горизонтали или вертикали, будет 32·24 = 768.
Перестановки
a) Ясно, что искомые числа состоят из цифр 1, 2, 3, 4, 5, расставленных в разном порядке. Значит, количество таких чисел равно количеству способов упорядочить множество из пяти цифр. На первое место можно поставить любую цифру от 1 до 5. После того как первая цифра выбрана, вторую можно выбрать четырьмя способами. Когда выбраны первая и вторая цифры, третью можно выбрать тремя способами, и так далее. Значит, всего искомых чисел 5·4·3·2·1 = 5! = 120 (сравните с пунктом I «Теоретических сведений»).
b) Здесь, в отличие от пункта а, на первое место можно поставить не любую цифру: число не может начинаться с нуля. Поэтому на первом месте может стоять любая из четырех, а не пяти, цифр. Дальнейшие рассуждения полностью аналогичны предыдущим. Так что всего искомых чисел будет 4·4·3·2·1 = 96.
Задачи занятия №4
Сочетания без повторений
a) Выбрать пять человек из шести — все равно, что выбрать одного, которого в команду не возьмут. А выбрать одного человека из шести, очевидно, можно шестью способами.
b) Аналогично предыдущему, выбрать пять человек из семи — все равно, что выбрать двух. Первого человека можно выбрать 7 способами, а второго после этого — шестью. То есть если важно, кто первый, а кто второй, число способов это сделать равно 7·6 = 42. Но одну и ту же пару человек можно упорядочить двумя способами. Значит, число неупорядоченных пар, выбранных из семи человек, равно 42:2 = 21.
c) Набрать две команды по пять человек из десяти претендентов — все равно что набрать одну команду, а из остальных претендентов составить другую. Посчитаем число способов выбрать пять человек из 10. Если порядок важен, то есть 10·9·8·7·6 способов это сделать. Но существует 5! = 120 способов упорядочить 5 человек (вспомните задачу 3.10 а). Так что каждому способу выбрать 5 человек неупорядоченным образом соответствует 120 способов выбрать их упорядоченным образом. Значит, количество способов набрать команду из пяти человек в 120 раз меньше, чем 10·9·8·7·6. А это, как нетрудно посчитать, есть в точности 252.
Упорядоченные выборки, полученные из разных неупорядоченных выборок, различны (хотя бы потому, что состоят из различных элементов). Каждую упорядоченную выборку можно получить из какой-то неупорядоченной (а именно той, которая состоит из элементов интересующей нас упорядоченной). Тем самым доказано, что упорядоченных выборок из k элементов ровно в k! раз больше, чем неупорядоченных выборок того же объема. Это и доказывает первое равенство в приведенной формуле.
Сочетания с повторениям
Пусть пирожки разных типов разложены на пяти лотках. Когда мы покупаем пирожки, мы действуем так: сначала берем сколько-то пирожков с картошкой (может быть, ни одного), затем переходим к лотку с пирожками с капустой и берем сколько-то пирожков оттуда, и так далее до тех пор, пока не наберем восемь пирожков.
Последовательность наших действий при этом можно описать так. Запишем в ряд восемь единиц. Отсчитаем от начала столько единиц, сколько пирожков с картошкой мы взяли, и поставим после них вертикальную черту. В частности, если мы не взяли ни одного пирожка с картошкой, поставим черту перед первой единицей, а если мы их взяли сразу восемь, поставим ее после последней единицы. Далее проделаем то же самое по отношению к пирожкам с капустой, с мясом, с рисом и с яблоком. Если в какой-то момент мы наберем восемь пирожков, а до последнего лотка еще не дойдем, оставшиеся вертикальные черточки будем в нужном количестве ставить после последней единицы. Если, наоборот, мы ничего не возьмем с первых нескольких лотков, черточки будем ставить перед первой единицей.
Всего в нашей записи будет 8 единиц и четыре вертикальные черты, то есть 12 символов. Чтобы получить произвольную запись такого вида, нужно выбрать 8 позиций из 12, на которые мы поставим единицы, а на остальные позиции поставить вертикальные черточки. Тем самым количество возможных способов купить восемь пирожков равно C 8 12 = 495 (примените формулу из задачи 4.2).
Применим принцип, использованный в предыдущих задачах. Сначала распределим по лифтам пятиклассников, потом шестиклассников, затем семиклассников и наконец, восьмиклассников.
Присвоим лифтам номера от 1 до 5. Каждый способ распределить по лифтам пятиклассников будем записывать так: сначала пишем в ряд столько единиц, сколько пятитклассников посадим в первый лифт, затем ставим вертикальную черту и пишем еще столько единиц, сколько пятитклассников посадим во второй лифт, и так далее. Число таких записей равно числу способов распределить по лифтам пятиклассников и равно в точности C 4 14 (вспомните предыдущие задачи). Для шестиклассников аналогичным образом получим C 4 15 способов, для семиклассников C 4 12 и наконец, для восьмиклассников C 4 16 способов. Теперь все эти числа надо перемножить.
Разные задачи
При решении задачи 3.11 мы подсчитали, что число кодов, состоящих из не более чем четырех символов азбуки Морзе, равно 30. Среди этих кодов есть только два, которые используют более трех однотипных символов: это, соответсвенно, код из четырех точек и код из четырех тире. Все остальные коды нам подходят. Тем самым у нас уже есть 28 «хороших» кодов. Осталось придумать еще пять кодов, удовлетворяющих нашим требованиям. Например, таких: — — — · ·, · — — — ·, · — · — ·,— · — · —, — — — · · ·. Теперь у нас есть 33 «хороших» кода, и мы можем ими зашифровать весь русский алфавит.
Попробуйте самостоятельно сосчитать количество всех «хороших» кодов. Хватит ли их, чтобы зашифровать сначала русские буквы, а потом латинские? А цифры?
a) Число треугольников с вершинами в этих точках равно числу способов выбрать две точки на одной прямой и одну — на другой. При этом пару точек, лежащих на одной из прямых, нужно выбирать неупорядченным образом: при их перестановке треугольник не изменится. Если одну вершину выбирать на первой прямой, а еще две на второй, то получится 10·C 11 2 = 550 различных треугольников (10 способов выбрать вершину на первой прямой и C 10 2 = 55 способов выбрать две вершины на второй прямой). Аналогично найдем, что если на первой прямой брать две вершины, а на второй — только одну, получится 11·C 10 2 = 495 различных треугольников. Значит, всего треугольников с вершинами в отмеченных точках существует 550+495 = 1045.
b) Для построения четырехугольника надо выбрать по две точки на каждой прямой (иначе получится не четырехугольник, а треугольник или даже отрезок). При этом та точка, которая лежит левее на первой прямой, будет соединяться стороной с точкой, лежащей левее на второй прямой (и то же самое касается точек, которые лежат правее), иначе получится фигура, которую мы четырехугольником не считаем (попробуйте нарисовать такую фигуру). Поэтому пары точек на каждой прямой надо выбирать неупордоченным образом, а затем вершины соединять вышеуказанным способом. Всего есть C 10 2 = 45 способов выбрать пару точек на первой прямой и C 11 2 = 55 способов выбрать пару точек на второй прямой. Количество искомых четырехугольников равно произведению этих чисел, а именно 2475.
Выберем какого-нибудь человека из нашей компании (назовем его А). Тогда в компании либо есть трое, которые с ним знакомы, либо трое, которые с ним незнакомы. Этих троих назовем Б, В, Г.
Пусть сначала Б, В, Г знакомы с А. Если среди них есть двое знакомых друг с другом, то эти двое и А знакомы между собой, и утверждение задачи выполнено. Если же среди них нет знакомых, то они и есть те трое, которые друг с другом не знакомы, и утверждение вновь выполнено. Случай, когда Б, В и Г не знакомы с А, рассматривается точно так же, только слова «знакомы» и «не знакомы» меняются местами.
Сколькими способами можно выбрать на шахматной доске два квадрата – белый и черный?
Сколькими способами можно выбрать на шахматной доске две клетки, чтобы из одной в другую можно было попасть ходом коня
Сколькими способами можно выбрать на шахматной доске для клетки так, чтобы из одной в другую можно.
Сколькими способами можно разместить 8 слонов на шахматной доске?
Сколькими способами можно разместить 8 слонов на шахматной доске, чтобы никто из них не мог бить.
Сколькими способами можно разместить на шахматной доске восемь ладей?
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они смогли сьесть.
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга?
Помогите решить, задачу,если есть возможность объяснить первый шаг решения задачи,или общий ход.
Сколькими способами из 7 элементов можно выбрать два набора?
Сколькими способами из 7 элементов можно выбрать два набора так, чтобы их объединение состояло из.
Сколькими способами можно выбрать два красных шарика
В корзине есть 8 красных, 5 белых и 3 черных шаров. Сколькими способами можно выбрать две красных.
Сколькими способами можно расставить фишки на доске?
Сколькими способами можно расставить на доску с 16 квадратов а) 16 различных фишек, так чтобы.
Сколькими способами можно разместить фигуры на доске?
Дана шахматная доска 19 на 19. Сколькими способами можно разместить 9 разных башен так, чтобы ни.
UML_4822 дм практикум
= | A B C | – | A | – | B | – | C | + | A B | + | A C | + | B C | – | A B C |.
Данное выражение позволяет найти число элементов для любой операции, если известны их значения для всех других операций.
Рассмотренный принцип доказывается следующей парой теорем. Теорема 3. Если A и B конечные подмножества некоторого универ-
B A и формула (2.7) дает N ( A ) = N ( A )
+ N ( A ) – N ( A ) = N ( A ), то есть верное равенство.
N ( A ) + N ( B ) – N ( A ) = N ( B ), то есть верное равенство.
левой части последнего равенства число общих элементов
дут перечислены дважды. Отсюда и следует равенство (2.7). Теорема 3 доказана.
Задача 56. Сколькими способами можно выбрать гласную и согласную буквы из слова «Камзол»?
Задача 57. В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?
Решение. Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 15 (3 5 = 15).
Задача 59. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для
участия в состязании. Сколькими способами может быть сделан этот выбор?
Задача 60. Бросают игральную кость с шестью гранями и запускают волчок, имеющий восемь граней. Сколькими различными способами могут они упасть?
Задача 61. На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям?
Задача 62. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?
Задача 63. Сколькими способами можно указать на шахматной доске два квадрат – белый и черный? А если нет ограничений на цвет выбранных квадратов?
Задача 64. Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?
Задача 65. Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 7 экземпляров учебника тригонометрии надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать?
Задача 66. Сколькими способами можно выбрать четырехзначное число, все цифры которого различны?
Согласно правилу произведения искомое число способов выбора четырехзначного числа с различными цифрами равно: 9 9 8 7 = 4536.
Задача 67. Сколько четырехзначных чисел можно составить, пользуясь только цифрами 0, 1, 2, 3, 4, 5, если ни одна из цифр не повторяется более одного раза?
Задача 68. Сколько четырѐхбуквенных «слов» можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»?
Задача 69. Сколькими способами можно поставить на шахматную доску белую и черную ладью так, чтобы они не били друг друга?
В разобранной задаче вопрос о том, считаются ли ладьи одинаковыми, возникнуть не мог. Но во многих задачах с однородными объектами, приступая к решению, надо ясно представлять, считаются ли эти объекты неразличимыми.
Задача 70. Сколькими способами можно поставить на доску восемь ладей так, чтобы они не били друг друга?
Если же считать ладьи различными (как в предыдущем примере), то число перестановок ладей равно
Действительно, для первой ладьи можно выбрать любое поле доски размером 8 8, вторая ладья фактически ставится на квадратную доску 7 7
(мы удалили одну горизонталь и одну вертикаль и «сдвинули» оставшиеся части доски) и т.д.
Зафиксируем одну из таких расстановок различных ладей. Число перестановок ладей на выделенных полях равно 8! Если мы считаем ладьи одинаковыми, то (8!) 2 позиций разбиваются на классы по 8! позиций в каждом, и все позиции данного класса будут одинаковыми. Поэтому чис-
ло перестановок одинаковых ладей равно 8! 2 8!, что совпадает с ранее
Задача 71. Сколько существует четырѐхзначных чисел, у которых все цифры нечѐтные? Сколько существует четырѐхзначных чисел, в записи которых есть хотя бы одна чѐтная цифра?
Чтобы ответить на второй вопрос, проще не определять последовательно, сколько существует чисел, в записи которых ровно одна чѐтная цифра, две, три, четыре, а воспользоваться полученным ответом на первый вопрос. Все четырѐхзначные числа, а их 9999 – 999 = 9000, делятся на две группы: те, в записи которых все цифры нечѐтные, и те, в записи которых есть хотя бы одна чѐтная цифра. Следовательно, количество чисел второго типа равно 9000 – 625 = 8375.
Обратите внимание на идею, которую мы использовали – переход к дополнению изучаемого множества. Это пример применения второго общего правила комбинаторики – правила суммы.
Рис. 13. Карта дорог Страны Чудес
чество возможных маршрутов: в первом – 24, во втором – 6. По принципу сложения получим общее количество маршрутов – 30.
Задача 73. В букинистическом магазине лежат 6 экземпляров романа И.С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?
Задача 74. Та же задача, если кроме того, в магазине есть 3 тома, в которые входят «Рудин» и «Отцы и дети».
Задача 75. Имеются три волчка с 6, 8 и 10 гранями соответственно. Сколькими различными способами могут они упасть? Та же задача, если известно, что по крайней мере два волчка упали на сторону, помеченную цифрой 1.
Решение. 6 8 10 = 480; если первые два волчка упали на сторону «1», то третий волчок может упасть 10 способами; аналогично рассматриваются случаи, когда на такую сторону падают другие два волчка; всего получаем 6 + 8 + 10 способов, но при этом один способ (когда на сторону «1» падают все три волчка) считается трижды, поэтому остается 22 способа.
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Общим термином «соединения» будем называть три вида комбинаций, составляемых из некоторого числа различных элементов, принадлежащих одному и тому же множеству – перестановки, сочетания и размещения.
Процедура перестановки имеет большое значение при выборе алгоритмов сортировки данных на компьютере для быстрого и экономного использования оперативной памяти. Все алгоритмы опираются на отношение порядка и формируют линейно упорядоченные множества.
Пусть задано конечное множество A мощности n.
Теорема 4. (Теорема о числе перестановок). Если через P n обозна-
(2.8). Теорема доказана.
Задача 76. Дано трехэлементное множество M = <1, 2, 3>. Укажите всевозможные перестановки этого множества.
Задача 77. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него?
Задача 78. К кассе кинотеатра подходит 6 человек. Сколько существует различных вариантов установки их в очередь друг за другом?
Задача 79. Сколько различных слов (пусть и не имеющих смысла) можно получить путем перестановки букв в слове “дубленка”?
Задача 80. В заезде на ипподроме участвуют 12 рысаков. Играющие в тотализатор заполняют карточки, в которых указывают порядок, в котором, по их мнению, рысаки придут к финишу. Будем считать, что к финишу одновременно не могут придти два и более рысаков. Сколько вариантов заполнения карточек существует?
Задача 81. На заседании Думы 14 депутатов записались на выступления. Сколько вариантов списков выступающих может быть составлено, если списки отличаются только порядком? Подсчитайте количество расстановок депутатов в списке выступающих, если известно, что некоторые депутаты “Ж” и “З” уже добились, чтобы их включили в список выступающих под номерами соответственно 3 и 7.
Задача 82. Сколько существует способов, чтобы расположить на полке 5 различных книг?
Задача 83. Сколькими способами можно упорядочить множество <1, 2,…, 2 n >, так чтобы каждое четное число имело четный номер?
Задача 84. Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом?
Задача 85. Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?
Вообще, если рассматривать перестановки n предметов, расположенных не в ряд, а по кругу, и считать одинаковыми расположения, переходящие друг в друга при вращении, то число различных перестановок равно ( n – 1)!.
Задача 86. Сколько ожерелий можно составить из 7 различных бу-
Рис.14. К решению задачи 86
Из определения следует, что две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.
Сколькими способами можно выбрать на шахматной доске две клетки, чтобы из одной в другую можно было попасть ходом коня
Проверить можно ли ходом короля из одной клетки попасть в другую
Делать было нечего решил все простые задачи перерешать с сайта. Ближе к делу: Поле шахматной доски.
Определить, возможно ли попасть из одной клетки в другую одним ходом шахматного коня
Заданы две клетки шахматной доски. Требуется определить, возможно ли попасть из одной клетки в.
Сколькими способами можно выбрать на шахматной доске два квадрата – белый и черный?
Сколькими способами можно выбрать на шахматной доске два квадрата – белый и черный?
Поиск последовательности перемещений коня на шахматной доске из одной клетки в другую
Реализовать алгоритм решения задачи о поиске последовательности перемещений коня на шахматной доске.
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга?
Помогите решить, задачу,если есть возможность объяснить первый шаг решения задачи,или общий ход.
Сколькими способами можно разместить 8 слонов на шахматной доске?
Сколькими способами можно разместить 8 слонов на шахматной доске, чтобы никто из них не мог бить.
Сколькими способами можно разместить на шахматной доске восемь ладей?
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они смогли сьесть.
Сколькими способами можно выбрать 5 карт из 52 так, чтобы среди них оказались две карты одного достоинства
Сколькими способами можно выбрать 5 карт из 52 так, чтобы среди них оказались две карты одного.
UML_4822 дм практикум
= | A B C | – | A | – | B | – | C | + | A B | + | A C | + | B C | – | A B C |.
Данное выражение позволяет найти число элементов для любой операции, если известны их значения для всех других операций.
Рассмотренный принцип доказывается следующей парой теорем. Теорема 3. Если A и B конечные подмножества некоторого универ-
B A и формула (2.7) дает N ( A ) = N ( A )
+ N ( A ) – N ( A ) = N ( A ), то есть верное равенство.
N ( A ) + N ( B ) – N ( A ) = N ( B ), то есть верное равенство.
левой части последнего равенства число общих элементов
дут перечислены дважды. Отсюда и следует равенство (2.7). Теорема 3 доказана.
Задача 56. Сколькими способами можно выбрать гласную и согласную буквы из слова «Камзол»?
Задача 57. В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?
Решение. Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 15 (3 5 = 15).
Задача 59. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для
участия в состязании. Сколькими способами может быть сделан этот выбор?
Задача 60. Бросают игральную кость с шестью гранями и запускают волчок, имеющий восемь граней. Сколькими различными способами могут они упасть?
Задача 61. На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям?
Задача 62. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?
Задача 63. Сколькими способами можно указать на шахматной доске два квадрат – белый и черный? А если нет ограничений на цвет выбранных квадратов?
Задача 64. Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?
Задача 65. Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 7 экземпляров учебника тригонометрии надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать?
Задача 66. Сколькими способами можно выбрать четырехзначное число, все цифры которого различны?
Согласно правилу произведения искомое число способов выбора четырехзначного числа с различными цифрами равно: 9 9 8 7 = 4536.
Задача 67. Сколько четырехзначных чисел можно составить, пользуясь только цифрами 0, 1, 2, 3, 4, 5, если ни одна из цифр не повторяется более одного раза?
Задача 68. Сколько четырѐхбуквенных «слов» можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»?
Задача 69. Сколькими способами можно поставить на шахматную доску белую и черную ладью так, чтобы они не били друг друга?
В разобранной задаче вопрос о том, считаются ли ладьи одинаковыми, возникнуть не мог. Но во многих задачах с однородными объектами, приступая к решению, надо ясно представлять, считаются ли эти объекты неразличимыми.
Задача 70. Сколькими способами можно поставить на доску восемь ладей так, чтобы они не били друг друга?
Если же считать ладьи различными (как в предыдущем примере), то число перестановок ладей равно
Действительно, для первой ладьи можно выбрать любое поле доски размером 8 8, вторая ладья фактически ставится на квадратную доску 7 7
(мы удалили одну горизонталь и одну вертикаль и «сдвинули» оставшиеся части доски) и т.д.
Зафиксируем одну из таких расстановок различных ладей. Число перестановок ладей на выделенных полях равно 8! Если мы считаем ладьи одинаковыми, то (8!) 2 позиций разбиваются на классы по 8! позиций в каждом, и все позиции данного класса будут одинаковыми. Поэтому чис-
ло перестановок одинаковых ладей равно 8! 2 8!, что совпадает с ранее
Задача 71. Сколько существует четырѐхзначных чисел, у которых все цифры нечѐтные? Сколько существует четырѐхзначных чисел, в записи которых есть хотя бы одна чѐтная цифра?
Чтобы ответить на второй вопрос, проще не определять последовательно, сколько существует чисел, в записи которых ровно одна чѐтная цифра, две, три, четыре, а воспользоваться полученным ответом на первый вопрос. Все четырѐхзначные числа, а их 9999 – 999 = 9000, делятся на две группы: те, в записи которых все цифры нечѐтные, и те, в записи которых есть хотя бы одна чѐтная цифра. Следовательно, количество чисел второго типа равно 9000 – 625 = 8375.
Обратите внимание на идею, которую мы использовали – переход к дополнению изучаемого множества. Это пример применения второго общего правила комбинаторики – правила суммы.
Рис. 13. Карта дорог Страны Чудес
чество возможных маршрутов: в первом – 24, во втором – 6. По принципу сложения получим общее количество маршрутов – 30.
Задача 73. В букинистическом магазине лежат 6 экземпляров романа И.С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?
Задача 74. Та же задача, если кроме того, в магазине есть 3 тома, в которые входят «Рудин» и «Отцы и дети».
Задача 75. Имеются три волчка с 6, 8 и 10 гранями соответственно. Сколькими различными способами могут они упасть? Та же задача, если известно, что по крайней мере два волчка упали на сторону, помеченную цифрой 1.
Решение. 6 8 10 = 480; если первые два волчка упали на сторону «1», то третий волчок может упасть 10 способами; аналогично рассматриваются случаи, когда на такую сторону падают другие два волчка; всего получаем 6 + 8 + 10 способов, но при этом один способ (когда на сторону «1» падают все три волчка) считается трижды, поэтому остается 22 способа.
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Общим термином «соединения» будем называть три вида комбинаций, составляемых из некоторого числа различных элементов, принадлежащих одному и тому же множеству – перестановки, сочетания и размещения.
Процедура перестановки имеет большое значение при выборе алгоритмов сортировки данных на компьютере для быстрого и экономного использования оперативной памяти. Все алгоритмы опираются на отношение порядка и формируют линейно упорядоченные множества.
Пусть задано конечное множество A мощности n.
Теорема 4. (Теорема о числе перестановок). Если через P n обозна-
(2.8). Теорема доказана.
Задача 76. Дано трехэлементное множество M = <1, 2, 3>. Укажите всевозможные перестановки этого множества.
Задача 77. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него?
Задача 78. К кассе кинотеатра подходит 6 человек. Сколько существует различных вариантов установки их в очередь друг за другом?
Задача 79. Сколько различных слов (пусть и не имеющих смысла) можно получить путем перестановки букв в слове “дубленка”?
Задача 80. В заезде на ипподроме участвуют 12 рысаков. Играющие в тотализатор заполняют карточки, в которых указывают порядок, в котором, по их мнению, рысаки придут к финишу. Будем считать, что к финишу одновременно не могут придти два и более рысаков. Сколько вариантов заполнения карточек существует?
Задача 81. На заседании Думы 14 депутатов записались на выступления. Сколько вариантов списков выступающих может быть составлено, если списки отличаются только порядком? Подсчитайте количество расстановок депутатов в списке выступающих, если известно, что некоторые депутаты “Ж” и “З” уже добились, чтобы их включили в список выступающих под номерами соответственно 3 и 7.
Задача 82. Сколько существует способов, чтобы расположить на полке 5 различных книг?
Задача 83. Сколькими способами можно упорядочить множество <1, 2,…, 2 n >, так чтобы каждое четное число имело четный номер?
Задача 84. Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом?
Задача 85. Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?
Вообще, если рассматривать перестановки n предметов, расположенных не в ряд, а по кругу, и считать одинаковыми расположения, переходящие друг в друга при вращении, то число различных перестановок равно ( n – 1)!.
Задача 86. Сколько ожерелий можно составить из 7 различных бу-
Рис.14. К решению задачи 86
Из определения следует, что две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.