Математика EN

Тренажёры · Глава 45

Считаем варианты

Правило произведения, перестановки, размещения и сочетания, а на последнем уровне — задачи с повторениями, «шары и перегородки» и включения-исключения.

Как решать

Почти любую задачу на подсчёт вариантов решают два правила: если выбор делается по шагам, варианты на шагах перемножаются; если выбирают одно из нескольких непересекающихся множеств — складываются. Перестановки, размещения и сочетания — частные случаи правила произведения.

По шагам

  1. Разбейте выбор на шаги и посчитайте варианты на каждом. Перемножьте.
  2. Важен ли порядок? Медали, места, цифры числа — важен (размещения); команда, набор, подмножество — нет (сочетания).
  3. Можно ли повторять? С повторениями на каждом шаге столько же вариантов, $n^k$; без повторений их становится на один меньше.
  4. Одинаковые предметы по разным ящикам — «шары и перегородки»: $n$ шаров и $k - 1$ перегородка, выбираем места перегородок.
Из скольких выбираем. Сколько выбираем. В сочетаниях порядок не важен — делим на $k!$ способов упорядочить выбранное. Пример: медали в забеге $14$ бегунов — размещения: $14 \cdot 13 \cdot 12 = 2184$. Раздать $8$ одинаковых конфет $3$ детям: $\binom{10}{2} = 45$.

Где ошибаются

  • Путают, важен ли порядок: «выбрать двух дежурных» — сочетания, «выбрать старосту и заместителя» — размещения.
  • Складывают там, где нужно перемножать: шаги выбора идут подряд — это произведение.
  • В числах забывают, что первая цифра не может быть нулём.
  • В «шарах и перегородках» берут $k$ перегородок вместо $k - 1$.

Пример

Математика

Главы курса

Вступление

  1. 0 Что такое математика

I Числа

  1. 1 Счёт
  2. 2 Ноль и минус
  3. 3 Простые числа
  4. 4 Делимость
  5. 5 Дроби
  6. 6 Корень из двух

II Алгебра

  1. 7 Буквы
  2. 8 Уравнения
  3. 9 Функции и графики
  4. 10 Квадратные уравнения
  5. 11 Системы и неравенства
  6. 12 Степени и логарифмы
  7. 13 Последовательности
  8. 14 Многочлены
  9. 15 Комплексные числа

III Геометрия

  1. 16 Начала Евклида
  2. 17 Треугольник
  3. 18 Теорема Пифагора
  4. 19 Окружность и π
  5. 20 Площадь и объём
  6. 21 Тригонометрия
  7. 22 Векторы
  8. 23 Симметрия
  9. 24 Конические сечения

IV Анализ

  1. 25 Пределы
  2. 26 Производная
  3. 27 Экстремумы
  4. 28 Интеграл
  5. 29 Число e
  6. 30 Ряды
  7. 31 Дифференциальные уравнения
  8. 32 Многие переменные
  9. 33 Ряды Фурье
  10. 34 Комплексный анализ

V Линейная алгебра

  1. 35 Матрицы
  2. 36 Метод Гаусса
  3. 37 Векторные пространства
  4. 38 Собственные векторы
  5. 39 МНК и SVD

VI Структуры

  1. 40 Группы
  2. 41 Остатки и шифры
  3. 42 Кольца и поля
  4. 43 Теория Галуа
  5. 44 Дзета и кривые

VII Случай и данные

  1. 45 Комбинаторика
  2. 46 Графы
  3. 47 Вероятность
  4. 48 Случайные величины
  5. 49 Статистика
  6. 50 Марков и информация

VIII Основания

  1. 51 Логика и множества
  2. 52 Бесконечности
  3. 53 Строгий анализ
  4. 54 Мера и интеграл
  5. 55 Функциональный анализ
  6. 56 Гёдель и Тьюринг

IX Горизонты

  1. 57 Топология
  2. 58 Неевклидовы геометрии
  3. 59 Хаос и фракталы
  4. 60 Передний край