### PROBLEM LINK:

**Author:** Utkarsh Saxena

**Testers:** Jakub Safin

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

easy-medium

### PREREQUISITES:

probability, expected value

### PROBLEM:

Consider a string s = “aaabbaa”. Let us call maximal sequence of continuous ones as a group. You have to find expected the number of groups in a string of length N and alphabet size K. The final output required in the problem was twice of this value.

### SOLUTION

### Satyaki’s solution.

Let E(N, K) be the answer for given N and K.

The recurrence is -

We can keep the N-th character same as N-1-th character with probability \frac{1}{K}, in this case, the E(N, K) remains same as of E(N-1, K). In the other case when the N-th character is different than the N-1-th character, the number of groups will be 1 more.

### Linearty of expectation based solution

The number of maximal groups is 1 + the number of character changes. The probability of each of change is \frac{K-1}{K}. By linearity of expectation, the number of groups will be (N-1) \frac{K-1}{K}.

So, the answer will be 1 + (N-1) \frac{K-1}{K}.

### Combintorics based solution

The number of strings for which the number of groups is g is given by K * (K - 1)^{g - 1} * \binom{N - 1}{g - 1}. The combination \binom{N - 1}{g - 1} denotes the selection of g-1 places where the character will change. The character of the first group can be selected in K ways, then the second group in K-1 ways, third K-1 ways, and so on till the g-th group.

So, the expected number of groups will be

By change of variable g \rightarrow g + 1

The term

Binomial theorem states

In this formula, if we replace x by K-1, and n by N-1, we get the second term of the above summation. So, the second term becomes K^{N-1}.

Let us see how to calculate the first term.

By differentiating the binomial theorem by both the sides, we get.

Multiplying both the sides by x, we get

So, by replacing x with K-1 and n by N-1 again, we get the first term of the summation

So, the expected number of groups turn out to be

.