Сколькими способами можно составит ожерелье

Содержание

Задача об ожерельях
Содержание
Алгоритм решения задачи про ожерелья [ править ]
Алгоритм решения задачи про ожерелья с отражениями [ править ]
Сколькими способами из 7 бусенок разных цветов можно составить ожерелье с застёжкой?Объясните почему
Ответ или решение 1
22. Варианты самостоятельных работ

Задача об ожерельях

Задача:

Требуется посчитать количество ожерелий из [math]n[/math] бусинок, каждая из которых может быть покрашена в один из [math] k [/math] цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).

Решение этой задачи опирается на лемму Бёрнсайда и теорему Пойа.

Содержание

Алгоритм решения задачи про ожерелья [ править ]

Пусть нам даны бусинки [math]k[/math] различных цветов, а ожерелье должно состоять из [math]n[/math] бусинок.

Для решения воспользуемся формулой из теоремы Пойа.

По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом. Очевидно, что для каждой перестановки длины [math]n[/math] существует ровно [math]n — 1[/math] инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе [math]n[/math] , теперь найдем [math]P(i)[/math] . Заметим, что в [math]i[/math] -ой перестановке на [math]l[/math] -ой позиции стоит элемент [math](i + l)\bmod n[/math] . Также, заметим, что элемент [math]a[/math] переходит в элемент [math]a + in[/math] , где [math]i = 1, 2, \ldots k[/math] . Из этого следует, что длина цикла для [math]i[/math] -ой перестановки равна [math] \dfrac<\mathrm(n, i)> = \dfrac<\mathrm(i,n)>[/math] , где [math]\mathrm(i, n)[/math] — НОД [math](i, n)[/math] , [math]\mathrm(i, n)[/math] — НОК [math](i, n)[/math] . Откуда следует что:

где [math]|C|[/math] — кол-во различных ожерелий,которые можно составить из [math]n[/math] бусинок [math]k[/math] различных цветов.

Если раскраски ожерелья одинаковые, то они принадлежат одной орбите, т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их [math]n[/math] штук. Тогда, по лемме Бёрнсайда, число орбит равняется [math]\dfrac

=\operatorname(n,i)[/math] , где [math]p[/math] минимальное число такое, что [math]ip[/math] делится на [math]n[/math] , и число их раскрасок [math]N_i=k^<\operatorname(n,i)>[/math] . Сумма же инвариантных раскрасок для всех поворотов: [math]S=\sum\limits_^N_i=\sum\limits_^k^<\operatorname(n,i)>[/math] . В последней сумме [math]\varphi(n)[/math] слагаемых [math](\varphi(n)[/math] — функция Эйлера [math])[/math] , для которых [math]\operatorname(n,i)=1[/math] . Если же [math]\operatorname(n,i)=q[/math] , то [math]\operatorname\left(\dfrac,\dfrac\right)=1[/math] . Чтобы определить количество таких [math]i[/math] , меньших [math]n[/math] , нужно перебрать числа вида [math]i=lq,\,0\leqslant l\leqslant \dfrac[/math] и проверять их на условие [math]1=\operatorname\left(\dfrac,\dfrac\right)=\operatorname\left(\dfrac,l\right)[/math] . Таких чисел, очевидно, [math]\varphi\left(\dfrac\right)[/math] (по определению [math]\varphi(n)[/math] ). Поэтому сумму можно заменить: [math]S=\sum\limits_^k^<\operatorname(n,i)>=\sum\limits_\varphi\left(\dfrac\right)k^q[/math] .

Тогда [math]|C| =[/math] [math] \dfrac <1>[/math] [math]\sum\limits_\varphi\left(\dfrac\right)k^q[/math] .

Алгоритм решения задачи про ожерелья с отражениями [ править ]

Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets [1] . Будем пользоваться леммой Бёрнсайда. Разберём два случая.

Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.

Поворот и отражение — отражение.

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

Отражение и поворот — отражение.

Отражение и отражение — поворот.

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

Пусть число бусинок нечётное, тогда мы имеем [math]n[/math] осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет [math]k^<\frac<2>>[/math] . Операций в группе будет в два раза больше, чем было: [math]2n[/math] ( [math]n[/math] сдвигов и [math]n[/math] отражений).

По Лемме Бёрнсайда: [math] |B| = [/math] [math]\dfrac <1><|G|>[/math] [math]\sum\limits_I(k)[/math]

[math] |G| = 2n[/math] . Первые [math]n[/math] операций — повороты, и сумма количества их неподвижных точек, делённая на [math]2n[/math] , принимает значение [math]\dfrac <|C|><2>[/math] , где [math]|C|[/math] — количество ожерелий из [math]n[/math] бусинок [math]k[/math] различных цветов без отражений (задача выше) т.к. деление в задаче без отражений происходило на [math]n[/math] , а здесь на [math]2n[/math] . Следующие [math]n[/math] операций — отражения. У каждой такой операции [math]k^<\frac<2>>[/math] неподвижных точек. Поэтому сумма получается [math]k^<\frac<2>>n[/math] .

Разберём теперь чётный случай. Тут мы имеем [math]\frac<2>[/math] осей, проходящих через пустоты между бусинками (ось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться). В таких вот случаях можно выбрать по [math]\frac<2>[/math] бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет [math]k^<\frac<2>>[/math] . Ещё у нас есть [math]\frac<2>[/math] осей, проходящих через бусинки. В данных случаях мы можем выбрать по [math]\frac <2>+ 1[/math] бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет [math]k^<\frac <2>+ 1>[/math] неподвижных точек. Операций также [math]2n[/math] .

Читайте также: Способ принятия экономических решений командной экономики
Источник

Сколькими способами из 7 бусенок разных цветов можно составить ожерелье с застёжкой?Объясните почему

Ответ или решение 1

Бусинок всего 7, они разных цветов и использовать их можно в каждой комбинации только однократно. Если бусы состоят из 7 бусинок, то мест для бусин 7 и при выборе каждой следующей бусины, их количество сокращается. Следовательно:

На 1-м месте возможны все 7 бусин;

На 2-м месте возможны 6 бусин из 6-ти оставшихся (7-ю мы уже использовали);

На 3-м месте возможны 5 бусин;

И т.д., пока бусины не закончатся, на последнем месте выбор будет только из 1 бусины.

Количество комбинаций определяется произведением количества выборов бусин на каждом месте:

7 * 6 * 5 * 4 * 3 * 2 * 1 = 7! = 5 040.

Ответ: для бус из 7 бусин количество комбинаций 5 040.

Но если бусин в комбинациях может быть меньше, чем 7, то есть бусы могут состоять из 7, 6, 5, 4, 3, 2 или 1 бусинок, то количество комбинаций определяется сложением всех возможных комбинаций для каждого набора бус (для 7, для 6 и т.д.):

Для бус из 7 бусин количество комбинаций посчитано:

Для бус из 6-ти бусин количество комбинаций будет такое же, так как мест 6, на 1-м месте возможны 7 бусин, на 2-м 6 бусин, . на последнем 6-м месте будет выбор из 2-х бусин:

7 * 6 * 5 * 4 * 3 * 2 = 5 040.

Здесь уместно пользоваться формулой числа размещений без повторов:

А 6 ₇ = 7! / (7 – 6)! = 7! / 1! = 5 040.

Тогда для 5-ти бусин (на 1-м месте 7 бусин, на 5-м месте 3 бусины) расчет такой:

А 5 ₇ = 7! / (7 – 5)! = 7! / 2! = 2 520.

А 4 ₇ = 7! / (7 – 4)! = 7! / 3! = 840.

А 3 ₇ = 7! / (7 – 3)! = 7! / 4! = 210.

А 2 ₇ = 7! / (7 – 2)! = 7! / 5! = 42.

Для 1 бусины комбинаций всего 7.

Общее число комбинаций при меняющемся числе бусин на бусах:

5040 + 5040 + 2520 + 840 + 210 + 42 + 7 = 13699.

Источник

22. Варианты самостоятельных работ

1. Решить уравнение

2. Найти шестой член разложения .

Ответ: .

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

Ответ: .

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

Ответ: .

5. Сколько делителей у числа 105?

Ответ: Разложим число 105 на простые множители . Тогда , или по формуле (7.3) получаем .

6. На вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 пары на танец?

Ответ: .

7. Сколько ожерелий можно составить из 7 бусинок различных размеров (надо использовать все бусинки)?

Ответ: Т. к. ожерелье остается неизменным при циклических перестановках бусинок и при переворачивании, то можно получить 7!/14=360 видов ожерелий.

8. В первой урне находятся 4 белых и 3 черных шара, во второй – 3 белых и 5 черных шаров. Из каждой урны случайным образом вынули по одному шару. Найти вероятность того, что все шары будут белые.

Ответ: .

9. 10 вариантов контрольной работы распределены среди 6 студентов. Найти вероятность того, что варианты с номерами 1 и 2 не будут использованы.

Ответ: .

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

Ответ: .

11. Студент разыскивает нужную ему формулу в трех справочниках. Вероятности того, что формула содержится в первом, втором и третьем справочнике соответственно равны 0,6, 0,8 и 0,9. Найти вероятность того, что формула содержится только в двух справочниках.

1. Решить уравнение .

2. В разложении вычислить член, не содержащий x.

Ответ: .

3. На плоскости проведены n прямых линий, из которых никакие две не являются параллельными и никакие три не пересекаются в одной точке. Сколько точек пересечения имеют эти прямые?

Ответ: .

4. Сколькими способами можно разложить 12 различных марок между тремя мальчиками, если один берёт 6 марок, а остальные – по 3 марки?

Ответ: .

5. Сколько делителей у числа 360?

Ответ: Поскольку , то в соответствие с формулой (7.3) получаем (3+1)(2+1)(1+1)=24 делителей.

6. В избушке на курьих ножках собрались Баба-Яга, Кощей и Леший. У Бабы-Яги есть 4 чашечки, 5 блюдец и 6 чайных ложечки (все чашки, блюдца и ложечки отличаются друг от друга). Сколькими способами она может накрыть стол для чаепития (каждый получает одну чашку, одно блюдце и одну ложечку)?

Ответ: .

7. Шесть девушек водят хоровод. Сколькими способами они могут организовать хоровод?

Ответ: Т. к. хоровод остается неизменным при циклических перестановках девушек, то можно получить 6!/6=120 способов.

8. В урне находятся 5 белых и 3 черных шаров, из которой случайно по порядку с возвращением вынимаются 4 шара. Какова вероятность того, что первые два шара будут белые, а последние два черные.

Читайте также: Как называется способ дробления изолецитальных яйцеклеток
Ответ: .

9. Студент пришел на экзамен, зная лишь 24 вопроса из 32 вопросов программы. Экзаменатор задал студенту 3 вопроса. Найти вероятность того, что студент ответ на все вопросы?

Ответ: .

10. Случайным образом выписаны 3 цифры. Найти вероятность того, все цифры различные.

Ответ: .

11. При включении зажигания двигатель начинает работать с вероятностью 0,9. Найти вероятность того, что для запуска двигателя потребуется включить зажигание не более двух раз.

1. Решить уравнение .

2. Раскрыть скобки в выражении .

Ответ: .

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

Ответ: .

4. На пять сотрудников университета выделены три путёвки на один курорт. Сколькими способами их можно распределить, если: а) все путёвки в различные санатории; б) все путёвки в один санаторий.

Ответ: а) , б) .

5. Сколькими способами можно выбрать из полной колоды карт, содержащей 52 карты, по одной карте каждой масти? А ели среди вынутых карт нет ни одной пары одинаковых, т. е. двух королей, двух десяток и т. д.?

Ответ: Получаем размещения с повторениями из 13 карт по 4. Всего . Если среди карт не должно быть пар, то имеем размещения без повторений; их число .

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

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

7. Из 12 девушек и 10 юношей выбирают команду в составе 5 человек. Сколькими способами можно выбрать эту команду так, чтобы в неё вошло не более 3 юношей?

Ответ: .

8. Автобус должен сделать 8 остановок, в котором едут 5 пассажиров. Какова вероятность, что на каждой остановке выйдет не более одного пассажира, если предположить, что каждый пассажир имеет одинаковую вероятность выйти на любой остановке?

Ответ: .

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

Ответ: .

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

Ответ: .

11. Вероятность для данного спортсмена улучшить свой предыдущий результат с одной попытки равна 0,6. Определить вероятность того, что на соревнованиях спортсмен улучшит свой результат, если разрешается делать две попытки.

1. Решить уравнение .

2. Найти член разложения , содержащий x3 .

Ответ: .

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

Ответ: .

4. Из семи гвоздик и пяти тюльпанов надо составить букет, состоящий из трёх гвоздик и двух тюльпанов. Сколькими способами можно это сделать?

Ответ: .

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

Ответ: .

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

Ответ: .

7. В первенстве края по футболу участвуют 11 команд. Сколько существует различных способов распределения мест в таблице розыгрыша, если на первое место могут претендовать только 4 определенные команды?

Ответ: .

8. 8 вариантов контрольной работы случайным образом распределены среди 6 студентов. Найти вероятность того, что варианты с номерами 7 и 8 не будут использованы?

Ответ: .

9. В первой урне находятся 5 оранжевых и 4 фиолетовых шара, во второй – 3 оранжевых и 7 фиолетовых шара. Из каждой урны случайным образом вынули по три шара. Найти вероятность того, что все шары будут одного цвета.

Ответ: .

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

Решение: В данной задаче порядок размещения рекламы неважен. Следовательно, в данной задаче мы имеем дело с сочетаниями. Общее число размещений рекламы в журнале . Если реклама будет размещена на страницах, идущих одна за другой, то эти страницы можно считать за одну. Тогда число страниц будет равно 18, следовательно, и число благоприятствующих исходов будет равно m=18. Таким образом, .

11. В ОТК поступают 4 детали. Вероятность того, что деталь бракованная равна 0,1. Проверка производится последовательно до обнаружения бракованной детали. Найти вероятность того, что будут проверены все 4 детали.

1. Уравнение .

Ответ: .

2. Найти показатель степени бинома , если его четвёртый член не зависит от a.

Ответ: .

3. На складе имеются 7 ящиков с различными фруктами и 5 ящика с различными овощами. Сколькими способами можно каждой из трёх овощных палаток выдать по одному ящику с фруктами и овощами?

Ответ: .

4. Сколькими способами 6 одинаковых монет могут распределить между собой Буратино, лиса Алиса и кот Базилио?

Ответ: .

5. В команду должны быть отобраны 4 спортсмена из имеющихся 10. Сколькими способами это можно сделать, если два определенных спортсмена должны войти в команду?

Читайте также: Способ замены плоскостей проекций презентация
Ответ: .

6. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях будет ровно один туз?

Ответ: .

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

Ответ:

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

Ответ: .

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

Ответ: .

10. 10 вариантов контрольной работы распределяется среди случайным образом среди 10 студентов, сидящих в один ряд. Найти вероятность того, что варианты с номерами 1 и 2 достанутся рядом сидящим студентам.

Ответ: .

11. Два охотника одновременно и независимо друг от друга стреляют по зайцу. Найти вероятность того, что попадёт только один из охотников, если вероятность попадания для первого охотника равна 0,8, а для второго – 0,7.

Ответ: .

1. Уравнение .

Ответ: .

2. Найти средний член разложения .

Ответ: .

3. В пространстве даны 7 точек, причем никакие четыре из них не лежат в одной плоскости. Сколько различных плоскостей можно провести через эти 7 точек?

Ответ: .

4. Эллочка Людоедка решила расставить семь различных книг на полке. Сколькими способами она может это сделать, если две наиболее красивые книги (по её мнению) в красном переплёте должны стоять по краям?

Ответ: .

5. В первенстве края по футболу участвуют 12 команд. Сколько существует различных способов распределения мест в таблице розыгрыша, если на первое место могут претендовать только 3 определенные команды?

Ответ: .

6. Сколькими способами декан может раздать 7 поручений 4 студентам?

Ответ: .

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

Ответ: .

8. Для проведения тестирования группу студентов, состоящую из 18 человек, случайным образом разбивают на две подгруппы из 12 и 6 человек. Какова вероятность, что две подружки, Оля и Тяня, окажутся в одной подгруппе?

Решение: В данной задаче порядок неважен, т. е. не принимается во внимание порядок отбора студентов в группу. Следовательно, в данной задаче мы имеем дело с сочетаниями. Для того чтобы разбить 18 студентов на две подгруппы достаточно выбрать, например, 12 студентов в одну подгруппу, тогда остальные образуют другую подгруппу. Таким образом, общее число разбиений студентов на две подгруппы будет равно . Для того, чтобы разбить команды на две подгруппы с указанными условиями, можно к Оле и Тане добавить либо 10 студентов из оставшихся 16 (это можно сделать способами ), либо добавить 4 студентов из 16 ( способов). Оставшиеся студенты будут образовывать другую подгруппу. Таким образом, число благоприятствующих исходов будет равно . В результате, получаем .

9. В газете из 16 страниц на каких-либо трех страницах помещают случайным образом разные объявления. Какова вероятность, что эти объявления будут размещены на страницах, идущих одна за другой?

Ответ: .

10. В одной урне 3 зелёных и 4 жёлтых шаров, в другой – 6 зелёных и 2 жёлтых шара. Из каждой урны взяли по два шара. Какова вероятность того, что все шары будут одного цвета?

Ответ: .

11. Студент знает 5 вопросов из 12. Какова вероятность того, что он получит зачет, если нужно ответить на все три задаваемых вопроса?

Ответ: .

1. Решить уравнение .

2. Найти член разложения , содержащий x–1.

Ответ: .

3. Сколько диагоналей можно провести в выпуклом восьмиугольнике?

Ответ: .

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

Ответ: .

5. Труппа состоит из 10 человек. Сколькими способами можно выбирать из неё в течение двух вечеров по 6 человек для участия в спектаклях так, чтобы эти составы не совпадали друг с другом?

Ответ: .

6. Сколькими способами Буратино, лиса Алиса и кот Базилио могут поделить между собой 5 одинаковых золотых монет и 2 разных брильянтовых ожерелья?

Ответ: .

7. Сколькими способами можно разложить 9 книг по 3 бандеролям по 3 книги в каждой (порядок бандеролей не принимать во внимание)?

Ответ: .

8. Для проведения тестирования группу студентов, состоящую из 18 человек, случайным образом разбивают на две подгруппы из 12 и 6 человек. Какова вероятность, что две подружки, Оля и Таня, окажутся в разных подгруппах?

Ответ: Решается аналогично задаче 8 предыдущего варианта .

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

Ответ: .

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

Ответ:

11. Вероятность боя стеклянной тары при погрузке на автомашины равна 0,03, а при транспортировке – 0,07. Какова вероятность боя стеклянной тары?

Ответ: .

Источник