Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 44 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

член этой по сле до ва тель но сти мо жет быть вы бран лю бым из n спо со -
бов, от ку да по обоб щен но му пра ви лу про из ве де ния и по лу ча ем тре буе -
мую фор му лу.
В даль ней шем для боль шей общ но сти фор мул бу дем счи тать,
что 0!=1.
Ут вер жде ние 2:
A
n
m
= n (n – 1) ... (n – m + 1) = n! / (n – m)!, при n £ m;
A
n
m
= 0, при m > n.
Рас смот рим слу чай, ко гда m £ n (слу чай m > n оче ви ден). Ка ж дое
(n,m)-раз ме ще ние без по вто ре ний яв ля ет ся упо ря до чен ной по сле до ва -
тель но стью дли ны m, чле ны ко то рой по пар но раз лич ны и вы би ра ют ся
из мно же ст ва с n эле мен та ми. То гда пер вый член этой по сле до ва тель но -
сти мо жет быть вы бран n спо со ба ми, по сле ка ж до го вы бо ра пер во го
чле на по сле до ва тель но сти вто рой член мо жет быть вы бран (n – 1) спо -
со ба ми и т.д. Со от вет ст вен но по сле ка ж до го вы бо ра пер во го и так да лее.
(m – 1)-го чле нов по сле до ва тель но сти m-й член мо жет быть вы бран
n – (m – 1) = n – m + 1 спо со ба ми, от ку да по обоб щен но му пра ви лу
про из ве де ния и по лу ча ем тре буе мую фор му лу.
След ст вие: P
n
=
A
n
m
= n (n – 1) ... 1 = n!
Ут вер жде ние 3:
C
n
m
=
A
n
m
/ m! = n! ((n – m)! m), при m £ n;
C
n
m
= 0, при m > n.
Рас смот рим не три ви аль ный слу чай, ко гда m £ n. Ка ж дое (n,m)-со -
че та ние мож но упо ря до чить m! спо со ба ми. Объ е ди не ние по лу чае мых
та ким об ра зом по пар но не пе ре се каю щих ся мно жеств (n,m)-раз ме ще -
ний для всех воз мож ных (n,m)-со че та ний оче вид но, даст все (n,m)-раз -
ме ще ния. То гда по пра ви лу сум мы име ем
A
n
m
=
C
n
m
m! (здесь сум ми ро ва -
ние про из во дит ся по всем (n,m)-со че та ни ям без по вто ре ний), от ку да:
C
n
m
=
A
n
m
/m!.
44
член этой последовательности может быть выбран любым из n спосо-
бов, откуда по обобщенному правилу произведения и получаем требуе-
мую формулу.
      В дальнейшем для большей общности формул будем считать,
что 0!=1.


     Утверждение 2:
     Anm = n (n – 1) ... (n – m + 1) = n! / (n – m)!, при n £ m;

     Anm = 0, при m > n.

      Рассмотрим случай, когда m £ n (случай m > n очевиден). Каждое
(n,m)-размещение без повторений является упорядоченной последова-
тельностью длины m, члены которой попарно различны и выбираются
из множества с n элементами. Тогда первый член этой последовательно-
сти может быть выбран n способами, после каждого выбора первого
члена последовательности второй член может быть выбран (n – 1) спо-
собами и т.д. Соответственно после каждого выбора первого и так далее.
(m – 1)-го членов последовательности m-й член может быть выбран
n – (m – 1) = n – m + 1 способами, откуда по обобщенному правилу
произведения и получаем требуемую формулу.
      Следствие: Pn = Anm = n (n – 1) ... 1 = n!


     Утверждение 3:
     C nm = Anm / m! = n! ((n – m)! m), при m £ n;

     C nm = 0, при m > n.

     Рассмотрим нетривиальный случай, когда m £ n. Каждое (n,m)-со-
четание можно упорядочить m! способами. Объединение получаемых
таким образом попарно непересекающихся множеств (n,m)-размеще-
ний для всех возможных (n,m)-сочетаний очевидно, даст все (n,m)-раз-
мещения. Тогда по правилу суммы имеем Anm = C nm m! (здесь суммирова-
ние производится по всем (n,m)-сочетаниям без повторений), откуда:
C nm = Anm /m!.

44

Страницы