3 Элементарные методы пересчета выборок icon

3 Элементарные методы пересчета выборок




Скачати 205.09 Kb.
Назва3 Элементарные методы пересчета выборок
Дата05.09.2012
Розмір205.09 Kb.
ТипДокументи

3. Комбинаторный анализ

Комбинаторным анализом (или просто комбинаторикой) называется раздед теории множеств, в котором изучают проблемы составления различных комбинаций, подчиненных определенным условиям, из множества (или нескольких множеств) заданных объектов и методы подсчета всех возможных способов, которыми могут быть состевлены такие комбинации.

Основные понятия комбмнаторики были рассмотрееы в ХVІІ-ХVІІІ веках в работах Б. Паскаля (1623-1662), П. Ферма (1601-1665), Г. В. Лейбница (1646-1716), Я. Бернулли (1654-1705), Л. Эйлера (1707-1783). В самостоятельную научную дисциплину комбинаторный анализ оформился в начале XX века. В настоящее время методы комбинаторного анализа находят широкое применение при решении задач теории вероятностей, теории информации, теории автоматов, при планировании и анализе научных экспериментов, в линейном и динамическом программировании, математической экономике и многих дру­гих областях науки и техники.

3.1. Элементарные методы пересчета выборок

3.1.1. Основные правила комбинаторики

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

1. Правило суммы. Рассмотрим два конечных множества: * .

Как известно, число элементов конечного множества А обозначается (А). В нашем случае * .

Предположим, что множества А и В не имеют общих элементов, т.е. * . Тогда множество * будет состоять из * различных элементов:

Таким образом, один элемент из имеющихся * элементов можно выбрать * различными способами. Это и есть правило суммы. Обычно оно формулируется следующим образом:

Если объект А может быть выбран * различными способами, а объект * – другими * различными способами, то выбор объекта * или * ("или" имеет исключающий смысл) может быть осуществлен * способами.

Пример 3.1. В учебной группе 10 студентов регулярно выполняют упражнения по математике на отлично, 13 – на хорошо, 5 – на удовлетворительно. Сколько студентов могут выполнить упражнение по математике не ниже, чем на хорошо?

^ В учебной группе имеется 10+13=23 студента, которые могут выполнить упражнение по математике на хорошо или отлично.

Правило произведения. Пусть * и * – конечные множества, причем * . Из элементов этих множеств образуются всевозможные упорядоченные пары (двухместные кортежи) *, (3.2)


где * , * . Так как первый элемент пары * может быть выбран * способами, а второй элемент пары * способами, то всего можно образовать * упорядоченных пар вида (3.2), являющихся элементами декартового произведения АхВ. Следовательно, * (3.3)

Итак, если элемент * из множества А можно выбрать * способами, а элемент *; из множества В, можно выбрать * спо­собами, то кортеж * можно составить т.п различными способами. Это и есть правило произведения. Обычно его формулируют следующим образом.

Если о6ъект А можно выбрать т различными способами, а объект В – другими * различными способами, то выбор пары объектов А и В (в указанном порядке) можко осуществить * различными способами.

Пример 3.2. В учебной группе 5 сержантов и 23 рядовых. Для патрулирования нужно выделить пару из одного сержанта и одного рядового. Сколько таких пар можно образовать из курсантов данной учебной группы?

Согласно правилу произведения можно образовать 5.23 = 115 различных пар указанного типа.

Обобщим правило произведения для случая К множеств *. Пусть * , т. е. * .

Составим всевозможные * -местные кортежи * (3.4)

где * .

Кортежи вида (3.4) называются в комбинаторике упорядоченными К-выборками. Они являются элементами декартового произведения * . Покажем, что * (3.5)

Действительно, элемент * из первого множества * можно выбрать * способами, элемент * из множества * способами, поэтому упорядоченные пары * можно составить * способами. К каждой такой паре элемент * из множества * можно присоединить * способами, т. е. можно образовать * различных упорядоченных троек * . Продолжая этот процесс, получим, что число различных К-местных кортежей вида (3.4) равно * .

Теперь сформулируем правило произведения в общем виде.

Пусть нужно выполнить одну за другой К операций. Если первую операцию можно выполнить * способами, вторую операцию – * , способами, …, * операцию – * способами, то все К операций вместе могут быть выполнены * способами.

П р и м е р 3.3. В группе из 20 лагкоатлетов 5 специализируются в беге на 100 м, 4 - на 200 м, 6 - на 400 м и 5 - на 800 м. Сколько различных команд можно составить для участия в комбинированной эстафете 100+200+400+800 м?

На первом этапе может бежать один из 5 спортсменов, на втором - одон из 4 спортсменов, на третьем - один из 6 спортсменов, на четвертом - один из 5 спортсменов. Следовательно, * , *, *, *.

Общее число способов создания эстафетной команды *.

3. Правило включений и исключений.

Решим следующую задачу. Найти число элементов в объединении нескольках множеств, зная число элементов в каждом из них, а также число элементов в каждом из пересечений этих множеств по два, по три и т. д.

Начнем со случая двух множеств. Пусть * - конечные множества, причем * . Здесь * – общее число элементов, которые принадлежат как множеству *, так и множеству *. Очевидно, что общее число различных элементов множества * равно сумме общеґо числа элементов множества * и общего числа элементов множества ( * ), которые принадлежат * , но не принадлежат * . Так как * , то * .

Таким образом, чтобы найти число элементов объединения множеств * и *, нужно найти сумму числа элементов множества * и числа элементов множества * и исключить из нее (вычесть) число елементов, общих для множеств * и * . Следовательно, справедлива формула * (3.6)

Перейдем теперь к случаю трех множеств * . Пусть * , * ,

Найдем * . Используя свойства операций над множеством и формуму (3.6, получим: *

Мы пришли к следующему равенству: * (3.7) *

Применяя метод математической икдукции, можно получить общую формулу: * (3.8)

При этом учытываются всевозможные пересечения заданных * множеств * …, * и мощность пересечения четного киличества множеств берется со знаком “минус”, а мощность пересечения нечетного числа множеств берется со зкаком “плюс”.

Равенство (3.8) называется формулой включений и исключений, так как для каждого элемента подсчитывают, сколько раз он включается и сколько исключается.

Пусть * - универсальное множество, * - его подмножество. Известна мощность каждого из множеств * , а также мощность каждого из пересечений этих множеств по два, по три и т. д. Требуется выснить, сколько элементов в * принадлежат ни одному из множеств * . , т. е. принадлежат множеству * ...

Очевидно, * , что с учетом формулы (3.8) приводит к результату * (3.9)

Формула включений и исключений применяется для решения следующей задачи. Рассмотрим множество из * объектов и некоторую совокупность свойств * . Введем обозначения: * - количество объектов, обладающих свойством * ( * = І, 2, …, К) * ( * ) - количество объектов, которые обладают свойствами * одновременно; …; п(* ) – число объектов, обладающих всеми свойствами * . Тогда количество объектов, обладающих хотя бы одним из свойств * , находят по формуле * (3.10)

Число объектов, которые не обладают ни одним из свойств * * (3.11)

Пример 3.4. Каждый студент учебной группы либо спортсмен, либо радиолюбитель, лбо любит математику. В группе 20 спортсментов, из них 12 радиолюбителей, и один радиолюбитель – спортсмен, любящий математику. Всего в группе 24 радиолюбителя, из них математику любят 12. Всего студентов, любящих математику 17, из них 6 спортсменов. Сколько студентов в учебной группе?

Каждый студент обладает хотя бы одним из трех свойств: * - быть спортсменом, * - быть радиолюбителем, * - любить математику.

При этом *** Количество студентов в учебной группе подсчитаем по формуле (3.10)


Пример 3.5. Из 100 студентов английский язык знают 34, немецкий – 28, французский – 19, английский и немецкий – 12, английский и французский – 5, все три языка – 3. Сколько студентов не знают ни одного из указанных языков?

Пусть * - знать английский язык, * - знать немецкий язык, * - знать французский язык. Тогда * .

Таким образом, 60 студентов из 100 знают хотя бы один из трех иностранных языков (английский, немецкий мля французский). А 100-60=40 студентов на знают ни одного из трех указанных языков.

3.1.2. Выбор с возвращением. Размещения с повторениями

Предположим, что из некоторого множества А , содержащего п элементов * , на каждом шаге последовательно выбирается один из элементов * , который затем возвращается обратно в данное множество. Такой выбор называется выбором с в о з в р а щ е н и е м. Через К шагов выбора с возвращением получим комбинацию вида * (3.12)


где * - элемент, выбранный на первом шаге, * - элемент, выбранный на втором шаге, … , * - элемент, выбранный на К-ом шаге. Комбинация (3.12) представляет собой упорядоченную К-выборку (К-местный кортеж) и является элементом декартового

произведения * .

Так как * (общее число элементов множества А равно * ), то на каждом шаге существует * способов выбора одного из них. Следовательно, по правилу произведения, существует * различных комбинаций вида (3.12). Так как выбор с возвращением, то в комбинации (З.12) любой элемент * , может встретиться от одного до К раз. Такие упорядоченные К-выборки с повторениями элементов называются в комбинаторике размещениями с повторениями. Число всех размещений с повторениями из * элементов по К элементов ообозначается * . Из сказанного выше следует, что * (3.13)

Например, из трех элементов * можно составить * различных размещений с повторениями по два элемента: * .

П р и м е р 3.6. Телефонный номер состоит из семи цифр. Сколько всевозможных номеров можно набрать на телефонном диске?

На телефонном диске имеется множество из 10 цифр: 0, І, 2, З, 4, 5, 6, 7, 8, 9. Следовательно, каждую из семи цифр телефонного номера можно выбрать десятью способами ( * ). Цифры в телефонном номере могут повторяться. Значит, здесь речь идет о раз-мещениях с повторениями из 10 элементов по 7 элементов ( * ). По формуле (3.13) * .

Таким образом, существует десять миллионов различных семизначных телефонных номеров.


З.1.3. Выбор без возвращения. Размещения без повторений

Имеется множество, состоящее из п различных элементов * . На каждом шаге выбирается один из элементов * . *, который не возвращается в данное множество. Такой выбор называется выбором без возвращения. Через К шагов выбора без возвращения получим упорядоченную К-выборку вида (3.12), в которой ни один иа элементов * не повторяется. Такие комбинации называются размещениями без повторений (или просто размещениями) из п элементов по К элементов. Общее их число обозначается через А*.

На первом шаге элемент * можно выбрать из имеющихся * элементов * способами. Так как выбранный элемент не возвращается, то на втором шаге элемент * можно выбрать из оставшихся * элементов * способами. Следовательно, на * шаге элемент * можно выбрать из оставшихся * элементов * способами. Примення правило произведения, находим * (3.14)

Если ввести обозначение * (3.15)

то формулу (3.14) можно записать в виде * (3.16)

Например, из трех элементов а, б, с можно составить

  • различных размещений по два элемента (без повтворения элементов): *

Таким образом, два размещения отличаются друг от друга хотя бы одним элементом или состоят из одних и тех же элементов, но расположенных в разном порядке.

Пример 3.7. Сколько можно составить семизначных теле­фонных номеров с неповторяющимися цифрами?

На телефонном диске 10 цифр. Первую цифру телефонного номера можно выбрать десятью способами, вторую - девятью способами, так как она не должна повторять первую и т. д. Всего имеется * семизначных телефонных номеров с неповторяющимися цифрами.

Докажем. Что справедливо рекуррентное соотношение * (3.17)

Зафиксируем некоторый элемент * . Все размещения без повторений из п элементов по К элементов разобъем на две группы: содержащие элемент * и не содержащие его. Чтобы получить число размещений, содержащих элемент * , поступим так. Вначале из остальных * элементов * составим все размещения по * элементов: * (3.18)


Всего их будет * . Затем к каждому из размещений вида (3.І8) присоединим элемент * . Он может занять К разных позиций: пе­ред * , между * и * , между * и * , между * и * , после *. Следовательно, число К-выборок, содержащих элемент * , составит * , равно * . Применяя правило суммы, получим, что число всех размещений из * элементов по К равно * .

Полагают, что *.

Эти равенства служат граничными условиями для рекуррентного соотношения (3.17).


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

Рассмотрим множество, состоящее из * различных элементов * . Из этих элементов составляют упорядоченные * выборки (без повторения элементов):

*

Они могут отличаться друг от друга только порядком расположения входящих в них элементов. Такие размещения из л элементов по * элементов называются перестановками из * элементов. Их общее число находят по формуле *

П р и м е р 3.8. Сколько существует способов построения в шеренгу пятерых студентов: Иванова, Николаева, Петрова, Сидорова, Шабунина, так, чтобы студенты Иванов и Сидоров не стояли рядом?

Пятиэлементное множество (Иванов, Николаев, Петров, Сидоров, Шабунин) можно упорядочить * различными способами. Из них нужно исключить те построения, в которых Иванов и Сидоров окажутся рядом. Подсчитаем количество таких построений. Для этого рассмотрим следующее четырехэлементное множество: (Иванов, Сидоров, Николаев, Петров, Шабунин). Его можно упорядочить * способами, т. е. можно построить 24 шеренги, в которых Иванов и Сидоров будут стоять рядом, причем сначала Иванов, а затем Сидоров. Еще можно построить 24 шеренги, в которых Иванов и Сидоров будуть стоять рядом, причем Сидоров впереди Иванова. Следовательно, всего возможно * способа построения в шеренгу пятерых студентов так, чтобы студенты Иванов и Сидоров не стояли рядом.

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

Предположим, что имеется * элементов * различных типов: * элементов первого типа, * элементов второго типа, …, * элементов *-го типа, так что * .

Элементы каждого типа (однотипные элементы) считаются неразличимыми. Общее число различных перестановок из этих * элементов обозначают через *. Если бы все * элементов были различными, из них можно было бы составить * различных перестановок. Но так как среди * элементов некоторые неразличимы, получим меньшее число различных перестановок.

Действительно, комбинация из п элементов будет содержать п.1 неразличимых элементов первого типа, которые можно переста­вить между собой * способами и при этом указанная комбинация не изменится. Аналогично, рассматриваемую комбинацию не изменят * перестановок неразличимых элементов * типа. Следовательно, согласно правилу произведения существует * способов перестановки неразличимых элементов, не изменяющих рассматриваемую комбинацию из * элементов. Поэтому число различных переста­новок из * элементов указанного типа * (3.20)

П р и м е р 3.9. Сколько различных слов можно составить, пареставляя буквы в слове “математика”?

В слово "математика" 10 букв (2 буквы м, 3 буквы а, 2 буквы т, по одной буква е, и, к). Общее число различных перестановок из этих букв определяем по формуле (3.20): *


3.1.6. Сочетания без повторений (неупорядоченные к-выборки)

пусть конечное множество А состоит из * элементов: * .

Произвольное К – элементное подмножество множества А называется неупорядоченной К-выборкой, или сочетанием без повторений из * элементов по К.

Сочетания отличаотся друг от друга составом, но не поряд­ком расположения элементов. Например, из трех элементов а, в, с можно составить три сочетания по два элемента: * .

Общее число сочетаний из * элемонтов по ^ К, т. е. общее число к –элементных подмножеств * -элементного множества А, обозначается так: С * или * . Если элементы каждого сочетания переставить между собой * способами, то, очевидно, получим все размещения из * элементов по * элементов. Следовательно, * , откуда * (3.21).

Используя формулы (3.14) и (3.160 для подсчета числа размещений, находим: * (3.22) или * (3.23)

Пример 3.10. Собрание, на котором присутствуют 30 студентов, должно избрать трех делегатов на конференцию. Сколькими способами это можно сделать?

Искомое число способов равно числу сочетаний из 30 элементов по 3, т. е. * .

Числа * , где * , называются также биномиальными коэффициентами, так как коэффициент при * в разложении бинома * равен *:

  • (3.24)

Отметим некоторые свойства сочетаний.


  1. * (3.25)

*


Формулой (3.25) удобно пользоваться при подсчете числа сочетаний, когда * .

Например, * .


2) * (3.26)


Это следует из формулы (3.23) и того, что * , где * - гамма-функция Эйлера.


  1. * (3.27)

*

Используя формулу (3.27), можно построить так называемый треугольник Паскаля, представляющий собой таблицу

значений коэффициентов * при различных значениях * . Каждое число таблицы, не равное единице, есть сумма двух чисел предыдущей строки – стоящего над ним и левее.

*

0

1

2

3

4

5



0

1








































  1. * (3.28)




  1. * (3.29)


Это равенство следует из формулы (3.24), если принять в ней * . Соотношение (3.29) интерпретируют так: общее число всех подмножеств, которые можно образовать из * - элементного множества А, равно * (включая пустое множество * и само множество А).

  1. * (3.30)

Действительно, полагая в формуле (3.24) * , получим данное равенство.

Пример 3.11. Пусть А - непустое множество, (А) *. Как известно, разбиением множества А называется семейство не­пустых подмножеств * , * , ••••, таких, что *

Выясним, сколько существует различных разбиений множсетсва А на К подмножеств * , если * .

Подмножество * мощности п есть неупорядоченная * -выборка из * элементов множества А, поэтому число таких выборок равно С *. Так как * , то подмножество * мощности * является неупорядоченной *-выборкой из оставшихся * элементов множества А. и, следовательно, число таких выборок равно * . Наконец, подмножество * мощости * представляет собой неупорядоченнуо *-выборку из тех элементов множества А , которые не вошли в подмножества А , А , число таких выборок * .

Применив правило произведения, получим искомое число различных разбиений: ***

Таким образом, общее количество способов разбиения * - элементного множества на * классов равно числу различных перестановок с повторениями из * элементов, среди которых имеется * неразличимых элементов первого типа, * неразличимых элементов второго типа, …, * элементов * типа.

П р и м е р 3.12. Сколько существует способов распределения 10 сообщений по трем каналам связи, чтобы на первый канал по­пало два сообщения, на второй и третий - по четыре сообщения?

Множество из 10 элементов ( * = 10) разбиваем на три группы, причем * . По формуле (3.20) * (способов).

П р и м е р 3.ІЗ. Ранее было установлено, что мощность множества * может быть вычислена по формуле включений и исключений: *

Справедливость этого равенства модно установить, доказав, что каждый элемент * учитывается в правой части формулы включений и исключений только один раз. Предположим, что рассматриваемый элемент * принадлежит ровно * множествам * . Такой елемент * подсчитывается в правой части формулы (3.31) в соответстви с равенствами (3.26) и (3.30) следующее число раз: *

Таким образом, любой элемент * учитывается в правой части формулы (3.31) ровно один раз, что и доказывает справедливость этой формулы.

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

Сочетания с повторениями из * элементов по * называются неупорядоченные К -выборки из элементов * множества А, в которых каждый элемент * может встречаться любое допустимое (от 0 до К) число раз.

^ Например, из трех элементов а, в, с можно составить следующие сочетания с повторениями по два элемента. ***

Число различных сочетаний с повторениями из * элементов по * обозначают * и вычисляют по формуле * (3.32)


Пусть * - элементы множества А, из которых составляются сочетания с повторениями по х элементов. Любое сочетание можно полностью определить, если указать, сколько раз каждый их элементов * (*) входит в это сочетание. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную по следующему правилу: напишем подряд столько единиц, сколько раз элемент * входит в сочетание; далее поставим нуль и после него запишем столько единиц, сколько раз элемент * входит в сочетание; затем поста­вим нуль и после него напишем столько единиц, сколько раз элемент * входит в сочетание и т. д. Например, приведенным выше сочетаниям из трех элементов а, в, с по два будут соответствовать последовательности 1100, 1010. 1001, 0110, 0101, 0011.

Следовательно, каждому сочетанию с повторениями из * элементов по К соответствует последовательность из К единиц и * нулей. Наоборот, имея какую-то последовательность из К единиц и * нулей, можно однозначно восстановить соответствующее ей сочетание с повторениями из * элементов по К. Число различных последовательностей из К единиц и * нулей равно числу перестановок с повторениями из * элементов, т. е. * .

Таким образом, число сочетаний с повторениями из п элементов по к действительно равно числу сочетаний без повторений из * элементов по к элементов.

Пример 3.14. На склад поступили однотипные радиодетали, изготовленные на шести заводах. Из них комплектуют группы по четыре детали в каждой. Сколькими способами это можно сделать?

Учитивая, что в группу из четырех деталей могут войти дета­ли, изготовленные только на одном заводе, или детали, изготовленные на разных заводах, имеем сочетания с повторениями из 6 элементов по 4 элемента. По формуло (3.32) находим: * (способов).


3.1.8. Формула Стирлинга

В выражения для подсчета общего числа размещений, перестано­вок, сочетаний входит величина л! Непосредственное вычисление ее по формуле (3.15) при больших п весьма затруднительно. Формула Стирлинга позволяет определить приближенное значение для * при больших * : * (3.33)

где * 3,14159, * 2,71828.

3.2. Производящие функции. Z – преобразование. Экспоненциальное Z - преобразование

3.2.1. Производящие функции

При изучении сочетаний было установлено, что функция * тесно связана с числами * , которые являются коэффициентами при * в разложении * по степеням * . В соответствии с этим * называется производящей функцией для биномиальных коэффициентом * .

Дадим общее определение производящей функции. Рассмотрим некоторую последовательность действительных или комплексных чисел: * или * (3.34)

Поставим в соответствие этой последовательности ряд по целым степеням комплексной переменной * :

* (3.35)

Предположим, что существует действительное число * , для которого * (*). В этом случае степенной ряд (3.35) имеет сумму * , которая является аналитической функцией при * : * (3.36) внутри круга сходимости ряда.

Функция комплексного переменного * , являющаяся суммой ряда (3.35), называется производящей функцией последовательности (3.34). Соответствие между числовой последовательностью и ее производящей функцией взаимно однозначно.

Так как последовательность * представляет собой функцию от * , обозначим ее через * . При этом * .

Иногда для последовательности (3.34) вводят производящую функцию другого типа, называемую экспонепнциальной производящей функцией: * (3.37)

Между функциями * и * в круге * также существует взаимно однозначное соответствие. Заметим, что если * то * .

3.2.2. Z – преобразование, его основные свойства

Производящая функция * называется * - преобразованием последовательности * .

* - преобразование приводит к некоторому символическому исчислению, аналогичному операционному исчислению, исходящему из преобразования Лапласа.

Часто в рассматриваемых здесь задачах мы будем понимать * - преобразование лак формальный степенной ряд, не интересуясь его сходимостью. Возникающие на этом пути формальные соотношения и алгоритмы оказываются эффективными в задачах комбинаторного анализа.

Рассмотрим примеры * - преобразования числовых последовательностей * .

Примар 3.15. Пусть * , тогда * , если * .

Таким образом, * .

Пример 3.16. Пусть *** .

Тогда * для *.

Пример 3.17. Пусть * , тогда при * * *

Следовательно, * .

Пример 3.18. Пусть * , тогда * .

Учитывая, что * , а при * получаем: ***

Таким образом, * при *

Обратное * - преобразование состоит в том, чтобы по заданой функции * восстановить последовательность * . Если функцию * разложить в ряд Маклорена, то коэффициент при * в этом разложении * .

Пример 3.19. * ; найти * .

  • * * если * . Следовательно, * , *

Пример 3.20. * ; найти * .

Так как при * , при , т. е. при * . Таким образом, * .

Рассмотрим основные свойства * - преобразования.

  • Если * , то * , т. е. линейной комбинации оригиналов соответствует такая же линейная комбинация их * - образов.

*

*

  • Если *

т. е. запаздыванию оригина на * соответствует умножение * - образа на * .

*

*

  • если * , то *

Это свойство называют теоремой опережения оригинала.

*

В частности *

*. Если * , то *

  • . Если * , то *

  • Последовательность * (3.38)

Называется дискретной сверткой последовательностей * и * .

Если * , то * .

Таким образом, дискретной свертке оригиналов соответствует произведение из * - образов. *

3.2.3. Экспоненциальное * - преобразование, его основные свойства

Экспоненциальным * - преобразованием последовательности * называется производящая функция * .

Пример 3.21. Пусть * , тогда * при * .

Пример 3.22. Если * , то * при * .

Пример 3.23. Пусть * , тогда *

Итак, * ,

Экспоненциальное * - преобразование обладает свойствами, подобными свойствам обычного * - преобразования. Рассмотрим некоторые из них.

* Если * , то * .

  • Если * , то * .

По индукции можно доказать, что **

  • Если * , то * .

  • Если * , то * .

  • Если * , то * .

  • Если * , то * * *.

3.3. Элементы комбинаторного анализа

Метод производящих функций является одним из наиболее эффективных методов решения комбинаторных задач, связанных с составлением из элементов данного множества различных комбинаций, удовлетворяющих тем или иным условиям, и с подсчетом общего числа таких комбинаций. Если производящая функция применяется для перечислення всех комбинаций, обладающих заданными свойствами, то она называется энумератором. Если же производящая функция используется для пересчета общего числа таких комбинаций, то она называется д е н у м е р а т о р о м.

3.3.1. Производящие функции для сочетаний без повторения

Рассмотрим некоторое множество объектов * и каждому о6ъекту А, поставим в соответствие определенное чис­ло * : * .

Схожі:

3 Элементарные методы пересчета выборок icon* в формуле 40) дадут перечисление неупорядоченных к -выборок без повторений, т е. сочетаний без повторений из *
Если заменить числа на объекты, то коэффициенты при в формуле 40 дадут перечисление неупорядоченных к -выборок без повторений, т...
3 Элементарные методы пересчета выборок iconАнализ задачи о разложении спектров фотолюминесценции кристалла znS, легированного ионами mn2+, на элементарные полосы

3 Элементарные методы пересчета выборок icon2. 4 Законы распределения
В разделе 1 мы рассматривали элементарные примеры случайных величин. В случаях с монетой и кубиком говорили о том, что все возможные...
3 Элементарные методы пересчета выборок iconУправление парусно моторным судном (теория)
Приемы и методы уменьшения парусности. Рифление грота, методы, приемы и порядок рифления
3 Элементарные методы пересчета выборок iconОтчет по нир: 44 с., 34 рис., 2 табл., 16 ист. Объекты исследования рабочий процесс вихревых компрессоров
Методы исследования – теоретические методы (термодинамический анализ, математические), физический эксперимент
3 Элементарные методы пересчета выборок iconМетоды лечения в ортодонтии. Биологический и хирургический методы
Эта так называемая индивидуальная форма, или, иначе, вариант нормы. Например, истинная прогнатия и прогения, диастема до 4 мм, тремы,...
3 Элементарные методы пересчета выборок icon616. 093. 2 Пухлик Б. М
В книге в доступной форме изложены методы предупреждения развития аллергических заболеваний, разъясняется необходимость своевременного...
3 Элементарные методы пересчета выборок iconЛекция 3 Тема: Практические методы управления природоохранной деятельностью
Это доминирующие методы во многих странах мира. Одна из самых распространенных форм административного регулирования – введение нормативов...
3 Элементарные методы пересчета выборок iconМетоды и средства терапии и реабилитации
Методы и средства терапии и реабилитации: Конспект лекций / Составитель С. В. Соколов. Сумы: Изд-во СумГУ, 2007. – 117 с
3 Элементарные методы пересчета выборок iconГосударственный стандарт союза сср вода питьевая гост методы определения содержания сульфатов 4389-72
Настоящий стандарт распространяется на питьевую воду и устанавливает методы определения содержания сульфатов
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи