Combinatorics: Creating a Sum of 1's and 2's with Repetitions Allowed

[majestrooo]

Homework Statement

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.

Homework Equations

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

The Attempt at a Solution

A few failed attempts :(

 

[Avodyne]

A few failed attempts :(

Let's see 'em!

 

[majestrooo]

Let's see 'em!

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? :)

 

[Focus]

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.

 

[majestrooo]

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.

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

 

[majestrooo]

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?

 

[Avodyne]

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

Then, given n_1 and n_2, what are k and n?