babak's blog

number of ways
By babak, 12 years ago, In English

How many ways I can put r1 (same) balls with color 1 , r2 balls with color 2 , ..., rp balls with color p in q different boxes with sizes s1,**s2**,..,**sq** ?

note : r1+r2...+rp=s1+s2+...+sq=N

note 2: N<=1000

I don't have a good algorithm to solve this problem .

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

maby, dynamic O(n*n) and CRT?

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

I think there are N! / (Product_i r_i! * Product_i s_i!) ways.

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

    Sorry, the formula is wrong. Am I right that we can distinguish every pair of boxes?

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

What is the origin of this problem? How much can be p and q?

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

    I know exponential solution which works for n~50-60, based on Burnside's lemma..

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

      Could you suggest what do you mean by set and group in lemma?

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

    And there is dp in O(p*q*n*binomial(p+q,p))

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

      I don't know about p and q. :) could you please give me some hint about dp.

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

        Please answer from where this problem is first :)

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

          It's my homework. I don't know what's the source.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            Hm, maybe you know some related theory? Because I don't know how to solve it with n up to 1000..

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

              it's all about counting and I don't know any idea too. :(

              → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            If it's homework, there are some other tasks like this one. Could you give us some examples? Maybe, after it, we will understand, which methods to use...

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

              counting number of ways to put distinguishable/indistinguishable balls in distinguishable/indistinguishable boxes and one of most related problems is this problem without limitation on size of boxes but I think this problem is far different from these.

              → Reply