Комбинаторика. Задачка.

Pavlovsky · Сообщение **Pavlovsky** » 16 апр 2010, 14:44

Задача. Сколькими способами можно представить S как сумму K различных чисел из интервала [1,…,N]?
Конкретно. Сколькими способами можно представить 68 как сумму 4х различных чисел из интервала [1,…,16]?

СергейП

Pavlovsky писал(а):Source of the post Конкретно. Сколькими способами можно представить 68 как сумму 4х различных чисел из интервала [1,…,16]?

Вообще-то ни одним
Максимальное число 13+14+15+16=58
Видимо, что-то надо поправить.

tonka · Сообщение **tonka** » 16 апр 2010, 15:07

Pavlovsky писал(а):Source of the post
Задача. Сколькими способами можно представить S как сумму K различных чисел из интервала [1,…,N]?
Конкретно. Сколькими способами можно представить 68 как сумму 4х различных чисел из интервала [1,…,16]?

Может не 68, a 58???

Pavlovsky · Сообщение **Pavlovsky** » 16 апр 2010, 15:08

Извиняюсь. Надо подправаить.
Сколькими способами можно представить 29 как сумму 4х различных чисел из интервала [1,…,16]?

Ian · Сообщение **Ian** » 17 апр 2010, 12:02

Pavlovsky писал(а):Source of the post
Задача. Сколькими способами можно представить S как сумму K различных чисел из интервала [1,…,N]?

См.число на K-й странице S-й строке N-го столбца прилагаемого файла. Строится как бесконечный тетраэдр в духе треугольника Паскаля.
[img]/modules/file/icons/application-octet-stream.png[/img] SNk.rar

Pavlovsky · Сообщение **Pavlovsky** » 17 апр 2010, 12:19

См.число на K-й странице S-й строке N-го столбца прилагаемого файла. Строится как бесконечный тетраэдр в духе треугольника Паскаля.

Спасибо. A ссылочки на теорию есть?

Выртуозное владение екселем! поделись секретом как составлял?

Ian · Сообщение **Ian** » 17 апр 2010, 12:26

Pavlovsky писал(а):Source of the post

A ссылочки на теорию есть?

поделись секретом как составлял?

Обозначив искомое количество способов $\Sigma_k(S,N)=\Sigma_{k-1}(S-k,N-1)+\Sigma_{k-1}(S-2k,N-2)+\Sigma_{k-1}(S-3k,N-3)+\Sigma_{k-1}(S-4k,N-4)+...$ суммирование,пока слагаемые отличны от нуля)Это просто варианты:минимальное слагаемое=1;2;3...
B эксель одним автозаполнением не получилось,например 4я страница делалась автозаполнением строк по 4штуки сразу.Заняло минут 40.Сохраню в архивах.

СергейП

Ian писал(а):Source of the post См.число на K-й странице S-й строке N-го столбца прилагаемого файла. Строится как бесконечный тетраэдр в духе треугольника Паскаля.

Круто!

Pavlovsky писал(а):Source of the post Спасибо. A ссылочки на теорию есть?

Решение Ian-a похоже на методы динамического программирования. Видимо, конкретные ф-лы вывести будет сложновато.
Если они нужны, то можно попробовать через производящие функции. Например, начало: $$ \sum_{i = 1}^{16} t^i $^4$ . Коэффициент при $t^{29}$ равен числу способов представить 29 как сумму 4х чисел из интервала [1,…,16]. Чтобы исключить повторы, надо или поработать c производящей функцией или, если не получится, придется по принципу включений/исключений вычесть число комбинаций c повторами чисел. Ну и учесть их перестановки.

Ian · Сообщение **Ian** » 17 апр 2010, 16:58

СергейП писал(а):Source of the post
Если они нужны, то можно попробовать через производящие функции. Например, начало: $$ \sum_{i = 1}^{16} t^i $^4$ . Коэффициент при $t^{29}$ равен числу способов представить 29 как сумму 4х чисел из интервала [1,…,16]. Чтобы исключить повторы, надо или поработать c производящей функцией

Еще круче.Pavlovsky, $sort(t,expand(simplify((t^{117}-t)^{14}/(t-1)^{14})));$ и ищите число способов представить 1129 в виде суммы 14 слагаемых, не превосходящих 117, примерно на 40й странице многочлена, который Вам выдаст maple по этой команде вот только способы будут c учетом порядка слагаемых и c совпадающими слагаемыми.

yourdomain.com