# Thread: Difficult Combinatorics Problem, Help PLZ

1. ## Difficult Combinatorics Problem, Help PLZ

i have this assignment due tmrw where i have to answer this question, plzzzzzzzz help i really dont understand it, im being marked for the process of thinking so steps will be very helpful

in a sequence of p zeroes and q ones, the ith term ti, is called a change point if ti does not equal ti-1, for i= 2,3,4....p+q. For example, the sequence of 0,1,1,0,1,0,1,0 has p=q=4, and five change points t2, t4, t6, t7, t8. For all possible sequences of p zeroes and q ones with 1 less then or equal to p which is less then or equal to q, determine the average number of change points.

i know its a difficult problem but plz jus try to help i really dont understand it!

2. Originally Posted by ChiragDesai01
i have this assignment due tmrw where i have to answer this question, plzzzzzzzz help i really dont understand it, im being marked for the process of thinking so steps will be very helpful

in a sequence of p zeroes and q ones, the ith term ti, is called a change point if ti does not equal ti-1, for i= 2,3,4....p+q. For example, the sequence of 0,1,1,0,1,0,1,0 has p=q=4, and five change points t2, t4, t6, t7, t8. For all possible sequences of p zeroes and q ones with 1 less then or equal to p which is less then or equal to q, determine the average number of change points.

i know its a difficult problem but plz jus try to help i really dont understand it!

Define $\displaystyle X_i = \begin{cases} 1 \text{ if } t_i \neq t_{i-1}\\ 0 \text{ otherwise} \end{cases}$

For any i from 1 to p+q-1,
$\displaystyle Pr(t_{i-1} = 0) = p / (p+q)$ and $\displaystyle Pr(t_i=1 | t_{i-1} = 0) = q / (p+q-1)$
$\displaystyle Pr(t_{i-1} = 1) = q / (p+q)$ and $\displaystyle Pr(t_i=0| t_{i-1} = 1) = p / (p+q-1)$
so
$\displaystyle Pr(X_i = 1) = \frac{p}{p+q} \frac{q}{p+q-1} + \frac{q}{p+q} \frac{p}{p+q-1} = \frac{2pq}{(p+q)(p+q-1)}$
This is also $\displaystyle E(X_i)$.

The number we want, the average number of change points, is
$\displaystyle E(X_1 + X_2 + \cdots + X_{p+q-1})$. There is an extremely useful theorem saying that if X and Y are random variables then E(X+Y) = E(X) + E(Y). It's important to note that it is not necessary that X and Y be independent in order to apply this theorem. This good for us because the $\displaystyle X_i's$ are not independent. So let's apply it as follows:

$\displaystyle E(X_1 + X_2 + \cdots + X_{p+q-1})$
$\displaystyle = E(X_1) + E(X_2) + \cdots + E(X_{p+q-1})$
$\displaystyle = (p+q-1) E(X_i)$
$\displaystyle = (p+q-1) \frac{2pq}{(p+q)(p+q-1)}$
$\displaystyle = \frac{2pq}{p+q}$

Hope this helps-- I'm in a rush, but then so are you.

jw

3. broooooo thanks alot! this dus help im jus guna copy this into my notebook cuz im getting marked on process and thinking thanks boss