Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1 \leq k \leq n-1$. For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1$, $2$, $3$, $4$, $5$, but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1$, $2$, $\ldots$, $7$.

There are $2^{10} = 1024$ possible $10$-letter strings in which each letter is either an $A$ or a $B$. Find the number of such strings that do not have more than $3$ adjacent letters that are identical.

In a small pond there are eleven lily pads in a row labeled $0$ through $10$. A frog is sitting on pad $1$. When the frog is on pad $N$, $0 < N < 10$, it will jump to pad $(N-1)$ with probability $\frac{N}{10}$ and to pad $(N+1)$ with probability $1-\frac{N}{10}$. Each jump is independent of the previous jumps. If the frog reaches pad $0$ it will be eaten by a patiently waiting snake. If the frog reaches pad $10$ it will exit the pond, never to return. What is the probability that the frog will escape without being eaten by the snake?

How many length ten strings consisting of only $A$s and $B$s contain neither "$BAB$" nor "$BBB$" as a substring?

Cozy the Cat is going up a staircase of $10$ steps. She can either walk up $1$ step a time or jump $2$ steps a time. How many different ways can she reach the top of this staircase?

Joe wants to write $1$ to $n$ in a $1 \times n$ grid. The number 1 can be written in any grid, while the number $2$ must be written next to $1$ (can be at either side) so that these two numbers are together. The number 3 must be written next to this two-number block. This process goes on. Every new number written must stay next to the existing number block. How many different ways can Joe fill this $1 \times n$ grid?

How many different ways are there to cover a $1\times 10$ grid with some $1\times 1$ and $1\times 2$ pieces without overlapping?

Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24$. A fence is located at the horizontal line $y = 0$. On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where $y=0$, with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where $y < 0$. Freddy starts his search at the point $(0, 21)$ and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.

Show that $$\binom{n}{1}-\frac{1}{2}\binom{n}{2}+\frac{1}{3}\binom{n}{3}-\cdots+(-1)^{n+1}\binom{n}{n}= 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$$

Misha rolls a standard, fair six-sided die until she rolls $1-2-3$ in that order on three consecutive rolls. Find the probability that she will roll the die an odd number of times.

How many different strings of length $10$ which contains only letter $A$ or $B$ contains no two consecutive $A$s are there?

Dividing a circle into $n \ge 2$ sectors and coloring these sectors using $m\ge 2$ different colors. If no adjacent sectors can be colored the same, how many different color schemes are there?

Let $\mathbb{S} =\{a_1,\ a_2,\ \cdots,\ a_n\}$ be a permutation of $\{1,\ 2,\ \cdots,\ n\}$ which satisfies the condition that for every $a_i$, $(i=1$, $2$, $\cdots$, $n)$, there exists an $a_j$ where $i< j \le n$ such that $a_j=a_i+1$ or $a_j=a_i-1$. Find the number of such $\mathbb{S}$.

Let $\mathbb{S}=\{a_1,\ a_2,\ \cdots,\ a_n\}$ where every element $a_i\in\{1,\ 2,\ \cdots,\ k\}$. Find the number of $\mathbb{S}$ which has an even number of $1$s.

In the Banana Country, only Mr Decent always tells the truth and only Mr Joke always tells lies. Everyone else has a probability of $p$ to tell a lie. One day, Mr Decent has decided to run for the President and told his decision to the first person who in turn told this to the second person. The second person then told this to the third person, and so on, till the $n^{th}$ person who told this news to Mr Joke. No one has been told this news twice in this process. Finally, Mr Joke announced Mr Decent's decision to everyone. What is the probability that Mr Joke's statement agrees with Mr Decent's intention?

As shown, an isosceles trapezoid is obtained by removing the top part of an equilateral triangle. The lengths of its two bases are $a$ and $b$, respectively, which are both integers. Both bases and sides are equally divided into unit-length parts. Their ending points are then connected to create several segments which are parallel to either two bases or one side. Find the number of equilateral triangles in this diagram.

Find the number of ways to divide a convex $n$-sided polygon into $(n-2)$ triangles using non-intersecting diagonals.

Given two distinct values $b_1$ and $b_2$, their product can be written in two ways: $b_1\times b_2$ and $b_2\times b_1$. Given three distinct values $b_1$, $b_2$, and $b_3$, their products can be expressed in $12$ ways: $b_1\times(b_2\times b_3)$, $(b_1\times b_2)\times b_3$, $b_1\times(b_3\times b_2)$, $(b_1\times b_3)\times b_2$, $b_2\times(b_3\times b_1)$, $(b_2\times b_3)\times b_1$, $b_2\times(b_1\times b_3)$, $(b_2\times b_1)\times b_3$, $b_3\times(b_1\times b_2)$, $(b_3\times b_1)\times b_2$, $b_3\times(b_2\times b_1)$, and $(b_3\times b_2)\times b_1$. Please note that in this definition, orders matter and parentheses etc cannot be simplified. The question is how many different ways to express the product of $n$ distinct values?

Let $x_i\in\{+1,\ -1\}$, $i=1,\ 2,\ \cdots,\ 2n$. If their sum equals $0$ and the following inequality holds for any positive integer $k$ satisfying $1\le k < 2n$: $$x_1+x_2+\cdots + x_k\ge 0$$

Find the number of possible ordered sequence $\{x_1,\ x_2,\ \cdots,\ x_{2n}\}$.

(Hanoi Tower) There are $3$ identical rods labeled as $A$, $B$, $C$; and $n$ disks of different sizes which can be slide onto any of these three rods. Initially, the $n$ disks are stacked in ascending order of their sizes on $A$. What is the minimal number of moves in order to transfer all the disks to $B$ providing that each move can only transfer one disk to another rod's topmost position and at no time, a bigger disk can be placed on top of a smaller one.

Find the total number of sequences of length $n$ containing only letters $A$ and $B$ such that no two $A$s are next to each other. For example, for $n = 2$, there are $3$ possible sequences: $AB$, $BA$, and $BB$.

Contessa is taking a random lattice walk in the plane, starting at $(1, 1)$. (In a random lattice walk, one moves up, down, left, or right $1$ unit with equal probability at each step.) If she lands on a point of the form $(6m, 6n)$ for $m$, $n\in\mathbb{Z}$, she ascends to heaven, but if she lands on a point of the form $(6m+ 3, 6n+ 3)$ for $m,\ n\in\mathbb{Z}$, she descends to hell. What is the probability that she ascends to heaven? 

In an election for the Peer Pressure High School student council president, there are $2019$ voters and two candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia both vote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of the remaining $2016$ voters votes for a candidate randomly, with probabilities proportional to the current number of the respective candidate’s votes. For example, the first undecided voter David has a $2/3$ probability of voting for Alice and a $1/3$ probability of voting for Celia. What is the probability that Alice wins the election (by having more votes than Celia)?