
§ 5.
Посmроеnuе
ct-классuфur.ацuЙ-nеречuслеnllЙ
81
с
учетом
(2.5.
7)
~i
a
можно
записать
в
виде
~ia
=
(М
:
+ Si
m
;)
~~
O
\
Si
=
0,1,2,
...
,l
i' i =
1,2,
...
,
n.
(2.5.8)
Очевидно,
что
для любого
а
Е
А
должно
быть
выполнено
или
n
n.
~
~
i
a
=
~
(M
i
+ S;mi)
~~
o
= 100
;=1
i=
l
n
~S
i
m
i
=
N',
;'
=1
n
N'
= 100 _ ~
М·
д~o
LJ
i·
i=
l
(2.5.9)
(2.5.9)'
Это
позволяет
сформулировать
задачу
в
комбинаторных
тер
минах:
при
заданных
N'
и
m;
требуется
найти
такие
компози
ции
n
чисел
S
l'
S
2'
•••
,
Sш
которые
допускаются
неравенствами
Si
-<
l;, i = 1,2,
...
,
n.
Рассмотрим
множество
Х,
состоящее
из
элементов
n
видов
Х
1
,
Х
2
,
•••
,
Х
n
•
Каждой
интересующей
нас
композиции
чисел
S~,
S; , ... ,
S~
можно
привести
во
взаимно
однозначное
соот
ветствие
N'
-сочетание
с
повторениями
вида
'---v----' '---v----'
m,S;
р пз
тnБ
n
раз
(2.5.10)
--
-
--------v-'------------'
N'
раз
Наша
задача
сводится
к
перечислению
N'
-сочетаний
с
повто
рениями,
где
элеме.llТ
Xi,
i = 1,2,
...
,
n,
может
встречаться
О,
mi,
...
, lim·
раз.
Для
таких
сочетаний
известна
производя
щая
функция
n
т;
2т;
li
mi
<р
=
п
[1 + (Xit) +
(X
i
t)
+ ... + (Xit)
J.
(2.5.11)
;=
1
Эта
функция
обж3.дает
таким
свойством,
что
если
в
(2.5.11)
про
извести
пере
мно
жение
и
представить
(2.5.11)
в
виде
то
интереСУIfi)щие
нас
N'
-сочетания
будут
даваться
в
явном
виде
фующиейjN'
из
(2.5.11)'.
Положим,
что
(2.5.10) -
одно
6
Г
еон
О!
ин
и
математика