1. ## Combinatorics question

a) What is the number of sequences of length 20 of 1, -1 so that the total sum of the numbers is 0?
The answer is 20 choose 10 right?

This is what I'm stuck on:
b) How many of the sequences in part a) have a positive sum for the first k numbers and a negative sum for the first m numbers? (where 1≤k≤m≤20)

Thanks

2. a) Nope.

To get 0, you need to have exactly 10 of -1 and 10 of 1.

Now the number of sequences is $\dfrac{20!}{10! \times 10!}$

20! is 'shuffling' all the 20 terms
10! is dividing by the number of ways -1 can be arranged because there are 10 similar -1
The other 10! is for 1.

EDIT: Cross that out, I messed up P and C... again -.-

b) I don't know the shortcut (though I'd like to learn about it) but I could do by the long way.

For the first k numbers, the sum is positive when you have:
k = 1, first term 1
k = 2, first terms 1 1
k = 3, first terms 1 1 1, or 1 1 -1
k = 4, first terms 1 1 1 1, or 1 1 1 -1
k = 5, first terms 1 1 1 1 1, or 1 1 1 1 -1, or 1 1 1 -1 -1
.
.
.
k = 10, first terms 10(1), or 9(1)1(-1), or 8(1)2(-1), or 7(1)3(-1), or 6(1)4(-1)

Then, you multiply by 2 due to the symmetry for the last term to be negative.

When k = 1, you have $\dfrac{19!}{10! \times 9!}$

When k = 10, you have $\dfrac{10! \times 10!}{10! \times 10!} + \dfrac{10! \times 10!}{9! \times 9!} + \dfrac{10! \times 10!}{8!\times 2!\times 2!\times 8!} + \dfrac{10! \times 10!}{7!\times 3!\times 3!\times 7!} + \dfrac{10! \times 10!}{6!\times 4!\times 4!\times 6!}$

Okay, maybe a summation formula would simplify that calculation...

3. Originally Posted by Unknown008
a) Nope.
To get 0, you need to have exactly 10 of -1 and 10 of 1.
Now the number of sequences is $\dfrac{20!}{10! \times 10!}$
It is worth pointing out that:
$\dbinom{20}{10}=\dfrac{20!}{10! \times 10!}$ that is a combination of twenty choosing ten.

I don't understand what part (b) means.

4. But isn't

$\displaystyle \binom{20}{10} = \dfrac{20!}{10!}$

Now, I'm very confused >.<

EDIT: Sorry, that's 20P10. I'll be correcting my above mistake...

5. Originally Posted by Unknown008
But isn't
$\displaystyle \binom{20}{10} = \dfrac{20!}{10!}$
$\displaystyle \binom{N}{k} = \dfrac{N!}{k!(N-k)!}$