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

[arseniiv]

(После написания сообщения оказалось жутким оффтопом.)

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

Надо правда осознать, почему при $S=0$ она не дает результат $N=1$...

Давайте я подставлю числа за вас.

ex-math в сообщении #1043095 писал(а):

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

$s = 0\Rightarrow{}$

$$\sum_{0\leqslant l\leqslant0} (-1)^l\, C_n^l\, C_{n+s-l (m+1)-1}^{n-1} = (-1)^0\, C_n^0\, C_{n-1}^{n-1} = 1\cdot1\cdot1 = \ldots$$

-- Сб авг 08, 2015 23:03:21 --

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

где $0 \leqslant S_1 \leqslant m\cdot n$, <…> $0 \leqslant S_2 \leqslant m^2\cdot n$

Кстати, незачем так стараться с ограничениями. Они, будучи выбраны естественными, никак особо не помогают (к примеру, при обычном определении $C_n^{k<0}$ или $C_n^{k>n}$ будут просто нулевыми, так что иногда даже некоторые суммы можно для упрощения хотя бы промежуточных выкладок сделать неограниченными); а будь они даже сильнее, они тоже вряд ли бы — если только не совсем сильные и отрезающие по единицам комбинаций — помогли бы упростить вид ответа.

[ex-math]

Mihaylo
По поводу Вашего последнего вопроса. Есть же еще остаточный член асимптотики, вот он и покрывает единицу при $S=0$. С тем же успехом можно удивляться, почему не получается ноль при отрицательных $S $.

-- 08.08.2015, 22:13 --

По поводу второй задачи. Вы можете четче сформулировать, что Вас интересует, точная формула или асимптотика при больших $n $, или, может быть, какие-то особые свойства этого количества? В первой задаче Ваши интересы все время менялись. Вам казалось, что, получив точную формулу, остальное будет просто. Но, как видите, нахождение асимптотики и выяснение некоторых свойств функции не требовало точной формулы, а проводилось совсем иными методами. Так что же конкретно Вас интересует?

[Mihaylo]

arseniiv писал(а):

Кстати, незачем так стараться с ограничениями.

Я с Вами не согласен. Факториалы при отрицательных числах не вычисляются, это во-первых. Во-вторых, именно благодаря ограничению мне удалось упростить формулу в начале топика. Пока не знаю, почему.

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

Так что же конкретно Вас интересует?

Меня интересует полная теория на этот счет: построение точной закономерности и анализ этой закономерности. На самом деле я хоть и разбрасываюсь вопросами о помощи в получении очередной формулы, но я их все старательно записываю и изучаю. Сейчас попробую уже включить мозг, вспомнить по производящим функциям, чтобы вывести первую формулу...

[ex-math]

Так в первой задаче точная закономерность ровным счетом ничего не дала для анализа. Нужна ли она в таком случае?

[Mihaylo]

Численный анализ можно производить, правда факториалы быстро переполняют все регистры.

[arseniiv]

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

Факториалы при отрицательных числах не вычисляются, это во-первых.

Если понимать $C_n^m$ как ровно $\prod_{k=1}^m (n-k+1)/k$, всё прекрасно работает при любом целом $m$ и даже нецелом $n$. Если дело в вычислениях, то по формуле $n!/m!(n-m)!$ биномиальные коэффициенты тоже вычислять невыгодно (вы вот сами написали про факториалы только что), а вот по приведённому определению уже лучше.

[ex-math]

Я полагаю, что предельную функцию можно найти методами мат.статистики. У вас есть выборка $x_1,\dots,x_n. $ Вы хотите проследить за суммой иксов, т.е. за $n\overline{x},$ и за суммой их квадратов, т.е. за $(n-1)s^2+n\overline{x}^2.$ Если бы распределение наших иксов было нормальным, то на этот счет есть теорема Фишера, о том, что величины $\overline{x} $ и $s^2$ независимы, и о том, как именно они распределены. Но у нас иксы имеют дискретное равномерное распределение. Возможно, существует некий асимптотический аналог теоремы Фишера, что при больших $n $ ее утверждение приближенно выполняется для произвольных, не обязательно нормальных выборок. Здесь я Вам уже не смогу помочь. Попробуйте обратиться к вероятностникам, например, к --mS-- или к ShMaxG

-- 09.08.2015, 15:21 --

Что же касается точной формулы, то здесь нужно взять функцию двух переменных $(1+xy+(xy^2)^2+\ldots+(xy^m)^m)^n $ и посчитать от нее производную $S_1$ раз по иксу и $S_2$ раз по игреку в нуле. Здесь уже не геометрическая прогрессия, и я пока не вижу способа привести это выражение в удободифференцируемый вид. Возможно, может помочь формула производной $n $-го порядка сложной функции (формула Фаа-ди-Бруно).

[iancaple]

1.Если $S_1$ четно, то и $S_2$, и наоборот.То есть число вариантов для пар $(S_1,S_2)$ разной четности равно 0
2.Если $S_1^2>nS_2$, тоже независимо от остальных данных, число вариантов равно 0, по неравенству Коши-Буняковского.
3.Если $n=3$, а $S_2$ при делении на 8 дает остаток 7, то это число не может быть представлено в виде суммы трех квадратов, число вариантов равно 0. А вот в виде суммы четырех квадратов целых чисел- представимо любое неотрицательное целое.
И "будущая асимптотика" должна будет учесть сотню таких теорем, среди которых есть и открытые проблемы (у Серпинского в списке видел), это я еще самые простые привел. Для произвольной фиксированной пары $(S_1,S_2)$ это нереально.
Можно предложить от точного задания пар $(S_1,S_2)$ перейти к интервальному, чтобы длина интервала для каждого из $S_i$ росла с ростом n хотя бы медленно, чтобы сгладить все эти эффекты.

[ex-math]

Если статистика не поможет, можно представить искомую величину в виде двойного интеграла

$$\int\int\left (\sum_{l=0}^me^{2\pi i (lx+l^2y)}\right)^ne^{-2\pi i(S_1x+S_2y)}dxdy $$

по квадрату $|x|,|y|\leqslant 0.5. $ При больших $n $ основной вклад вроде бы должна давать окрестность нуля. Там надо разложить функцию в ряд Тейлора до квадратичных членов, и после приведения формы к главным осям получится произведение двух гауссовых интегралов.
Сумма по $m $ называется суммой Гаусса, про нее многое известно, но далеко не все, к сожалению.

-- 09.08.2015, 22:28 --

iancaple
Четность, конечно, должна быть учтена, а остальные теоретико-числовые сложности при больших $n $ вроде не должны влиять. Кстати, в аддитивных задачах теории чисел асимптотики вытаскивают из подобных интегралов, и они содержат множитель (т.н. сингулярный ряд), который отвечает за арифметику. При неподходящих параметрах (четности и т.п.) этот множитель обращается в нуль.

[Mihaylo]

Ну, друзья, надо что-то однозначно делать с моим куполом... Спасибо!

[Mihaylo]

Итак, напомню первую задачу и приведу ее конечное решение.

Mihaylo писал(а):

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

Mihaylo писал(а):

Поэтому формула чуть упрощается:
$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$ - это есть энтропия.
$H=\log N$
Тут очень важно понять, что это за энтропия: известен размер массива $n$; известны значения, которые могут принимать числа массива (от 0 до $m$); и зафиксирована некоторая сумма чисел $S$.

Общеизвестна другая энтропия:
$H_0=\log N_0 = \log (m+1)^n=n\cdot\log (m+1)$

Если при известных $n$ и $m$ сообщить о величине суммы $S$, то энтропия уменьшится с $H_0$ до $H$.

Огромнейший интерес представляет величина средней энтропии, приходящейся на один элемент массива
$h=\frac{H}{n}$
в двух отдельных случаях
а) $m\to\infty$
б) $n\to\infty$

Рассмотрим случай а) при некотором конечном значении $S$. В этом случае верхний предел суммы $\left\lfloor\frac S {m+1}\right\rfloor$ устремится к нулю и выражение сильно упростится.

$N = C_n^0C_{n+S-1}^{n-1}=\frac{(n+S-1)!}{S!(n-1)!}$

Хорошее выражение для взятия логарифма:

$h=\frac{1}{n}\cdot\log \frac{(n+S-1)!}{S!(n-1)!}$

Использовав формулу Стирлинга-Муавра, получаем в конечном итоге
$h=(\frac{S}{n}+1)\log(\frac{S}{n}+1)-\frac{S}{n}\log\frac{S}{n}=\frac{S}{n}\log(1+(\frac{S}{n})^{-1})+\log(\frac{S}{n}+1)$

Заменив $\frac{S}{n}$ на $\overline{x}$, получим энтропию первого центрального момента при $m\to\infty$ и конечном значении $\overline{x}$
$h=\overline{x}\log(1+\overline{x}^{-1})+\log(\overline{x}+1)$

При достаточно больших значениях $\overline{x}$ можно пользоваться приближенной формулой
$h=\log e+\log\overline{x}$

Отмечу, что в исходной формулировке задачи рассматриваются только целые натуральные числа. Изменив формулировку, можно получить более общие выражения, но общий смысл остается прежним: центральные моменты распределения сами по себе имеют вычислимое количество информации (энтропии).

[iancaple]

физика, что ли? $n$~ общая масса, $S$ вроде импульса, $S_2$ вроде энергии ? Так может и задача решенная?

[Mihaylo]

Ну можно и так представить: $n$ бильярдных шаров одинаковой массы изначально покоятся, шар-биток ударяет с импульсом $S_1$ и энергией $S_2$, происходит сложное (или несложное) столкновение всех (или не всех) шаров. Столкновения идеальные (без потерь энергии и импульса), трение отсутствует. Узнать, какую скорость по модулю будет иметь каждый шар в некоторый момент времени после начала столкновений.
Решенная ли эта задача? Я знаю только формулу Больцмана с логарифмом $S=\log W$.

[Mihaylo]

Ну и напоследок приведу доказательство информационной связи между суммой первой степени $S_1$, суммой квадратов $S_2$ чисел массива и первым-вторым центральными моментами.
Связь $S_1$ с $\overline{x}$ очевидно однозначна (при фиксированном $n$)

$S_1=n\overline{x}$

Связь $\sigma$ с $S_2$ посложнее
$\sigma=\sqrt{\frac{1}{n}\sum(x-\overline{x})^2}$

$\sigma=\sqrt{\frac{1}{n}\sum(x^2-2x\overline{x}+\overline{x}^2)}$

$\sigma=\sqrt{\frac{1}{n}(S_2-2S_1\overline{x}+n\overline{x}^2)}$

$\sigma=\sqrt{\frac{1}{n}(S_2-n\overline{x}^2)}$

Ну и наконец
$S_2=n\sigma^2+n\overline{x}^2=n(\sigma^2+\overline{x}^2)$

То есть имеет место вывод: для массива из $n$ чисел первый центральный момент информационно эквивалентен сумме первых степеней чисел, а первый и второй центральные моменты - сумме первых и сумме вторых степеней.

[Mihaylo]

Mihaylo писал(а):

Отмечу, что в исходной формулировке задачи рассматриваются только целые натуральные числа. Изменив формулировку, можно получить более общие выражения

По всей видимости имеет смысл рассмотреть следующую задачу. Пусть задача формулируется таким же образом, только числа $x_i$ могут принимать значения $\Delta, 2\Delta, 3\Delta, ..., m\Delta$. Таким образом в комбинаторном смысле задача та же, нужно только пересчитать сумму $S$ и среднее $\overline{x}$.

Энтропия первого центрального момента при $m\to\infty$ и конечном значении $\overline{x}$
$h(\Delta)=\frac{\overline{x}}{\Delta}\log(1+(\frac{\overline{x}}{\Delta})^{-1})+\log(\frac{\overline{x}}{\Delta}+1)$ (1)

Приближенная формула
$h(\Delta)\approx\log e+\log(\frac{\overline{x}}{\Delta})$ (2)

Устремим величину $\Delta$ к нулю, таким образом числа $x_i$ можно считать $\in\mathbb{R}$. При этом заметим, что требование конечности $\overline{x}$ означает конечность максимального элемента $m\Delta$, для упрощения будущих выражений обозначим $X_0=m\Delta$ - некоторое конечное действительное число.
Обратим внимание, что при $\Delta\to 0$ энтропия согласно формулам (1) и (2) бесконечна. Бесконечность энтропии - это типичная ситуация для непрерывных величин.

Вместо энтропии рассчитаем количество информации (негэнтропию) первого центрального момента для конечных действительных чисел
$I=h_0-h=\frac{H_0}{n}-h=\frac{n\log(m+1)}{n}-h\approx\log m-\log e-\log(\frac{\overline{x}}{\Delta})=$
$=\log X_0-\log e-\log\overline{x}=\log(\frac{X_0}{e\overline{x}})$