42081

Основные понятия комбинаторики

Лабораторная работа

Математика и математический анализ

В появившемся диалоговом окне Мастер функции – шаг 1 из 2 слева в поле Категория указаны виды функции. В поле Функции выбираем функцию ФАКТР . В рабочее поле Число вводим с клавиатуры число переставляемых объектов в примере – 26. В появившемся диалоговом окне Мастер функции – шаг 1 из 2 слева в поле Категория указаны виды функции.

Русский

2013-10-27

2.58 MB

83 чел.

Министерство образования и науки Украины

Национальный технический университет Украины

«Киевский Политехнический Институт»

Факультет социологии и права

Лабораторная работа №1

по теории вероятности

на тему:

«Основные понятия комбинаторики»

Выполнил

Студент 2-го курса

Группы АМ-74

Балашов Дмитрий Валерьевич

Проверила

Бахтина Галина Петровна

Киев 2008

Цель работы

Ознакомится с основными понятиями комбинаторики и способами их решения в программе Microsoft Excel.

Теоретические сведения:

Комбинаторика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики - алгеброй, геометрией, теорией вероятности, и имеет широкий спектр применения, например в информатике и статистической физике.

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд "Рассуждения о комбинаторном искусстве".

ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

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

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

В комбинаторике принято следующее обозначение: если в множестве имеется n элементов, Pn – число перестановок элементов этого множества.

Как вычислить число перестановок? Рассмотрим конкретные множества:

  •  n = 0: P0 = 1 – по определению;
  •  n = 1: P1 = 1;
  •  n = 2: например, есть множество {1, 2}, возможны числа 12 и 21, значит P2 = 2;
  •  n = 3: сколько различных трехзначных чисел можно составить из множества {1, 2, 3}? Начнем с тех, которые начинаются с 1: 123, 132, затем с 2: 213, 231, и с 3: 312, 321. Всего получается 6 чисел. Это значит, что P3 = 6.

Можно предположить, что

                                                           Pn = n × Pn-1                                                         (1.1)

И это действительно так. Доказывается, например, методом математической индукции.

Формула (1.1) называется рекуррентной, так как позволяет вычислять значение очередной величины через предыдущее.

Применяя формулу (1.1) для множества n элементов последовательно, начиная с первого, получим:

Pn = n × (n-1) × (n-2) × … × 3 × 2 × 1 = 1 × 2 × 3 × … × n;

Pn = n! = 1 × 2 × 3 × … × n.

Формула числа перестановок в множестве из n элементов.

Для нахождения числа перестановок в Microsoft Excel используется специальная функция – ФАКТР. Рассмотрим пример нахождения числа перестановок на компьютере.

ПРИМЕР:

P26 = 26

РЕШЕНИЕ:

  1.  Устанавливаем табличный курсор в свободную ячейку, например  в А1. Здесь должно оказаться значение числа перестановок.

  1.  Для получения значения перестановок воспользуемся специальной функцией: нажимаем на панели инструментов кнопку Вставить функцию (fx).

3. 1. В появившемся диалоговом окне Мастер функции – шаг 1 из 2 слева в поле Категория указаны виды функции. Выбираем Математические. 

3. 2. В поле Функции выбираем функцию ФАКТР . Нажимаем кнопочку «ОК».

  1.  Появляется диалоговое окно ФАКТР.

 

В рабочее поле Число вводим с клавиатуры число переставляемых объектов (в примере – 26).

Нажимаем на кнопочку «ОК».

  1.  В ячейке А1 появляется искомое число перестановок – 4,03291E+26

2. Сочетание

Рассмотрим пример. Какие наборы можно составить из различного количества предметов, если всего их 4 – Шампанское, Печенье, Конфеты, Апельсины?

Были составлены наборы из 1 предмета, из 2, из 3, из 4, на основе исходных 4 предметов. Иначе можно сказать: были составлены подмножества из 1, 2, 3, 4 предметов, из 4 элементов данного множества. Такие подмножества называются сочетаниями.

По 1 предмету

По 2 предмета

По 3 предмета

По 4 предмета

Ш

Ш, А

Ш, А, П

Ш, А, П, К

А

Ш, К

Ш, А, К

П

Ш, П

П, К, А

К

К, П

П, К, Ш

К, А

П, А

Всего 4

Всего 6

Всего 4

Всего 1

Сочетаниями называются конечные подмножества, составленные из элементов данного множества. Если во множестве элементов – n, а в подмножестве m, то общее количество всех сочетаний обозначается и читается как число сочетаний из n элементов по m.

Очевидно, что n m. Приведем формулу для вычисления числа сочетаний:

 

Для нахождения числа сочетаний в Microsoft Excel используется специальная функция – ЧИСЛКОМБ.

В функции ЧИСЛКОМБ (число; число_выбранных) должны быть заданы следующие параметры:

  •  число – это число объектов n;
  •  число_выбранных – это число объектов в каждой комбинации m.

Рассмотрим пример нахождения числа сочетаний на компьютере.

ПРИМЕР:

РЕШЕНИЕ:

  1.  Устанавливаем табличный курсор в свободную ячейку, например  в А1. Здесь должно оказаться значение числа перестановок

.

  1.  Для получения значения числа сочетаний воспользуемся специальной функцией: нажимаем на панели инструментов кнопку Вставить функцию (fx).

3. 1. В появившемся диалоговом окне Мастер функции – шаг 1 из 2 слева в поле Категория указаны виды функции. Выбираем Математические. 

3. 2. Справа в поле Функции выбираем функцию ЧИСЛКОМБ . Нажимаем кнопочку «ОК».

4. Появляется диалоговое окно ЧИСЛКОМБ.

В рабочее поле Число вводим с клавиатуры число объектов n (в примере – 36). В рабочее поле Число_выбранных вводим с клавиатуры число объектов, которые необходимо выбрать, m (в примере – 2). Нажимаем на кнопочку «ОК».

= 630

3. Размещение

Допустим, что есть ткань трех цветов: Красная, Синяя, Белая. Какие сочетания по 2 цветам можно составить? Следующее:

{К; С}, {С; Б}, {К; Б}

А сколько различных двухцветных флагов можно составить?

К

С

С

Б

К

Б

С

К

Б

К

Б

К

В данном случае подмножеств, состоящих из элементов «красная» и «синяя»,  два, поскольку каждое из них представляет свою расцветку флага:

Красная

Синяя

Синяя

Красная

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

Размещениями называются конечные упорядоченные подмножества из элементов данного множества. Общее количество размещений обозначается как:   и читается: число размещений из n по m (nm).

Приведем формулы для вычисления числа размещений:

Рассмотрим оба способа нахождения числа размещений на компьютере с помощью программы Microsoft Excel.

ПРИМЕР:

РЕШЕНИЕ (способ №1):

  1.  Устанавливаем табличный курсор в свободную ячейку, например А1

  1.  Находим число сочетаний. Нажимаем на панели инструментов кнопку Вставить функцию (fx).

  1.  1. В появившемся диалоговом окне Мастер функции – шаг 1 из 2 слева в поле Категория указаны виды функции. Выбираем Математические.

3. 2. В поле Функции выбираем функцию ЧИСЛКОМБ . Нажимаем кнопочку «ОК».

4. Появляется диалоговое окно ЧИСЛКОМБ.

5. В рабочее поле Число вводим с клавиатуры число объектов n (в примере – 21). В рабочее поле Число_выбранных вводим с клавиатуры число объектов, которые необходимо выбрать, m (в примере – 2). Нажимаем на кнопочку «ОК».

  1.  Указателем мыши щелкаем в Строке формул после последней скобки формулы =ЧИСЛКОМБ(21;2) и вводим с клавиатуры знак умножения - *. Для получения значения m! Дописываем после знака умножения (*) функцию ФАКТР(2) и нажимаем кнопочку Enter. В ячейке А1 получим желаемый результат  

= 420

РЕШЕНИЕ (способ №2):

  1.  Устанавливаем табличный курсор в свободную ячейку, например А2.

  1.  Для получения значения числа размещения воспользуемся специальной функцией ПЕРЕСТнажимаем на панели инструментов кнопку Вставить функцию (fx)

  1.  1. В появившемся диалоговом окне Мастер функции – шаг 1 из 2 слева в поле Категория указаны виды функций. Выбираем Статистические.

3. 2. Справа в поле Функция выбираем функцию ПЕРЕСТ. Нажимаем на кнопку «ОК»

    4. Появляется диалоговое окно ПЕРЕСТ.

В рабочее поле Число вводим с клавиатуры число объектов n (в примере – 21). В рабочее поле Число_выбранных вводим с клавиатуры число объектов, которые необходимо выбрать, m(в примере – 2).

= 420

ВЫВОД:

В ходе лабораторной работы мы ознакомились с основными  понятиями комбинаторики (такими как: перестановки, сочетания и размещение) и научились вычислять их в программе Microsoft Excel.

Так же привели пример решения каждого из этих способов.


 

А также другие работы, которые могут Вас заинтересовать

39883. Создание Web-страниц 625.5 KB
  Объект исследования: наиболее подходящая программа для создания Webстраниц. Цель работы: создание Webстраниц. В дипломной работе выполнено: обзор программ для создания Webстраниц; сравнительный анализ Macromedia Dreamweaver и Front Page; описан процесс создания и разработки современного сайта; оценка экономической целесообразности использования персонального компьютера; правила охраны труда на рабочем месте оператора компьютерного набора и верстки. Webсайт Htmlпрограммирование ДИЗАЙН САЙТА FRONT PAGE MACROMEDIA DREAMWEAVER.
39884. Разработать принципиальную схему и текст программы контроллера на основе микропроцессора КР580 42 KB
  Алгоритмическое проектирование Процесс Основной Начало подается 0 на Селектор считывания температуры в основной камере Считывается значение температуры с Заданная температура в основной камере под 1 на Селектор считывания температуры в основной камере М1: сравнивается Заданное значение температуры в основной камере и Значение температуры в основной камере если больше то прыг на М2 иначе подается 0 на Включение основной камеры прыг на М1 М2: ожидаем 2 мин.5 часа то Авария М3: сравнивается Заданное значение температуры в морозильной...
39885. ОФОРМЛЕНИЕ ОБЯЗАТЕЛЬНЫХ УЧЕБНЫХ ДОКУМЕНТОВ 636.5 KB
  2 Примечания следует помещать непосредственно после текстового графического материала или таблицы к которым относятся эти примечания и печатать с прописной буквы с абзаца. Примечание к таблице помещают в конце таблицы над линией обозначающей окончание таблицы. Ссылки на подразделы пункты таблицы и иллюстрации не допускаются за исключением подразделов пунктов таблиц и иллюстраций данного документа Ссылка заключается в квадратные скобки [ ] содержит порядковой номер документа в СПИСКЕ ЛИТЕРАТУРЫ указание страниц. Сноски помещают с...
39886. Разработка программного обеспечения для ведения финансовой отчетности Кировской территориальной избирательной комиссии 309 KB
  Во всех территориальных избирательных комиссиях на постоянной штатной основе работают председатели в Мурманской территориальной избирательной комиссии в связи с большим числом избирателей на штатной основе работает и секретарь главные бухгалтеры. Кроме того для обеспечения передачи данных о ходе проводимых избирательных кампаний в вышестоящие избирательные комиссии председателям территориальных избирательных комиссий оперативно подчиняются системные администраторы ГАС Выборы работающие в аппарате Комиссии области. Для обеспечения...
39887. Разработать на основе МПК I8085 контроллер управления, обеспечивающий и поддерживающий определенную температуру (точность: плюс/минус 0.1 С) в холодильной камере, в зависимости от вида продукции для хранения 204.08 KB
  3 Постановка задачи4 Структурная схема устройства5 Общая схема алгоритма.6 Функциональная схема8 Детальная схема алгоритма. Структурная организация устройства Общая схема алгоритма Основная программа Х1: 1 значение с датчиков равно значению с переключателей; 0 – не равно; Х2: 1 – значение датчика больше чем значение переключателей; 0 – меньше: Рис. Общая схема алгоритма работы устройства.
39888. Прохождение практики на Предприятии ОАО «Апатит» 177.73 KB
  Служба эксплуатации контрольноизмерительных приборов и автоматики КИП и А выполняет следующие функции: метрологический надзор; техническое обслуживание; ремонт и настройку контрольноизмерительных приборов и приборов автоматического управления. Цех КИП и А выполняет такие наиболее ответственные работы как ремонт и поверка приборов эксплуатация сложных систем автоматики и др. Внедряет новые системы автоматики осуществляет техническое руководство группами эксплуатации приборов КИП и А в других цехах предприятия организует...
39889. ОПРЕДЕЛЕНИЕ РАВНОВЕСНОЙ ТЕМПЕРАТУРЫ ВОЗДУХА В ОХЛАЖДАЕМОМ ПОМЕЩЕНИИ (НА ПРИМЕРЕ НИЗКОТЕМПЕРАТУРНЫХ ПРИЛАВКОВ И ШКАФОВ) 6.31 MB
  При включении холодильной машины в охлаждаемом помещении устанавливается температура ниже температуры наружного окружающего помещение воздуха. при балансе: При наступлении равновесия между теплопритоками и теплоотводом в камере установится определенная температура называемая равновесной температурой. Не будет теплопритока от грузов и в случае если это камера длительного хранения куда грузы заложены уже давно и их температура стала равна температуре в охлаждаемом помещении. Для ограждения не подверженного действию солнечной радиации:...
39890. Бизнес-план создания ОАО «Мебель Интерьер Центр» 300.5 KB
  Расчетные данные согласно приложениям 16 показывают что предприятие в 2013 году будет иметь стабильный экономический рост: общая выручка от реализации продукции составит 14187 млн. 7663 млн. Темп роста составит 1851; объемы реализации промышленной продукции увеличатся с 45069 млн. в 2012 году до 102270 млн.
39891. Программирование баз данных 29 KB
  Создание модуля данных Доступ к базе данных в системе DELPHI выполняется достаточно просто с использованием богатого набора невизуальных компонентов работы с СУБД. Как правило эти компоненты группируются в создаваемой программе в специальном модуле данных TDtModule. Модуль данных представляет собой хранилище объектов которое позволяет централизованно управлять их работой и отделяет программную логику связанную с базами данных от программного кода выполняющего вычислительные действия и отображение данных на форме.