moglobi.ru Другие Правовые Компьютерные Экономические Астрономические Географические Про туризм Биологические Исторические Медицинские Математические Физические Философские Химические Литературные Бухгалтерские Спортивные Психологичексиедобавить свой файл
страница 1

Занятие № 6

Тема: «Факториал. Основные комбинаторные конфигурации»

Цели:


  1. Содействовать формированию знания основных комбинаторных соединений.

  2. Способствовать развитию навыков использования комбинаторных соединений при решении задач.

Структура занятия:

  1. Оргмомент

  2. Проверка домашнего задания

  3. Лекция

  4. Решение задач

  5. Домашнее задание

  6. Подведение итогов

Ход занятия.

  1. Проверка домашнего задания

Определить является ли последовательность нечетных чисел возвратной, если да, то определить ее порядок.

Решение


и1=1, и2=3,…, иn=2 n-1

иn+1=2 (n+1)-1=2 n-1+2= иn+2

иn+2= иn+1+2= иn+1+ иn+1- иn, т.е. возвратная последовательность 2го порядка.

  1. Лекция

Основные положения лекции:

    1. Факториал

    2. Соединение

    1. Размещения без повторений

    2. Размещения с повторениями

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

    4. Сочетания

Факториал

def║ Факториалом называется произведение натуральных чисел от 1 до какого-либо данного натурального числа n.

n!=1  2 … n

Соединения



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

Различаются три главных вида соединений:

Размещения
Перестановки
Сочетания.

Размещения



def║ Размещения - это упорядоченные подмножества данного конечного множества.

Размещения разделяют на размещения с повторениями и размещения без повторений.

Размещения без повторений

def║ Размещения без повторений из n элементов по k - упорядоченные k-множества, состоящие из элементов n- множества.

Обозначение:


Общий вид задач:

Имеется n различных предметов. Сколько из них можно составить расстановок?

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

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



Выразим эту формулу через факториал.



n!=1  2 … n

(n-k)!=1  2 … ( n-k)

Рассмотрим отношение



=

Задача


Нужно выбрать президента общества, вице-президента, ученого - секретаря и казначея. Сколькими способами может быть сделан это выбор, если каждый член общества может занимать лишь один пост? Всего в обществе состоит 25 человек.

Решение


В этом случае нужно найти число размещений (без повторений) из 25 элементов по 4, т.к. на первый пост можно выбрать 25 способами, на следующий – 24, на следующий 23 и на последний 22. Поэтому число способов -

Размещения с повторениями



def║ Размещения с повторениями - кортежи длины k, составленные из элементов n-множества.

Обозначение:

Общий вид задач:

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

Выборки такого рода называются - размещениями с повторениями из n элементов по k. Число всех таких расстановок можно найти по формуле:



= n k

Задача


Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4.

Решение


Т.к. каждая цифра может встречаться в числе неоднократно, то это размещения с повторениями: = 4 3=64.
Перестановки без повторений

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

Обозначение: Pn



Pn==n!

Задача


Сколькими способами можно составить из горизонтальных полос четырехцветный флаг, имея 4 различных цвета

Решение


Первый цвет выбирается 4 способами, 2й – 3, 3й – 2, 4й – 1, т.е

Р4=1234=24
Сочетания

def║ Сочетанием из n по k или неупорядоченной выборкой называется k – подмножество n –множества.

Сочетания, составленные из k элементов, отличающиеся друг от друга составом.

Обозначение:

Пример.


Составим из множества Х={a, b, c, d, e}подмножества из 2х элементов:

{a, b}{a, c}{a, d}{a, e}

{b, c}{b, d}{b, e}

{ c, d}{c, e}

{d, e}

Выведем формулу числа сочетаний. Пусть из n –множества составляют k – подмножества. Упорядочим всеми способами каждое из подмножеств. Количество всех упорядоченных k – подмножеств равно , каждое подмножество можно упорядочить Рk= k! способами (переставить), значит число неупорядоченных подмножеств равно / Рk, т.е.



=

Задача


Сколькими способами можно из колоды карт, содержащей 52 карты, вытянуть 10 карт? В скольких случаях среди этих карт окажется туз? 4 туза?

Решение.




  1. Посчитаем, сколькими способами при выборке не встретилось туза. Это все равно, что выбирали из колоды без тузов, т.е. из 48 карт, , значит в случаях среди выбранных карт окажется туз

  2. Надо взять 4 туза, а остальные 6 карт выбирать из 48, т. о. В случаях среди выбранных карт окажется 4 туза.

Д.з.

        1. В классе изучают 10 предметов, в понедельник – 6 уроков, все уроки различны. Сколькими способами можно составить расписание на понедельник.

        2. Сколько существует двузначных двоичных чисел (из 0 и 1).

        3. Сколькими способами можно расставить на 32 черных полях шахматной доски 12 белых и 12 черных шашек.




Преподаватель

Авдеева Е.В. Белгородский педагогический колледж



страница 1
скачать файл


Смотрите также: