Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 70 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

70
ступеньки из 10: С
5
10
= 10!/5!5! =
= 252 способов.
Варианты построения показаны на рис. 58.
1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0
Рис. 58
В общем случае (если k ступенек, то лестницу можно построить C
k
n+1
способами.
Эта задача похожа на предыдущую: укротитель не может ставить
двух тигров, а строитель – делать ступеньки удвоенной высоты. Но есть
существенное различие: все звери разные, а ступеньки одинаковые, поэто-
му выбор у строителя меньше.
Обобщением задачи о лестнице (лестницу зашифровать с помощью 1
и 0: 1– вертикальная ступенька, 0 – горизонтальная) может быть следую-
щее: сколькими
способами можно расставить n нулей и k единиц, чтобы две
единицы не стояли рядом.
Это можно сделать C
k
n+1
способами.
3.8.2. Ограничения на порядок выбора
Задача 1. На книжной полке стоит 12 книг. Сколькими способами
можно выбрать 5 из них так, чтобы никакие две из них не стояли рядом.
Зашифруем выбор 0 и 1: каждой оставленной книге поставим в соот-
ветствие 0, каждой выбранной – 1. Таким образом, имеем 5 единиц и 7 ну-
лей и задача сводится к предыдущей:
C
5
71+
= C
5
8
.
В общем виде: если стоит n книг, а выбирается k книг, не стоящих ря-
дом, то это можно сделать
k
1k)(n
С
+−
. 
ступеньки      из        10:       С510       =             10!/5!5!    =
                 = 252 способов.
     Варианты построения показаны на рис. 58.
101010      0   1 0   0   0 10   0   101 0 0 1 0 0 1 0 0 1 00




                             Рис. 58

      В общем случае (если k ступенек, то лестницу можно построить Ckn+1
способами.
      Эта задача похожа на предыдущую: укротитель не может ставить
двух тигров, а строитель – делать ступеньки удвоенной высоты. Но есть
существенное различие: все звери разные, а ступеньки одинаковые, поэто-
му выбор у строителя меньше.
      Обобщением задачи о лестнице (лестницу зашифровать с помощью 1
и 0: 1– вертикальная ступенька, 0 – горизонтальная) может быть следую-
щее: сколькими способами можно расставить n нулей и k единиц, чтобы две
единицы не стояли рядом.
      Это можно сделать Ckn+1 способами.

                 3.8.2.     Ограничения на порядок выбора
      Задача 1. На книжной полке стоит 12 книг. Сколькими способами
можно выбрать 5 из них так, чтобы никакие две из них не стояли рядом.
      Зашифруем выбор 0 и 1: каждой оставленной книге поставим в соот-
ветствие 0, каждой выбранной – 1. Таким образом, имеем 5 единиц и 7 ну-
лей и задача сводится к предыдущей:
                                           5      5
                                       C        =C .
                                           7 +1   8

      В общем виде: если стоит n книг, а выбирается k книг, не стоящих ря-
дом, то это можно сделать
                                        k
                                       С(n          .
                                           − k) + 1




                                            70

Страницы