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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

78
На карусели катаются n ребят. Они решили пересесть таким образом,
чтобы впереди каждого оказался другой, чем был раньше. Сколькими спо-
собами они могут это сделать?
Эта задача похожа на предыдущую, но теперь число запрещенных пар
равно n: (1, 2), (2, 3), ..., (n – 1, n), (n, 1). Кроме того, перестановки, полу-
чаемые друг из друга пересадкой по кругу , считать не будем
. Поэтому из k
элементов, можно сделать P
к
= = (k – 1)! существенно различных переста-
новок.
В этой задаче могут быть все n пар, так как C
1
n
= n], а перестановок
всего C
1
n
P
n–2
. По формуле включения–исключения получаем
Q
n
= P
n–1
– C
1
n
P
n–2
+ C
2
n
P
n–3
– ... +
+ (–1)
n–1
C
1-n
n
P
0
+ (–1)
n
C
n
n
. (20)
Исходя из формулы (17) мы берем n пар, а не (n – 1), но так как следу-
ет учитывать вращение, то P
n–1
, а не P
n
. Формула смещения в общем виде
записывается следующим образом:
E
n
= P
n
– C
1
1-n
P
n–1
+ C
2
1-n
P
n–2
– C
3
1-n
P
n–3
+ ... +
+ (–1)
n–1
C
1-n
1-n
P
n
.
Упражнения 3.9
1. Сколькими способами можно переставить буквы слова “логарифм”
так, чтобы ни одна буква не осталась на своем месте?
Решение. Используем общую формулу о смещении элементов.
Число D̃
8
перестановок из 8 элементов, при которых ни один элемент
не остается в первоначальном положении
D
~
̃
8
= 8![1 – 1/1! + 1/2! – 1/3! + 1/4! – 1/5! + 1/6! –1/7! + + 1/8!] = . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
Ответ: . . . . . . . . . . 
       На карусели катаются n ребят. Они решили пересесть таким образом,
чтобы впереди каждого оказался другой, чем был раньше. Сколькими спо-
собами они могут это сделать?
     Эта задача похожа на предыдущую, но теперь число запрещенных пар
равно n: (1, 2), (2, 3), ..., (n – 1, n), (n, 1). Кроме того, перестановки, полу-
чаемые друг из друга пересадкой по кругу , считать не будем. Поэтому из k
элементов, можно сделать Pк = = (k – 1)! существенно различных переста-
новок.
      В этой задаче могут быть все n пар, так как C 1 = n], а перестановок
                                               n
       1
всего C Pn–2. По формуле включения–исключения получаем
       n
      Qn = Pn–1 – C 1 Pn–2 + C 2 Pn–3 – ... +
                    n            n
            + (–1)n–1 C n - 1 P0 + (–1)n C n .      (20)
                        n                  n
      Исходя из формулы (17) мы берем n пар, а не (n – 1), но так как следу-
ет учитывать вращение, то Pn–1, а не Pn. Формула смещения в общем виде
записывается следующим образом:
      En = Pn– C 1     Pn–1 + C 2      Pn–2 – C 3       Pn–3 + ... +
                 n -1           n -1             n -1
       + (–1) C n - 1 Pn.
             n–1
                  n -1
      Упражнения 3.9
      1. Сколькими способами можно переставить буквы слова “логарифм”
так, чтобы ни одна буква не осталась на своем месте?
        Решение. Используем общую формулу о смещении элементов.
      Число D̃8 перестановок из 8 элементов, при которых ни один элемент
не остается в первоначальном положении
       ~ ̃8 = 8![1 – 1/1! + 1/2! – 1/3! + 1/4! – 1/5! + 1/6! –1/7! + + 1/8!] = . . . . . .
       D
..................................................................
.
      Ответ: . . . . . . . . . .




                                            78

Страницы