На головну

Метод включення і виключення. Функція Ейлера. Число заворушень.

  1. Стандартний алгоритм симплекс-методу
  2. DFD - методологія в проектуванні ІС
  3. I етап - Множення на однозначне число
  4. I етап. Розподіл на однозначне число.
  5. I.3.3. Методи виносу в натуру проектних точок.
  6. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  7. II. Статечна функція збуту

нехай дано n-безліч елементів S и N-безліч властивостей p1, ...,pN. елементи безлічі S можуть як мати, так і не мати будь-якою з властивостей pi. Кількість елементів, що володіють тими чи іншими властивостями і їх комбінаціями, відомо.
потрібно знайти число елементів, що не володіють жодним з властивостей.
позначимо:

1.
 через  деяку i-у вибірку властивостей, а через  - Число елементів, кожен з яких має усіма цими r обраними властивостями.

2.
 через  - Відсутність у елемента властивості pi. Тоді, наприклад,  - Число елементів, що володіють властивостями p1 и p3 і що не володіють властивостями p2 и p4.
 Розглянемо два окремих випадки.

1.
 Є лише одна властивість p. Тоді очевидно, що число елементів, що не володіють властивістю p, Дорівнює загальній кількості елементів мінус число елементів, що володіють властивістю p. .

2.
 Є кінцеве безліч властивостей p1, ...,pN, Але вони не сумісні (т. Е. Жоден з елементів не може володіти більш ніж одним властивістю). Тоді число елементів, що не володіють жодним з властивостей, дорівнює загальній кількості елементів мінус число елементів, що володіють властивістю p1, Мінус число елементів, що володіють властивістю p2 і т.д.

^ Загальний випадок - Елементи можуть мати комбінацією сумісних властивостей.
Теорема. якщо дані n-безліч елементів S и N властивостей pi  , То число елементів, що не володіють жодним з властивостей, так само (формула решета):

.

Примітка 1. Символічна запис методу:
 , (*)
 де буквою n позначений функціональний знак. Сенс такого запису - спочатку розкриваємо дужки всередині квадратних, а потім знак функції n приписуємо до кожного з доданків. наприклад,
,
 вважаючи, що .

Приклад застосування формули включень-виключень - знаходження явного виразу для функції Ейлера  , Що виражає кількість чисел з  , Взаємно простих з .

Нехай канонічний розклад числа  на прості множники має вигляд

число  взаємно просто з  тоді і тільки тоді, коли жоден з простих дільників  поділяє  . Якщо тепер властивість  означає, що  ділить  , То кількість чисел взаємно простих з  є .

кількість  чисел, що володіють властивостями  одно  , оскільки .

За формулою включень-виключень знаходимо

Ця формула перетвориться до виду:

Безладом називається перестановка без нерухомих точок.

Кількість всіх заворушень порядку n може бути обчислено за допомогою принципу включення-виключення і дається виразом:

яке називається субфакторіалом числа n.

Квиток намбер 3:

Лінійний оператор і його матриця. Власні числа і власні вектори лінійного оператора. Поняття діагоналізіруемості лінійного оператора. Існування базису з власних векторів лінійного оператора як основний необхідна і достатня ознака його діагоналізіруемості. Характеристичний многочлен лінійного оператора і його властивості.

Відповідь на квиток намбер 3:

Нехай задані лінійні простори и  . Правило, за яким кожному елементу  ставиться у відповідність єдиний елемент  , називається оператором, Чинним в лінійних просторах  . Результат дії оператора  на елемент  позначають  або  . якщо елементи и  пов'язані співвідношенням  , то  називають чином елемента  ; елемент прообразом елемента .

Безліч елементів лінійного простору  , Для яких визначено дію оператора  , називають областю визначення оператора і позначають .

Безліч елементів лінійного простору  , Які є образами елементів з області визначення оператора  , називають чином оператора і позначають  . якщо  , то .

оператор  , Який діє у лінійних просторах  називається лінійним оператором, якщо и  для будь-яких  і для будь-якого числа .

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



квиток 2 | Лінійний оператор і його матриця.

Біном Ньютона | ряд Ньютона | Виробляють функції і рекурентні співвідношення | Про єдиному нелінійному рекуррентном співвідношенні | Власні значення і власні вектори лінійного оператора | Діаганалізаруемость лінійного оператора і т. Д. І т. П. | Характеристичний многочлен лінійного оператора і його властивості | Види облікових структур. Методи роботи зі списками. | КВИТОК 5 | Зв'язкові графи. |

© um.co.ua - учбові матеріали та реферати