пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Основные правила комбинаторики. Правило произведения. Правило сумм. Перечислительная комбинаторика. Перестановки. Перестановки с повторениями. Размещения. Размещения с повторениями. Упорядоченное размещение. Сочетания. Сочетания с повторениями.

Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения.

Правило суммы. Если некоторый объект A можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор "либо A, либо B" можно осуществить n+m способами.

Правило произведения. Если объект А можно выбрать n способами, а после каждого такого выбора другой объект B можно выбрать (независимо от выбора объекта A) m способами, то пары объектов A и B можно выбрать n*m способами.

 

Перечислительная комбинаторика

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

Пусть A конечное множество, состоящее из n элементов, т.е. мощность этого множества │A= card A = n. 

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

Перестановкой элементов множества A называется любой кортеж <a1, a2, ..., an> состоящий из n различных элементов множества A

Pn =n

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

Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, ... ,nk) из элементов (a1, a2, ... ,ak) называется кортеж длиной n = n1 + n2 + ...+ nk, в который a1 входит n1 раз, a2 входит n2 раз и т.д. Число таких перестановок 

Размещения 

Кортежи длины k (1kn), состоящие из различных элементов n-элементного множества A (кортежи отличаются один от другого как самими элементами, так и их порядком), называются размещениями из n элементов множества A по k. Число таких

размещений обычно обозначается А из Н по К(буква A от французского слова arrangement -размещение)

Упорядоченное размещение

Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два размещения назовем равными, если в каждом ящике содержится одна и та же последовательность объектов. Размещения такого типа называются упорядоченными размещениями п объектов по m ящикам. Обозначим число таких упорядочений через |m|^n

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


09.06.2014; 00:11
хиты: 1005
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2025. All Rights Reserved. помощь