v1 · padrão canônico

Lição 36 — Princípio Fundamental da Contagem

PFC: se uma tarefa tem k etapas independentes com n₁, n₂, …, nₖ opções cada, o total de sequências possíveis é o produto. Princípio aditivo, fatorial e aplicações.

Used in: 1.º ano do EM (15 anos) · Equiv. Math A japonês · Equiv. Klasse 10 alemã

N = n_1 \times n_2 \times \cdots \times n_k

Choose your door

Rigorous notation, full derivation, hypotheses

Строгая формулировка и аддитивный принцип

Мультипликативный принцип (ПФС)

«Если есть $m$ способов сделать одно и $n$ способов сделать другое, то есть $m \cdot n$ способов сделать оба.» — OpenStax College Algebra 2e, §11.5

Формальное обоснование: множество всех последовательностей — это декартово произведение $E_1 \times E_2 \times \cdots \times E_k$ , и $|A \times B| = |A| \cdot |B|$ (доказывается по индукции). ПФС — это в точности этот факт.

Аддитивный принцип

Связка между этапами	Операция
«И» — последовательные независимые этапы	умножение
«ИЛИ» — взаимно исключающие альтернативы	сложение

«Принцип сложения гласит: если в событии $A$ есть $m$ исходов, в событии $B$ есть $n$ исходов, и события $A$ и $B$ взаимно исключают друг друга, то в событии "А или В" есть $m + n$ исходов.» — OpenStax College Algebra 2e, §11.5

Факториал

Дерево возможностей

Дерево решений с $k$ уровнями графически представляет ПФС: каждый узел на уровне $i$ порождает $n_i$ потомков. Общее число листьев равно $n_1 \times n_2 \times \cdots \times n_k$ .

Дерево с 3 вариантами на 1-м уровне и 2 на 2-м: 6 листьев = 3 × 2. ПФС в действии.

Функции и подмножества через ПФС

Общее число функций $f: A \to B$ с $|A| = m,\, |B| = n$ : $n^m$ (каждый элемент из $A$ имеет $n$ независимых образов).
Общее число подмножеств множества $S$ с $|S| = n$ : $2^n$ (каждый элемент включается или исключается).
Инъективные функции $f: A \to B$ ( $m \leq n$ ): $n \cdot (n-1) \cdots (n-m+1) = \frac{n!}{(n-m)!}$ — основа размещений (Урок 37).

Решённые примеры

Example— 1· ПФС с двумя независимыми этапами

Задача: Ресторан предлагает 4 закуски и 6 основных блюда. Посетитель выбирает ровно одну закуску и одно основное блюдо. Сколько различных заказов он может составить?

Стратегия: Выбор закуски и выбор основного блюда независимы — любая закуска сочетается с любым основным. Два последовательных этапа: применяем ПФС.

Решение:

Этап 1 — Закуска: 4 варианта.
Этап 2 — Основное блюдо: 6 вариантов.
ПФС: $4 \times 6 = 24$ различных заказа.

Проверка: Дерево решений: 4 корня (закуски), каждый с 6 листьями (основные). Всего листьев = $4 \times 6 = 24$ . Согласуется.

Источник. OpenStax College Algebra 2e, §11.5 — лицензия CC-BY 4.0.

Example— 2· ПФС с тремя этапами — номерной знак транспортного средства

Задача: Номерной знак в старом стандарте (до Меркосура) состоял из 3 букв, за которыми следуют 4 цифры. При 26 буквах и цифрах 0-9 с повторениями, сколько различных номеров было возможно?

Стратегия: 7 независимых этапов — 3 выбора букв и 4 выбора цифр. Применяем ПФС.

Решение:

Буквы: каждая из 3 позиций имеет 26 вариантов. Подитог: $26^3 = 17\,576$ .
Цифры: каждая из 4 позиций имеет 10 вариантов. Подитог: $10^4 = 10\,000$ .
ПФС: $26^3 \times 10^4 = 17\,576 \times 10\,000 = 175\,760\,000$ .

Проверка: Порядок величины: $\approx 1{,}8 \times 10^8$ . Бразилия имела около 100 миллионов транспортных средств в 2019 году — пространство из $1{,}8 \times 10^8$ номеров было достаточно. Согласуется с историческим фактом, что система работала десятилетиями.

Источник. OpenStax College Algebra 2e, §11.5 — лицензия CC-BY 4.0.

Example— 3· Аддитивный принцип — взаимно исключающие альтернативы

Задача: Ученик хочет вернуться из школы домой на общественном транспорте. Он может взять один из 3 доступных автобусов ИЛИ одну из 2 линий метро, которые проходят по этому маршруту. Сколькими способами он может совершить путь?

Стратегия: Автобус и метро — альтернативные средства (исключают друг друга — берёт один ИЛИ другой, не оба). Применяем аддитивный принцип.

Решение:

Две альтернативы исключают друг друга (ученик использует ровно одно средство транспорта):

$N = 3 + 2 = 5 \text{ способов}$

Внимание: если бы в задаче было «взять автобус И потом метро» (два последовательных этапа), то всего было бы $3 \times 2 = 6$ . Связка «ИЛИ» (альтернатива) даёт сумму; связка «И» (последовательность) даёт произведение.

Источник. Book of Proof, 3rd ed., §3.1 — Richard Hammack, лицензия CC-BY-ND.

Example— 4· Факториал — полное размещение предметов

Задача: Сколькими способами можно расставить 5 различных книг на полке?

Стратегия: Каждое расположение — это перестановка 5 книг. Первый слот имеет 5 вариантов, второй 4, третий 3 и т.д. Это ПФС с убывающим числом вариантов.

Решение:

$N = 5 \times 4 \times 3 \times 2 \times 1 = 5! = 120$

Обобщение: для $n$ различных предметов число размещений в полный ряд — $n!$ . Факториальная функция растёт очень быстро: $10! = 3\,628\,800$ , $20! \approx 2{,}4 \times 10^{18}$ .

Источник. Book of Proof, 3rd ed., §3.1 — Richard Hammack, лицензия CC-BY-ND.

Example— 5· Пароль со смешанными ограничениями — с и без ограничений на 1-й позиции

Задача: Система требует паролей из 6 символов, состоящих из букв нижнего регистра (a-z, 26 вариантов) и цифр (0-9, 10 вариантов) с повторениями. Сколько паролей возможно, если (a) нет дополнительных ограничений; (b) пароль должен начинаться с буквы?

Стратегия: Применяем ПФС прямо в (a). Для (b) зафиксируем ограничение на первый символ перед умножением.

Решение:

(a) Без ограничений: каждая из 6 позиций принимает любой из $26 + 10 = 36$ буквенно-цифровых символов.

$N_a = 36^6 = 2\,176\,782\,336 \approx 2{,}2 \times 10^9$

(b) Первая позиция должна быть буквой: 1-я позиция имеет 26 вариантов (только буквы); остальные 5 позиций имеют 36 вариантов каждая.

$N_b = 26 \times 36^5 = 26 \times 60\,466\,176 = 1\,572\,120\,576 \approx 1{,}6 \times 10^9$

Проверка: $N_b / N_a = 26/36 \approx 0{,}72$ — пароли, начинающиеся с буквы, составляют 72% от всех, что согласуется с $26/36$ букв из 36 всех вариантов.

Источник. OpenStax College Algebra 2e, §11.5 — лицензия CC-BY 4.0.

Exercise list

40 exercises · 10 with worked solution (25%)

Application 27Understanding 6Modeling 6Challenge 1

Ex. 36.1Application
Человек имеет 3 рубашки и 4 пары брюк. Сколькими способами он может выбрать рубашку и пару брюк для одевания?
Solve online
Ex. 36.2ApplicationAnswer key
Меню имеет 5 основных блюд, 3 гарнира и 4 десерта. Сколько различных обедов (1 основное + 1 гарнир + 1 десерт) возможно?
Solve online
Ex. 36.3Application
Сколько трёхзначных паролей (0-9) возможно с повторениями?
Solve online
Ex. 36.4Application
Сколько трёхзначных паролей (0-9) возможно, если цифры не повторяются?
Solve online
Ex. 36.5Application
Сколько целых чисел с 4 цифрами имеют первую цифру, отличную от нуля?
Solve online
Ex. 36.6ApplicationAnswer key
Номерной знак в старом стандарте состоит из 3 букв (A-Z), за которыми следуют 4 цифры (0-9) с повторениями. Сколько различных номеров возможно?
Solve online
Ex. 36.7Application
Общество имеет 8 членов. Сколько различных списков президента, секретаря и казначея могут быть составлены (один человек не может занимать две должности)?
Solve online
Ex. 36.8Application
Три монеты подбрасываются одновременно. Сколько различных результатов возможно?
Solve online
Ex. 36.9Application
Два обычных кубика (грани 1-6) подбрасываются. Сколько упорядоченных пар $(d_1, d_2)$ результатов возможно?
Solve online
Ex. 36.10Application
Сколькими способами можно расставить 5 различных книг на полке?
Solve online
Ex. 36.11ApplicationAnswer key
Сколько анаграмм (переупорядочиваний букв) имеет слово из 4 букв, используя все буквы?
Solve online
Ex. 36.12Application
Сколько подмножеств имеет множество $\{1, 2, 3, 4, 5\}$ (включая пустое множество и само множество)?
Solve online
Ex. 36.13Application
Три разных приза (1-е, 2-е и 3-е место) будут распределены между 5 кандидатами. Каждый кандидат может получить максимум один приз. Сколько различных распределений возможно?
Solve online
Ex. 36.14Application
Сколько бинарных строк (последовательности 0 и 1) длины 10 существует?
Solve online
Ex. 36.15ApplicationAnswer key
Сколько функций $f: \{1, 2, 3\} \to \{a, b\}$ существует?
Solve online
Ex. 36.16Application
5-значное число — палиндром, когда читается одинаково в обе стороны (пример: 12321). Сколько 5-значных палиндромов существует?
Solve online
Ex. 36.17Application
Сколько последовательностей ДНК длины 10 возможно? (Используйте основания A, T, C, G — 4 основания.)
Solve online
Ex. 36.18Application
Сколько чисел с 4 различными цифрами (без повторений) имеют первую цифру, отличную от нуля?
Solve online
Ex. 36.19ApplicationAnswer key
Сколькими способами можно выбрать различных представителя и заместителя в классе из 6 учеников (порядок важен: представитель ≠ заместитель)?
Solve online
Ex. 36.20Application
Тест «истинно или ложно» имеет 4 вопроса. Сколько различных шаблонов ответов возможно?
Solve online
Ex. 36.21ApplicationAnswer key
Сколько целых чисел с 3 цифрами имеют среднюю цифру чётной (0, 2, 4, 6 или 8)?
Solve online
Ex. 36.22Application
Сколько 4-значных паролей начинаются с цифры 1 и заканчиваются цифрой 9?
Solve online
Ex. 36.23Application
Сколько 4-значных ПИНов имеют все различные цифры (без повторений)?
Solve online
Ex. 36.24ApplicationAnswer key
Ученик может вернуться из школы домой на автобусе (3 доступных линии) или на метро (2 линии). Сколькими способами он может совершить путь?
Solve online
Ex. 36.25Understanding
Если $A$ и $B$ — множества с непустым пересечением, какова корректная формула для $|A \cup B|$ ?
Solve online
Ex. 36.26Application
На соревновании 6 спортсменов соревнуются за медали золота, серебра и бронзы (3 разные позиции). Сколькими способами можно составить подиум?
Solve online
Ex. 36.27Application
Сколько анаграмм (переупорядочиваний всех букв) имеет слово из 6 букв, все различные?
Solve online
Ex. 36.28ApplicationAnswer key
Два обычных кубика (грани 1-6) подбрасываются. Сколько упорядоченных пар $(d_1, d_2)$ дают чётную сумму?
Solve online
Ex. 36.29UnderstandingAnswer key
Пароль имеет 6 буквенно-цифровых символов (a-z нижний регистр или 0-9) с повторениями. Выпишите выражение для числа паролей, содержащих по крайней мере одну цифру.
Solve online
Ex. 36.30Understanding
Сколько путей существует в декартовой плоскости от $(0, 0)$ до $(3, 2)$ , двигаясь только вправо $(+1, 0)$ или вверх $(0, +1)$ на каждом шаге?
Solve online
Ex. 36.31Understanding
Сколько целых чисел с 3 цифрами (от 100 до 999) не содержат цифру 0?
Solve online
Ex. 36.32Understanding
В колоде из 52 карт (26 красных, 26 чёрных; 4 короля всего) сколько карт красных или королей? Какая формула применяется и почему?
Solve online
Ex. 36.33Modeling
Алгоритм шифрования AES-128 использует ключи из 128 битов (каждый бит 0 или 1). Сколько различных ключей существует? Обоснуйте, используя ПФС.
Solve online
Ex. 36.34Modeling
Банкомат требует 4-значный ПИН. Сколько различных ПИНов начинаются с цифры 1?
Solve online
Ex. 36.35Modeling
Ресторан предлагает 8 блюд: 3 с мясом и 5 вегетарианских. Вегетарианский посетитель выбирает ровно 1 блюдо. Сколько вариантов у него есть?
Solve online
Ex. 36.36Modeling
Адрес сети IPv4 представлен 32 битами (каждый бит 0 или 1). Сколько различных адресов IPv4 существует?
Solve online
Ex. 36.37Modeling
5 различных книг будут расставлены на полке. 2 из этих книг должны всегда стоять рядом (друг за другом). Сколькими способами можно сделать расположение?
Solve online
Ex. 36.38Modeling
5 различных книг будут расставлены на полке. Сколькими способами книги A и B стоят отдельно (никогда рядом)?
Solve online
Ex. 36.39UnderstandingAnswer key
Пусть $A$ с $m$ элементами и $B$ с $n$ элементами, с $m \leq n$ . Определите число инъективных функций $f: A \to B$ . Обоснуйте ПФС.
Solve online
Ex. 36.40Challenge
Из 5 различных книг (A, B, C, D, E) на полке, сколько расположений существует, где A и B отдельны И C и D отдельны? (Вызов: применить включение-исключение дважды.)
Solve online

Источники этого урока

OpenStax College Algebra 2e — Jay Abramson et al. · OpenStax · 2022 · EN · CC-BY 4.0 · §11.5 (Counting Principles). Первичный источник.
Book of Proof, 3rd ed. — Richard Hammack · 2018, 3rd ed. · EN · CC-BY-ND · Cap. 3 (Counting), §3.1 (Multiplication Principle), §3.2 (Lists and Functions). Первичный источник.
Wikilivros — Matemática elementar / Combinatória — collaborative · PT-BR · CC-BY-SA · PFC, fatorial, применения.