Производящая функция [Комбинаторика]

[Whitaker]

Здравствуйте дорогие друзья!
Задачку, которую я чуть ниже напишу была обсуждена здесь и она была решена через формулу включений-исключений. Но теперь мне нужно решить ее, применив производящие функции. Напомню условие задачи:
Дано уравнение $x_1+x_2+...+x_p=m$. Найти число его целых решений, удовлетворяющих неравенствам $0 \leq l \leq x_k \leq n$ ($m, p, l, n$ - заданные целые числа).
Составим производящую функцию: $G(x)=(x^l+x^{l+1}+\dots+x^n)^p$
Преобразуем выражение $G(x)$.

$$G(x)=\Big(x^l(1+x+\dots+x^{n-l}) \Big)^p=x^{pl}\cdot \Big(\dfrac{1-x^{n-l+1}}{1-x} \Big)^p=x^{pl}(1-x^{n-l+1})^p(1-x)^{-p}$$

Первую скобку раскроем по биному Ньютона и получим:
$(1-x^{n-l+1})^p=\sum \limits_{k=0}^{p}C_p^k 1^{p-k}(-x^{n-l+1})^{k}=\sum \limits_{k=0}^{p}(-1)^kC_p^k x^{k(n-l+1)};$
Вторую тоже раскроем и получим:
$(1-x)^{-p}=1-C_p^1 x+C_{p+1}^{2}x^2-C_{p+2}^{3}x^3+\dots+(-1)^kC_{p+k-1}^{k}x^k+\dots;$
Теперь выражение $G(x)$ имеет следующий вид:
$G(x)=x^{pl}\Big(1-C_{p}^{1}x^{n-l+1}+C_{p}^{2}x^{2(n-l+1)}-C_{p}^{3}x^{3(n-l+1)}+\dots+(-1)^p C_{p}^{p}x^{p(n-l+1)} \Big)\times \Big(1-C_{p}^{1}x+C_{p+1}^{2}x^2-C_{p+2}^{3}x^3+...+(-1)^k C_{p+k-1}^{k}x^k+\dots \Big);$
Чтобы получить ответ к задаче нам нужно найти коэффициент при $x^m$
Так как перед скобками стоит $x^{pl}$, то в скобках нам надо всего лишь найти коэффициент перед $x^{m-pl}$ и он равен:
$(-1)^{m-pl}\Big[C_{p+m-pl-1}^{m-pl}-(-1)^{-(n-l+1)}C_p^1 C_{p+m-pl-1-(n-l+1)}^{m-pl-(n-l+1)}+(-1)^{-2(n-l+1)}C_p^2 C_{p+m-pl-2(n-l+1)+1}^{m-pl-2(n-l+1)}+\dots \Big]$
Скажите пожалуйста правильный ли у меня ответ? Дело в том, что в книге ответ немного другой, но я вроде нигде не ошибься. Я несколько раз проверял свое решение.

С уважением, Whitaker.

[svv]

Уважаемый Whitaker!
Совпадает ли Ваш ответ с тем ответом, который был найден раньше с помощью формулы включений-исключений?
Совпадают ли в книге оба ответа для различных способов решения?
Так мы поймём, кто, скорее всего, ошибся.
Конечно, могут быть ещё на вид различные, но эквивалентные представления решения.

[Whitaker]

Уважаемый svv!
Мой ответ, который был получен формулой включений-исключений (можете посмотреть здесь - post506736.html#p506736) не совпадает с ответом, который я получил пр. функцией.
Если честно, в книге есть ошибка.

Whitaker в сообщении #512433 писал(а):

Преобразуем выражение $G(x)$.

$$G(x)=\Big(x^l(1+x+\dots+x^{n-l}) \Big)^p=x^{pl}\cdot \Big(\dfrac{1-x^{n-l+1}}{1-x} \Big)^p=x^{pl}(1-x^{n-l+1})^p(1-x)^{-p}$$

А в книге автор пишет $\dots=x^{pl}(1-x^{n-l+1})^p(1-x)^{p}$
Вы наверное заметили ошибку? Они не ставят минус в степени, а из-за этого потом получается ошибочный ответ у них.

[svv]

Цитата:

Мой ответ, который был получен формулой включений-исключений (можете посмотреть здесь - post506736.html#p506736) не совпадает с ответом, который я получил пр. функцией.

Но если задача одна, то Ваши ответы, полученные двумя способами, должны совпадать, и книга здесь ни при чём.

Или Вы основывались в своем решении на какой-то формуле из книги, и именно она неправильная?

[Whitaker]

Вы правы svv!
Но в этой решенной задаче я вроде никаких ошибок пока, что не нашел
И в той задаче я также ничего ошибочного не нашел

-- Ср дек 07, 2011 15:56:14 --

Уважаемый svv!
После вашего сообщения я нашел одну разницу в задачах.
В этой задаче нужно найти решения уравнения $0 \leq l \leq x_k \leq n$
А в той задаче (можете посмотреть здесь topic51427.html) нужно найти решения уравнения $l \leq x_k \leq n$, где $l$ и $n$ фиксированные натуральные числа.
Вы заметили разницу?

[svv]

Whitaker писал(а):

$(1-x)^{-p}=1-C_p^1 x+C_{p+1}^{2}x^2-C_{p+2}^{3}x^3+\dots+(-1)^kC_{p+k-1}^{k}x^k+\dots;$

Проверим для случая $p=1$. Тогда все биномиальные коэффициенты имеют вид $C_n^n$ и равны $1$. Поэтому из Вашей формулы следует
$\frac 1{1-x}=1-x+x^2-x^3+\dots$
А ведь мы знаем, что
$\frac 1{1-x}=1+x+x^2+x^3+\dots$

[Whitaker]

Вот я слепой несколько раз проверил, но не нашел.
Значит, должно быть $(1-x)^{-p}=1+C_p^1 x+C_{p+1}^{2}x^2+C_{p+2}^{3}x^3+\dots+C_{p+k-1}^{k}x^k+\dots;$
Теперь я напишу каким будет новый ответ после того как напишу его на бумажке

-- Ср дек 07, 2011 16:50:00 --

Уважаемый svv!
Я провёл работу над ошибками и у меня получился такой ответ:
$C_{m-(l-1)p-1}^{m-pl}-C_{p}^{1}C_{m-(l-1)(p-1)-n-1}^{m-pl-(n-l+1)}+C_{p}^{2}C_{m-(l-1)(p-2)-2n-1}^{m-pl-2(n-l+1)}-\dots$

[Whitaker]

Уважаемый svv.
В книге ответ такой:
$C_{m-(l-1)p-1}^{m}-C_p^1C_{m-(l-1)(p-1)-n-1}^{m+l-n-1}+C_p^2C_{m-(l-1)(p-2)-2n-1}^{m+2(l-n-1)}-\dots$

[svv]

Посмотрите на верхний индекс биномиального коэффициента. Там в Вашем ответе стоит слагаемое $-k(n-l+1)$, а в книге $k(l-n-1)$. Они равны. Значит, единственное отличие -- это слагаемое $-pl$, которое в Вашем ответе есть, а в книге нет.

[Whitaker]

Да svv я это тоже заметил
Но не понятно всё-таки у кого ошибка

[svv]

Кстати, поскольку Ваше решение изменилось, начиная с некоторого места, то мы теперь и проверить не можем. А интересно было бы взглянуть на новую формулу $G(x)$, и как из неё получается коэффициент при $x^{m-pl}$ -- чуть подробнее.

[Whitaker]

svv в сообщении #512547 писал(а):

Кстати, поскольку Ваше решение изменилось, начиная с некоторого места, то мы теперь и проверить не можем. А интересно было бы взглянуть на новую формулу $G(x)$, и как из неё получается коэффициент при $x^{m-pl}$ -- чуть подробнее.

svv я Вас не совсем понял

[svv]

Ну, я хочу проверить Ваше решение. А где оно? В первом сообщении -- это устаревший вариант, до исправления ошибок.

[Whitaker]

Уважаемый svv вот измененное решение:
Изначально у нас было: $G(x)=x^{pl}(1-x^{n-l+1})^p(1-x)^{-p}$
Раскладывая первую скобку по биному получим:
$(1-x^{n-l+1})^p=1-C_{p}^{1}x^{n-l+1}+C_{p}^{2}x^{2(n-l+1)}-C_{p}^{3}x^{3(n-l+1)}+\dots+(-1)^pC_{p}^{p}x^{p(n-l+1)};$
Раскладывая вторую скобку в ряд получим:
$(1-x)^{-p}=1+C_{p}^{1}x+C_{p+1}^{2}x^2+C_{p+2}^{3}x^3+\dots+C_{p+k-1}^{k}x^{k}+\dots;$.
Теперь нам нужно найти в выражении $G(x)$ коэффициент, стоящий перед $x^{m}$, но т.к. перед скобками стоит $x^{pl}$, то в скобках нам надо найти коэффициент перед $x^{m-pl}$, а он равен:
$C_{p+m-pl-1}^{m-pl}-C_{p}^{1}C_{p+m-pl-(n-l+1)-1}^{m-pl-(n-l+1)}+C_{p}^{2}C_{p+m-pl-2(n-l+1)-1}^{m-pl-2(n-l+1)}-\dots$

[svv]

Да, в книге ошибка, а у Вас правильно.
1) То, что они забыли поставить минус в показателе степени $(1-x)^{-p}$ -- совершенно очевидно.
2) Возьмем совершенно нормальный случай $l=1$.
Тогда их биномиальный коэффициент $C^{m+k(l-n-1)}_{m-(l-1)(p-k)-kn-1}=C^{m-kn}_{m-kn-1}$, очевидно, будет равен нулю во всех слагаемых, что даст нулевой (неправильный) ответ.