Формула включений и исключений.

Пусть |Ω| - общее количество объектов, а |Ai| - количество объектов, которые обладают свойством i, |A1∩A2| - количество объектов, обладающих свойствами 1 и 2,...,|A1∩...∩An| - количество объектов, обладающих свойствами 1,...,n. Тогда количество объектов, не обладающих ни одним из свойств равно:

Примеры решения задач

В летнем лагере 70 ребят. Из них 27 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок, и хор. Сколько ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке

Решение:

70-27-32-22+10+6+8-3=10.

Ответ: 10 ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке.


Сколько существует натуральных чисел, не превосходящих 1000, которые не делятся ни на 3, ни на 5?

Решение:

Натуральное число, которое делится на 3 можно представить в виде: 3·n, где n - натуральное число. Следовательно, 333 числа делятся на 3.

Натуральное число, которое делится на 5 можно представить в виде: 5·n, где n - натуральное число. Следовательно, 200 чисел делятся на 5.

Натуральное число, которое делится и на 3 и на 5 можно представить в виде: 15·n, где n - натуральное число. Следовательно, 66 чисел делятся на и на 3 и на 5.

1000-333-200+66=533.

Ответ: 533 числа не делятся ни на 3, ни на 5.


Сколько существует натуральных чисел, не превосходящих 1000, которые не делятся ни на 5, ни на 7?

Решение:

Натуральных чисел, которые делятся на 5: 200.

Натуральных чисел, которые делятся на 7: 142.

Числа, которые делятся и на 5 и на 7: 28.

1000-200-142+28=686.

Ответ: 686 чисел, не превосходящих 1000, не делятся ни на 5, ни на 7.


Каждая сторона в треугольнике ABC разделена на 8 равных отрезков. Сколько существует различных треугольников с вершинами в точках деления (точки A, B, C не могут быть вершинами треугольников), у которых ни одна сторона не параллельна ни одной из сторон треугольника ABC?

Решение:

На каждой стороне треугольника 7 точек. Всего можно построить 73 треугольников. У 3·72 треугольников одна из сторон параллельна одной из сторон треугольника ABC, у 3·7 треугольников –  две стороны, у 1 треугольника –  все стороны.

73-3·72+3·7-1=343-147+21-1=216.

Ответ: 216 треугольников.


В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на своё место?

Решение:

Общее количество пересаживаний равно: 30!.

Количество пересаживаний, когда 1 ученик остается на своем месте равно: 29!·(30!/(30-1)!/1!)=29!·30.

Количество пересаживаний, когда 2 ученика остаются на своем месте равно: 28!·30!/(30-2)!/2!=28!·30·29/2!

...

Количество пересаживаний, когда 29 учеников остаются на своем месте равно: 1!·30!/(30-29)!/29!=30.

Количество пересаживаний, когда 30 учеников остаются на своем месте равно: 0!·30!/(30-30)!/30!=1.

30!-29!30+28!·30·29/2!-...-30+1=30!(1-1/1!+1/2!-...-1/29!+1/30!)=30!(1/2!-...-1/29!+1/30!).

Ответ: 30!(1/2!-...-1/29!+1/30!).

 

Читать далее

Размещения и сочетания.

Сколько вариантов подбора четырехзначного кода, состоящего только из цифр? А из букв латинского алфавита? Прочитав данную статью до конца, вы сможете решить данные задачи без проблем. Итак, начнем.

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

Число всех возможных размещений, если все n элементы различны, определяется формулой:

 A=n(n-1)(n-2)...(n-m+1).

Число размещений по m с повторениями из n элементов равно nm. Таким образом: A(c повторениями)=nm.

Примеры:

  1. Сколько способов выбрать старосту и заместителя старосты из 25 кандидатов?
    Решение:
    25•24=600
    Ответ: 600.
  2. Сколькими способами девочка Кристи может разложить 6 кукол по трём ящикам, если каждый ящик может вместить все куклы?
    Решение:
    A=312 =531441
    Ответ: 531441.

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

Число сочетаний из n элементов по m обозначают: С(m,n).

Число всех возможных сочетаний, если все n элементы различны, определяется формулой:

С(m,n)=n!/(m!(n-m)!).

Число сочетаний с  повторениями равно: С(m,n) с повт. = С(m,n+m-1).

Полагают, что С(0,n)=1.

Для количества сочетаний справедливы равенства:

  1. С(m,n)=C(n-m,n),
  2. C(m+1,n+1)=C(m,n)+C(m+1,n),
  3. C(0,n)+C(1,n)+C(2,n)+...+C(n-1,n)+C(n,n)=2(число всех подмножеств множества, состоящего из n элементов равно 2n).

Примеры:

  1. Сколько способов выбрать три лица на три одинаковые должности из 25 кандидатов?
    Решение:
    С(3,25)=25!/(3!(22)!)=(23•24•25)/6=2300
    Ответ: 2300.
  2. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток?
    Решение:
    С(12,10)=С(12,12+10-1)=С(12,21)=21!/(12!(21-12)!)=293930
    Ответ: 293930.
Читать далее

Элементы комбинаторики. Перестановки.

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

В перестановках элементы только переставляют. Поменяв местами любые два элемента множества, мы получим новую перестановку. Количество возможных перестановок множества из n элементов обозначают: Pn.

Алгоритм нахождения перестановок:

  1. Выберем элемент, который будет находиться на первом месте. Количество способов его выбрать равняется количеству элементов. Всего n элементов, значит количество способов тоже n.
  2. Так как первый элемент уже на месте, то количество элементов которые ещё не на месте уменьшается на единицу. На второе место мы можем поставить n-1 элемента.
  3. На третье место n-2 элемента.
  4. На четвертое n-3 элемента.
  5.  ...

n. На n-ое место оставшийся элемент.

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

Pn=n•(n-1)•(n-2)•(n-3)•...•1=n!

n! - произведение n первых натуральных чисел (читается как "эн факториал")

Замечание: 

Пустое множество можно упорядочить только одним способом. Полагают, что 0!=1.

Примеры:

  1. Сколько различных способов выстроиться в ряд компании из 6 человек?

    Решение:

    P6=6•(6-1)•(6-2)•(6-3)•...•1=6!=720.

    Ответ: 720.

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

    Решение:

    P3=3•(3-1)•(3-2)=3!=6.

    Ответ: 6.

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

Pn(n1,n2,n3,...,nk)=n!/(n1!•n2!•n3!•...•nk!)

Примеры:

  1. Сколько различных перестановок букв можно сделать в слове: М,А,Т,Е,М,А,Т,И,К,А?

     Решение:

     Количество букв равно 10.

     Буква М повторяется 2 раза, буква А - 3 раза, буква Т - 2 раза, буквы И и К по одному разу.

     P10(2,3,2,1,1)=10!/(2!•3!•2!•1!•1!)=3628800/(2•6•2•1•1)=151200

    Ответ: 151200.

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

     Решение:

     P6(1,2,3)=6!/(1!•2!•3!)=720/12=60.

    Ответ: 60.

 

 

Читать далее

Элементы комбинаторики. Правило суммы и произведения.

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

Правило суммы: если существует группа из m элементов и отличная от неё группа из n элементов, а требуется выбрать из них всего один элемент, то сделать это можно m+n способами.

Пример:

В гардеробе у Нади 2 платья и 3 костюма. Ей необходимо выбрать наряд для праздника.  Сколько вариантов у нее имеется.

Ответ: 2+3=5.

Правило произведения: если нужно выбрать пару элементов, причем один из группы в m элементов, а другой из группы в n элементов, то сделать это можно  m•n способами.

Пример:

В гардеробе у Маши 10 футболок и 5 шорт. Сколько комплектов Маше можно составить из данной одежды.

Ответ:  5•10=50 комплектов.

Расширенное правило произведения: если существуют n обособленных групп элементов(допустим, в первой m1 элемент, во второй m2 элемента, ... в последней mn элементов) и из каждой такой группы нужно выбрать по одному элементу для составления новой комбинации элементов, то это можно сделать m1•m2•m3•...m способами.

Пример:

У Маши 7 вечерних нарядов, 5 туфель и 6 сумок. Все они идеально подходят друг к другу.  Сколько комплектов можно составить из данной одежды.

Ответ:  7•5•6=210 комплектов.

Читать далее