Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Размещения






Упорядоченная (n, k) выборка, в которой элементы могут повторяться, называется (n, k) размещением с повторениями.

Иными словами размещениями с повторениями из n элементов по k называют векторы длины k, составленные из n элементов множества Х.

Число размещений с повторениями из n элементов по k определяется оценкой соответствующего декартова произведения Хk n-элементного множества, обозначается (по-видимому от английского слова Assing – назначать) и вычисляется следующим образом:

=nk.

Таким образом, первый элемент вектора длины k выбирается n способами, второй – n способами и т.д.: n× n×...× n=nk.

Пример. Сколькими способами можно оснастить две различные фирмы компьютерами трех типов?

Каждый способ оснащения есть выборка (3, 2), вектор длины 2, составленный из 3-х элементного множества типов Т={t1, t2, t3}. Поэтому число способов оснащения – число размещений с повторениями из 3 по 2:

.

Рассмотрим подробнее:

1) (t1, t1); 2) (t1, t2); 3) (t1, t3);

4) (t2, t2); 5) (t2, t3); 6) (t2, t1);

7) (t3, t3); 8) (t3, t2); 9) (t3, t1).

Получили различные упорядочения двухэлементных векторов из 3-х элементного множества, т.е. множество Т2.

Здесь каждый вектор соответствует способу оснащения. Видно, что, например, (t1, t2), (t2, t1) считаются разными способами, так как фирмы предполагаются различными («первая – первым типом», «вторая – вторым» и т.д.). Имеются повторения: (t1, t1), (t2, t2), (t3, t3).

В ряде задач необходимо определить число векторов длины k из n элементов данного множества без повторения элементов.

Если элементы упорядоченной (n, k) выборки попарно различны, то они называются (n, k) размещением без повторений или просто (n, k) размещением.

Число таких размещений без повторений обозначается .

Каждое (n, k) размещение без повторения является упорядоченной последовательностью длины k, элементы которой попарно различны и выбираются из множества с n элементами. Тогда первый элемент этой последовательности может быть выбран n способами, после каждого выбора первого элемента последовательности второй элемент может быть выбран n-1 способами и т.д., k-й элемент выбирается n-(k-1) способом:

=(n-1)(n-2)...[n-(k-1)].

Преобразуем эту формулу, умножая и деля ее на произведение чисел 1× 2× × × (n-k):

В частности, при k=0 . Очевидно, что при k> n =0.

Пример. Сколькими способами из 3-х студентов можно назначить группу на прополку клубники в составе начальника и подчиненного?

Речь идет о выборе упорядоченных двухэлементных подмножеств множества студентов, состоящего из трех элементов (K={1, 2, 3}), т.е. о размещениях без повторений из 3 элементов по 2, поэтому:

.

Подробнее, в виде векторов из номеров студентов, например, по журнальному списку, первая компонента которого обозначает номер студента-начальника, вторая – подчиненного:

(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2).

Ясно, что здесь существенен порядок следования компонент и не может быть повторений (один студент не может быть начальником и подчиненным одновременно), поэтому это множество – подмножество декартового произведения.

Пример. Сколькими способами можно провести распределение 10 механизаторов по 3 сушильным установкам? Один механизатор назначается на одну сушильную установку.

Распределение механизаторов – размещение без повторений из 10 элементов по 3, поэтому:

.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.