Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Maruf089's blog

By Maruf089, history, 5 weeks ago, In English,

The problem of counting the solutions (a1,a2,. . .. . ,an) with integer ai≥0 for i∈{1,2,…,n} such that a1+a2+a3+....an = N

can be solved with a stars-and-bars argument. What is the solution if one adds the constraint that ai ≤ ri for certain integers r1,…,rn?

Upper Bound with Each Partition

e.g. for n=3, N=6 and (r1,r2,r3)=(3,3,2), the tuple (a1,a2,a3)=(2,3,1) is a solution, but (2,1,3) is not a solution because

a3=3>2=r3.

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can use inclusion-exclusion for n items.

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it