Test of Independence: Combinatorics for P-values? I feel bad for posting a whole question, but I'm really stuck on it, and would appreciate anything even a hint to it!
I'll show what I tried at the bottom.
Question
A test is used to determine if a sequence of binary numbers are independent, by counting the number of times $X$ that there is a change in response between consecutive trials in the sequence (from failure to success and vice versa).
As an example, a sequence (let $S$ denote success and $F$ denote failure) is
$$S \ S \ F \ S \ F \ S \ F \ S \ S \ F.$$
This sequence has $X = 7$ changes.  
$(i)$ Assume this test is an unconditional test, with some known probaility $p = 0.5$ where $n$ is the number of trials.
Explain why $X \sim Bin(n-1,0.5)$.
$(ii)$ Consider the 3 sequences:
$$(A): \ \ \ F \ F \ S \ S \ S \ S \ S \ F \ F \ S \\ (B): \ \ \ S \ S \ F \ S \ F \ S \ F \ S \ S \ F \\ (C): \ \ \ S \ S \ S \ F \ S \ F \ S \ S \ F \ F.$$   
Which test is the least consistent with a sequence of independent failures/successes?
We are given the p-values for
$X = 1,2,3,4,5,6,7,8,9$ being $0.002, \quad 0.020, \quad 0.090, \quad 0.254,  \quad0.500, \quad 0.746, \quad 0.910, \quad 0.980 , \quad0.998, \quad 1.000$ respectively.  
My attempts
The amount of changes $K$ are dependent on how many $F's$ are squeezed between two adjacent $S's$.
So for the case where $F$ does not start at the beginning or end,
we require $\frac{K}{2}$ number of failures, where $K$ is even. The number of ways we can do this is: $\begin{pmatrix} n-1 \\ \frac{K}{2}\end{pmatrix}$. Sadly, this is only the case where $K$ is even and when the failures are not adjacent to other failures...   
$(ii)$ I feel like the most least "consistent" is $(A)$, but I'm not sure how to mathematically reason with this. Do we test a hypothesis that $p = 0.5$ vs. $p \neq 0.5$?
 A: If the coin is fair the probability of a change is 50-50 each time you flip a new coin and is independent of the previous flips. There are $n-1$ opportunities for a change in $n$ flips. This is why it's binomial(1/2,n-1). 
To figure out which is least consistent count the number of changes in each data set. You expect $(n-1)/2$ changes and the set that deviates the most from this is the least consistent.
I do not know why they call the list of numbers they give you "p values". It differs sharply from the usual meaning of the term.
A: I think you might mean which sequence, (A), (B), or (C), is least
consistent with independence.
If I count correctly, (A) has 3 changes, (B) has 7 changes, and (C) has 5
changes. For $X \sim \mathsf{Binom}(9, .5),$ the expected number is
$E(X) = 4.5.$ So (B), with $X = 7$ is apparently farthest away for
what is expected; that is $|7 - 4.5| = 2.5.$ 
By the standard definition of P-value,
values of $X$ that are farther away (in either direction) are 0, 1, 2, 7, 8, and 9. So the P-value is $1 - P(X = 3,4,5,6) \approx .18.$ Because this exceeds 0.05,
$X = 7$ is not significantly different from 4.5, so there is not evidence
to argue that even sequence (B) is non-random. This is not surprising because a sequence of ten outcomes is seldom enough to establish non-randomness.
In general, this kind of test of independence is called a runs test. You
can google that if you want to know more. (A run is a sequence of repeated
values.)  
While I have been typing this, another Answer by @spaceisdarkgreen has appeared.
It is somewhat different from mine in details, but I agree with it and have
up-voted it.
