Xreferat.com » Рефераты по математике » Связь комбинаторики с различными разделами математики

Связь комбинаторики с различными разделами математики

способа раскраски неотличимы, если один из них можно получить из другого, применяя к семиугольнику либо преобразования вращения, либо симметрии относительно осей. Будем описывать раскраски «словами» длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). Проделаем те же действия, что и в задаче 1 для применения леммы Бернсайда. Опишем разложения в произведение циклов для всех перестановок из группы G.

а) Тождественному преобразованию соответствует перестановка:

1) (1)(2)(3)(4)(5)(6)(7)

б) Поворотам на углы Связь комбинаторики с различными разделами математики соответствуют перестановки:

2) (1,2,3,4,5,6,7)

3) (1,3,5,7,2,4,6)

4) (1,4,7,3,6,2,5)

5) (1,5,2,6,3,7,4)

6) (1,6,4,2,7,5,3)

7) (1,7,6,5,4,3,2)

в) Симметриям относительно осей, соединяющих вершины семиугольника с серединами противоположных сторон, соответствуют перестановки:

8) (1) (2,7) (3,6) (4,5)

9) (2) (1,3) (7,4) (5,6)

10) (3) (2,4) (1,5) (6,7)

11) (4) (3,5) (2,6) (7,1)

12) (5) (4,6) (3,7) (2,1)

13) (6) (5,7) (4,1) (2,3)

14) (7) (1,6) (2,5) (3,4),

где 1, 2, 3, 4, 5, 6, 7 – числа, с помощью которых занумерованы вершины семиугольника.

Итак, в группе G имеется:

1 перестановка типа <1, 1, 1, 1, 1, 1, 1>,

6 перестановок типа <7>,

7 перестановок типа <1, 2, 2, 2>.

Слово неподвижно относительно перестановки Связь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математики тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке α, совпадают. Поэтому тождественная перестановка имеет 27 неподвижных точек на М, перестановки второго типа – по 2, а перестановки третьего типа – по 24. Применяя лемму Бернсайда, получаем

Связь комбинаторики с различными разделами математики(27 + 6∙2 + 7∙24) = 18.

Итак, из бусин двух цветов можно составить 18 семибусенных ожерелий.

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

Связь комбинаторики с различными разделами математикиРешение.

Грань (1' 4' 5' 8') – 1

Грань (2' 3' 6' 7') – 2

Грань (3' 4' 7' 8') – 3

Грань (1' 2' 5' 6') – 4

Грань (1' 2' 3' 4') – 5

Грань (5' 6' 7' 8') – 6


Рис. 3

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

1) (1) (2) (5, 4, 6, 3)

2) (1) (2) (4, 3) (6, 5)

3) (1) (2) (5, 3, 6, 4)

4) (3) (4) (1, 6, 2, 5)

5) (3) (4) (1, 2) (6, 5)

6) (3) (4) (5, 2, 6, 1)

7) (5) (6) (1, 3, 2, 4)

8) (5) (6) (1, 2) (3, 4)

9) (5) (6) (4, 2, 3, 1)

б) Вокруг каждой из четырёх диагоналей куба имеется по два вращения. Им соответствуют перестановки:

10) (2, 6, 3) (1, 5, 4)

11) (3, 6, 2) (4, 5, 1)

12) (6, 4, 2) (1, 5, 3)

13) (2, 4, 6) (3, 5, 1)

14) (1, 3, 6) (2, 4, 5)

15) (6, 3, 1) (5, 4, 2)

16) (1, 4, 6) (2, 3, 5)

17) (6, 4, 1) (5, 3, 2)

в) Вокруг каждой из шести осей, соединяющих середины противоположных рёбер куба, имеется одно вращение. Им соответствуют перестановки:

18) (2, 3) (1, 4) (5, 6)

19) (1, 3) (4, 2) (5, 6)

20) (1, 6) (5, 2) (3, 4)

21) (1, 5) (6, 2) (3, 4)

22) (4, 6) (3, 5) (1, 2)

23) (6, 3) (5, 4) (1, 2)

Вместе с тождественной перестановкой (1)(2)(3)(4)(5)(6) получаем 24 перестановки – все элементы группы G. Итак, в группе G вращений куба имеется:

1 перестановка типа <1, 1, 1, 1, 1, 1>,

6 перестановок типа <1, 1, 4>,

3 перестановки типа <1, 1, 2, 2>,

8 перестановок типа <3, 3>,

6 перестановок типа <2, 2, 2>.

Поэтому тождественная перестановка имеет 26 неподвижных точек на М, перестановки второго и пятого типов имеют по 23 неподвижных точек на М, перестановки третьего типа – по 24, а перестановки четвёртого типа – по 22. Тогда по лемме Бернсайда получаем Связь комбинаторики с различными разделами математики(26 + 6∙23+ 3∙24+ 8∙22 + 6∙23) = 10.

Итак, число геометрически различных способов раскраски граней куба в два цвета равно 10.

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

Решение. Переформулируем задачу так: сколькими геометрически различными способами можно раскрасить вершины правильного шестиугольника так, чтобы две были синего цвета, две – белого, две – красного? а) Вокруг центра шестиугольника имеется пять поворотов на углы Связь комбинаторики с различными разделами математики. Им соответствуют перестановки:

1) (1, 2, 3, 4, 5, 6)

2) (1, 3, 5) (2, 4, 6)

3) (1, 4) (2, 5) (3, 6)

4) (1, 5, 3) (2, 6, 4)

5) (1, 6, 5, 4, 3, 2)

б) Имеется три симметрии относительно осей, соединяющих противоположные вершины правильного шестиугольника. Им соответствуют перестановки:

6) (1) (4) (2, 6) (3, 5)

7) (2) (5) (3, 1) (4, 6)

8) (3) (6) (2, 4) (1, 5)

в) Имеется три симметрии относительно осей, соединяющих середины противоположных сторон правильного шестиугольника. Им соответствуют перестановки:

9) (1, 2) (6, 3) (5, 4)

10) (1, 6) (2, 5) (3, 4)

11) (2, 3) (1, 4) (6, 5)

Вместе с тождественной перестановкой (1) (2) (3) (4) (5) (6) получаем 12 перестановок – все элементы группы G. Итак, в группе G имеется:

1 перестановка типа <1, 1, 1, 1, 1, 1>,

2 перестановки типа <6>,

2 перестановки типа <3, 3>,

4 перестановки типа <2, 2, 2>,

3 перестановки типа <1, 1, 2, 2>.

Определим количество неподвижных точек для перестановок каждого типа. Так как количество различных цветов, в которые нужно раскрасить шестиугольник, равно трём, то минимальное количество циклов в перестановке должно быть равно трём, чтобы она имела неподвижные точки. То есть перестановки 1), 2), 4), 5) неподвижных точек не имеют. Для перестановки первого типа получим Связь комбинаторики с различными разделами математики36 = Связь комбинаторики с различными разделами математики = 90 неподвижных точек. Для каждой перестановки типа <2, 2, 2> по принципу умножения получаем по Р3 =3∙2∙1= 6 неподвижных точек. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения получим по Р3 =3∙2∙1∙1= 6 неподвижных точек. Применим лемму Бернсайда: Связь комбинаторики с различными разделами математики(1∙90+ 4∙6+ 3∙6) = 11.

Итак, 11 различных ожерелий можно составить из двух синих, двух белых, двух красных бусин.

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

Решение. Обозначим М – множество различных способов расположения трёх одинаковых мух в вершинах пятиугольника, если вершины занумерованы. Тогда |M| = Связь комбинаторики с различными разделами математики25 (3, 2)=Связь комбинаторики с различными разделами математики=10 способов расположения мух, где 2 – количество элементов множества М1 = {м, с} (где м – муха, с – свободная вершина),

3, 2 – кратности соответственно м и с.

а) Вокруг центра пятиугольника имеется четыре поворота на углы Связь комбинаторики с различными разделами математики. Им соответствуют перестановки:

1) (1, 2, 3, 4, 5)

2) (1, 3, 5, 2, 4)

3) (1, 4, 2, 5, 3)

4) (1, 5, 4, 3, 2)

б) Имеется пять симметрий относительно осей, соединяющих вершины пятиугольника с серединами противоположных сторон. Им соответствуют перестановки:

5) (1) (2, 5) (3, 4)

6) (2) (1, 3) (5, 4)

7) (3) (2, 4) (1, 5)

8) (4) (3, 5) (2, 1)

9) (5) (1, 4) (2, 3),

где 1, 2, 3, 4, 5 – числа, с помощью которых занумерованы вершины пятиугольника. Вместе с тождественной перестановкой (1)(2)(3)(4)(5) имеем 10 элементов группы G. Итак, в группе G имеется:

1 перестановка типа <1, 1, 1, 1, 1>,

4 перестановки типа <5>,

5 перестановок типа <1, 2, 2>.

Определим количество неподвижных точек для перестановок каждого типа. Чтобы перестановка имела неподвижные точки, минимальное количество циклов в перестановке должно быть равно двум, так как множество М1 состоит из двух элементов м и с. Поэтому перестановки 1) – 4) не имеют неподвижных точек. Тогда для перестановки типа <1, 1, 1, 1, 1> имеем по формуле: Связь комбинаторики с различными разделами математики25 (3, 2) = Связь комбинаторики с различными разделами математики= 10 неподвижных точек. Для каждой перестановки типа <1, 2, 2> получим по принципу умножения по Р2 =2∙1∙1= 2 неподвижные точки. По лемме Бернсайда получаем Связь комбинаторики с различными разделами математики(1∙10+ 5∙2) = 2.

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

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

Решение. Для решения этой задачи воспользуемся задачей 1. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по формуле Связь комбинаторики с различными разделами математикиnk (k1, k2, …, kn) = Связь комбинаторики с различными разделами математики получим |M| = Связь комбинаторики с различными разделами математики28 (4,4) = Связь комбинаторики с различными разделами математики= 70 по-разному раскрашенных кубов. Так как нам нужно раскрасить вершины в два цвета (4 - в красный, 4 - в синий), то минимальное количество циклов в перестановке должно быть равно двум. Поэтому все перестановки 1) – 24) (задача 1) имеют неподвижные точки. В результате в группе G имеется:

1 перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>,

6 перестановок типа <4, 4>,

9 перестановок типа <2, 2, 2, 2>,

8 перестановок типа <1, 1, 3, 3>.

Тогда перестановка типа <1, 1, 1, 1, 1, 1, 1, 1> имеет Связь комбинаторики с различными разделами математики28 (4,4) = Связь комбинаторики с различными разделами математики= 70 неподвижных точек. Каждая перестановка типа <4, 4> имеет (по принципу умножения Р2 =2∙1= 2 неподвижные точки. Для каждой перестановки типа <2, 2, 2, 2> имеется Связь комбинаторики с различными разделами математики24 (2, 2) = Связь комбинаторики с различными разделами математики= 6 неподвижных точек. Каждая перестановка типа <1, 1, 3, 3> имеет (по принципу умножения) Р2 =2∙1∙2∙1= 4 неподвижные точки. По лемме Бернсайда получаем Связь комбинаторики с различными разделами математики(1∙70+ 6∙2 + 9∙6 + 8∙4) = 7.

Итак, семью способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета было поровну.

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

Решение. Для решения этой задачи воспользуемся задачей 3. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по принципу умножения: первую грань можно раскрасить 4 способами, вторую – тремя, третью – двумя, четвёртую – одним способом, пятую – четырьмя, шестую – четырьмя способами. Получим |M| = 4∙3∙2∙1∙4∙4 = 384. Найдём геометрически различные способы раскраски. Для этого используем описанные в задаче 3 разложения в произведение циклов всех перестановок из группы G вращений куба. Так как в раскраске куба должны присутствовать четыре разных цвета, то минимальное количество циклов в перестановке должно быть равно четырём. Поэтому перестановки 1), 3), 4), 6), 7), 9) – 23) в задаче 3 неподвижных точек не имеют. Таким образом, неподвижные точки имеют 3 перестановки типа <1, 1, 2, 2> и 1 перестановку типа <1, 1, 1, 1, 1, 1>. Определим количество неподвижных точек для перестановок каждого типа. Для перестановки типа <1, 1, 1, 1, 1, 1> имеем по принципу умножения Р4 = 4∙3∙2∙1∙4∙4 = 384 неподвижные точки. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения имеется Р4 = 4∙3∙2∙1 = 24 неподвижные точки. По лемме Бернсайда получаем Связь комбинаторики с различными разделами математики(1∙384+3∙24) = 19.

Итак, существует 19 различных способов раскраски граней куба в 4 цвета так, чтобы все 4 цвета присутствовали в раскраске каждого куба.

§ 2. «Метод просеивания» [4]

Познакомимся с наиболее общим методом пересчёта, который можно назвать «методом просеивания» или «комбинаторным просеиванием»: с любым свойством P можно связать его расщепление на некотором множестве A, в соответствии с которым A разбивается на две части: подмножество А1, образованное элементами, обладающими свойством Р, и А2, образованное элементами, не обладающими свойством Р, т. е. обладающими свойством Связь комбинаторики с различными разделами математики. Выбирая свойства подходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями.


2.1. Формула включения и исключения

Пусть А – конечное множество и Связь комбинаторики с различными разделами математики. Будем обозначать через Связь комбинаторики с различными разделами математики дополнение А1 по отношению к А, а через Card A – число элементов в А.

Тогда

Связь комбинаторики с различными разделами математики.

Если Связь комбинаторики с различными разделами математикии Связь комбинаторики с различными разделами математики, то

Связь комбинаторики с различными разделами математики (1)

Связь комбинаторики с различными разделами математики.

Покажем, что формула (1) обобщается на случай n подмножеств Связь комбинаторики с различными разделами математики, i=1, 2, ... n:

Связь комбинаторики с различными разделами математики (2)

Действуем по индукции. Имеем

Связь комбинаторики с различными разделами математики (3)

Предположим, что (2) выполняется для случая n-1 подмножеств Ai, i=1, 2,…,n-1:

Связь комбинаторики с различными разделами математикиСвязь комбинаторики с различными разделами математики (4)

Рассмотрим следующие подмножества множества An:

Связь комбинаторики с различными разделами математики

Применяя (4) с A=An, имеем

Связь комбинаторики с различными разделами математики (5)

Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:

Связь комбинаторики с различными разделами математики (6)

Формулы (2) и (6) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения. Пусть элементы Связь комбинаторики с различными разделами математики обладают свойством Pi, i=1, 2, …,n. Тогда мы скажем, что подмножество Связь комбинаторики с различными разделами математикиобладает свойством Связь комбинаторики с различными разделами математики. Таким образом, если элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не обладающих n-k остальными, дается формулой (6).

2.2. Общий метод «просеивания» или «пропускания через решето». Решето Сильва – Сильвестра

Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.

Пример. Рассмотрим множество

Связь комбинаторики с различными разделами математики

и следующие свойства:

Связь комбинаторики с различными разделами математикичетное число,

Связь комбинаторики с различными разделами математики и А >6, (7)

Связь комбинаторики с различными разделами математики и 2 < A < 8.

Подсчитаем число элементов А, обладающих свойством Связь комбинаторики с различными разделами математики. Обозначим подмножества, соответствующие свойствам Р1, Р2, Р3, через А1, А2, А3. Тогда

Связь комбинаторики с различными разделами математики

«Просеиваем» сначала А через Р1: Card A1=6. Затем просеиваем А1 через Р2 и Р3: Связь комбинаторики с различными разделами математики, Связь комбинаторики с различными разделами математики. Просеиваем Связь комбинаторики с различными разделами математики через Р3: Связь комбинаторики с различными разделами математики Итак, Связь комбинаторики с различными разделами математики

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

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

Похожие рефераты: