Задать вопрос юристу

№18. Сочетания с повторениями. Перестановки без повторений с повторениями.

Сочетания с повторениями

Число монотонных функций, или число размещений п неразличимых предме­тов по т ящикам, называется числом сочетаний с повторениями и обозначается

V(m,n).

ТЕОРЕМА V(m,n) = C(n+m-n)

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

Монотонной функции f: {1,..., п) {1,..., т} однозначно соответствует стро­го монотонная функция f': {1,...,n} {1,...

,п + т -1}. Это соответствие устанавливается следующей процедурой.

f'(1): = f(1) { первые элементы совпадают }

for i from 2 to n do

if f(i) = f(i - 1) then

f'(i): = f'(i-l) + 1 {плато}

else

f'(i) : = f'(i-1) + f(i) - f(i - 1) { подъем}

end if

end for

5.1.4. Перестановки.

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

Теорема: P(n)=n!

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

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

Иногда требуется переставлять предметы, некоторые из которых неотличимы друг от друга. Рассмотрим такой вариант перестано­вок, который называется перестановками с повторениями. Пусть имеется п1 предметов 1-го типа, n2 предмета 2-го, пк пред­метов k-то типа и при этом п1+ п2 +...+ пк = п. Количество разных перестановок предметов

Р(n1, n2, n3, ...nк) = (n!)/(n1! n2!... nk!) (5)

Для обоснования ( 5 ) сначала будем переставлять п предметов в предположении, что они все различны. Число таких перестановок равно n! Затем заметим, что в любой выбранной расстановке пере­становка n1 одинаковых предметов не меняет комбинации, анало­гично перестановка п2 одинаковых предметов также не меняет ком­бинации и т. д. Поэтому получаем выражение (5).

<< | >>
Источник: Дискретная математика. Шпаргалка. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме №18. Сочетания с повторениями. Перестановки без повторений с повторениями.:

  1. 2. Выборки. Размещения с повторением и без повторений. Перестановки.
  2. №17. Размещения без повторений, с повторениями. Сочетания без повторений.
  3. 3. Обчислення кількості розміщень, перестановок і сполук без повторень і з повтореннями.
  4. 3. Сочетания с повторениями и без.
  5. Вопрос 6. Повторение и его виды. Урок обобщающего повторения.
  6. 9.Повторение испытаний. Частная теорема о повторении опыта.
  7. 27. Правило суммы и произведения в комбинаторике. Основные комбинаторные схемы. Формулы подсчета числа размещений с повторениями и без повторений, числа разбиений конечного множества на подмножества фиксированной мощности. Бином Ньютона, полиномиальная формула. Формула включений и исключений.
  8. 10. Повторение на уроках русского языка
  9. 34 Повторение на уроках биологии
  10. 34. Повторение опытов. Формула Бернулли.
  11. Повторение испытаний.
  12. Теорема о повторении опытов
  13. Повторение испытаний. Формула Бернулли.
  14. Шпаргалки.com 1. ОСНОВЫ ПЕДИАТРИИ. ПРОГРАММА ПОВТОРЕНИЯ К ЭКЗАМЕНУ, 2016
  15. 10. Общая теорема о повторении опытов. Производящая функция.
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -