KEMBAR78
Recursive Relations | PDF
Scribd
Upload
49 views1 page

Recursive Relations

The document contains 10 problems about finding recursive relations for various sequences. The problems involve tiling rectangles with tiles, coloring segments or polygons with colors, counting strings of characters with certain constraints, and paths on graphs. Solutions involve determining the number of ways to build up to length n+1 based on length n.

Uploaded by

28ahsan.khalid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
49 views1 page

Recursive Relations

The document contains 10 problems about finding recursive relations for various sequences. The problems involve tiling rectangles with tiles, coloring segments or polygons with colors, counting strings of characters with certain constraints, and paths on graphs. Solutions involve determining the number of ways to build up to length n+1 based on length n.

Uploaded by

28ahsan.khalid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

RECURSIVE RELATIONS

SEYED HESSAM FIROUZI

(1) What is the number of ways to put some disjoint 1 × 2 tiles on a 1 × 12 rectangle, such that
no more tiles can be placed (every tile completely two neighbor squares).
(2) The 1 × n (n ≥ 1) rectangle is devided to unit squares. Prove that the number of wayes to
color some unit segments, such that in every square at least one segment is colored, is odd.
(3) an is the number of strings of length n by a, b and c such that do not contain abc. Find a
recursive relation for an .
(4) an is the number of strings of length n by a and b such that every a is adjacent to at least
another a. Find a recursive relation for an .
(5) Given k ∈ N, an is the number of ways to color vertices of n-gon A1 , . . . , An by k colors
such that no two adjacent vertices have different colors. Find a recursive relation for an .
(6) an is the number of permutations x1 , . . . , xn of [n] such that for any k ∈ [n−1], max(x1 , . . . , xk ) >
k. Find a recursive relation for an .
(7) an is the number of strings of length n by a, b and c such that every a is adjacent to at least
one b. Find a recursive relation for an .
(8) an is the number of ways to go from A to B by n steps in pentagon ABCDE. In any move
we can go from a vertex to one of its neighbors. Find a recursive relation for an .
(9) Prove that the number of ways of tiling a 3 × 200 rectangle by dominos is divisible by 3.
(10) Find the number of strings of length 2023 by a, b and c such that any of them appear odd
times.

You might also like