Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2017-11-27 | 752 |
5.00
из
|
Заказать работу |
|
|
v(Si)- вес элемента S;
… – выборка свойств из Р1 …РN
V( … ) – сумма весов элементов, обладающих всеми из заданных свойств.
сумма весов для всех выборок
(ps последняя формула не точно, общий материал взят из леций Гусева)
Принцип включения и исключения. Теорема о числе элементов, обладающих в точности R-свойствами из N–множества свойств. Доказательство.
Теорема:
Доказательство.
Пусть некоторый элемент i имеет вес v(Si) и удовлетворяет в точности t свойствам pi1…pit из R.
Возможно 3 случая
1. t< R вес этого элемента в подсчете не участвуют, вносится 0
2. t=R в правую часть вносит свой собственный вес
3. t> R вносит свой вес v(Si):
Так как: )
Тогда выражение в скобках равно 0, так как оно является частным случаем разложением бинома Ньютона.
13. Задача о беспорядках. Теорема о числе беспорядков из элементов
n–множества. Доказательство. Следствия.
Пусть имеется конечное упорядоченное множество элементов {1,…, n }. Из этих элементов могут быть образованы перестановки a 1,…, an (ai Î{1,…, n }). Число всех возможных перестановок – n!. Среди этих n! перестановок есть такие, что ни один элемент не стоит на своём месте (ai ¹ i, i = ). Иначе говоря, элемент номер 1 не стоит на 1-ом месте, элемент номер 2 не стоит на 2-м месте, и т.д., элемент номер n не стоит на n -м месте. Такие перестановки называются беспорядками.
Число беспорядков из n элементов обозначается Dn (ясно, что Dn<n!).
Теорема. Число беспорядков из n элементов равно:
.
Доказательство
Обозначим через свойство pi – «i -й элемент стоит на i -м месте». Тогда по формуле решета .
Общее число перестановок n элементов – n! Число перестановок, где i -й элемент стоит на i -м месте, равно (n -1)! (ставим i -й элемент на i -е место, а оставшиеся n -1 элементы переставляем (n -1)! способами). При этом сам i -й элемент можно выбрать способами. Таким образом, число перестановок, где хотя бы по одному элементу стоит на своём месте, равно .
|
Число перестановок, где i -й элемент стоит на i -м месте, а j -й на j -м (i ¹ j), равно (n -2)!, при этом i -й и j -й элементы можно выбрать способами. Таким образом, число перестановок, где хотя бы два элемента стоят на своих местах – .
Аналогично, число перестановок, где на своих местах стоят хотя бы три элемента – . Число перестановок, где на своих местах стоят хотя бы r элементов – . Число перестановок, где все элементы стоят на своих местах . Подставляем в формулу решета:
Следствие 1.
Так как ,
то .
Следствие 2.
Так как , то .
Функция Эйлера
Функция Эйлера φ (n), где n – натуральное число, дает количество натуральных чисел, не превышающих n и взаимно простых с n. Иначе говоря, φ (n)= k, где 0< k £ n; (k, n)=1.
Теорема
, где pi – все простые делители n. ( - произведение по всем простым делителям числа n).
# В теореме Лежандра заменим ai на pi, где pi – простые делители n.
Тогда (так как pi делят n нацело).
По теореме Лежандра
. #
Пример. Определим, сколько чисел, не превышающих 100, взаимно простые с 100. Разложим число 100 на простые сомножители: 100=2·2·5·5=2252. Таким образом, у числа 100 два простых делителя – 2 и 5. По формуле Эйлера получаем
.
Таким образом, среди первой сотни есть 40 чисел, взаимно простых с 100.
Функция Мебиуса
Функция Мебиуса m (n), где n – натуральное число, принимает следующие значения:
Функция Мебиуса позволяет записать функцию Эйлера в виде суммы:
.
Суммирование идет по всем делителям n (а не только по простым делителям).
Пример. Вычислим φ (100), используя функцию Мебиуса.
Все делители 100 – {1, 2, 4, 5, 10, 20, 25, 50, 100}.
m (1) = 1,
m (2) = (-1)1 = -1 (у двойки один простой делитель – 2)
m (4) = 0 (4 делится на квадрат двойки)
m (5) = (-1)1 = -1 (у 5 один простой делитель – 5)
|
m (10) = (-1)2 = 1 (у 10 два простых делителя – 2 и 5)
m (20) = 0 (20 делится на квадрат двойки)
m (25) = 0 (25 делится на квадрат пятерки)
m (50) = 0 (50 делится и на 22, и на 55)
m (100) = 0 (100 делится и на 22, и на 55)
Таким образом,
Свойство функции Мебиуса: .
Например, n =100, a Î{1, 2, 4, 5, 10, 20, 25, 50, 100}.
.
16 Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Доказать с помощью получения рекуррентной формулы.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!