Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a counting problem

  1. Nov 19, 2014 #1
    we have to make n with k integers.k integers will have to be choosen from k ranges.Every range has a minimum value and a maximum value.In how many ways we can make n
    according to the conditions.For example,k=4,n=10
    and the ranges are :
    1 1
    2 2
    3 3
    4 4

    we can make n in only one way.


    Another example is


    k=2,n=10
    and the ranges are:
    1 10
    1 10
    Here,the result will be 9


    How can I find the number of ways by using inclusion-exclusion principle.Can anyone give me hints with better explanation?
     
  2. jcsd
  3. Nov 24, 2014 #2
    Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
     
  4. Nov 25, 2014 #3

    Mark44

    Staff: Mentor

    What does "make n" mean here? If you take one number from each range and add them together, you get 1 + 2 + 3 + 4 = 10. I suppose this is what you mean.
    Or more clearly (I think), there are 9 ways: 1 + 9, 2 + 8, 3 + 7, 4 + 6, 5 + 5, 6 + 4, 7 + 3, 8 + 2, and 9 + 1 for the 9 ways.
    For some problems, the answer is zero. For example, if k = 3 and n = 10 with these ranges:
    1 1
    2 2
    3 3
    The only possible sum is 1 + 2 + 3 = 6
    For a solution to exist it must be the case that ##\sum_k \text{range minima} \leq n \leq \sum_k \text{range maxima}##.
     
  5. Nov 25, 2014 #4
    So, if I may put some notation around this problem, we are trying to find the number of ways to specify a set of k integers ##\{s_i\}## such that each ##s_i## lies within its specified interval, ##a_i \leq s_i \leq b_i##, and ##\sum s_i = m##. The problem specification implies that the values are ordered by claiming 9 solutions (rather than 5) for the second case, so {9,1} is a different solution to {1,9}.

    Obviously a solution is only possibly if ##\sum a_i \leq m \leq \sum b_i##. If ##m = \sum a_i## or ##m = \sum b_i## there is only one set of choices for S

    I also considered changing the problem a little, defining ##r_i = b_i - a_i## and ##m' = m - \sum a_i## and then one needs to find ##\{t_i\}## with ##0 \leq t_i \leq r_i## and ##\sum t_i = m'##. This can be regarded as problem of distributing ##m'## identical balls into an ordered set of cups of limited size. If all the ##r_i > m'## then the limits do not come into play and the number of options is just ##C^{m'+k-1}_{k-1}##. This is obviously a maximum in any case.
     
  6. Nov 27, 2014 #5
  7. Nov 27, 2014 #6
    Here's a worked example:
    Determine how many ways can you choose 3 integers, ##a##, ##b##, ##c##, such that ##a+b+c=24## and with ##6 \leq a \leq 14##, ##3 \leq b \leq 10##, ##1 \leq c \leq 6##

    The general approach is as follows:
    • Transform the ranges so that they all run zero to ##r_i## and find the modified sum ##m'##
    • Check for an easy answer (1 or 0)
    • Calculate the number of combinations ##A## as if there were no top limits
      • As above this is ##C^{m'+k-1}_{k-1} ##, in this case ##k=3## so ##A = C^{m'+2}_{2} ##
    • Calculate the number of combinations, ##B(x)##, that break the constraint for each single variable
      • if u is the upper limit on the variable, u+1 breaks the constraint, so preallocate u+1 to that variable and count combinations for the allocation of the remaining units
      • ##B(x) = C^{m'-(u+1)+2}_{2} ##
      • Total these up
    • Calculate the number of combinations that break the constraint for pairs of variables, ##B(x\cup y)##
      • These have been double counted above so need removing
      • As above but preallocate multiple constraint-breaking numbers (if possible), ##C^{m'-(u+1)-(v+1)+2}_{2} ##
    • Calculate the number that break the constraint for all three variables
      • In principle this was triple counted and then triple removed, so needs adding back in, but there won't be any
    • Combine the above results according to the inclusion-exclusion rules
      • Result ##= A - (B(a)+B(b)+Br(c)) + (B(a\cap b)+B(a\cap c)+B(b\cap c)) - B(a\cap b\cap c)##
    ##a'=a-6##
    ##b'=b-3##
    ##c'=c-1##
    Total of lower limits ##= 6+3+1 = 10##
    Revised total ##m' = 24-10 = 14##
    Revised upper limits ##r_i = {8,7,5}##
    ##\sum r_i = 20 ## ∴ no easy answer
    Combinations disregarding upper limits ##C^{14+3-1}_{3-1}= C^{16}_2 = 120##
    Combinations breaking 1-variable constraint
    ## B(a') = C^7_2 = 21##
    ## B(b') = C^8_2 = 28##
    ## B(c') = C^{10}_2 = 45##
    Total ##21+28+45=94##
    Combinations breaking 2-variable constraint
    ## B(a'\cap b')## not possible (9+8>14)
    ## B(a'\cap c)## not possible (9+6>14)
    ## B(b'\cap c')=C^2_2 = 1## (8+6=14)
    Total ##1##
    Reconcile on inclusion-exclusion
    Result ##=120-94+1 = 27##
     
    Last edited: Nov 27, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving a counting problem
  1. Counting Problems (Replies: 2)

  2. Problem Solving (Replies: 0)

Loading...