Перечень функции

Пусть мы имеем конечные множества D и R и хотим рассмотреть множество RD всех отображений D в R. Каждый элемент rÎR имеет вес w(r); поэтому каждая функция fÎ RD имеет вес

W(f)=[f(d)].

Тогда перечень множества RD равен перечню множества R в степени, равной числу элементов множества D:

Перечень RD==½D½. (11)

Это можно увидеть следующим образом. ½D½-я степень может быть записана как произведение ½D½ сомножителей. Если в каждом сомножителе мы выделим один член и возьмем произведение таких членов. То получим один член полного выражения для произведения (которое содержит½R½½D½ членов, т. е. столько, сколько существует способов выбора). Возьмем некоторое взаимно однозначное соответствие между сомножителями в (11) и элементами множества D; благодаря этому соответствию можно сказать, что выбор членов из каждого сомножителя может быть описан отображением f множества D в R. Функция f соответствует член

[f(d)]

из полного разложения для произведения. Так как этот член равен W(f), мы замечаем, что полное произведение равно сумме всех W(f), т.е. равно перечню множества RD.

Оценим теперь перечень некоторого подмножества S множества RD. Пусть D разбито на несколько непересекающихся компонент D1,…, Dk, так что

½D½= ½D1½+…+½Dk½.

Рассмотрим множество S всех функций f, обладающих тем свойством, что f постоянна на каждой компоненте; функция может быть различной на различных компонентах, но не обязательно. Такие функции f можно рассматривать как сложные функции f=jy, где j и y определены следующим образом: y – функция отображающая d на индекс той компоненты, которой принадлежит d, так что мы всегда имеем dÎDy(d), а j – отображение множества {1,…,k} в R. Заметим, что y – фиксированная функция, а j существует ½R½k возможностей.

Справедливо следующее соотношение:

Перечень S=. (12)

Это опять может быть получено при рассмотрении полного разложения произведения. Член этого разложения получается выбором одного члена в каждом сомножителе (12), а это означает выбор отображения j множества{1,…,k} в R. Следовательно, такое отображение даст член

{w[j(1)]}½½… {w[j(k)]}½½=.

Если jy=f, то этот член равен в точности W(f), так как, очевидно,

{w[j(i)]}½½= {j[w(d)]}

и

[f(d)]=W(f).

Таким образом каждая функция fÎS получается в точности один раз. Следовательно, сумма весов W(f) для всех fÎS равна сумме всех членов в разложении произведения (12), что и доказывает справедливость (12).

Пример 14. три человека Ч1, Ч2, Ч3 распределяют между собой m фишек так, чтобы Ч1 получил такое количество фишек, что и Ч2. Сколькими способами это можно сделать? Мы интересуемся не отдельными фишками, а только тем, сколько фишек получает каждый человек. Иначе говоря, мы хотим получить функции f определенные на множестве D={ Ч1, Ч2, Ч3},с областью значений R={0,1,2,…} и ограничениями f(Ч1)=f(Ч2) и f(Ч1)+f(Ч2)+f(Ч3)=m. Положим {Ч1, Ч2}=D1, {Ч3}=D2.

Возьмем переменную x и предадим элементам 0,1,2,…множества R веса 1, x, x2, x3,… соответственно. Таким образом, функции, которыми мы интересуемся, имеют вес xm.

Из (12) перечень всех функций, постоянных на каждом Di, равен

(1 +x2+x4+…)(1+x+x2+ …). (13)

Искомое число есть коэффициент при xm в этом разложении. Поскольку

(1 - x2)-1(1 – x)-1=(1 + x)-1+(1 – x)-2+(1 – x)-1,

то для требуемого числа функций получаем

(m+1) +[1+(-1)m],

т. е. ½m +1, если m четно, и ½m+½, если m нечетно. Легко получить этот результат непосредственно: заметим, что требуемое число может быть интерпретировано как число представлений натурального числа m, в Виде суммы двух натуральных чисел, одно из которых четно.

То, что запас есть бесконечное множество, а перечень – сумма бесконечного ряда, не должно нас особенно волновать. Мы можем обрезать запас, заменив его множеством {0,1,2,…,m}, остальные элементы не будут играть никакой роли в задаче, в силу ограничения f(Ч1)+f(Ч2)+f(Ч3)=m. Более того, коэффициент при xm в (13) равен коэффициенту при xm в выражении

(1 +x2+x4 +…+x2m)( 1+x+x2+ …+xm).