Перестановки с повторениями

По формуле (3.4) получаем: наборов.

Перестановки с повторениями

Всякое размещение с повторениями, в котором элемент повторяется раз, элемент повторяется раз и т.д. элемент повторяется раз, где , , , — данные числа, называется перестановкой с повторениями порядка

в которой данные элементы повторяются соответственно , , раз.

Теорема. Число различных перестановок с повторениями из элементов , в которых элементы повторяются соответственно раз, равно

Доказательство. Если мы будем считать все элементов перестановки с повторениями различными, то всего различных вариантов перестановок элементов — . Однако среди этих перестановок не все различны. В самом деле, все элементы мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы , , , . Таким образом, всякая перестановка может быть записана способами. Следовательно, число различных перестановок с повторениями равно

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

Вопрос №9 Вывод формул числа всех разбиений множества на части определённых мощностей (упорядоченные и неупорядоченные).

Неупорядоченное разбиение n -элементного множества X — это любое семейство { X ₁, X ₂,…, X _k}, где 1 ≤ k ≤n; X₁, X₂,…,X_k - непустые попарно непересекающиеся подмножества множества X, объединение которых равно X.

Называем такое разбиение неупорядоченным, так как семейство — это неупорядоченная совокупность.

Упорядоченным разбиением конечного множества X с n-элементами называется любой кортеж вида <X₁, X₂,…,X_k>, где 1 ≤k ≤ n; X₁, X₂,…,X_k - непустые попарно непересекающиеся, подмножества множества X, объединение которых равно X. Называем такое разбиение упорядоченным, так как элементы кортежа упорядочены.

Вопрос №10, 11. Свойства чисел сочетаний , бином Ньютона.

Свойства чисел:

1.

2.

3. ;

4. ;

5. , (m1);

Числа С(n, к) возникают как коэффициенты при раскрытии скобок в биноме (а + b)ⁿ. Например,

Эта формула называется биномом Ньютона. Ровно поэтому коэффициенты С(n, к) часто называют биномиальными коэффициентами. Биномиальные коэффициенты полезно выстроить в так называемый треугольник Паскаля

Вопрос №12. Задача о числе счастливых билетов.

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

Найдем — число билетов, у которых сумма первых трех цифр равна сумме трех последних цифр и равна . Ясно, что может принимать значения от (три ) до (три “девятки’’).

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

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

Число способов получить сумму от до можно вычислить по полученной формуле:

: (впрочем, это и так очевидно, , иначе никак),

: ,

: ,

: ,

: ,

: ,

: ,

: ,

: ,

: .

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

: .

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

: ,

: ,

: .

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

Осталось найти общую сумму:

.

Итак, всего есть “счастливых’’ билета.

Группы, кольца, поля

Вопрос №13. Группа, кольцо, поле. Примеры числовых групп, колец, полей.

Множество с алгебраической операцией называется группой, если выполняются следующие условия:

1. Операция в ассоциативна: ;

2. В существует нейтральный элемент ;

3. для каждого элемента существует обратный ему элемент .

Примеры групп:

· Все целые, все рациональные, все действительные и все комплексные числа являются группами относительно операции сложения чисел, играющего роль групповой операции умножения;

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

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

Множество , на котором заданы две операции — сложение и умножение , называется кольцом, если выполняются следующие условия:

1. Относительно операции сложения множество — коммутативная группа, т.е.

· операция сложения коммутативна: ;

· операция сложения ассоциативна: ;

· существует нулевой элемент ;

· для каждого элемента существует противоположный ему элемент ;

2. Операция умножения во множестве ассоциативна;

3. Операции сложения и умножения связаны законами дистрибутивности.

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

Примеры колец при обычных операциях сложения и умножения кольцом является:

1. Множество целых чисел;

2. Множество рациональных чисел;

3. Множество действительных чисел;

4. Множество рациональных чисел;

5. Множество, состоящее лишь из одного числа 0;

6. Множество четных чисел и вообще множество целых чисел, кратных некоторому числу n;

7. Множество комплексных чисел a + bi с целыми a и b (так называемое кольцо целых комплексных чисел).

Множество , на котором заданы две операции: сложение и умножение , называется полем, если выполняются следующие условия:

1. — коммутативное кольцо с единицей ;

2. Для каждого элемента , отличного от нулевого , существует обратный элемент .

Поле — это множество, в котором определены четыре операции: сложение, умножение, вычитание и деление. Полями, например, являются множества рациональных и действительных чисел.

Примеры полей:

1. Множество комплексных чисел a + bi с любыми рациональными a, b;

2. Множество всех рациональных функций с действительными коэффициентами от одного или нескольких переменных;

3. Множество из двух элементов, которые обозначим через 0 и 1, при следующем определении операций:

Вопрос №14, 15. Действие группы на множестве, орбита элемента, подгруппа, теорема Лагранжа о порядке подгруппы.

Группа действует на , если любых и определено действие элемента на элемент (обозначаемое ), обладающее следующими свойствами:

1. ,

2. Для любых выполнено ,

3. Для любого выполнено .

Действие группы:

· Действие группы на себя. Пусть — группа с операцией и множество . Зададим отображение , такое что . Тогда все свойства из определения выполнятся вследствие соответствующих свойств группы. Таким образом группа действует на . Такое действие называется "действие левыми сдвигами".

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

Орбитой элемента x ∈ X под действием G называется множество Gx = {gx | g ∈ G}. Количество элементов в данной орбите называется длиной орбиты (в разных орбитах может быть разное количество элементов). Любые две орбиты либо не пересекаются, либо совпадают. Таким образом, мно- жество X разбивается в дизъюнктное объединение орбит

Подгруппа ― подмножество группы , само являющееся группой относительно операции, определяющей .

Подмножество группы является её подгруппой тогда и только тогда, когда:

· содержит произведение любых двух элементов из ,

· содержит вместе со всяким своим элементом обратный к нему элемент .

В случае конечных и, вообще, периодических групп проверка условия 2 является излишней.

Теорема Лагранжа: В конечных группах порядок любой подгруппы делит порядок группы

Формула (лемма) Бернсайда о числе орбит.

Пусть группа действует на множество . Будем называть два элемента и эквивалентными, если для некоторого . Тогда число классов эквивалентности равно сумме числа стабилизаторов по всем элементам группы , делённой на размер этой группы: . Где — количество стабилизаторов для элемента .

Доказательство:

Так как - сумма стабилизаторов элемента , то по определению . Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство: Рассмотрим правую часть равенства: Заметим, что Следовательно: . Очевидно, что Тогда получим: Откуда следует, что ч.т.д.

Вопрос №16, 17. Задача о числе раскрасок вершин правильного многогранника (куба, тетраэдра, октаэдра).

Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зеленый)?

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

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

Ситуация существенно меняется, если мы откажемся от предположения о том, что кубы жестко закреплены, так как по-разному окрашенные кубы можно повернуть так, что в новом положении их окраски совпадут (рис. 33).

Рис. 33

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

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

Переформулируем теперь эту задачу так, чтобы стала понятной ее связь с леммой Бернсайда. Пусть М — множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано, , G — группа всех вращений куба, состоящая из 24 перестановок. Группа G естественным образом определяет группу перестановок на множестве М. Именно: если а — некоторое вращение, то каждому кубу из М можно сопоставить некоторый, вообще говоря, другой куб, который получается из первого при вращении а. Это соответствие является, очевидно, перестановкой на множестве которую будем обозначать а. Группу всех таких перестановок множества М, определяемых перестановками из G, мы будем обозначать G. Ясно, что

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

Считая вершины кубов занумерованными числами 1,2, 3, 4, 5, 6, 7, 8, раскраску каждого из 38 кубов можно однозначно охарактеризовать «словом» из 8 букв, каждая из которых есть либо к, либо с, либо з. То, что i-я буква слова равна к (или с, или з), означает; что i-я вершина при выбранной нумерации окрашена в красный цвет (или в сцний, или в зеленый соответственно). Например, для куббв, изображенных на рис. 33, имеем соответственно последовательности . Перестановки из группы G переставляют такие последовательности. Например, если то перестановка а слово переводит в , слово ссззсскк переводит в слова оставляет неизменными и т. д. Выписать всю таблицу значений для перестановки а затруднительно, поскольку она состоит из строк!

Для того чтобы применить лемму Бернсайда, необходимо определить число неподвижных точек каждой перестановки из G. Последовательность букв будет неподвижной для перестановки тогда и только тогда, когда при разложении соответствующей перестановки в произведение "Циклов вершины куба, номера которых входят один и тот же цикл, окрашены одним цветом. Например, если , то неподвижными относительно а будут слова, составленные целиком из одной буквы, и слова, составленные из двух разных букв, причем одна из них стоит на первых четырех местах в слове, а вторая — из четырех последующих. Поэтому имеется 9 неподвижных точек перестановки на множестве М. Уже на этом примере видно, что подсчет числа неподвижных точек перестановок из G сильно упрощается, если извесгны разложения в произведение циклов соответствующих перестановок из G. Если перестановка разложена в произведение циклов, то число ее неподвижных точек равно

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

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

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

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

Вместе с тождественной получаем 24 перестановки. Итак, в группе G вращений куба имеется

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

Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета равно 333.

Вопрос №18. Кольца и поля вычетов, решение уравнений в кольцах и полях вычетов.