Элементы комбинаторики

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

1. Размещения

 

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

Под множеством понимается некоторая совокупность объектов, объединенных по какому-то общему признаку.

Так, можно говорить о множестве стульев и столов в классе, множестве натуральных чисел, целых, рациональных и действительных (вещественных) чисел.
Объекты, входящие в множество, мы будем называть элементами.
Число 5 является элементом множества натуральных чисел. Стол является элементом множества столов в классе. Обычно множества обозначаются большими латинскими буквами
A, B, C, D, ..., X, Y, Z, а их элементы - малыми буквами a, b, c, d, ..., x, y, z.
О том факте, что a является элементом множества A говорят, что a принадлежит множеству A.
Обычно элементы множества записываются в фигурных скобках 

Пусть нам даны множества A, с уже указанными его элементами, и множество B = {a1, a2, a3, a4}.
Как вы заметили, каждый элемент множества B является и элементом множества A. В этом случае говорят, что B является подмножеством множества A.

Определение. Если каждый элемент множества B является в то же время элементом и множества A, то говорят, что B есть подмножество (часть) A.

Очень часто нам будет важно знать не только элементы множества, но и порядок их расположения в множестве.
Если учитывается порядок расположения элементов в множестве, тогда множества, имеющие одинаковые элементы, но имеющие их разное расположение, будут для нас различными.
Например: Z = {z1, z2, z3, z4 } и B = {z2, z1, z3, z4}будут считаться разными, так как у них различен порядок расположения элементов.

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

Рассмотрим некоторые простые примеры.


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

Для простоты рассуждений обозначим учебные предметы числами от 1 до 12:
1, 2, 3, 4, 5, ..., 10, 11, 12.
По условию задачи, нам необходимо из этих 12 чисел выбирать по 5 чисел. Причем эти наборы из пяти чисел могут отличаться не только числами, но и расположением чисел, например, один из наборов будет: {1, 2, 3, 4, 5}; набор, который получается при перестановке этих же чисел {2, 1, 3, 4, 5}, также будет удовлетворять условию задачи.
В самом деле, пусть первый набор будет состоять из следующих предметов: {алгебра, физика, химия, история, литература}; тогда набор, полученный при перестановке хотя бы двух предметов уже даст новое расписание: {физика, алгебра, химия, история, литература}.
Таким образом, наборы из 5 чисел могут отличаться не только самими числами, но и порядком их расположения.
Такие подмножества называются в комбинаторике размещениями.

Определение. Размещением из n элементов по k называется всякое упорядоченное подмножество данного множества, содержащее k элементов.

О размещениях можно сказать несколько иначе, правда менее строго с математической точки зрения, но более понятно для нас.
Размещением из n элементов по k называется всякое подмножество данного множества, состоящее из k элементов, которое может отличаться не только элементами, но и порядком их расположения.
Например, из множества M = {1, 2, 3, 4} можно образовать 12 различных размещений, из 4 по 2:
{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}
{2, 1} {3, 1} {4, 1} {3, 2} {4, 2} {4, 3}
Число размещений, взятых из n элементов по k, мы будем обозначать символом  и определять по формуле:  = .
Значит,  =  =  =   = 12.
Возвращаемся к примеру 1. В нем, как теперь уже стало ясно, надо найти число размещений из 12 по 5.
По формуле находим:  =  =   
Вычислить число размещений можно другим способом:
= =
Итак,   
Словами можно сказать, что число размещений из n элементов по k равно произведению k элементов  
Например,  
Таким образом, составив процедуру вычисления размещений по этому принципу, мы избегаем недопустимо больших чисел, которые могут образовываться при вычисление факториалов и упрощаем составление программ, а также имеем возможность в дальнейшем применять процедуру размещений в других программах.


Блок-схема процедуры размещений из n элементов по k элементов


Рис. 93

Процедура

Procedure placement(n, k : integer;  var r : longint);
      var
i : integer;
      begin
r := 1;
         for i := 1 to k do r := r*(n - k + i)
      end;

Блок-схема основной программы


Рис. 94


Программа

Program Problem1;
uses WinCrt;
var
n, k, r : longint;
{----------------------------------------------------------------------------------------}
{ Процедура вычисления числа размещений из n по k }
Procedure placement(n, k : integer;  var r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
end;
{----------------------------------------------------------------------------------------}
      begin
write("Введите число всех предметов "); readln(n);
write("Введите число уроков в день "); readln(k);
placement(n, k, r);
writeln("Число вариантов расписания равно ", r)
end.

Пример 2. Сколько различных четырехзначных чисел можно написать при помощи цифр 0, 1, 2, ..., 9?

Рассуждения могут быть очень простыми. Нам надо выяснить сколькими способами можно выбрать по 4 цифры из 10, причем важен порядок расположения цифр, так как 1234 и 2134 дают разные числа. Значит необходимо определить число размещений из 10 элементов по 4, .
Но из этого количества чисел мы должны исключить те, которые начинаются цифрой 0, например, 0123, 0213 и т.п. Эти числа уже не будут четырехзначными.
Сколько таких чисел? Да столько, сколько трехзначных чисел получится из 9 цифр (без нуля), т. е. равное числу размещений из 9 элементов по 3, .
Окончательное количество четырехзначных чисел, которые можно составить из 10 цифр равно разности: .

Блок-схема


Рис. 95

Программа

Program Problem2;
uses WinCrt;
var
n, k, a, a1 : longint;
{----------------------------------------------------------------------------------------}
Procedure placement(n, k : integer;  var r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
end;
{----------------------------------------------------------------------------------------}
begin
write("Введите заданное ко-во цифр "); readln(n);
write("Введите ко-во цифр, из скольких составляется число "); readln(k);
placement(n, k , a);
placement(n - 1, k - 1, a1);
writeln("Число различных 4-х знач. чисел, которые можно");
writeln("написать при помощи цифр 0, 1, 2, .., 9 равно ", a - a1)
end.

Задание 1

 

Составьте блок-схемы и программы с использованием процедуры размещений.
1. Сколькими различными способами собрание, состоящее из 40 человек, может выбрать из своей среды председателя, его заместителя и секретаря?


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

Задачи, решаемые с помощью размещений

 

Пример 3. Некто забыл нужный ему номер телефона, который состоит из одной из десяти букв и пяти цифр, но он помнит, что в образовании этого номера участвуют цифры 3, 5, 7, 9. Какое наибольшее количество проб надо сделать, чтобы дозвониться нужному абоненту?

В искомый номер должны войти четыре цифры, которые можно разместить на 5 местах  различными способами, но пятая цифра может быть любой из 10 цифр (0, 1, 2, ..., 9). Поэтому различных телефонных номеров без буквы будет .

Комбинируя эти номера с каждой из десяти букв, получаем:
10 10  .

Блок-схема основной программы


Рис. 96

Программа

Program Problem3;
uses WinCrt;
var
p : longint;
{----------------------------------------------------------------------------------------}


     Procedure placement(n, k : integer;  var r : longint);
var
i : integer;
begin
r := 1;
                for i := 1 to k do r := r*(n - k + i)
           end;
{----------------------------------------------------------------------------------------}
      begin
placement(5, 4, p);
p := 10*10*p;
writeln("Надо сделать ", p, " проб, чтобы дозвониться")
      end.

Пример 4. Сколько размещений из n элементов по m будет начинаться с первого элемента?

Соображения по составлению программы

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

Блок-схема


Рис. 97


Программа

Program Problem4;
uses WinCrt;
       var
p      : longint;
m, n : integer;
{----------------------------------------------------------------------------------------}
       Procedure placement(n, k : integer;  var r : longint);
var
i : integer;
             begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
             end;
{----------------------------------------------------------------------------------------}
       begin
write("Введите число всех элементов "); readln(m);
write("Введите число выбираемых элементов "); readln(n);
placement(m - 1, n - 1, p);
writeln("Число размещений из ", m, " элементов по ", n, ",");
writeln("которые нач. с первого элемента, равно ", p)
       end.

Пример 5. Составлены размещения из 10 элементов по 7 элементов. Сколько из этих размещений будут содержать: а) первый элемент, б) второй и четвертый элементы?

Решение

Во-первых, чем эта задача отличается от предыдущей?
В предыдущей задаче к первому элементу было строгое требование, - он должен находиться в образуемых размещениях обязательно на первом месте.
В этом примере, первый элемент просто должен присутствовать в получаемых размещениях, но совсем необязательно чтобы он находился на первом месте, значит он может занимать любое из 7 мест в получаемых размещениях.
Пронумеруем элементы множества цифрами от 1 до 7, тогда заданное множество элементов может быть записано так: {1, 2, 3, 4, 5, 6, 7}. Первый элемент выбираем из заданного множества, а "незанятые" места обозначим "x". Как видно, получается 7 подмножеств.

Отсюда следует, что его можно расположить в получаемых размещениях   способами.
Во-вторых, после того, как "вытащили” первый элемент из 10 в нем осталось 9 элементов. Из этих 9 надо выбрать и добавить к первому элементу еще 6, чтобы всего получаемых эл. было бы 7. Это можно сделать   способами.

В итого мы имеем количество способов, равное произведению размещений . Продумайте решение пункта б) этой задачи.

Блок-схему и программу составьте самостоятельно

Задание 2

1. Сколько размещений из m элементов по n будет начинаться любым элементом за исключением первого? Составить блок-схему и программу.


2. Составлены размещения из 10 элементов по 7 элементов. Сколько из этих размещений не будет содержать: а) первого элемента, б) третьего и пятого?

Упражнения

 

  1. Сколько можно составить трехзначных чисел из нечетных цифр, если каждую из этих цифр использовать только один раз?
  2. Сколько трехзначных чисел можно составить из всех цифр так, чтобы цифры в числах не повторялись?
  3. Собрание, на котором присутствует 20 человек, избирает в президиум двух человек, один из которых должен быть председателем, а другой - секретарем. Каким числом способов это можно сделать?
  4. Сколько различных слов, каждое из которых содержит 4 буквы, можно составить из букв слова  выборка?
  5. Сколько различных четырехзначных чисел можно написать при помощи цифр 0, 1, 2, ..., 9?
  1. Сколько различных правильных дробей можно составить из чисел 3, 5, 7, 11, 13, 17, 19, 23?

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

 

Пример 6. Каким числом способов 10 человек могут находиться в очереди?

Рассуждая над этой задачей, нам становится понятным, что необходимо 10 элементов (10 человек) разместить на 10 местах в очереди, т.е. необходимо выполнить размещения из 10 элементов по 10 -  , которое равно:
= 10 9 8  ... 3 2 1 = 10!
Размещения из n элементов по n называются перестановками из n элементов. Таким образом, две различные перестановки из n элементов могут отличаться друг от друга не числом элементов, а только порядком расположения элементов.


Определение. Пусть имеется конечное множество M = {a1, a2, ..., an}. Всякое упорядоченное множество, состоящее из n элементов множества M, называется перестановкой этого множества.

Согласно определению, число всевозможных различных перестановок из n элементов равно:

Не забывайте, что принято 0! = 1.
Для решения нашей задачи, надо составить программу с процедурой вычисления факториала числа.

Блок-схема программы


Рис. 98

Программа

Program Problem6;
uses WinCrt;
var
        n, f  : longint;
{----------------------------------------------------------------------------------------}
     Procedure factorial(n : integer;  var f : longint);
var
i : integer;
          begin
f := 1;
if n = 0 then f := 1
else for i := 1 to n do f := f*i
          end;
{----------------------------------------------------------------------------------------}
     begin
write("Введите число элементов множества "); readln(n);
factorial(n, f);
writeln("Десять человек могут находится в очереди ", f, " способами")
     end.

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


2, 3, 4, 5, 9?

Математический алгоритм решения

Четными будут те числа, которые оканчиваются четной цифрой. В данном примере четных цифр две.
Допустим, что одна из четных цифр находится во всех случаях на последнем месте, тогда все получаемые числа будут четными. Сколько таких чисел будет? Их будет столько, сколько перестановок можно сделать из оставшихся 4-х цифр, т. е. 4! Но среди заданных цифр есть еще одна четная. Допустим, что теперь эта вторая цифра находится на последнем месте, тогда снова будут получаться четные числа и их также будет 4!
Окончательное число четных пятизначных чисел равно  
Выполните самостоятельно блок-схему и программу.

Задание 3

 

Сколько пятизначных чисел, кратных 5, можно изобразить цифрами 0, 1, 2, 3, 5?

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

 

Пример 8.Сколько различных слов, каждое из которых состоит из семи букв, можно составить из букв слова "коробок".

В отличие от предыдущего примера здесь не все буквы слова различны (там были все цифры разными). Если бы все буквы были различны, то из них можно было бы составить 7! различных слов.
Однако не все перестановки букв дают новые слова. Очевидно, что перестановка букв "к", так же как и букв "о", между собой не дают нового слова. Следовательно, рассматриваемая задача свелась к тому, чтобы определить число перестановок, в результате которых получается одно и то же слово. Число перестановок буквы "к" между собой, в результате которых получаются одинаковые слова равно 2! После каждой такой перестановки буква "о" может быть переставлена 3! способами. Применяя правило произведения, получим, что каждое новое слово будет повторяться  раз, и поэтому число различных слов, которое можно составить из слова "коробок", равно .
Вообще, пусть дано множество M = {a, b, c, ...}, состоящее из n элементов, из которых элемент a повторяется n1 раз, элемент b - n2 раз, элемент c - n3 раз, ... так, что
Требуется найти число перестановок с заданным числом повторений входящих в него элементов.
Число перестановок в этом случае определяется по формуле:

где Если  то из этой формулы получается: .

Блок-схема


Рис. 99

Программа
Program Problem8;
uses WinCrt;
var
s, k1, k2 : longint;
{----------------------------------------------------------------------------------------}
Procedure factorial(n : integer;  var f : longint);
var
i : integer;
begin
f := 1;
if n = 0 then f := 1
else  for i := 1 to n do f := f*i
end;
{----------------------------------------------------------------------------------------}
begin
factorial(7, s);
factorial(3, k1);
factorial(2, k2);
s := s div (k1*k2);
writeln("Из слова "КОРОБОК" можно составить ", s, " различных слов")
end.


Задание 4

Сколькими способами можно расставить на книжной полке 4 книги по теории вероятностей, 3 книги по теории игр и 2 книги по математической логике, если книги по каждому предмету одинаковые?

4. Сочетания

 

Пусть M - конечное (не обязательно упорядоченное) множество, состоящее из n элементов.

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

Другими словами, в сочетаниях не важен порядок элементов, а важен лишь их состав. Так, например, из множества M = {1, 2, 3, 4} можно составить четыре различных сочетания из 4 по 3: {1, 2, 3}, {1,2,4}, {2, 3, 4}, {1, 3, 4}.
Число различных сочетаний из n элементов по k равно:
Если k = 0, тогда
Учитывая, что число размещений из n элементов по k равно, но
,
можно выразить число сочетаний через число размещений, тогда получим:
.


Пример 9. Дано 10 точек, из которых никакие три не лежат на одной прямой и никакие четыре точки не лежат в одной плоскости. Сколько различных плоскостей можно провести через эти точки?

Из геометрии нам известна аксиома, что через три точки, не лежащие на одной прямой можно провести плоскость и притом только одну.
Поскольку это так, тогда, если плоскость проходит через три точки A, B, C, то через точки B, A, C или C, B, A и т.п., проходит та же плоскость, т. е. порядок расположения трех точек, через которые проходит плоскость не имеет значения. А значит число различных плоскостей, проведенных через каждые три точки из 10 равно числу сочетаний из 10 элементов по 3.
Составим процедуру вычисления числа сочетаний из n элементов по k.
Для этого удобней воспользоваться второй формулой, в которой вычисляется только один факториал числа k. В формуле  их надо вычислять целых три (n!, (n - k)! и k!) и может возникнуть ситуация, когда будут получаться очень большие числа, которые могут выходить за пределы указанного целого типа.
Можно найти и другую формулу для числа сочетаний, в которой можно избежать больших чисел и вычисления факториалов чисел.

.

Итак, пользуемся формулой:   .

В процедуре, в качестве входных формальных переменных будут две переменные n и k, для числа всех элементов и числа выбираемых элементов. Выходной параметр для значения сочетания обозначим c, имя процедуры - Сombination.

Получим: Procedure Combination(n, k : integer; var  с : longint);

Входные параметры имеют тип integer, а выходной - longint, так как значение числа сочетаний может быть даже очень большим числом.
Переменные самой процедуры - i, - переменная для цикла for и p - промежуточная переменная для факториала k!.
В процедуре устанавливаются первоначальные значения для числа сочетаний (c := 1).
Организуется цикл for от 1 до k, в котором в переменную с будет накапливаться произведение, которое и является числом сочетаний из n элементов по k:

                                                     ,                                                     (1)
где  -  знак произведения от 1 до k.

Давайте проверим, будет ли эта формула выдавать нам число сочетаний из n элементов по k. Пусть n = 5, k = 3, тогда по формуле для числа сочетаний будем иметь:

.

а по формуле (1), получаем:

.

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


Блок-схема процедуры вычисления числа сочетаний


Рис. 100

Процедура

Procedure combination(n, k : integer;  var с : longint);
var
i : longint;
      begin
с := 1;
          for i := 1 to k do с := с*(n - k + i) div i
      end;

Для составления программы решения данной задачи, надо в основной программе обратиться к процедуре combination, причем фактические значения переменных будут 10, - общее число точек и 3 - число точек через которые проходит одна плоскость.

Блок-схема основной программы


Рис. 101


Программа
Program Problem9;
uses WinCrt;
var
pl : longint;
{----------------------------------------------------------------------------------------}
      Procedure combination(n, k : integer;  var c : longint);
           var
i : longint;
            begin
c := 1;
                 for i := 1 to n - k do c := c*(n - k + i) div i
            end;
{----------------------------------------------------------------------------------------}
      begin
combination(10, 3, pl);
writeln("Число плоскостей равно: ", pl)
      end.

Пример 10. Сколько различных вариантов хоккейной команды можно составить из 9 нападающих, 5 защитников и 3 вратарей, если в состав команды должны войти 3 нападающих, 2 защитника и 1 вратарь?

Алгоритм составления программы

Из 9 нападающих можно выбрать троих числом способов:  Из 5 защитников можно выбрать двоих  способами. Из 3 вратарей можно выбрать одного  способами. Общее число возможных способов равно произведению числа способов выбора нападающих, защитников и вратарей: .
Блок-схема


Рис. 102


Программа

Program Problem10;
uses WinCrt;
var
h1, h2, h3 : longint;
{----------------------------------------------------------------------------------------}
Procedure Combination(n, k : integer;  var c : longint);
var
i : longint;
begin
c := 1;
for i := 1 to k do c := c*(n - k + i) div i
end;
{----------------------------------------------------------------------------------------}
begin
combination(9, 3, h1);
combination(5, 2, h2);
combination(3, 1, h3);
writeln("Хоккейную команду можно составить ", h1*h2*h3, " способами");
end.

Задание 5

1. Собрание, на котором присутствуют 30 чел., в том числе две женщины, выбирает 4 чел. для работы на избирательном участке. Сколько может встретиться таких случаев, когда в число избранных войдут обе женщины? Составить блок-схему и программу.


2. В лотерее разыгрывается 5 предметов. Всего в урне 100 билетов. Первый подошедший к урне вынимает из нее 5 билетов. Каким числом способов он может их вынуть, чтобы три из них оказались выигрышными? Составить блок-схему и программу.

5. Сочетания и бином Ньютона

 

В математике известна формула бинома (двучлена) Ньютона. Она используется для возведения двучлена a + b в n-ю степень. Эта формула имеет вид:

Числа  в этой формуле называются биномиальными коэффициентами. Надо отметить, что биномиальные коэффициенты образует треугольник Паскаля. Этот треугольник имеет вид:
1
1       1
1      2      1
1     3       3      1
1     4      6      4       1
1     5     10     10      5      1
1     6     15     20     15      6      1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Его можно записать иначе и сразу обозначить строки треугольника:


Номера строк.                  Треугольник Паскаля.

       0                                        1
1                                        1   1
2                                        1   2    1
3                                        1   3   3   1
4                                        1   4   6   4   1
5                                        1   5   10  10   5   1
. . .                                      . . . . . . . . . . . . . .
n                                      

Пример 11. Вычислить сумму пяти средних элементов девятой строки треугольника Паскаля.

Всего в девятой строке треугольника Паскаля 10 элементов. Пять средних элементов будут находиться начиная с третьего места и по 7-е место.
Эти элементы будут следующими: .

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

Блок-схема


Рис. 103


Программа

Program Problem11;
uses WinCrt;
var
s, j, s1 : longint;
{----------------------------------------------------------------------------------------}
      Procedure Combination(n, k : integer;  var c : longint);
var
i : longint;
            begin
c := 1;
                for i := 1 to k do c := c*(n - k + i) div i
            end;
{----------------------------------------------------------------------------------------}
      begin
s := 0;
for j := 2 to 6 do
begin
combination(8, j, s1);
s := s + s1
         end;
writeln("Сумма пяти средних элементов 9-й строки равна ", s)
      end.

Пример 12.Составить программу вывода на экран n заданных строк треугольника Паскаля.

Понятно, что для вывода строк треугольника Паскаля на экран необходимо организовать два цикла for. Один - по числу строк, второй - по числу элементов в каждой строке.
Первый, внешний цикл, для числа строк должен быть организован от 0 до n, пусть с переменной j1.
Второй, внутренний цикл, надо организовать от 0 до j1. Это легко объясняется тем, что в каждой строке должно быть на 1 больше элементов, чем номер ее строки. В нулевой строке 1 элемент, в 1-й 2 элемента, во 2-й три элемента и т. д., в n-й строке будет n + 1 элементов. Такое вызвано тем, что элементы начинают нумероваться с нуля.


Блок-схема


Рис. 104

Программа

Program Problem12;
uses WinCrt;
var
j, j1, n, p : longint;
{----------------------------------------------------------------------------------------} 
   Procedure Combination(n, k : integer;  var c : longint);
 var
i : longint;
         begin
c := 1;
            for i := 1 to k do c := c*(n - k + i) div i
         end;
{----------------------------------------------------------------------------------------}
    begin
write("Введите число строк треугольника Паскаля "); readln(n);
writeln("Треугольник Паскаля ");
for j1 := 0 to n do
         begin
for j := 0 to j1 do
         begin
combination(j1, j, p);
write(p, " ")
               end;
writeln
         end
    end.

Задание 6

 

Составить программу вычисления суммы четырех средних членов десятой строки треугольника Паскаля.

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

Каждый выбор карт из колоды есть выбор 10-множеств из 52 множеств. Это может быть сделано   способами.
Найти число способов, когда среди выбранных карт есть хотя бы один туз, на первый взгляд сложнее - надо разбирать случаи, когда есть ровно один туз, ровно два туза, ровно три туза, ровно четыре туза. Но проще найти сначала, в скольких случаях среди выбранных карт нет ни одного туза - во всех остальных случаях будет хотя бы один туз. Но если среди выбранных карт нет ни одного туза, то выбор совершался не из 52, а из 48 карт (всех карт, кроме тузов), а потому число таких выборов равно . Следовательно, хотя бы один туз будет в   случаях.
Чтобы найти, в скольких случаях будет ровно один туз, разобьем операцию выбора карт на две - сначала выбирают из четырех тузов один туз - это можно сделать  способами. А потом из оставшихся 48 карт выберем 9, что можно сделать   способами.
По правилу произведений получаем, что весь выбор можно сделать  способами.
Наконец, выбор, содержащий четыре туза, можно сделать  способами - надо взять 4 туза и выбрать еще 6 карт из 48.


Блок-схема


Рис. 105

Программа
Program Problem13;
uses WinCrt;
var
t, t1 : real;
{----------------------------------------------------------------------------------------}
Procedure Combination(n, k : integer;  var c : real);
var
i : longint;
begin
c := 1;
                 for i := 1 to k do c := c*(n - k + i)/i
end;
{----------------------------------------------------------------------------------------}
begin
combination(52, 10, t); 
combination(48, 10, t1);
writeln("Хотя бы один туз будет в ", t - t1:12:0, " случаях");
combination(48, 9, t);
combination(4, 1, t1);
writeln("Ровно один туз будет в ", t*t1:12:0, " случаях");
combination(48, 6, t);
writeln("Четыре туза будет в ", t:12:0," случаях")
end.

Обратите внимание! В программе указан тип real переменных t, t1 и в процедуре для числа сочетаний c.
Это вызвано тем, что получаются очень большие числа и целого типа, даже longint, "не хватает" для значения этих переменных.
Тогда результат будет выдаваться значением вещественного числа в экспоненциальной форме. Такой вывод результата не нагляден и не всегда может устраивать пользователя. Поэтому будем применять в программе форматированный вывод результата, с которым вы уже знакомы.
Таким образом, в нашей программе для вывода значений вещественных переменных указано всего 10 позиций, а для дробной части указано 0 позиций, т. е. дробной части при выводе числа не будет.

Задание 7

 

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

* * *

6. Для дополнительных занятий

Пример 14.Сколько всех делителей у числа 210? У числа 30030? У целого числа n?

Первая мысль, которая возникает, - это делить заданное натуральное число на простые числа и подсчитать число простых делителей. Остальные делители получаются всевозможными сочетаниями из простых делителей. Значит, возникает необходимость подсчитать число таких сочетаний, причем сочетания должны быть различными.
Но такой путь является достаточно сложным и долгим. Более простой путь решения можно избрать, если знать следующее математическое утверждение.
Пусть p1, ..., pm - различные простые делители числа q. Если , где - некоторые натуральные числа, тогда число всех делителей числа q (включая 1 и q) равно числу сочетаний с повторениями (кортежей) показателей степеней a1, a2, ..., am, которое, в свою очередь, равно произведению: .
Основываясь на этом предложении составим программу.


Алгоритм для составления программы может быть таким:
1. Определяется число простых делителей, равных 2.
2. Число этих делителей увеличивается на 1 и присваивается переменной s.
3. Определяется число нечетных простых делителей.
4. Для каждого простого нечетного делителя устанавливается их число, увеличивается на 1 и умножается на s.
5. Результат - число всех делителей выводится на экран.

Блок-схема

Рис. 106


Программа

Program Problem14;
uses WinCrt;
     var
s, q, m, j, n : integer;
      begin
write("Введите целое число "); readln(n);
m := n;
q := 0;
s := 0;
while m mod 2 = 0 do
begin
q := q + 1;
m := m div 2
end;
s := q + 1;
j := 3;
q := 0;
while j <= m do
begin
if m mod j =0
then
                           begin
q := q + 1;
m := m div j
                     end;
s := s*(q + 1);
                 if m mod j <> 0 then j := j + 2
end;
writeln("К-во всех делителей числа ", n, " равно ", s)
       end.

Задание 8

 

Во скольких точках пересекаются 15 прямых линий, если четыре из них параллельны между собой и через каждую точку пересечения проходит не более двух прямых?

Библиотека часто встречающихся процедур и функций

 

29. Процедура размещений из n элементов по k элементов.

Procedure placement(n, k : integer;  var r : longint);
var
i : integer;
     begin
r := 1;
      for i := 1 to k do r := r*(n - i + 1)
     end;


30. Процедура числа сочетаний из n элементов по k элементов.

Procedure Combination(n, k : integer;  var c : longint);
var
i : longint;
    begin
c := 1;
       for i := 1 to k do c := c*(n - k + i) div i


    end;

Упражнения

 

  1. Определить число всех диагоналей 5-, 8 -, 12 - и 15 - угольников?
  2. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для участия в состязаниях. Сколькими способами можно это сделать?
  3. У одного человека есть 7 книг по информатике, а у другого - 9 книг. Сколькими способами они могут обменяться друг с другом по две книги?
  4. Для премий на олимпиаде по информатике выделено 3 экземпляра одной книги, два экземпляра другой и один экземпляр третьей книги. Сколькими способами могут быть вручены премии, если в олимпиаде участвовало 20 человек и никому не дают двух книг сразу? Та же задача, если никому не дают двух экземпляров одной и той же книги, но могут быть вручены две или три различные книги.
  5. Во скольких точках пересекаются 8 прямых линий, если две из них параллельны между собой и через каждую точку пересечения проходит не более двух прямых?
  6. Вычислить сумму четырех крайних членов одиннадцатой строки треугольника Паскаля.
  7. Сколько хорд можно провести через 4 точки, лежащие на одной окружности?
  8. На отрезке AB дано пять точек: C, D, E, F, K. Сколько различных отрезков, включая отрезок AB, получилось при этом?
  9. Сколькими способами группу учащихся из восьми человек можно разбить на две подгруппы, состоящие из трех и пяти учеников.
  10. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну перчатку на правую руку так, чтобы эти перчатки были различных размеров?
  11. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти различных цветов?
  12. Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?
  1. Найти число точек пересечения диагоналей, лежащих внутри выпуклого n-угольника, если никакие три из них не пересекаются в одной точке.

Автор: Тишин Владимир Иванович

Упражнение 08

Упражнение 8 Материал: 4 одинаковых треугольника. Задание: "Возьми два треугольника и сложи из них один. Теперь возьми два других треугольника и сложи из них еще один треугольник, но другой формы. Чем они отличаются? (Один высокий, другой - низкий; один узкий, другой - широкий.) Можно ли сложить из этих двух треугольников прямоугольник? (Да.) Квадрат? (Нет ...

Египетский бог солнца - Ра

РА (Ре), в древнеегипетской мифологии бог солнца, почитался как царь и отец богов. Отождествлялся с богом Амоном. Изображался в облике фараона. Очи бога Ра были одним из влиятельнейших символов в искусстве древнего Египта. Их изображали на саркофагах, бортах лодок, стелах, одеждах и амулетах. Очи Ра жили какой-то странной, независимой от основного организма жизнью. Считалось, например ...

Present continuous

Времена группы 'Continuous' обозначают действие имеющее отношение к определённому моменту. Утвердительная форма настоящего времени группы 'Continuous' образуется путём прибавления 'TO BE' который ставится перед смысловым глагол, a смысловой глагол оканчивается на 'ING' : speak - speaking = говорить - говорит. Если в конце слова 'E' то она отпадает : come - coming = прийти - приходит. Глаголы, употребляющие ...

Canon 15x45 IS binoculars

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