Сколькими способами можно соединить n точек

комбинаторика — Сколько способов выбрать точки?

Сколько существует способов выбора k различных точек из n точек, расположенных на окружности так, чтобы никакие две выбранные точки не являлись соседними?

задан 20 Сен ’16 0:15

Asifer
157 ● 13
66&#037 принятых

@Asifer если я правильно понимаю, то на окружности континуум точек, взяв две точки на ней, никогда не получится так, что они соседи.

Я знаю ответ пока только для частных случаев. Скажем, при k=3 будет n(n-4)(n-5)/6 при n>=6. Для общего случая также надо подумать, что там получится.

Тоже хорошая задача, кстати.

@abc: при k=1 должно получаться n. При k=2 ответом будет n(n-3)/2. По Вашей формуле вроде как получаются другие значения.

@falcao да ошибся с форматированием, вот так верно: $%C_^+C_^$%

1 ответ

Рассмотрим линейный вариант задачи, когда имеются числа от 1 до n, и из них выбираются k, среди которых нет соседей (такая задача интересна сама по себе). Обозначим ответ для неё в виде f(n,k). Ясно, что f(n,0)=1 и f(n,1)=n. При $%k\ge2$% найдём рекуррентные формулы.

Если число 1 взято, то 2 не берём, и из оставшихся чисел берутся k-1. Если 1 не взято, то k чисел берутся из следующих n-1. Тем самым, $%f(n,k)=f(n-2,k-1)+f(n-1,k)$%. Индукцией по k легко проверяется, что $%f(n,k)=C_^k$%.

Зная ответ, легко дать чисто комбинаторное доказательство, без вычислений. Пусть мы выбрали k чисел из n без соседей. Можно представить себе это так, что мы в клетчатой полоске длиной n закрасили k клеток. Справа от каждой закрашенной место пустует. Сотрём эти места, и все клетки вплотную сдвинем. Получится n-k+1 место, среди которых k мест выделено. Таких конфигураций в точности $%C_^k$%. Ясно, что прежняя ситуация однозначно восстанавливается: вставляем по одной пустой клетке после каждой отмеченной, не считая крайней справа.

Теперь циклический вариант, когда числа 1, 2, . , n стоят по кругу. Если 1 взято, то 2 и n брать нельзя, и в оставшейся части выделяем k-1 число. Если 1 не взято, то берём k чисел из n-1. Итого $%f(n-3,k-1)+f(n-1,k)=C_^+C_^k$%. Данная величина может также быть записана как $%\fracC_^k$%, а также в виде $%\frackC_^$%.

Источник

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

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

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

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

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

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

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

.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

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

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

.

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

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

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Источник

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

Комбинаторика онлайн калькуляторы

Элементы комбинаторики перестановки, размещения, сочетания	Число перестановок находит все варианты перестановки
Обратная перестановка онлайн калькулятор	Количество инверсий в перестановке это количество пар элементов
Циклическая перестановка перевод цикла в стандарт	Число сочетаний вычисление числа сочетаний из n по k элементов
Порядок перестановки стандартной и циклической	Число сочетаний с повторениями онлайн калькулятор для нахождения сочетаний
Число размещений нахождение количества размещений	Разложение Бинома Ньютона калькулятор разложения степени
Комбинаторные уравнения решение комбинаторных уравнений

Смотрите также

Сколько существует трёхзначных чисел, которые делятся на 5?

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

составьте всевозможные перестановки из элементов множества А, если а=,иллюстрируйте решение, используя понятие регулярного дерева

У Васи есть кубики трех цветов. Он строит из них башню, ставя каждый следующий кубик на предыдущий. Запрещено использовать более 7 кубиков каждого из цветов. Вася заканчивает строить башню, как только в ней окажется по 7 кубиков каких-то двух цветов. Сколько различных башен может построить Вася?

Сколько существует четырехзначных чисел, в запись которых входит ровно одна цифра 3?

Рассмотрим четыре случая:
1) Когда число начинается на 3.
Каждый разряд (сотен, десятков и единиц) можно выбрать девятью способами.
9 × 9 × 9 = 729 чисел.

2) Когда цифра 3 в разряде сотен.
Первую цифру можем выбрать восемью способами, а третью и четвертую – девятью способами, получаем.
8 × 9 × 9 = 648 чисел.

3) Когда цифра 3 в разряде десяток.
8 × 9 × 9 = 648 чисел.

4) Когда цифра 3 в разряде единиц.
8 × 9 × 9 = 648 чисел.

Общее количество: 729 + 648 + 648 + 648 = 2673 чисел.

Источник

Тема 1. Элементы комбинаторики. Теоретические сведения

При выборе M элементов из N различных элементов говорят, что они образуют Соединение из N элементов по M. Различают три вида соединений элементов:

1. Размещениями называются соединения, которые отличаются друг от друга составом элементов или их порядком, и каждое из которых содержит M элементов, взятых из N различных элементов.

Например, выпишем все размещения элементов a, b, c, d по два: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

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

Например, выпишем все перестановки из элементов a, b, c: abc, acb, bac, bca, cab, cba.

3. Сочетаниями из N элементов по M называются соединения, отличающиеся друг от друга, по крайней мере, одним элементом, каждое из которых содержит M элементов, взятых из N различных элементов.

Например, выпишем все сочетания из элементов a, b, c, d, e по три: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

Задача о числе размещений: Сколькими способами можно выбрать и разместить по M различным местам N разных предметов? Количество таких способов обозначается и читается: «Число размещений из N по M».

, (по определению)

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

Решение. Это задача о выборе и размещении по пяти разным местам пяти из десяти различных цифр. Поэтому число указанных телефонных номеров равно .

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

Решение. Поскольку нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр. Следовательно, указанных чисел имеется .

Задача о числе перестановок: Сколькими способами можно переставить N разных предметов, расположенных на N разных местах? Количество таких способов обозначается и читается: «Число перестановок из N».

, (по определению)

Пример 1. Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7, 9, если в каждом из этих чисел ни одна цифра не повторяется?

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

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

Решение. Эта задача о числе перестановок семи разных книг . Следовательно, имеется 5040 способов осуществить расстановку книг.

Задача о числе сочетаний: Сколькими способами можно выбрать M из N разных предметов? Количество таких способов обозначается и читается: «Число сочетаний из N по M».

; ;.

Пример 1. Сколькими способами читатель может выбрать две книжки из пяти имеющихся?

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

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

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

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

Если некоторый предмет можно выбран из совокупности предметов способами и после каждого такого выбора предмет может быть выбран способами, то пара объектов (,) в указанном порядке может быть выбрана способами. Правило распространяется на совокупность .

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

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

Пример 2. Сколько существует делителей числа 210?

Решение. Разложим данное число на простые множители: . Число делителей, составленных из произведения двух простых множителей, равно (это числа 6, 10, 14, 15, 21, 35); число делителей, составленных из произведения трех простых множителей, равно (это числа 30, 42, 70, 105); число простых делителей равно четырем (это числа 2, 3, 5, 7). Кроме того, делителями являются число 1 и число 210. Итак, согласно правилу сложения, число всех делителей равно .

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

Размещения с повторениями. Например, выпишем размещения по три из элементов 4 и 5 с повторениями: 444, 445, 454, 544, 555, 554, 545, 455.

Задача о числе размещений с повторениями: Сколькими способами можно разместить по M различным местам любые M предметов, выбранных из N различных предметов с повторениями каждого из них любое число раз, но не более M?

.

Пример 1. Каждый телефонный номер состоит из 5 цифр. Сколько всего телефонных номеров, содержащих только цифры 2, 3, 5 и 7?

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

Пример 2. Буквы азбуки Морзе состоят из символов – точка и тире. Сколько букв получим, если потребуем, чтобы каждая буква состояла не более чем из пяти указанных символов?

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

Перестановки с повторениями – перестановки из N предметов, в каждую из которых входят одинаковых предметов одного типа, одинаковых предметов другого типа и т. д. . Например, выпишем перестановки с повторениями цифр 4 и 5, каждая из которых взята по два раза: 4455, 5544, 4545, 5454, 4554, 5445.

Задача о числе перестановок с повторениями: Сколькими способами можно переставить N предметов K различных типов каждого типа соответственно одинаковых предметов, расположенных на n разных местах?

.

Пример 1. Сколькими способами можно расположить в ряд 2 зеленые и 4 красные лампочки?

Решение. способами.

Пример 2. Сколькими способами можно переставить буквы в слове какао, чтобы получались всевозможные различные наборы букв?

Решение. способами.

Сочетания с повторениями. Например, выпишем все сочетания из трех цифр 3, 4,5 по два с повторениями: 33, 34 (43), 35 (53), 44, 45 (54), 55.

Задача о числе сочетаний с повторениями: Если имеется по M одинаковых предметов каждого из N различных типов, то сколькими способами можно выбрать M из этих M×N предметов?

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

Решение. способов.

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

Решение. способов.

Источник