stould's blog

Combinatorics doubt.
By stould, 10 years ago, In English

Hello, I'm trying to solve a problem from SPOJ involving combinatorics (counting), but I cannot find a final answer... http://www.spoj.com/problems/MARBLES/

I've found some things that I guess will be useful to solve this task: You have to use at least one ball in each color, so, N-K (I will call it "X") balls left.

I need to distribute this X balls in the K colors, so I began to think: "I can use from 0 up to X balls in each color".

I'm trying hard to find out the answer, maybe am I thinking in a wrong way ?! Can you give to me some tips how to solve ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

An another thought process would be something like this - There are N-K balls, place them side by side, now we need to divide this into k partitions. i.e. put some k-1 bricks in between. How many ways can we do this?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Huh.... I'm so sorry.. I'm thinking about N Choose (K-1) to do it.. But I guess I'm missing something.. Woow... I need K-1 bars to generate K distinct groups..

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Think of the problem this way: You have N stars in a line and you want to put K-1 bars between them (divide them in K groups), such that no two bars are in the same position (this ensures you have at least one star in each group). How would you do that?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have to place this bars in all possible locations in wich no two bars will be together...

    Why K-1 bars ?!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Woow... I need K-1 bars to generate K distinct groups..

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exactly. And N-1 positions because you can't put the bars before the stars or after the stars.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Wow man, I got the answer, thinking this way is easier!! Thank you.

          → Reply