Сочетания формула комбинаторика: Азы комбинаторики — Без Сменки

alexxlab / / Разное

Содержание

Основные формулы комбинаторики. Комбинаторика: формула расчета перестановки, размещения

В данной статье речь пойдет об особом разделе математики под названием комбинаторика. Формулы, правила, примеры решения задач – все это вы сможете найти здесь, прочитав статью до самого конца.

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

Комбинаторные конфигурации

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

  • размещение;
  • перестановка;
  • сочетание;
  • композиция числа;
  • разбиение числа.

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

Разделы

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

  • перечислительная;
  • структурная;
  • экстремальная;
  • теория Рамсея;
  • вероятностная;
  • топологическая;
  • инфинитарная.

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

Правило сложения

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса — допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе – с2 способами, третье – с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.

Перестановка

Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n — 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга – Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша – это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение – это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n — 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n — m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики – знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи

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

  1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
  2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n — m)!)).
  3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
  4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
  5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n — m)!).

Пример

Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта – выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

ОСНОВНЫЕ ФОРМУЛЫ КОМБИНАТОРИКИ.

  • Авторы
  • Руководители
  • Файлы работы
  • Наградные документы

Шухратбеков А.Ш. 1Тоштемиров А.Ф. 1

1Академический лицей Международного Вестминстерского университета в Ташкенте

Хамраева Р. Р. 1

1WIUT

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке «Файлы работы» в формате PDF

Введение

«Число, положение и комбинация —

три взаимно пересекающиеся, но

различные сферы мысли, к которым

можно отнести все математические

идеи».

Дж. Сильвестр (1844 г.)

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры. Широко были распространены всевозможные лотереи. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр – сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре. Эти и другие проблемы азартных игр явились движущей силой в развитии комбинаторики и развивавшейся одновременно с ней теории вероятностей.

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывавшую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами (например, 1+3+4=4+2+2)

За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики.

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

Очевидно, комбинаторика – обширная, масштабная, увлекательная тема, занимающая немалую роль, как и в дискретной математике, так и в повседневной жизни. И в данном проекте, мы коснёмся основных понятий и формулировок комбинаторики, а также рассмотрим несколько задач. Более того, постараемся прийти к одному умозаключению.

Основные формулы комбинаторики

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

Комбинаторика перестановки

«Сколькими способами можно переставить n объектов?»

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

Pn=n!=1⋅2⋅3⋅…⋅(n−1)⋅n

Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n

Пример всех перестановок из n=3 объектов (различных фигур) — на картинке справа. Согласно формуле, их должно быть ровно P3=3!=1⋅2⋅3=6так и получается.

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

Комбинаторика размещения

Пусть имеется n различных объектов.

Будем выбирать из них m объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются

размещениями из n объектов по m, а их число равно

=n!(n−m)!=n⋅(n−1)⋅. ..⋅(n−m+1)

Пример всех размещений из n=3 объектов (различных фигур) по m=2m=2 — на картинке справа. Согласно формуле, их должно быть ровно A23=3⋅(3−2+1)=3⋅2=6A32=3⋅(3−2+1)=3⋅2=6.
Комбинаторика сочетания

Пусть имеется n различных объектов.

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

из n объектов по m, а их число равно

=n!(n−m)!⋅m!

Пример всех сочетаний из n=3 объектов (различных фигур) по m=2 — на картинке справа. Согласно формуле, их должно быть ровно =3!(3−2)!⋅2!=3. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний — нет), причем именно в m! раз, то есть верна формула связи:


=⋅Pm

Основные комбинаторные объекты и методы

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

Есть несколько основных типов комбинаторных задач:

— существование объекта с заданными свойствами;

— подсчет или оценка количества искомых комбинаций или их описание;

— поиск оптимальной комбинации по какому-то параметру.

Простейшие способы комбинаторных подсчетов. Правило суммы.

Комбинаторика тесно связана теорией конечных множеств: понятия подмножество, объединение множеств, пересечение множеств оказываются полезными при решении комбинаторных задач, т.

2— 25. При этом еще надо отбросить положение, когда оба флажка направлены вниз — оно служит для разделения слов. Всего получаем 24 комбинации, а этого недостаточно для передачи всех букв русского алфавита. Поэтому для некоторых букв и пришлось направить оба флажка в одну сторону.

Генетический код

Замечательным открытием биологии XX века была разгадка генетического кода. Удалось выяснить, каким образом наследственная информация передается потомству. Оказалось, что эта информация записана в гигантских молекулах дезоксирибонуклеиновой кислоты (ДНК). Различные молекулы ДНК отличаются друг от друга тем, в каком порядке идут них 4 азотистых основания: аденин, тиамин, гуанин и цитозин. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причем каждая аминокислота зашифрована кодом из трех азотистых оснований. Легко понять, откуда взялось число 3. Ведь с помощью комбинаций двух оснований можно зашифровать лишь 4^2=16 аминокислот, а этого недостаточно.

3=64 комбинации. А этого с избытком хватит, чтобы зашифровать два десятка. Было бы весьма интересно узнать, как используется в природе избыточность информации-ведь число комбинаций равно 64, а число аминокислот втрое меньше. В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом, невообразимо велико). Ничтожной доли этих комбинаций достаточно было, чтобы обеспечить все разнообразие живой природы за время существования жизни на Земле. Разумеется, надо иметь в виду, что лишь ничтожная доля теоретически возможных комбинаций приводит к жизнеспособным организмам.

Заключение

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

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

Литература

Н.Я. Виленкин “Комбинаторика”, 1969

М. А. Иванов, Ю. В. Якубович “Введение в комбинаторику. Теория и задачи”. 2018

Просмотров работы: 188

Перестановки и комбинации — Математика, уровень A

В этом разделе рассматриваются перестановки и комбинации.

Расстановка предметов

Количество способов расстановки n непохожих предметов в ряд равно n! (произносится как «н-факториал»). н! = n × (n – 1) × (n – 2) ×…× 3 × 2 × 1

Пример

Сколькими различными способами можно расположить буквы P, Q, R, S?

Ответ 4! = 24.

Это потому, что нужно заполнить четыре пробела: _, _, _, _

Первое место может быть заполнено любой из четырех букв. Второе место может быть заполнено любой из оставшихся 3 букв. Третье место может быть заполнено любой из двух оставшихся букв, а последнее место должно быть заполнено одной оставшейся буквой. Таким образом, общее количество возможных комбинаций равно 4 × 3 × 2 × 1 = 4!

  • Количество способов расположения n предметов, из которых p одного типа одинаковы, q второго типа, r третьего типа одинаковы и т. д. равно:

н!         .
р! вопрос! р! …

Пример

Сколькими способами можно расположить буквы в слове: СТАТИСТИКА?

В этом слове 3 буквы «С», 2 буквы «И» и 3 буквы «Т», следовательно, количество способов расстановки букв:

10! =50 400
3! 2! 3!

Кольца и кольцевые развязки

  • Количество способов расположения n непохожих предметов в кольце, когда расположение по часовой стрелке и против часовой стрелки различно, равно (n – 1)!

При одинаковом расположении по часовой и против часовой стрелки количество путей равно ½ (n – 1)!

Пример

Десять человек идут на вечеринку. Сколькими способами их можно рассадить?

Расположение против и по часовой стрелке одинаково. Следовательно, общее количество способов равно ½ (10-1)! = 181 440

Комбинации

Количество способов выбрать r объектов из n непохожих объектов:

Пример

В мешке 10 шаров, пронумерованных от 1 до 10. Три шара выбираются случайным образом. Сколькими способами можно выбрать три шара?

10 С 3 = 10! = 10 × 9 × 8 = 120
             3! (10 – 3)!3 × 2 × 1

Перестановки

Перестановка — это упорядоченное расположение.

n P r =        n!     .
          (н – р)!

Пример

В соревновании «Гол дня в матче дня» вам нужно было выбрать 3 лучших гола из 10. Поскольку порядок важен, мы используем формулу перестановки.

10 Р 3 = 10!
            7!

= 720

Таким образом, есть 720 различных способов выбрать три верхние цели.

Вероятность

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

Пример

В национальной лотерее выбираются 6 номеров из 49. Вы выиграете, если 6 выбранных вами шаров совпадут с шестью шарами, выбранными машиной. Какова вероятность выиграть в национальной лотерее?

Количество способов выбрать 6 чисел из 49 равно 49 C 6 = 13 983 816 .

Следовательно, вероятность выиграть в лотерею равна 1/13983816 = 0,000 000 071 5 (3 sf), что составляет примерно 1 шанс из 14 миллионов.

Brilliant Math & Science Wiki

Содержание
  • Введение
  • Основные примеры
  • Промежуточные примеры
  • Расширенные примеры
  • Комбинации с повторением
  • Комбинации с ограничением
  • Комбинации — решение проблем

Рассмотрим следующий пример: у Лизы 121212 различных украшений, и она хочет подарить маме на день рождения 555 украшений (порядок подарков не имеет значения). Сколькими способами она может это сделать?

Мы можем представить, как Лиза дарит своей маме первое украшение, второе украшение, третье украшение и т. д. Это можно сделать за 12!7! \frac{12!}{7!} 7!12!​ способов. Однако мама Лизы получает сразу все пять украшений, поэтому порядок, в котором Лиза выбирает украшения, не имеет значения. Есть 5! 5! 5! переупорядочивания выбранных украшений, из чего следует, что общее количество способов, которыми Лиза может подарить своей маме неупорядоченный набор из 555 украшений, равно 12!7!5! \frac{12!}{7!5!} 7!5!12!​.

Обратите внимание, что в ответе сумма факториалов в знаменателе равна значению в числителе. Это не совпадение. В общем, количество способов выбрать k k k неупорядоченных элементов из множества n n n равно n!k!(n−k)! \frac{n!}{k!(n-k)!} k!(n−k)!n!​. Это биномиальный коэффициент.

Доказательство (nk)=n!k!(n−k)!:\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}:(kn​)=k! (n−k)!n!​:

Теперь предположим, что мы хотим выбрать kkk объектов из nnn объектов, тогда число комбинаций kkk объектов, выбранных из nnn объектов , обозначается как (nk)n \choose k(kn ​). Поскольку nPk=k!(nk){_nP_k}=k!{n \выберите k}n​Pk​=k!(kn​), отсюда следует, что

(nk)=1k!(nPk)=n!k !(n−k)!.{n \выбрать k} = \frac{1}{k!}(_nP_k)= \frac{n!}{k!(n-k)!}.(kn​)=k! 1​(n​Pk​)=k!(n−k)!n!​.

Сколькими способами можно расположить 3 шоколадных печенья и 10 малиновых чизкейков в ряд по 13 штук?

Мы можем представить ситуацию, когда у нас есть 13 ячеек, заполненных 3 шоколадными печеньями и 10 печеньями с малиновым чизкейком. Затем мы просто выбираем 3 места для печенья с шоколадной крошкой, а в остальных 10 местах даем печенье с малиновым чизкейком. Количество способов выполнить эту работу: (133)=13×12×113×2×1=286.{13\choose3}=\frac{13\times12\times11}{3\times2\times1}=286. (313​)=3×2×113×12×11​=286. □_\квадрат□​

Сколько слов из 7 согласных и 4 гласных можно составить из 7 согласных и 2 гласных?

Количество способов выбора 3 согласных из 7 и 2 гласных из 4: (73)×(42)=210.{7\choose3}\times{4\choose2} = 210. (37​)× (24​)=210. Таким образом, число групп, содержащих по 3 согласных и 2 гласных, равно 210 210 210. Так как каждая группа содержит 5 букв, которые можно расположить между собой 5!=1205!= 1205!=120 способами, искомое количество слов 210×120=25200. □210\умножить на 120 = 25200.\ _\квадрат210×120=25200. □​

Сколькими способами можно выбрать 3 самца и 2 самки из 7 самцов и 5 самок?

Количество способов выбрать 333 самца из 777: (73)=7×6×53×2×1=35.{7 \выбрать 3} = \frac{7\times 6\times 5}{3 \times 2 \times 1}=35.(37​)=3×2×17×6×5​=35. Точно так же количество способов выбрать 222 самки из 555 равно (52)=5×42×1=10.{5 \выбрать 2} = \frac{5\times 4}{2 \times 1}=10. (25​)=2×15×4​=10. Следовательно, по правилу произведения ответ равен 35×10=35035 х 10=35035×10=350 способов. □_\квадрат□​

Есть 999 детей. Сколькими способами можно разделить эти 999 детей на 2, 3 и 4?

Количество способов выбрать 222 ребенка из 999 равно (92)=9×82×1=36. {9\choose2}=\frac{9 \times 8}{2 \times 1}=36.( 29​)=2×19×8​=36. Количество способов выбрать 333 ребенка из 9−2=79-2=79−2=7 равно (73)=7×6×53×2×1=35.{7 \выбрать 3}=\frac{ 7 х 6 х 5} {3 х 2 х 1} = 35. (37​) = 3 × 2 × 17 × 6 × 5​ = 35. Наконец, количество способов выбрать 444 ребенка из 7−3=47-3=47−3=4 равно (44)=1.{4 \выбрать 4}=1.(44​)=1. Следовательно, по правилу произведения ответ равен 36×35×1=126036 х 35 х 1=126036×35×1=1260 способов. □_\квадрат□​

Есть 999 различных стульев. Сколькими способами можно сгруппировать эти стулья в 3 группы по 3?

Количество способов выбрать 333 стула из 999 равно (93)=9×8×73×2×1=84.{9\choose3}=\frac{9 \times 8 \times 7}{3 \ умножить на 2 \раз 1}=84.(39​)=3×2×19×8×7​=84. Количество способов выбрать 333 стула из 9−3=69-3=69−3=6 равно (63)=6×5×43×2×1=20.{6 \выбрать 3}=\frac{ 6 \times 5 \times 4}{3 \times 2 \times 1}=20.(36​)=3×2×16×5×4​=20. Наконец, количество способов выбрать 333 стула из 6−3=36-3=36−3=3 равно (33)=1. {3 \выбрать 3}=1.(33​)=1. Теперь, поскольку в каждой из этих трех групп одинаковое количество трех стульев и порядок трех групп не имеет значения, по правилу произведения наш ответ равен 84×20×13!=280\frac{84 \times 20 \ умножить на 1}{3 !}=2803!84×20×1​=280 способов. □_\квадрат□​

На вечеринке все пожимают друг другу руки. Было 66 рукопожатий. Сколько человек было на вечеринке?

Комбинация — это способ выбора элементов из набора, в котором порядок не имеет значения.

В общем, количество способов выбрать k k k неупорядоченных элементов из набора элементов n n n равно n!k!(n−k)! \frac{n!}{k!(n-k)!} k!(n−k)!n!​. Это биномиальный коэффициент, обозначаемый (nk) n \choose k (kn​).

Сколько упорядоченных неотрицательных целочисленных решений (a,b,c,d) (a, b, c, d) (a,b,c,d) существует для уравнения a+b+c+d=10 a + b + c + d = 10 a+b+c+d=10?

Чтобы решить эту проблему, мы используем технику под названием «звезды и полосы», популяризированную Уильямом Феллером. Мы создаем взаимное соответствие между решениями a+b+c+d=10 a + b + c + d = 10 a+b+c+d=10 и последовательностями из 13 цифр, состоящих из десяти единиц и трех нулей. Имея набор из четырех целых чисел, сумма которых равна 10, мы создаем последовательность, которая начинается с a a a единиц, затем идет 0, затем идет b b b единиц, затем идет 0, затем идет c c c единиц, затем идет 0, а затем идет d d d 1 с. И наоборот, учитывая такую ​​последовательность, мы можем установить a a a равным длине начальной строки 1 (до первого 0), установить b b b равной длине следующей строки 1 (между первым и вторым 0) , установите c c c равным длине третьей строки из единиц (между вторым и третьим 0) и установите dd d равной длине четвертой строки из единиц. Ясно, что такая процедура возвращает исходное множество, а значит, мы имеем биекцию. Теперь осталось подсчитать количество таких последовательностей. Мы выбираем 3 позиции для нулей, а остальные позиции — для единиц. Следовательно, таких последовательностей (133)=286 {13 \выберите 3}= 286 (313​)=286. □_\квадрат□​

Есть 555 рубашек разных цветов, 444 пары брюк разных цветов и 222 пары обуви разных цветов. Сколькими способами Эми и Банни можно одеть в рубашку, штаны и пару туфель?

Мы выбираем 222 рубашки из 555 для Эми и Банни, поэтому (52)2!=20.{5\выбрать2}2!=20.(25​)2!=20.
Мы выбираем для них 222 пары штанов из 444, поэтому (42)2!=12.{4\выбрать2}2!=12.(24​)2!=12.
Мы выбираем для них 222 пары обуви из 222, поэтому (22)2!=2.{2\выбрать2}2!=2.(22​)2!=2.

Следовательно, по правилу произведения ответ равен 20×12×2=48020 х 12 х 2=48020×12×2=480 способов. □_\квадрат□​

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

Количество способов разделить 5+5=105+5=105+5=10 стран на 5 групп по 2 в каждой:

(102)×(82)×(62)×(42)×(22)5!=45×28×15×6×1120=945. (1)\frac{{10\choose2} \times {8 \choose2} \times {6\choose2} \times {4\choose2} \times {2\choose2}}{5 !} =\frac{ 45 \times 28 \times 15 \times 6 \times 1}{120} =945. \qquad (1)5!(210​)×(28​)×(26​)×(24​)×(22​)​=12045×28×15×6×1​=945.(1)

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

5!=5×4×3×2×1=120.(2)5 ! = 5 х 4 х 3 х 2 х 1 = 120. \qquad (2)5!=5×4×3×2×1=120.(2)

Следовательно, взятие (1)-(2)(1)-(2)(1)-(2) дает наш ответ 945-120=825,945-120=825,945-120=825. □_\квадрат□​

Найдите количество прямоугольников на шахматной доске размером 10×1210 х 1210×12.

Примечание. Все квадраты являются прямоугольниками, но не все прямоугольники являются квадратами.

Есть две разные коробки, 10 одинаковых красных шаров, 10 одинаковых желтых шаров и 10 одинаковых синих шаров. Сколькими способами можно рассортировать 30 шаров по двум ящикам так, чтобы в каждом ящике было по 15?

Имея в виду, что два ящика различны, пусть r,yr, yr,y и bbb будут количеством красных, желтых и синих шаров в первом ящике соответственно. Тогда нам сначала нужно получить количество случаев, удовлетворяющих r+y+b=15,r+y+b=15,r+y+b=15, а затем вычесть количество случаев, когда r>10,y>10r >10, у>10r>10,у>10 или б>10.б>10.б>10.

Используя звездочки и полосы, количество случаев, удовлетворяющих r+y+b=15r+y+b=15r+y+b=15, равно (172)=136.(1){17\choose2}=136. \qquad (1)(217​)=136.(1)

Теперь следующее дает количество случаев, когда 10

  • Если r=11,r=11,r=11, то y+b=4,y+b=4,y+b=4, то есть таких случаев 5.
  • Если r=12,r=12,r=12, то y+b=3,y+b=3,y+b=3, что означает, что таких случаев 4.
  • Если r=13,r=13,r=13, то y+b=2,y+b=2,y+b=2, что означает, что таких случаев 3.
  • Если r=14,r=14,r=14, то y+b=1,y+b=1,y+b=1, что означает, что таких случаев 2.
  • Если r=15,r=15,r=15, то y+b=0,y+b=0,y+b=0, что означает 1 такой случай.

Следовательно, количество случаев, когда 10

Следовательно, взяв (1)−(2)(1)−(2)(1)−(2), мы получим ответ 136−45=91,136−45=91,136−45=91. □_\квадрат□​

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

Пусть XXX будет количеством всех возможных стратегий продаж в течение календарной недели. Какой остаток от XXX при делении на 1000?

Пусть a,b,c,d,e,f,ga, b, c, d, e, f, ga,b,c,d,e,f,g будут 7 видами пиццы. Тогда ни один из этих 7 видов не мог бы продаваться 4 или более дней в неделю, потому что каждый из остальных 6 видов продавался бы в один и тот же день в течение первых 3 дней. На самом деле, поскольку каждую неделю продается 3×7=213\x 7=213×7=21 пицца, каждый из 7 видов продается ровно 3 раза в неделю.

Теперь, без ограничения общности, количество способов выбрать 3 дня для выставления ААА на продажу равно (73).{7\выбрать 3}.(37​). Тогда число способов выставить на продажу каждый из оставшихся 6 видов за эти 3 дня равно (62)×(42)×(22).{6\выберите 2}\times {4\выберите 2}\times {2 \выберите 2} .(26​)×(24​)×(22​). Следующая таблица является одним из примеров этой операции, где aaa продается все 3 дня в течение недели, тогда как каждый из остальных 6 видов продается только один раз:

пицца

Поскольку мы закончили с a,a,a, теперь мы кладем по одному bbb в каждый из 2 из оставшихся 4 дней, количество способов сделать это равно (42). {4 \выбрать 2}.(24​) . Затем, исключая ccc, который уже продавался вместе с bbb ​​в первый день, мы поставили d,e,f,gd, e,f,gd,e,f,g в те 2 дня, где только что поставили bbb. Однако, поскольку комбинации (d,e)(d,e)(d,e) и (f,g)(f,g)(f,g) уже использовались при работе с a,a,a, число Способов поместить d,e,f,gd, e, f, gd,e,f,g в два столбца вместе с bbb ​​является (42)−2.{4 \выбрать 2}-2.(24​) −2.

Наконец, в оставшиеся два столбца помещаем по одному купону, а затем заполняем столбцы, количество способов сделать это равно 2. Следовательно, количество всех возможных стратегий продаж в течение календарной недели равно (73)×( 62)×(42)×(42)×((42)−2)×2=151200.{7\выберите 3}\times {6\выберите 2}\times {4\выберите 2}\times {4\ выберите 2}\times\left({4 \choose 2}-2\right)\times 2=151200.(37​)×(26​)×(24​)×(24​)×((24​) −2)×2=151200.

Следовательно, остаток от 151200151200151200 при делении на 1000 равен 200. □_\квадрат□​

1744\frac1{744}7441​ 7744\frac7{744}7447​ 11744\фракция{11}{744}74411​ 13744\frac{13}{744}74413​

На шахматной доске случайным образом выбираются три клетки. Найти вероятность того, что они лежат на любой диагонали .


Примечание: Линия, соединяющая три квадрата (1,1),(2,3),(3,5)(1,1), (2,3), (3,5)(1, 1),(2,3),(3,5) не образует диагонали.

5042 5342 7072 7092 15912 31824 31876

ААА и ВВВ — единственные кандидаты, участвующие в выборах. Они набрали 111111 и 777 голосов соответственно. Сколькими способами это может произойти, если известно, что ААА опережала ВВВ на протяжении всего процесса подсчета голосов?

Основная статья: Комбинации с повторением

Вы хотите раздать 7 неразличимых конфет 4 детям. Если каждый ребенок должен получить хотя бы одну конфету, сколькими способами вы можете это сделать?

Сначала вы даете по одной конфете каждому из 4 детей, чтобы выполнить требование, согласно которому каждый ребенок должен получить хотя бы одну конфету. Затем у вас остается 3 конфеты, которые нужно раздать 4 детям, что эквивалентно задаче размещения k=3k=3k=3 неразличимых шаров в n=4n=4n=4 помеченных урн, что известно как 9.0006 шаров и урн или звезд и баров. Таким образом, наш ответ: (n+k−1k)=(n+k−1n−1)=(3+4−13)=20. □\binom{n+k-1}{k} =\binom{n+k-1}{n-1}=\binom{3+4-1}{3}=20. \ _\квадрат (kn+k−1​)=(n−1n+k−1​)=(33+4−1​)=20. □​

Уинстон должен выбрать 4 класса для своего последнего семестра в школе. Он должен пройти как минимум 1 урок естественных наук и хотя бы 1 урок искусства. Если в его школе есть 4 (отдельных) урока естественных наук, 3 (отдельных) урока искусства и 3 других (отличных) класса, сколько у него есть различных вариантов выбора уроков?


Детали и предположения:

  • Он не может дважды посещать один и тот же класс.

Сколько шестизначных целых чисел содержат ровно четыре разные цифры?

Попробуйте больше задач по комбинаторике.

Пусть x+y+z=m,x+y+z=m,x+y+z=m, где x,y,zx, y, zx,y,z — целые числа такие, что x≥1,y≥ 2,z≥3.x\ge 1, y\ge 2, z\ge 3.x≥1,y≥2,z≥3. Если количество упорядоченных троек (x,y,z)(x, y, z)(x,y,z), удовлетворяющих уравнению, равно 21,21,21, что такое m?m?m?

Пусть x-1=a,y-2=b,z-3=c,x-1=a, y-2=b, z-3=c,x-1=a,y-2=b ,z−3=c, где a,b,ca, b, ca,b,c неотрицательны, так как x≥1,y≥2,z≥3,x\ge 1, y\ge 2, z\ ge 3,x≥1,y≥2,z≥3, тогда

x+y+z=m(a+1)+(b+2)+(c+3)=ma+b+c=m−6.(1)\begin{выровнено} х+у+г&=м\\ (а+1)+(б+2)+(с+3)&=м\\ а+b+с&=m-6. \qquad (1) \end{align}x+y+z(a+1)+(b+2)+(c+3)a+b+c​=m=m=m−6.(1)​

Поскольку количество упорядоченных троек неотрицательных целых чисел (a,b,c)(a, b, c)(a,b,c), удовлетворяющих (1)(1)(1), равно 21,21,21, используя техника 92-9м-22&=0\\ (м+2)(м-11)&=0\\ m&=11 \end{выровнено}(m−63+(m−6)−1​)=(m−6m−4​)=(2m−4​)2!(m−4)(m−5)​m2− 9m+20m2−9m−22(m+2)(m−11)m​=21=21=42=0=0=11​

, потому что m>0. □m>0.\ _\squarem>0. □​

136 560 816 1140

Сколькими способами можно выбрать 333 числа из первых 202020 целых положительных чисел так, чтобы никакие 2 из выбранных чисел не были последовательными?

На приведенном выше рисунке с 9 квадратами сколькими способами можно выбрать два квадрата, которые не поделиться преимуществом?

Эта задача является частью набора Countings.

No related posts.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *