Блог пользователя waiter_pvl

Тот, кто хотя бы немного шарит в комбинаторике помогите!
Автор waiter_pvl, 14 лет назад, По-русски
Задача : Сколькими способами можно разложить в N + 1 ящик M - N шариков, если в один ящик можно ложить хоть сколько шариков?
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не хочу показаться капитаном очевидностью, но по-моему ответ (N + 1)(M - N). И еще не "ложить", а "класть" все-таки.
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится
    --туплю--
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да нет, все правильно. Каждому из (M - N) шариков сопоставлено (N + 1) способов его определить куда-то.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Но, если шарики неразличимые, некоторые варианты совпадают.
        Например, в 2 ящика 2 шарика можно положить тремя способами (2+0, 1+1, 0+2).
        Тут что-то поинтереснее.
        → Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
    А ещё по-моему выделяется запятыми, а Капитан Очевидность пишется именно так, с большими буквами =)))
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Шарики разные? А ящики?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Если ящики различимы, а шарики нет, похоже на сочетания с повторениями.
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    В случае неотличимости ящиков упорядочим их по убыванию количеств шаров и получим количество разбиений на слагаемые с одной проблемой: этих слагаемых не больше, чем ящиков.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, ваша версия, кажется, правильная. Наши математики также думают, потом спрошу почему.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Если у нас Н шариков и М ящиков, тогда можно представить Н+М объектов, где М из них - перегородки между "ящиками". Думаю, от того и сочетания.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        M-1 все же
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Да, вероятно, вы правы.Хотя, можно и ничего не класть в ящики.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, я понимаю что можно не класть, в этом случае будет несколько перегородок подряд, либо перегородка будет в начале/конце
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              И ничего не класть ни в один ящик так получится? Все шарики в "невидимом ящике"? Тогда, наверное, количество объектов будет на один больше. 


              Извините, что не "шарю в комбинаторике" :).

              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Если подразумевается, что шарик можно не класть никуда - тогда да, согласен будет М перегородок, как раз за счет несуществующего ящика. Я считал, что нужно каждый шарик положить куда-то, при этом не обязательно класть что-либо в каждую коробку.
                → Ответить
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  http://acmp.ru/index.asp?main=task&id_task=401

                  Думаю, это - та самая задача.

                  → Ответить