Я очень давно не читал учебников комбинаторики, и не очень представляю себе, где искать ответ на следующий простой вопрос.
Сколько есть наборов (с повторениями, порядок важен) из n целых чисел от нуля до R, таких, что сумма набора не больше R?
Если поможет, число R можно сделать маленьким, в идеале 3 (можно 2). Т.е. большинство из этих чисел будет равно 0.
Если не получается изящная формула, а вместо этого какие–то вложенные суммы, то, наверное, не нужно. Тогда проще перебором.
GD Star Rating
loading...
loading...
Комбинаторику вообще не помню. Попробую, как могу:
Только я сделаю, чтобы сумма была строго меньше R.
n — число целых чисел( R в моей задаче = R+1 в твоей)
n = 1 — R наборов — просто одно число >=0 и R–1 1
R 0
S =Summ(i,0,R,*)
S (R–i) = S ( i) = R(R+1)/2
n = 3 — 0 (R+1)(R)/2
1 R(R–1)/2
…
R–2 3
R–1 1
R 0
S (R+1–i)(R–i)/2 = S (i+1)(i)/2 = S(i^2)/2 + S(i)/2=R(R+1)(2R+1)/12 + R (R+1)/4 = R(R+1)((2R+1)/12+1/4)=R(R+1)(R+2)/6
В общем похоже, что это произведение от R до R+n–1, поделенное на n!.
Но, конечно, не факт. Надо методом индукции попробовать доказать, но я уже спать.
Мне кажется, что простой формулы нет, ибо вычисление сводится к двум операциям. Сначала раскладываем число на слагаемые, а потом их расфасовываем по наборам. Так вот из–за того, что числа могут повторяться, вторая функция как–то должна узнавать сколько и каких наборов одинаковых чисел выдает первая функция.
В смысле формула может быть на вид и проста, но получается нетривиально наверняка.
А для конкретного R, конечно, намного проще. Если R = 3. Имеем комбинации:
1
1+1
1+1+1
1+2
Итого: n + n(n–1)/2 + n(n–1)(n–2)/6 +n(n–1)
Ой, забыл еще просто 2. Еще + n.
я идиот! Разумеется. Сам же дал подсказку, что R маленькое.
%убиение стенкой%
Да лехко. На самом деле это называется «сочетания с повторениями», но я вам прямо тут выведу, шоб понятнее было.
Запишем число R как последовательность единиц:
1111111…111
Теперь каждое разбиение R на n слагаемых обозначим, «разбив» соответствующую последовательность на n частей. В качестве разделителей используем нули. Например:
1111 0 1 0 0 1111111 0 … 0 11
будет соотвествовать:
R = 4 + 1 + 0 + 7 + … + 2
Очевидно что соответствие один к одному (т.е. любому разложению R будет соответствовать некая двоичная последовательность из R единиц и (n–1) нулей и наоборот).
Итого вопрос в том, сколько существует последовательностей из R единиц и (n–1) нулей. Другими словами, сколькими способами можно выбрать (n–1) из (R+n–1). А это должен знать каждый ребенок:
C(R+n–1, n–1) = (R+n–1)! / R! (n–1)!
и не очень представляю себе, где искать ответ на следующий простой вопрос
Кстати, если я правильно помню, для ответа на этот вопрос не нужно учебников по комбинаторике. Подойдет и книжка «Энциклопедия для детей. Математика.» от Аванта+.
R=3 n=3 С:3+3–1)!/3!2!=5!/3!2!=10
1 100
2 010
3 001
4 110
5 101
6 011
7 111
8 200
9 020
10 002
11 210
12 201
13 120
14 021
15 102
16 012
16!=10
Ой, там же не больше. То есть еще три варианта: 300,030, 003.
А в вашей формуле, Peels, проблема в том, что количество нулей будет разным при разном разбиении, соответственно и формулы будут разные.
Вот ты идиот, ты еще все нули забыл.
Я почему–то прочитал задачу из поста «так что сумма набора РАВНА R».
Сейчас перечитал, понял что надо меньше или равна. В таком случае конечно же ответ будет суммой выражений которое я привел для всех R от нуля до собственно данного R.
Больше проблем в моей формуле нет.
Да.
При этом очевидно, что число таких комбинаций будет равно числу комбинаций из n+1 чисел, сумма которых строго равна R, так как мы просто добавляем в последнее число все, что не хватает до R.
То есть ответ N=Cn+Rn:n+R)!/n!/R!
Для случая n=3, R=3, N=6!/3!/3!=20
O, точно! Гениально!
Я же этот же ответ написал еще в самом первом комментарии.
Судя по всему, его просто никто не понял.
Ну, наверное, да. Стоило в блокноте решать, а не в поле для комментов 🙂
Ага, и избегай выражений «в общем похоже что это …, но конечно не факт, надо бы доказать бы, но мне влом и фиг поймешь вообще». Надо было писать «Итого видим что это вот. Формально доказывается по индукции, это я оставляю вам на домашнее задание.»
Тогда мы бы быстро выяснили что к чему. 🙂