I семестр), группы НИ, НК, НБ, НП

Список вопросов к коллоквиуму

По дисциплине «Дискретная математика» для I курса

I семестр), группы НИ, НК, НБ, НП

1. Определение множества, мощности множества, прямого произведения множеств, подмножества, булеана. Правило суммы и правило произведения. Принцип Дирихле, обобщенный принцип Дирихле.

ОТВЕТ:

Множеством — называется неупорядоченный набор различных элементов. Множества обозначаются большим латинскими буквами A, B, C …

Мощность множества — это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные. Существуют большие, есть меньшие бесконечные множества, среди них счётное множество является самым маленьким.

Подмножество — A x B {(a, b): a ∈ A, b ∈ B

Подмножество — Если каждый элемент множества B является также элементом множества А, множество B называется подмножеством множества А (обозначение - B ⊆ A или A ⊇ B). Согласно этому определению, каждое множество является своим подмножеством (это самое "широкое" подмножество множества).

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

Булеан - Пусть — множество. Множество всех подмножеств множества называется булеаном (также степенью множества, показательным множеством или множеством частей) и обозначается или .

Правило суммы: если объект из множества A можно выбрать m способами, а объект из множества B можно выбрать другими n способами, то выбор "либо из A, либо из B" может быть осуществлен m+n способами.

Правило произведения: если объект из множества A можно выбрать m способами, и после каждого из таких выборов объект из множества B можно выбрать n способами, то выбор "A и B" может быть осуществлен m x n способами.

Принцип Дирихле: если в n ящиков положено более чем n предметов (кроликов), то хотя бы в одном ящике может лежать 2 и более предметов (кролика).

2. Выборка объема r из n элементов, типы выборок. Определение и формулы (с доказательством) для их числа: размещение, размещение с повторением, сочетание, сочетание с повторением, перестановка, мультимножество.

ОТВЕТ:

— Упорядоченная выборка без повторений называется размещением из n элементов по r. A^r_n = n!/(n-r)! – число различных размещений.

—Упорядоченная выборка с повторением называется размещением с повторениями из n элементов по r. A^^r_n = n^r – число различных перестановок с повторением.

—Неупорядоченная (n,r) – выборка без повторений называется сочетанием из n элементов по r. C^r_n = n!/(n-r)!r! – число различных сочетаний.

— Неупорядоченная (n,r) – выборка с повторением называется сочетанием с повторениями из n элементов по r. C^^r_n = C^r_n+r-1 = C^n-1_n+r-1 – число различных сочетаний с повторениями.

— Упорядоченная (n,n) – выборка без повторений называется перестановкой из n элементов по n. P(n)=n! – число различных перестановок.

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

3. Основные тождества, связанные с числом сочетаний (4 тождества с доказательством).

ОТВЕТ:

Предметов из оставшихся r предметов.

4. Бином Ньютона (с доказательством).

ОТВЕТ:

Числа сочетаний С^r_n присутствуют в известной формуле бинома Ньютона, откуда они получили название биномиальных коэффициентов.

5. Свойства биномиальных коэффициентов (5 свойств с доказательством).

ОТВЕТ:

6. Треугольник Паскаля. Свойства треугольника Паскаля (свойство шестиугольника с доказательством).

ОТВЕТ:

Треугольник Паскаля – бесконечная числовая таблица треугольной формы, по боковым сторонам которой стоят 1 и всякое число, кроме этих боковых единиц получается, как сумма двух предшествующих.