bluemmb's blog

Distributing N distinct people in M identical rooms
By bluemmb, 9 years ago, In English

We have N persons numbered from 1 to N. Also there are M identical rooms with infinity capacity.

In how many ways we can distribute persons in rooms such that each room contains at least 1 person ?

Two ways A and B are regarded as the same if for any room in A, there exists a room in B that the persons in these two rooms have the same set of numbers. In other words, rooms are indistinguishable.

for example : 2 rooms , 3 persons , ans = 3 : (1)(2,3) , (2)(1,3) , (3)(1,2)

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

Comments Comments (11)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

Pretty sure you're talking about the Stirling numbers of second kind.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    thanks so much ...

    Now problem is that I have to answer 10^5 queries of this problem when N is same for all queries but M is different for each query from 1..10^5. ( N is in range 1..10^5 )

    It seems that this numbers need huge time for calculation , how can we reduce it ? or I am wrong ?

    → Reply
»
9 years ago, hide # |
← Rev. 3  
Vote: I like it +31 Vote: I do not like it

actually you can use this formula

as you can see it can be written as the product of two polynomials and (k - i)n
so you can easily find s(n, k) for a fixed n and all k.

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

    thanks... very nice! congratulations for being the only team who solved it ... :)

    I don't know FFT for programming contests yet ... I have to learn it first ... can you suggest a good resource for learning it ?

    → Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    I was reading your approach and I noticed that is not a 1-D array that you can easily multiply, it's 2-D so it can't be used. What we can do here is to reformat the formula: so you should use and . So if you have two polynomials, one with coefficients and one with coefficients , then k - th coefficient of their product is indeed s(n, k).

    P.S: Nice approach by the way, inclusion-exclusion principle...

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

Each of N persons to any of M rooms minus cases of N persons in M-1 rooms m^n-m*(m-1)^n

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    My friend , problem is not as easy as you think ... you must make sure that each room contains at least one person. Also notice that all the rooms are same.

    → Reply