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

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

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

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

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

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

[f(d)]

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

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

½D½= ½D₁½+…+½D_k½.

Рассмотрим множество S всех функций f, обладающих тем свойством, что f постоянна на каждой компоненте; функция может быть различной на различных компонентах, но не обязательно. Такие функции f можно рассматривать как сложные функции f=jy, где j и y определены следующим образом: y – функция отображающая d на индекс той компоненты, которой принадлежит d, так что мы всегда имеем dÎD_y(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. три человека Ч₁, Ч₂, Ч₃ распределяют между собой m фишек так, чтобы Ч₁ получил такое количество фишек, что и Ч₂. Сколькими способами это можно сделать? Мы интересуемся не отдельными фишками, а только тем, сколько фишек получает каждый человек. Иначе говоря, мы хотим получить функции f определенные на множестве D={ Ч₁, Ч₂, Ч₃},с областью значений R={0,1,2,…} и ограничениями f(Ч₁)=f(Ч₂) и f(Ч₁)+f(Ч₂)+f(Ч₃)=m. Положим {Ч₁, Ч₂}=D₁, {Ч₃}=D₂.

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

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

(1 +x²+x⁴+…)(1+x+x²+ …). (13)

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

(1 - x²)^-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(Ч₁)+f(Ч₂)+f(Ч₃)=m. Более того, коэффициент при x^m в (13) равен коэффициенту при x^m в выражении

(1 +x²+x⁴ +…+x^2m)(1+x+x²+ …+x^m).

Дата добавления: 2014-01-06