1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: creating a sum

  1. Apr 2, 2009 #1
    1. The problem statement, all variables and given/known data

    In how many ways can we create the sum

    k = x_1 + x_2 + ... + x_n

    where each x_i is either 1 or 2 with repetitions allowed. n <= k <= 2n

    For example

    n = 4
    k = 5

    1+1+1+2
    1+1+2+1
    1+2+1+1
    2+1+1+1

    are four ways.

    2. Relevant equations

    Is this solving the number of multisets (bags) and ordering them?

    3. The attempt at a solution

    A few failed attempts :(
     
  2. jcsd
  3. Apr 2, 2009 #2

    Avodyne

    User Avatar
    Science Advisor

    Let's see 'em!
     
  4. Apr 2, 2009 #3
    Heh allright! Didn't thought they would be of any interest, since I didn't get any far.

    Anyway I have tried to rewrite the the sequence k = x_1 + .... + x_n
    in different forms.

    only this one I felt was kind of near the solution...

    a_i = x _i + i .

    Which means I should try to find the number of sequences a_i.
    But this yields an increasing sequence

    2 <= a_1 <= a_2 <=. ... <= a_n <= 2 +n

    < = > 0 <= a_1 <= a_2 <=. ... <= a_n <= n

    since according to my lecturer, the numbers of above sequences are given by (n+k-1) over k. So that's why I tried to rewrite it like that. But I don't know where to go from there, or if that's really the right approach.

    Is this attempt good enough? :)
     
  5. Apr 2, 2009 #4
    Try working out the possible combinations for x_1, then once you pick x_1, how many combinations do you have for x_2,...?

    I'll use your example, for the first one you have two possibilities, 1 and 2 (3 would mean you can't have n=4). If x_1=1 then x_2+x_3+x_4=5-1=4, if x_1=2 then x_2+x_3+x_4=5-2=3. The first case gives 3 cases (you can make one of the x_2,x_3,x_4 = 2), the second gives one case. In total you have 4 ways of doing it.

    Now try it for n and k.
     
  6. Apr 3, 2009 #5
    But I don't know where to fit in n .

    if
    x1 = 1 then x2+x3+...+xn = k-1 (n-1 x left to choose)
    OR
    x1 = 2 then x2+x3+...+xn = k-2 (n-1 x left to choose)

    The n-1 can be chosen in how many ways? Because the choice for x2 is as you said depending on if x1 = 1 or 2 and also the value of k (remember: n <= k <= 2n) . So how do I formalise that?

    if x1 = 2

    x2=1 then x3+...+xn = k-2-1
    x2=2 then x3+...+xn = k-2-2
    (n-2 x left to choose)

    How do i choose the rest n-2 ??

    etc

    Help greatly appreciated:smile:
     
  7. Apr 3, 2009 #6
    Ok I've reached a formula by trial and error hehe :)

    n over k-n .

    But can anyone help me with answering my previous post?
     
  8. Apr 3, 2009 #7

    Avodyne

    User Avatar
    Science Advisor

    Suppose you were told that the sum consisted of [itex]n_1[/itex] 1's and [itex]n_2[/itex] 2's. Could you then answer the question of how many ways there are to create the sum?

    Then, given [itex]n_1[/itex] and [itex]n_2[/itex], what are [itex]k[/itex] and [itex]n[/itex]?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics: creating a sum
  1. Combinatorics question (Replies: 2)

Loading...