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

Пусть $X$ — множество из трёх элементов. Найти количество

Пусть $A=\left\{ a, b, c, d, e, f, g, h\right\}$. Сколько существует

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

Предположим, что имеется $n$ попарно непересекающихся множеств $A_{1}, A_{2}, \ldots , A_{n}$ и $\left|A_{i}\right|=k_{i}, i=1, \ldots , n$. Доказать, что количество множеств, содержащих не более чем по одному элементу из каждого $A_{i}$, равно $\left(k_{1}+1\right)\left(k_{2}+1\right) \cdots \left(k_{n}+1\right)$.

Пусть $n=p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{r}^{k_{r}}$ — разложение $n$ на простые сомножители. Используя предыдущую задачу, доказать, что количество различных делителей $n$ равно $t(n)=\prod_{i=1}^{r}\left(k_{i}+1\right)$. Доказать, что $n$ является квадратом тогда и только тогда, когда $t(n)$ нечётно.

Число $e$ является суммой следующего ряда: $e=\sum_{i=0}^{\infty } 1 / i!$. Пусть $e_{n}$ — сумма первых $n$ членов этого ряда: $e_{n}=\sum_{i<n} 1 / i!$. Доказать, что $A_{n}$ — общее количество размещений без повторений из $n$ предметов по любому количеству мест $m$, равняется $e_{n} n!$. Сделать вывод, что при больши́х $n$ оно приближённо равно en!.

Доказать тождества:

Доказать с помощью математической индукции формулу бинома Ньютона.

Доказать, что

где $\lfloor x\rfloor$ и $\lceil x\rceil$ означают округление числа $x$ до ближайшего целого вниз и вверх соответственно.

Сколько имеется различных путей на плоскости из точки $(0,0)$ в точку $(x, y)$, проходящих через точки с целочисленными координатами, в которых каждый отрезок единичной длины идёт либо слева направо, либо снизу вверх?

В разложении $\left(1+x^{2}+x^{5}\right)^{15}$ найти коэффициент при $x^{20}$.

Доказать, что количество разбиений $n$-элементного множества на $k$ подмножеств, первое из которых содержит $n_{1}$ элементов, второе $n_{2}$ элементов $, \ldots , k$-е $-n_{k}$ элементов, равно $\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!}$.

Определить, сколько различных слов можно составить из букв слова АБРАКАДАБРА, если каждую букву нужно использовать в точности один раз.

Доказать равенство

Найти количество раздач для каждой из следующих карточных игр.

Преподаватель рассчитывает читать один и тот же курс в течение 20 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год три анекдота, причём этот набор из трёх анекдотов не должен повторяться. Каково минимальное количество анекдотов, которые он должен приготовить?

Известно, что из всех пятиэлементных подмножеств множества $\left\{ 1,2,3, \ldots , n\right\} , n \geqslant 7$, четвёртая часть содержит элемент 7. Определить, чему равно число $n$.

На острове живёт племя туземцев, у которых набор зубов во рту состоит максимально из 30 зубов. При этом на острове нет двух жителей с одинаковыми наборами зубов (наборы одинаковы, если каждый зуб у обоих либо одновременно присутствует, либо одновременно отсутствует). Может ли на этом острове быть больше жителей чем в

Доказать тождество Коши:

Доказать, что число $C_{n}^{k}$ нечётно тогда и только тогда, когда $\rho (k) \subseteq \rho (n)$, где значение функции $\rho (x)$ — это множество двоичных разрядов, которые содержат единицы в двоичной записи числа $x$. Иначе говоря, если в двоичной записи $k$ на каком-то разряде стоит единица, то и в двоичной записи $n$ на этом разряде должна стоять единица. Указание. Использовать индукцию по $n$, представить $n=2^{u}+m$ для $1 \leqslant m \leqslant 2^{u}$ и применить тождество Коши.

Мультимножеством называется неупорядоченный набор элементов, каждый из которых может встречаться в нём сколько угодно раз. Два мультимножества равны, если каждый элемент встречается в них одно и тоже количество раз. Например, мультимножество $\left\{ 1,2,1,3\right\}$ равно мультимножеству $\left\{ 3,1,1,2\right\}$ и не равно мультимножеству $\left\{ 1,2,2,3\right\}$.

Доказать, что количество способов, которыми можно породить $k$ элементное мультимножество, имея $n$ попарно различных элементов и используя каждый из них сколько угодно раз, равно $C_{n+k-1}^{k}$.

Определить, сколько натуральных решений имеет уравнение $x+y+z+u=10$?

Сколько натуральных решений имеет уравнение $x_{1}+\cdots +x_{n}=k$, если $x_{i} \geqslant m$ для всех $i=1, \ldots , n$?

Сколько натуральных решений имеет уравнение $x_{1}+\cdots +x_{n}=k$, если $k \geqslant (n-1) m$ и $x_{i} \leqslant m$ для всех $i=1, \ldots , n$?

В парламенте некой страны имеется 401 место. Сколько имеется вариантов распределения мест в парламенте между тремя партиями, при которых ни одна из них не имеет абсолютного большинства (более половины мест)?

В кондитерском магазине продаются четыре сорта пирожных: заварные, песочные, «картошка» и бисквитные. Сколькими способами можно купить

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

Сколько существует способов расположить $n$ шаров, из них $-m$ чёрных, остальные — белые, в один ряд, чтобы никакие два чёрных шара не оказались рядом?

Доказать тождество $\sum_{2 m \leqslant n+1} C_{n-m+1}^{m}=F_{n+2}$.

На книжной полке стоят $n$ книг. Сколькими способами можно взять $m$ книг, так чтобы не брать соседние книги и книги, стоящие на краях полки?

За круглым столом короля Артура сидят 12 рыцарей. Каждый из них враждует со своими соседями. Нужно выбрать 5 рыцарей, чтобы освободить принцессу. Сколькими способами это можно сделать так, чтобы среди выбранных рыцарей не оказалось врагов?

Решить эту задачу в случае, когда из $n$ рыцарей за столом нужно выбрать $k$ рыцарей.

Доказать принцип включения и исключения в теоретико-множественной форме: если $A_{1}, \ldots , A_{n}$ — это конечные множества, то

Сколько в первой сотне положительных натуральных чисел не делится ни на одно из чисел $2,3,5$? А в первой тысяче чисел?

Определить, сколько целочисленных решений имеет следующая система:

Найти количество перестановок из $n$ элементов, при которых ни один элемент не остаётся в первоначальном положении.

Сколько существует перестановок букв $\left\{ a, c, f, m, p, r, t, x\right\}$, если

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

В олимпиаде по программированию участвуют $n$ студентов. Три человека, занявшие призовые места, получают дипломы первой, второй и третьей степени, ещё пять человек получают одинаковые дипломы лауреатов. Сколько существует различных вариантов награждения?

$n$ девушек водят хоровод. Сколькими различными способами они могут встать в круг?

Пять юношей и пять девушек купили 10 билетов в кино в одном ряду. Сколькими способами они могут занять места, если

Доказать, что количество слов длины $n$ в алфавите из $k$ букв, в которых каждая буква встречается хоть один раз, равно

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