no_life's blog

Stars and bars modified
By no_life, history, 6 years ago, In English

We all know that the number of solutions to a+b = 3 (where a and b are non negative) can be easily found out by stars and bars theorem. So answer of the above is 4. { (3,0),(0,3),(1,2),(2,1)}. But I want the answer to be 2 as the first two and last two are equivalent. Formally, as the stars and bars give the number of ordered sets, I want to find out the number of unordered sets.

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Number of ordered sets ((a+b)/2)+1 if i understood your question correctly.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

This can be solved by dynamic programming the general case. First of all define P(N,K) as the number of ways you can represent N using K numbers in ascending order.

Now for solving P(N,K), if K > N then answer is 0, otherwise let's distribute 1 item on each set. Your task is now to distribute N — K items without breaking the ascending order.

If you place an item, in the ith set, you must use n — i — 1 items for later sets to compensate. So you can just apply dynamic programming and solve it O(N*K).

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

    N is up to 1e9. Can we use prime factors of N to solve this?

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

?detaR tI sI

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

I'm gonna take a guess and say that you are looking for the partitions of a number. https://en.wikipedia.org/wiki/Partition_(number_theory) You can check here for fancy formulae, or just look for a dp solution :)

→ Reply