Белый шум красного карлика

Я тут обнаружил читерский способ находить формулу для комбинаторных задачек: считаем для первых десяти элементов, копируем ряд на http://oeis.org/

From:

Задачка: найти интересных пар рядов, совпадающих в первых десяти членах, а потом различающихся. :-)
(прошу прощения за кривую формулировку -- я простыл, голова не варит)

... throw 22 ...

From:

Я хотел сказать, что именно с появлением oeis, всяческих символических вычислялок и всего такого прочего, стало особенно интересно искать задачки, на которых ломается "интуитивная индукция" -- когда какое-нибудь свойство (например, совпадение двух последовательностей) соблюдается, соблюдается, а потом вдруг раз и перестаёт. Элементе этак на сороковом. Я такие примеры несколько раз находил и даже куда-то перепощивал, но, боюсь, собрать коллекцию как-то не догадался. :-( Правда, не уверен, что у меня были примеры именно на комбинаторику.

... Ускорение темпов роста повышения производительности труда ...

From:

Да, помню, очень красиво. Если есть примеры с интегрированием, то есть и на комбинаторику — это же суммирование, практически целочисленное интегрирование. Пример такой последовательности — площадь пересечения какой-нибудь трёхмерной фигуры плоскостью, в зависимости от её положения и наклона. При небольшом изменении параметров будет одна простая аналитическая формула, а при пересечении вершины или ребра — другая. В комбинаторике то же самое, но вдискретном пространстве.

From:

Коллекции, как я уже говорил, нет, но вот тут есть несколько интересных примеров. (...) Ух ты! А pdf-ку по первой ссылке я в прошлый раз как-то протормозил скачать и посмотреть! Судя по первой странице, авторы как раз про это ("интуитивная индукция" и вообще использование мощных, но тупых вычислялок) пишут. Пошёл читать.

... Семнадцатая пятилетка ...

From:

Спасибо, интересно. И последовательности, которые возникают в этой задаче оно находит.

From:

Я в своё время практически одновременно открыл для себя oeis и tineye, и с тех пор они у меня в голове служат примерами полезных "неканонических" искалок. :-)

... И они хитрили, и Аллах хитрил, а Аллах - величайший из хитрецов! ...

From:

пусть есть разбиение на слагаемые
упорядочим слагаемые по порядку
вычтем из упорядоченных слагаемых 1, 2, 3, 4 ... m
получим набор m положительных чисел, сумма которых равна n - (1+2+...+m)
поэтому кол-во разложений на разные слагаемые - равно количеству разложений на любые слагаемые, без ограничения на разноту, числа n - m(m+1)/2
поскольку среди слагаемых могут быть и нули, то задача формулируется как google "Number of partitions of n into at most k parts"

Чуть подробней про равенство разных формулировок. Строится взаимно-однозначное соответствие разбиений на m разных положительных слагаемыех (твоя задача) и разбиений на m не более чем слагаемых.

Например, если m=4, то число 6 можно представить как два слагаемых, 3+3
Запишем как 4 возрастающих слагаемых с нулями впереди:
0+0+3+3
превратим это в разбиение на 4 разных слагаемы числа 6+m(m+1)/2 = 16:
(0+1)+(0+2)+(3+3)+(3+4) = 6+10 = 16

Гугл выдает некрасивые точные формулы в виде многочленов со случайными рациональными коэффициентами или же красивые generating ряды 1/((1-x)*(1-x^2)*(1-x^3)*...*(1-x^m))

From:

Не понял, какое это имеет отношение.

From:

Производящие функции или эквивалентность двух формулировок?

Edited Date: 2012-09-15 10:12 am (UTC)

From:

Какое отношение имеют эти рассуждения к задаче? 6 можно представить и как 4 + 2, но разбиение (0 + 1) + (0 + 2) + (4 + 3) + (2 + 4) = 1 + 2 + 7 + 6 получается то же, что и при разложении 6 на 3 + 3. Я что-то по-видимому не понимаю?

From:

А ты представь не как 4+2, а как 2+4. 0+0+2+4. Соответствующее разбиение будет 1+2+5+8 = 16.

пусть есть разбиение на слагаемые
упорядочим слагаемые по порядку
.....
Запишем как 4 возрастающих слагаемых с нулями впереди:

Edited Date: 2012-09-15 05:36 pm (UTC)

From:

Не пойму, как это приближает к решению задачи.

From: