Я очень давно не читал учебников комбинаторики, и не очень представляю себе, где искать ответ на следующий простой вопрос.

Сколько есть наборов (с повторениями, порядок важен) из n целых чисел от нуля до R, таких, что сумма набора не больше R?

Если поможет, число R можно сделать маленьким, в идеале 3 (можно 2). Т.е. большинство из этих чисел будет равно 0.

Если не получается изящная формула, а вместо этого какие–то вложенные суммы, то, наверное, не нужно. Тогда проще перебором.

GD Star Rating
loading...
Tagged with →  

19 Responses to комбинаторика

  1. RettaMtn:

    Комбинаторику вообще не помню. Попробую, как могу:
    Только я сделаю, чтобы сумма была строго меньше 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!.
    Но, конечно, не факт. Надо методом индукции попробовать доказать, но я уже спать.

  2. GnimrahC:

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

  3. GnimrahC:

    В смысле формула может быть на вид и проста, но получается нетривиально наверняка.

  4. GnimrahC:

    А для конкретного 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)

  5. GnimrahC:

    Ой, забыл еще просто 2. Еще + n.

  6. Ilmig:

    я идиот! Разумеется. Сам же дал подсказку, что R маленькое.

    %убиение стенкой%

  7. Peels:

    Да лехко. На самом деле это называется «сочетания с повторениями», но я вам прямо тут выведу, шоб понятнее было.

    Запишем число 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)!

  8. Peels:

    и не очень представляю себе, где искать ответ на следующий простой вопрос
    Кстати, если я правильно помню, для ответа на этот вопрос не нужно учебников по комбинаторике. Подойдет и книжка «Энциклопедия для детей. Математика.» от Аванта+.

  9. GnimrahC:

    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

  10. GnimrahC:

    Ой, там же не больше. То есть еще три варианта: 300,030, 003.
    А в вашей формуле, Peels, проблема в том, что количество нулей будет разным при разном разбиении, соответственно и формулы будут разные.

  11. GnimrahC:

    Вот ты идиот, ты еще все нули забыл.

  12. Peels:

    Я почему–то прочитал задачу из поста «так что сумма набора РАВНА R».
    Сейчас перечитал, понял что надо меньше или равна. В таком случае конечно же ответ будет суммой выражений которое я привел для всех R от нуля до собственно данного R.

    Больше проблем в моей формуле нет.

  13. Noirolgn:

    При этом очевидно, что число таких комбинаций будет равно числу комбинаций из n+1 чисел, сумма которых строго равна R, так как мы просто добавляем в последнее число все, что не хватает до R.

    То есть ответ N=Cn+Rn:n+R)!/n!/R!

    Для случая n=3, R=3, N=6!/3!/3!=20

  14. Peels:

    O, точно! Гениально!

  15. RettaMtn:

    Я же этот же ответ написал еще в самом первом комментарии.

  16. Noirolgn:

    Судя по всему, его просто никто не понял.

  17. RettaMtn:

    Ну, наверное, да. Стоило в блокноте решать, а не в поле для комментов 🙂

  18. Peels:

    Ага, и избегай выражений «в общем похоже что это …, но конечно не факт, надо бы доказать бы, но мне влом и фиг поймешь вообще». Надо было писать «Итого видим что это вот. Формально доказывается по индукции, это я оставляю вам на домашнее задание.»
    Тогда мы бы быстро выяснили что к чему. 🙂

Добавить комментарий