[Tutorial] Recurrent Sequences — Application of combinatorics in DP (basics)

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Hello Codeforces community! I decided to write tutorial about recurrent sequences, tutorial is about very basics of that topic. If you have little combinatorics knowledge, you will understand this tutorial easily. This is my first tutorial, so this can be easy for you and there can be mistakes. Probably all Div1 users knows all things in this tutorial :) Hope this tutorial will help you. If you have any questions/suggestions please write in comments.

Recurrent Sequences — Application of combinatorics in DP

Let’s start with a problem to this topic.

Problem. In how many different ways you can write 8 (+) and 5 (-) signs consecutively such that no two (-) signs are adjacent are adjacent.

Solution of problem is easy. Let’s write (+) signs after 9 ms:

m + m + m + m + m + m + m + m + m

Now let's change 5 of ms to (-) sign. Actually, problem has been solved, no 2 (-) signs are consecutive. So, answer is $\text{[math]}$ (because there are 9 ms and we have to choose 5 of them). Generally, if we have k (+) signs and r (-) signs, we can make $\text{[math]}$ sequences such that no two (-) signs are consecutive.

Problem. There are 10 signs are written on the board consecutively. How many different sequences we can create if some of them are (+) and some of them are (-) signs such that no two (-) signs are adjacent.

Let's think all situations:

tutorial

With formula we found in previous problem answer is:

$\text{[math]}$

Generalized version of problem: If we have x signs which some of them are (+) and some of them are (-) signs, how many sequences we can create such that no two (-) signs are adjacent.

So, answer for this problem is

$\text{[math]}$

Let's write some few terms of S(n):

$\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , S(3) = 5, S(4) = 8, S(5) = 13 etc.

It remembered you something? Yes, Fibonacci numbers! Let's prove they are really Fibonacci numbers:

There are some proofs with Binet's formula, but we will prove this by strong induction:

$\text{[math]}$

We verified some first terms. Assume it is true for - 1, 0, 1, .., n and we want to show that it is true for n + 1:

$\text{[math]}$

Problem. In how many different ways rabbit can go 10th step if it can jump 1 or 2 steps?

Well, we can solve this problem by analyzing some cases, but it will be hard way for calculating answer. So, let's think a little different. We can go 10th step from 9th step or 8th step, then answer for going 10th step is sum of answers for 9th step and 8th step. If F(n) is answer for going n'th step, we can calculate it by this recursive formula: F(n) = F(n - 1) + F(n - 2) with base cases F(1) = 1 and F(2) = 2.

Problem. (Hanoi towers) As you can see below there are 8 discs and 3 sticks. We can change places of discs with some rules: Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. No disk may be placed on top of a smaller disk. Find minimum moves to move all discs to 3rd (left) stick.

tutorial1

For solving this problem, let's think little cases firstly. If we had 1 discs, we could solve problem in 1 step. If we had 2 discs, first we put little disc to middle stick, then big disc to left stick, then little disc to left stick, so in 3 moves we could do it. There is a gif for doing this for 3 discs:

So, if we have n discs, we can solve problem like this:

Move (n-1) smaller than biggest discs to middle stick (*)
Move biggest disc to 3rd (left) stick (**)
Move (n-1) smaller than biggest discs to 3rd (left) stick (***)

We can't move biggest disc without taking other. If 3rd (left) stick is not empty, we can't put biggest on it. So, using this 2 facts it is the best strategy to solve problem. Let H(n) be answer for n discs. Then we can do (*) and (***) in H(n - 1) steps and (**) in 1 step. So, we can calculate H(n) by this recursive formula: $\text{[math]}$ .

So, we can solve this problem in O(n) easily. But, what about if n is very big, like n ≤ 10¹⁸, for this constraint we have to make faster algorithm. Let's write first few terms of H(n):

H(1) = 1, H(2) = 2 * H(1) + 1 = 3, H(3) = 2 * H(2) + 1 = 7, H(4) = 2 * H(3) + 1 = 15 etc.

It is not hard so see H(n) = 2ⁿ - 1, so let's prove it by induction:

We show it is correct for first few terms
Assume that H(n - 1) = 2^n - 1 - 1 and show H(n) = 2ⁿ - 1

$\text{[math]}$

Prove is done!

Problem. There is a park station such just Cadillac, Continental and Porsche (yeah, very expensive station) can park there. Cadillac and Continental are big cars, so they need 2 "car place" to park and Porsche needs 1 "car place" to park. If there are n "car places" in park station find out in how many different ways cars can park at station. (It is not important to park all types of cars).

Let P(n) be answer for n "car places". If Porsche parks at first "car place", answer for remaining (n-1) places is P(n - 1). If Cadillac parks at first two "car places", answer for remaining (n-2) places is P(n - 2) , same thing for Continental. So our recurrence relation is:

P(n) = P(n - 1) + 2 * P(n - 2) and bases cases are P(1) = 1 and P(2) = 3 (easy to show).

Challenge Problem. Write code which solves previous problem for n ≤ 10¹⁸ constraint.

Challenge Problem. n runners will do a race. Some runners can pass finish line at the same time, for example, 6th runner finished race 1st, 2nd and 5th runners finished race 2nd and other 3rd. How many different results of race can be there?

P.S. Finally, I finished this tutorial :) Writing tutorial is really hard. I'm really sorry for some mistakes, please write if you have question.

Comments (20)

Show archived | Write comment?

TooNewbie

7 years ago, # |

Seems I have haters :\ Got -5 in 1 minute

→ Reply

Dalgerok

← Rev. 2 →

Very grateful for the first and last tasks :)

computerbox

Good work TooNewbie !

stringray

good work .

sniffleheim

Thank you for the tutorial! I think there is another interesting combinatorial proof for the first problem.

Let a_n be the number of sequences of length n comprised of "-" or "+" signs such that no two "-" signs are adjacent. Let b_n be the number of such sequences that end with "-", and c_n be the number of such sequences that end with "+".

Then we get the recurrences b_n = c_n - 1, c_n = c_n - 1 + b_n - 1 = c_n - 1 + c_n - 2, since we can only generate a string that ends with "-" by appending a "-" to a string that ends with "+", but we can get a string that ends with "+" by appending "+" to any string.

Now since c₁ = 1, c₂ = 2, it is evident that c_n follows the Fibonacci recurrence, and so does b_n (except it's shifted one index back). Then it follows that a_n = b_n + c_n = c_n - 1 + c_n = c_n + 1 = c_n + 2, and so a_n follows the Fibonacci recurrence as desired.

7 years ago, # ^ |

This proof is similar with solution of Parking Places problem :)

JustAni

Is there any direct formula for first challenge problem? I have tried my best but only succeeded in reducing the number steps by some factor. If there is any direct formula can you please explain it?

Well, the easiest way is matrix exponentiation, but there is better way:

We will write characteristic equation, let c be constant then our equation is:

cⁿ = c^n - 1 + 2c^n - 2

c² = c + 2 and c² - c - 2 = 0

We get c = 2 and c = - 1. So, for some x, y,

P(n) = x * 2ⁿ + y * ( - 1)ⁿ

Also, we know that P(1) = 1 and P(2) = 3, lets write this terms with x, y:

P(1) = 1 = 2x - y

P(2) = 3 = 4x + y

From this system, we get $\text{[math]}$ and $\text{[math]}$

So, final answer is:

$\text{[math]}$ which is easy to calculate in O(logN)

Great method! Thank you :D This method only works when there are real roots of the characteristic equation. Isn't it?

Well, I didn't faced with problem which doesn't have real roots of its characteristic equation, but it would be weird, because if it hasn't real roots then it means this function is decreasing function, and with big values you will get big negative numbers, and if they ask you to find it MOD M, you can (not in some cases) modify problem for solving it with characteristic equation.

And it is very standard matrix exponentiation problem, there are not very good resources for learning it, but this + practice problems will do work.

Thank you for your reply. I'll try out this method with other recurrences to understand it in a better way. For matrix exponentiation I found this blog which helped me in understanding it.

Tutis

If you want to calculate some weird function like a*(x+sqrt(y))^n+b*(z+sqrt(y))^n mod p you can do it using fast exponentiation and storing a number like a+b*sqrt(y) mod p.