как узнать количество комбинаций чисел

Формулы комбинаторики.

Перестановки. Подсчет числа перестановок.

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

Например, сначала оставляем на первом месте бордовый том, рядом с ним может находиться зеленый или оранжевый. Если на втором месте стоит зеленый том, то далее могут стоять либо оранжевый и синий, либо синий и оранжевый. Если на втором месте стоит оранжевый том, то далее могут стоять либо зеленый и синий, либо синий и зеленый. Итого, получается 4 возможных варианта.

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

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

В результате у нас получилось всего 12 вариантов расстановки 4-ёх книг на полке с заданным ограничением. Много это или мало? Если потратить по одной минуте на перемещение книг и обсуждение получившегося варианта с заказчиком, то, пожалуй, нормально. 12 минут можно и книжки подвигать, и поговорить. (Попробуйте посчитать, сколько получилось бы перестановок 4-ёх книг без всяких ограничений?)

А теперь представьте себе, что у заказчика книг больше, чем 4. Ну хотя бы 5. Понятно, что и вариантов расстановки будет больше, и реально переставлять их с места на место дольше, и запутаться и начать повторяться легче. Значит бросаться в бой без подготовки уже не стоит. Нужно сначала запланировать варианты на бумаге. Для краткости занумеруем наши цветные тома и будем переставлять на бумаге их номера. Чтобы меньше ошибаться, сначала выпишем все варианты перестановки, а затем вычеркнем те из них, которые подпадают под ограничение. Итак:

У нас 5 книг (или 5 цифр), каждая из которых может стоять на первом месте. Сделаем для каждого из этих 5-ти случаев свою табличку. На втором месте может стоять любая из оставшихся 4-ёх цифр, для каждой из них зарезервируем столбик в табличке.

В каждом столбике помещаем пары строк, в которых на третьем месте стоит одна из оставшихся 3-ёх цифр, а две последние цифры меняются местами. Таким образом мы аккуратно выписываем все варианты перестановок. Подсчитаем их общее число.

5(таблиц)×4(столбика)×3(пары строк)×2(строки)×1(вариант) = 120 (вариантов).

И, наконец, вычеркнем из всех таблиц варианты, содержащие «12» или «21». Таких оказалось по 6 в первой и второй табличках и по 12 в оставшихся 3-ёх, всего 48 вариантов, не удовлетворяющих ограничению. Значит заказчику надо показать 120 − 48 = 72 варианта расположения 5-ти книг. На это уйдет больше часа, даже если тратить на обсуждение каждого варианта только минуту.

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

Считать варианты перестановок приходится не только для книг. Это может потребоваться для большого числа любых объектов практически в любой сфере деятельности. Значит, как дизайнерам, так и людям других профессий может понадобиться помощник, а еще лучше инструмент для облегчения подготовительного этапа, анализа возможных результатов и сокращения объема непроизводительного труда. Такие инструменты создавали и создают ученые-математики, а затем отдают их обществу в виде готовых формул. Математики не обошли своим вниманием вопросы, связанные с перестановками, а также с размещениями и сочетаниями разных элементов. Соответствующим формулам уже не один век. Эти формулы очень просты, подрастающей части общества их «вручают» на уроках школьной математики. Поэтому всё, что было написано выше, это по-существу, «изобретение велосипеда», к которому пришлось прибегнуть из-за предположения, что дизайнеру интерьеров никогда не понадобится математика. Что ж, откажемся от этого предположения. Повторим математические понятия, а затем снова вернемся к задаче о книжной полке.

Комбинаторикой называется область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов заданного множества. Составляя комбинации, мы фактически выбираем из этого множества различные элементы и объединяем их в группы по нашим потребностям, поэтому вместо слова «комбинации», часто используют слово «выборки» элементов.

Формула для числа перестановок.

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

Если перестановки производятся на множестве из n элементов, их число определяется по формуле
P_n = n·(n−1)·(n−2). 3·2·1 = n!

Таким образом, общее число перестановок 5-ти книг P₅ = 5! = 1·2·3·4·5 = 120, что мы и получили выше. Фактически мы выводили эту формулу для маленького примера. Теперь решим пример побольше.

Задача 1.

На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом 1-й и 2-й тома не стояли рядом?

Решение.

Это очень большое число (после двойки еще 32 цифры). Даже если затратить секунду на каждую перестановку, то потребуются миллиарды лет. Стоит ли выполнять такое требование заказчика, или лучше уметь обоснованно возразить ему и настоять на применении дополнительных ограничений?

Перестановки и теория вероятностей.

Еще чаще необходимость подсчёта числа вариантов возникает в теории вероятностей. Продолжим книжную тему следующей задачей.

Задача 2.

На книжной полке стояло 30 томов. Ребенок уронил книги с полки, а затем расставил их в случайном порядке. Какова вероятность того, что он не поставил 1-й и 2-й тома рядом?

Решение.

Замечаниe: Если непонятно, как сокращаются дроби с факториалами, то вспомните, что факториал это краткая запись произведения. Её всегда можно расписать длинно и зачеркнуть повторяющиеся множители в числителе и в знаменателе.

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

Размещения. Подсчет числа размещений.

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

На рисунке представлены только 4 варианта размещения из 60 возможных. Сравните картинки. Обратите внимание, что размещения могут отличаться друг от друга либо только порядком следования элементов, как первые две группы, либо составом элементов, как следующие.

Формула для числа размещений.

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

Число размещений из n по m обозначается A_n m и определяется по формуле
A_n m = n·(n − 1)·(n − 2)·. ·(n − m + 1) = n!/(n − m)!

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

Задача 3.

Сколькими способами можно расставить 15 томов на книжной полке, если выбирать их из имеющихся в наличии 30-ти книг?

Решение.

Определим общее число размещений из 30 элементов по 15 по формуле
A₃₀ 15 = 30·29·28·. ·(30−15+1) = 30·29·28·. ·16 = 202843204931727360000.
Ответ: 202843204931727360000.

Будете размещать реальные книги? Удачи! Посчитайте, сколько жизней потребуется, чтобы перебрать все варианты.

Задача 4.

Сколькими способами можно расставить 30 книг на двух полках, если на каждой из них помещается только по 15 томов?

Решение.

Способ I.
Представим себе, что первую полку мы заполняем так же, как в предыдущей задаче. Тогда вариантов размещения из 30-ти книг по 15 будет A₃₀ 15 = 30·29·28·. ·(30−15+1) = 30·29·28·. ·16.
И при каждом размещении книг на первой полке мы еще P₁₅ = 15! способами можем расставить книги на второй полке. Ведь для второй полки у нас осталось 15 книг на 15 мест, т.е. возможны только перестановки.
Всего способов будет A₃₀ 15 ·P₁₅, при этом произведение всех чисел от 30 до 16 еще нужно будет умножить на произведение всех чисел от 1 до 15, получится произведение всех натуральных чисел от 1 до 30, т.е. 30!
Способ II.
Теперь представим себе, что у нас была одна длинная полка на 30 мест. Мы расставили на ней все 30 книг, а затем распилили полку на две равные части, чтобы удовлетворить условию задачи. Сколько вариантов расстановки могло быть? Столько, сколько можно сделать перестановок из 30 книг, т.е. P₃₀ = 30!
Ответ: 30!.

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

Размещения и теория вероятностей.

Задача 5.

На книжной полке находится собрание сочинений одного автора в 6 томах. Книги одинакового формата расположены в произвольном порядке. Читатель, не глядя, берет 3 книги. Какова вероятность того, что он взял первые три тома?

Решение.

Сочетания. Подсчет числа сочетаний.

Формула для числа сочетаний.

В этой формуле присутствуют два делителя и в качестве знака деления использован символ «/«, который более удобен для веб-страницы. Но деление можно также обозначать двоеточием «:» или горизонтальной чертой «−−−». В последнем случае формула выглядит как обыкновенная дробь, в которой последовательное деление представлено двумя сомножителями в знаменателе . Для тех, кому более понятно представление в виде дроби, все формулы продублированы в начале и в самом конце страницы. Разбирая решения задач сравнивайте мою запись с привычной для себя.
Кроме того, все множители и делители в этой формуле представляют собой произведения последовательных натуральных чисел, поэтому дробь хорошо сокращается, если её расписать подробно. Но подробное сокращение я в задачах пропускаю, его легко проверить самостоятельно.

Понятно, что для одинаковых исходных множеств из n элементов и одинаковых объёмов выборок (по m элементов) число сочетаний должно быть меньше, чем число размещений. Ведь при подсчёте размещений для каждой выбранной группы мы еще учитываем все перестановки выбранных m элементов, а при подсчёте сочетаний перестановки не учитываем: С_n m = A_n m /P_m = n!/(n−m)!/m!

Задача 6.

Сколькими способами можно расставить 15 томов на книжной полке, если выбирать их из имеющихся в наличии внешне неразличимых 30-ти книг?

Решение.

Мы решаем эту задачу в контексте работы дизайнера интерьеров, поэтому порядок следования на полке 15-ти выбранных внешне одинаковых книг не имеет значения. Нужно определить общее число сочетаний из 30 элементов по 15 по формуле
С₃₀ 15 = 30!/(30 − 15)!/15! = 155117520.
Ответ: 155117520.

Задача 7.

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

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

Сочетания и теория вероятностей.

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

Задача 8.

На книжной полке находится собрание сочинений одного автора в 6 томах. Книги одинаково оформлены и расположены в произвольном порядке. Читатель берет наугад 3 книги. Какова вероятность того, что он взял первые три тома?

Решение.

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

Заключительные замечания.

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

Для строгого вывода всех формул (который я здесь не приводила) используются два основных правила комбинаторики:

Понятие факториал также распространяется на ноль: 0! = 1, так как считается, что пустое множество можно упорядочить единственным способом.

Заключительная задача.

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

Задача 9.

Из аквариума, в котором 6 сазанов и 4 карпа, сачком выловили 5 рыб. Какова вероятность того, что среди них окажется 2 сазана и 3 карпа?

Решение.

Ответ: 0,238.

Если вы выпускник школы и будете сдавать ЕГЭ, то после изучения этого раздела, вернитесь к заданиям по теме «Вероятность» (10 для базового и 4 для профильного уровней ЕГЭ 2021 по математике), которые можно решать с использованием элементов комбинаторики и без неё (например, на бросание монеты). Какой из возможных способов решения задачи нравится вам больше теперь?

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

Понравились материалы сайта? Узнайте, как поддержать сайт и помочь его развитию.

Внимание, ©mathematichka. Прямое копирование материалов на других сайтах запрещено. Ставьте гиперссылку.

Источник

Интересное и простое из комбинаторики. Функция Эйлера

Предисловие

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

Сколько вариантов расставить n предметов?

Способ №1

Способ №2

Факториал — количество способов расставить n предметов.
Факториал высчитывается перемножением чисел от 1 до n.
Обозначается n! (читать как факториал n).

Допустим, нам нужно узнать, сколько вариантов в расстановке 10 предметов. Умножаем: 1x2x3..x10
Получим: 10! = 3628800

Как из n предметов выбрать k предметов?

Способ №1

Допустим, вы — организатор лотереи. Из 10 участников вам нужно выбрать 2 победителя. Вы можете узнать количество способов сделать это.
Так же как и в случае с факториалом, можно посчитать вручную. Выбирать n предметов, пока не иссякнут все варианты.
Цитирую: но есть способ, который по своей простоте опережает приведенный ранее способ.

Способ №2

Число сочетаний — это количество способов из n предметов выбрать k предметов.
Обозначается так:

Высчитывается по формуле:
Итак, сколько же способов из 10 участников выбрать 2 победителя?

Числа Фибоначчи

Стоит отдать должное человеку, который «придумал» эти числа. Леонардо Пизанский. Думаю достаточно, чтобы Вы запомнили имя этого великого человека.

Приступим. Числа Фибоначчи применяются в Теории Чисел. Если сказать честно, я знаю не слишком много об этих числах.
Числа Фибоначчи — это последовательность чисел, в котором каждое последующее числовое значение равно сумме двух предыдущих. Первые два числа Фибоначии — единицы. Соответственно, 3-е число = 2.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.

Еще раз повторюсь — я знаю не слишком много об этих числах. Если я еще не слишком вас утомил/отпугнул/надоел — идем дальше.

Функция Эйлера

В этом пункте я попытаюсь выложить все, что знаю об этом. Я потратил достаточно времени и сил, чтобы изучить эту, между прочим абсолютно простою вещь.

По правде говоря, я очень горжусь тем, что такой человек как Леонард Эйлер жил в России.

К делу. Есть три разных способа посчитать функцию Эйлера. На выбор одного из способов влияют некоторые факторы.
Функция Эйлера обозначается (читать как фи от n).

Способ №1

Увы, но этот способ применять следует для высчитывания функции простых чисел.
Например, функция Эйлера для 3 =

Способ №2

Данный способ следует применять если число можно представить как степень какого-то числа. Например, 9 — это
Посчитаем функцию для 9.


Получаем:

Способ №3

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




Таким образом получаем:

Источник

Комбинаторика

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

Правила в комбинаторике

Правило суммы: если есть взаимоисключающие друг друга действия A и B, которые можно выполнить способами m и n соответственно, то выполнить любое из этих действий можно m + n способами.

Правило произведения: если есть последовательность действий k, и первое действие его можно выполнить n₁ способом, второе n₂ и далее до n_k, то все действия этой последовательности можно выполнить n₁ · n₂ · n_k способами.

Элементы комбинаторики

Перестановки – конечное множество, в котором указан порядок его элементов. Количество перестановок вычисляется по формуле: P_n = n!

Калькулятор разложения бинома Ньютона с использованием треугольника Паскаля.

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

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

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

Источник