Количество комбинаций с ограничениями

[Mihaylo]

Всем привет! Спасибо за отличную помощь в решении предыдущей задачи:
Количество размещений "кактуса" по n (комбинаторная задача)

Сейчас у меня две новые практические задачи. Начну пока с первой задачи, так как вторая посложнее и как бы включает в себя первую.

Задача первая. Имеется массив из $n$ чисел: $x_1, x_2, ..., x_n$. Все числа целые и принимают значения от 0 до $m$, где $m \geqslant 0$. Необходимо пересчитать количество всевозможных комбинаций чисел при условии, что их сумма всегда равна некоторому числу $S$, где $0 \leqslant S \leqslant m\cdot n$.

Псевдорешение.
1. Если не учитывать ограничение $x_i \leqslant m$, то число комбинаций равно
$N = \frac{(n+S-1)!}{S!\cdot(n-1)!}$
2. Если не учитывать ограничение $\sum\limits_{i=1}^{n}x_i =S$, то число комбинаций равно
$N = (m+1)^n$

Нужно найти количество комбинаций, когда действуют оба ограничения.

[ex-math]

Попробуйте через производящие функции. Искомое количество -- коэффициент при $x^s $ в $(1+x+x^2+\ldots+x^m)^n $. Геометрические прогрессии можно свернуть, и в лоб взять соответствующую производную.

[ex-math]

Проверил, там действительно все неплохо получается. Ответ будет

$$\sum_{0\leqslant l\leqslant\min (n,\frac s {m+1})}(-1)^lC_n^lC_{n+s-l (m+1)-1}^{n-1} $$

[Mihaylo]

Я не знаю, верное решение или нет, но для меня это ошеломляющий результат! Я знаком с алгеброй производящих функций, но пока не готов от условия задачи перейти к данному решению...

Хорошо, пока я попытаюсь проверить решений при частных условиях.

[ex-math]

Mihaylo
С конкретными трудностями в переходе от условия к решению Вам здесь всегда помогут справиться.

[Mihaylo]

ex-math писал(а):

Ответ будет

$$\sum_{0\leqslant l\leqslant\min (n,\frac s {m+1})}(-1)^lC_n^lC_{n+s-l (m+1)-1}^{n-1} $$

С учетом того, что

Mihaylo писал(а):

где $0 \leqslant S \leqslant m\cdot n$.

$\frac{S}{m+1}$ всегда меньше $n$.

Поэтому формула чуть упрощается:
$N=\sum\limits_{i=0}^{\left\lfloor\frac S {m+1}\right\rfloor}(-1)^iC_n^iC_{n+s-i (m+1)-1}^{n-1}$

Я погонял эту формулу в Маткаде, вроде теоретически все сходится. Чуть позже попробую ее вывести.

Теперь неплохо бы доказать, что график $N(S)$ имеет максимум при $S=\frac{m\cdot n}{2}$.

[Mihaylo]

Формула плохо поддается анализу из-за наличия сложной суммы и нескольких факториалов. Как можно упростить формулу?
Можно, например, принять, что n и S - очень большие числа... Помогите, пожалуйста.

[Mihaylo]

Еще сложно доказать, что функция $N(S)$ симметрична, т.е. $N(S)=N(m\cdot n-S)$.

[iancaple]

Mihaylo в сообщении #1043304 писал(а):

Теперь неплохо бы доказать, что график $N(S)$ имеет максимум при $S=\frac{m\cdot n}{2}$.

Это легко видно, если вывести другое представление этих чисел, обозначим их $N_n^m(s)$.Заведем таблицу, в которой $s=0,1..$-номер столбца, $n=1,2,...$-номер строки, а $m$ -фиксированное, держим в уме. $N_1^m(s)=1(s\leqslant m)$,так как $x_1=s$ можно взять тогда и только тогда, когда $s\leqslant m$-первая строка заполнена $m+1$ единицами, а дальше нули. Рассмотрим $n$-й элемент $x_n$,принимающий значения от $0$ до $m$, остальные элементы имеют сумму $s-x_n$, ее можно набрать $N^m_{n-1}(s-x_n)$ способами, получили $N^m_n(s)=N^m_{n-1}(s)+...N^m_{n-1}(s-m)$-каждый элемент таблицы равен сумме стоящего над ним и $m$ левее того. Если столько элементов слева нет (таблица кончается)- соответствующие слагаемые считать нулями.
Докажем по индукции усиленное утверждение:график $N^m_n(s)$, как функции от $s$ располагается на своем носителе $0,1...mn$ симметрично, правее $\dfrac{mn}2$ не возрастает, а левее этой (виртуальной, может быть, нецелой) точки не убывает.Доказательство из одного слова "смотри":

(смотреть надо на зеленые клеточки, нижняя это сумма пяти верхних)
Относительно предельных функций для этого распределения(центрированного), мне скорей видится полуволна синусоиды, чем гауссов колокол. Т.к. синусоида -это решение функционального уравнения $f(x)=c_m\left[f(x+\dfrac m2)+f(x-\dfrac m2)\right]$, которому вдали от краев должна удовлетворять производная предельной функции

[ex-math]

Симметричность следует непосредственно из определения. Замена $x_i $ на "дополнительные" $m-x_i $ устанавливает взаимно однозначное соответствие между наборами с суммой $S $ и наборами с суммой $mn-S $.

[Mihaylo]

Спасибо, друзья.

iancaple писал(а):

правее $\dfrac{mn}2$ не возрастает, а левее этой (виртуальной, может быть, нецелой) точки не убывает.

Буду рассматривать этот нюанс более точно: функция имеет максимум в точках $\lfloor\ \frac{m \cdot n}{2} \rfloor$ и $\lceil\ \frac{m \cdot n}{2} \rceil$. Иногда эти точки совпадают.

iancaple писал(а):

Относительно предельных функций для этого распределения(центрированного), мне скорей видится полуволна синусоиды, чем гауссов колокол. Т.к. синусоида -это решение функционального уравнения $f(x)=c_m\left[f(x+\dfrac m{2})+f(x-\dfrac m{2})\right]$, которому вдали от краев должна удовлетворять производная предельной функции

Для практического использования очень выгодно искомую функцию представить как произведение компонентов, потому что потом эта функция логарифмируется... К сожалению, все полученные формулы (прямая, рекурсивная и предлагаемая предельная) дают сумму компонентов.

[Mihaylo]

Вообще я порассуждал и пришел к выводу, что:
1. Сумма S не всегда на практике может быть большой, хотя можно рассматривать и этот частный случай. Во всяком случае благодаря симметричности функции $N(S)$ большие значения S можно привести в соответствие к малым значениям S. Тем более аппроксимацию очень малых S я уже нашел, легко выводится из точной формулы при условии $S\leqslant m$:
$N=\frac{(n+1-S)!}{S!(n-1)!}$
То есть это одно из псевдорешений.
Это частное решение дает красивую конечную формулу, т.е. можно говорить, что для малых и очень больших S решение найдено. Нужно что-то делать с куполом, когда $S=\frac{m}{2}\lim\limits_{n\to\infty}^{}n$.

2. Предельная функция могла бы иметь некоторый экспоненциальный характер. Это понятно, ведь потом логарифмировать.

3. Предельная функция, на мой взгляд, не должна содержать произведение большого количества компонентов, например, n компонентов. В идеале 2-3 компонента.

[iancaple]

Mihaylo в сообщении #1043401 писал(а):

Нужно что-то делать с куполом, когда $S=\frac{m}{2}\lim\limits_{n\to\infty}^{}n$.

Цитата из "КонКретной математики"(1998г, стр.416)

Цитата:

Исследовательские проблемы
56 Докажите, что в некотором широком классе „простых замкнутых выражений" не существует „простого замкнутого выражения" для коэффициента при $z^n$ в $(1+ z + z^2)^n$, как функции от $n$.

Это показывает, что формула ex-math в некотором смысле hi-end.

[ex-math]

Асимптотика при $n\to+\infty$ будет такая

$$N (S)\sim\frac{\sqrt6 (m+1)^n}{\sqrt{\pi nm (m+2)}}\,e^{-\frac {6 (S-nm/2)^2}{nm (m+2)}} $$

Проще всего получить этот результат, используя центральную предельную теорему. Пусть $\xi_1,\dots,\xi_n $ -- независимые дискретные случайные величины, равновероятно принимающие целые значения $0,\dots,m $. Нетрудно посчитать их мат.ожидание и дисперсию. Тогда $N (S)/(m+1)^n $ есть вероятность того, что $\xi_1+\ldots+\xi_n=S $.

[Mihaylo]

Красивая формула, ей-богу! Надо правда осознать, почему при $S=0$ она не дает результат $N=1$... Слишком низкая вероятность у события, когда $n$ случайных чисел равны нулю?

---------------------
Не дожидаясь ответа на очередной вопрос, задаю вторую обещанную задачу.

Задача вторая. Имеется массив из $n$ чисел: $x_1, x_2, ..., x_n$. Все числа целые и принимают значения от 0 до $m$, где $m \geqslant 0$. Необходимо пересчитать количество всевозможных комбинаций чисел при условии, что их сумма всегда равна некоторому числу $S_1$, где $0 \leqslant S_1 \leqslant m\cdot n$, а сумма квадратов равна $S_2$, где $0 \leqslant S_2 \leqslant m^2\cdot n$.