Дискретный анализ - тест 10

Укажите верные равенства о количестве разбиений множества из  элементов на  классов:

 (1)  

 (2) , где  

 (3) , где  

 (4)  

 (5)  

Укажите верное рекуррентное соотношение для числа разбиений:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует разбиений  объектов на  классов, таких что объект с номером  - единственный в своем классе: 

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует разбиений  объектов на  классов, таких что объект с номером  не является единственным в своем классе:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует разбиений из 4 элементов на 2 класса:

Сколько существует разбиений из 5 элементов на 2 класса:

Для любого сюръективного отображения верно, что:

Что соответствует понятию сюръективного отображения в терминах слов длины  в алфавите из  символов:

 (1) всевозможные слова длины , в которых присутствует каждый символ в алфавите 

 (2) всевозможные монотонные слова длины , в которых присутствует каждый символ в алфавите 

 (3) всевозможные слова длины , в которых каждый символ алфавита присутствует не более раз 

 (4) всевозможные слова длины  

Что соответствует понятию сюръективного отображения в терминах размещения объектов по ящикам:

Сколько существует сюръективных отображений из множества, состоящего из  элементов на множество из  элементов:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько сюръективных отображений соответствует каждому разбиению множества  из  элементов на  классов:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует сюръективных отображений из множества, состоящего из 4 элементов на множество из 2 элементов:

Базис в пространстве многочленов образуют:

Укажите верный способ выразить степень переменной через нижние степени переменной:

 (1)  

 (2)  

 (3)  

 (4)  

Укажите верные способы выразить нижнюю степень переменной через степени переменной:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует всевозможных отображений множества, состоящего из  элементов, в множество, состоящее из   элементов:

 (1)  

 (2)  

 (3)  

 (4)  

Довод, согласно которому из равенства нулю полинома конечной степени в бесконечном множестве целых значений  переменной следует равенство полинома нулю для всех вещественных чисел, называют в комбинаторике:

Укажите верное рекуррентное соотношение для чисел Стирлинга II рода:

 (1)  

 (2)  

 (3)  

 (4)  

Числа Белла обозначают:

 (1) количество упорядоченных разбиений множества из элементов на произвольное число классов 

 (2) количество разбиений множества из элементов на фиксированное число классов 

 (4) количество разбиений -множества на произвольное число классов 

Рекуррентное соотношение для чисел Белла имеет вид:

 (1)  

 (2)  

 (3)  

 (4)  

Числа Белла выражаются через числа Стирлинга так:

 (1)  

 (2)  

 (3)  

 (4)  

Чему равно число Белла для множества из 3 элементов:

Укажите выражения, равные количеству размещений  одинаковых объектов по  различным ящикам:

 (1)  

 (2)  

 (3)  

 (4)  

Выразите задачу размещения  одинаковых объектов по  различным ящикам в терминах задачи Муавра:

 (1) представить целое положительное число в виде суммы неотрицательных слагаемых 

 (2) представить целое положительное число в виде суммы неотрицательных слагаемых 

 (3) представить целое положительное число в виде суммы слагаемых 

 (4) представить целое положительное число в виде суммы неотрицательных слагаемых 

Основная задача метода включений-исключений - это:

 (2) подсчет количества объектов, которые обладают ровно из указанными свойствами 

 (3) подсчет количества объектов, которые обладают не менее, чем из указанных свойств 

Основная польза метода включений-исключений состоит в следущем:

 (2) метод позволяет вычислить значение числа  

Формула включений-исключений имеет вид:

 (1)  

 (2)  

 (3)  

 (4)  

Задача о подсчете количества элементов  в объединении трех множеств  решается методом включений-исключений. Укажите возможные списки свойств объектов:

 (1)  

 (2)  

 (3)  

 (4)  

Запишите формулу включений-исключений для трех свойств:

 (1)  

 (2)  

 (3)  

 (4)  

Решение задачи о подсчете количества элементов в объединении трех множеств  с применением метода включений-исключений имеет вид:

 (1)  

 (2)  

 (3)  

 (4)  

В комбинаторике беспорядком называют:

Как в комбинаторике называют задачу, шутливая формулировка которой такова: "В лондонском клубе швейцар выдает шляпы наобум. Какова вероятность того, что ни один посетитель не получит свою шляпу?"

В комбинаторике перестановкой элементов конечного множества  называют:

 (1) запись, где элементы перечислены в произвольном порядке по одному разу 

 (2) взаимнооднозначное отображение множества на себя 

 (3) взаимнооднозначное отображение множества на себя, при котором ни один образ элемента не равен своему прообразу 

Сколько существует перестановок элементов множества , состоящего из  элементов, таких, что ровно , , элементов стоят на своих местах, а остальные  элементов расположены случайно:

 (1)  

 (2)  

 (3)  

 (4)  

Приближенное значение доли беспорядков ко всем перестановкам конечного множества , состоящего из  элементов, равно:

 (1)  

 (2)  

 (3)  

 (4) некоторое выражение, зависящее от - количества элементов множества  

Приближенное значение выражения  равно:

 (1)  

 (2)  

 (3)  

 (4)  

Укажите верное рекуррентное соотношение для числа беспорядков:

 (1)  

 (2)  

 (3)  

 (4)  

Укажите верное рекуррентное соотношение для числа беспорядков:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует беспорядков для множества, состоящего из  элемента, таких, что элемент  стоит на -ом месте, а элемент  - на -ом месте:

 (1)  

 (2)  

 (3)  

 (4)  

Сколько существует беспорядков для множества, состоящего из  элемента, таких, что элемент  стоит на -ом месте, а элемент    НЕ   стоит на -ом месте:

 (1)  

 (2)  

 (3)  

 (4)  

Укажите точное значение числа беспорядков на множестве из  элементов:

 (1)  

 (2)  

 (3)  

 (4)  

Укажите точное значение числа беспорядков на множестве из  элементов:

 (1)  

 (2)  

 (3)  

 (4)  

Формула явного вида для чисел Стирлинга II рода может быть записана как:

 (1) = 

 (2) = 

 (3) = 

 (4) = 

Укажите взимосвязь чисел Стирлинга II рода  и количества сюръективных отображений :

 (1)  

 (2)  

 (3)  

 (4)  

Укажите количество произвольных отображений из множества , в множество :

 (1)  

 (2)  

 (3)  

 (4)  

Укажите количество сюръективных отображений  из множества , на множество :

 (1)  

 (2)  

 (3)  

 (4)  

Количество разбиений  объектов на  непустых класса равно . Вычислите количество сюръективных отображений из множества, содержащего  элементов, на множество, содержащее  элемента:

Количество разбиений  объектов на  непустых класса равно . Вычислите количество сюръективных отображений из множества, содержащего  элементов, на множество, содержащее  элемента:

Система различных представителей:

При построении системы различных представителей:

Система различных представителей:

Что из перечисленного ниже есть система различных представителей для системы подмножеств , , ,  исходного множества :

 (1)  

 (2)  

 (3)  

 (4)  

Что из перечисленного ниже есть система различных представителей для системы подмножеств , , ,  исходного множества 

 (1)  

 (2)  

Что из перечисленного ниже есть система различных представителей для системы подмножеств , , ,  исходного множества 

 (1)  

 (2)  

 (3)  

Система различных представителей для совокупности из  множеств  существует тогда и только тогда, когда:

 (1) пересечение любых множеств из содержит не менее различных элементов, для всех  

 (2) объединение любых множеств из содержит не менее различных элементов, для всех  

 (3) пересечение любых множеств из содержит более различных элементов, для всех  

 (4) объединение любых множеств из содержит более различных элементов, для всех  

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

 (1) среди рассматриваемых множеств существуют пустые множества 

 (2) среди рассматриваемых множеств нет пустых множеств, при этом среди них найдутся два множества, объединение которых состоит из одного элемента 

 (3) объединение всех множеств состоит из элемента 

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

 (1) среди рассматриваемых множеств нет пустых множеств 

 (2) среди рассматриваемых множеств не более пустых множеств 

 (3) различные представители любых множеств из дают не менее различных элементов объединения этих множеств, для всех  

Для совокупности из  множеств  для каждого  последовательно выбрали . Тогда выбранный набор :

Замена представителей - это:

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

 (1) не существует С.Р.П. для исходной совокупности из множеств 

 (2) существует С.Р.П. для исходной совокупности из множеств 

 (3) С.Р.П. для исходной совокупности из множеств может существовать, а может и не существовать 

Система общих представителей - это:

Укажите условие существования системы общих представителей для разбиений  и  :

 (1) множества попарно не пересекаются и множества попарно не пересекаются 

 (2) каждое из множеств и непусто 

 (3) любые множеств содержатся не менее, чем в множествах : 

Понятие системы общих представителей формулируется для:

 (1) множества , представленного в виде разбиений на множества  

 (2) множества , представленного в виде разбиений на множества , и того же самого множества , представленного в виде разбиений на множества  

 (3) множества , представленного в виде разбиений на множества , и того же самого множества , представленного в виде разбиений на множества ,  

 (4) множества , представленного в виде разбиений на множества , и множества , представленного в виде разбиений на множества  

Для системы общих представителей  при разбиениях множества   и  справедливо, для :

 (1) ,  

 (2) , , где - перестановка 

 (3) ,  

 (4) , , где - путь 

Как можно доказать существование системы общих представителей в общем случае:

Укажите возможные ситуации для системы общих представителей  при разбиениях множества   и , для , :

 (1) для каждого из множеств найдется множество такое, что их пересечение не пусто 

 (2) некоторые из множеств попарно пересекаются 

 (3) некоторые из множеств попарно пересекаются