Подсчет двумя способами

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

1 симпатия

Подсказка по (a), попробуй посчитать количество подмножеств A = \{a_1, a_2, \ldots, a_n \} , при том важно не забывать о пустом множестве.

Решение:

С одной стороны

Можно выбрать элемент a_1, а можно и не выбрать – 2 способа;
Можно выбрать элемент a_2, а можно и не выбрать – 2 способа;
\ldots
Можно выбрать элемент a_n, а можно и не выбрать – 2 способа.
Итого: 2^n.

С другой стороны

Наши подмножества имеют мощности 0, 1, \ldots, n, посчитаем их отдельно:
Подмножество из 0 элементов можно выбрать C_{n}^{0};
Подмножество из 1 элементов можно выбрать C_{n}^{1};
\ldots
Подмножество из n элементов можно выбрать C_{n}^{n}.
Итого: C_{n}^{0} + C_{n}^{1} + \ldots + C_{n}^{n}.

3 симпатии

Можете по подробнее написать? Что за подмножества? Мощности подмножест? Было бы чудесно, если бы вы все расписали в деталях.

1 симпатия

Возможно решение этой все прояснит.

Леша поднимается по лестнице из 10 ступенек. За один раз он прыгает вверх на любое количество ступенек. (Может перепрыгнуть все 9 ступенек и оказаться на 10-й, а может 9 раз прыгнуть по одной ступеньке.) Сколькими способами Леша может подняться по лестнице?

Давай пронумеруем ступеньки от 1 до 9 и двумя способами посчитаем ответ.

С одной стороны, Леша может прыгнуть на 1-ю ступеньку, а может и не прыгнуть (2 способа); может прыгнуть на 2-ю ступеньку, а может и не прыгнуть (2 способа); … может прыгнуть на 9-ю ступеньку, а может и нет (2 способа). Пользуемся правилом произведения и получаем, что Леша может добраться до самой верхней ступеньки \underbrace{2 \cdot 2 \cdot 2 \cdots 2}_{9}=2^9 способами.

С другой стороны, Леша может прыгнуть один раз сразу на 10-ю ступеньку (это C_9^0 = 1 способ); может сделать один промежуточный прыжок, после которого прыгнет на 10-ю ступеньку, а для этого ему надо выбрать на какую ступеньку он прыгнет (это C_9^1 = 9 способов); он может сделать два промежуточных прыжка и выбрать для этого две ступеньки из 9-и (это C_9^2 = 36 способов); … и наконец он может сделать 9 промежуточных прыжков, то есть прыгнуть на каждую из 9-и ступенек (это C_9^9 = 1 способ). Пользуемся правилом сложения и получаем, что Леша может добраться до 10-й ступеньки C_9^0 + C_9^1 + C_9^2 + \cdots + C_9^9 способами.

Значит C_9^0 + C_9^1 + C_9^2 + \cdots + C_9^9 = 2^9. Те же самые рассуждения работают и для n ступенек. Ответил на вопрос? :wolf:

5 симпатий

Для пункта (b) попробуй решить задачу

Сколькими способами среди n учеников класса можно составить футбольную команду из s человек, и выбрать среди них r игроков кто будет сидеть на замене?

1 симпатия