0
votes
3answers
48 views

Recursion Problem [closed]

a) Ten people are sitting in a row of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
0
votes
3answers
35 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
0
votes
3answers
108 views

Strong Induction and Recursion

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that ...
1
vote
2answers
82 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
14
votes
1answer
235 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
0
votes
1answer
41 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
0
votes
1answer
40 views

Combinatorics recursion question. [closed]

How many binary vectors of length n do not contain a sequence '001' ? Solve by recursion and explain your solution.
0
votes
1answer
31 views

A question on combinatorics

Bob and Laura have bought an apartment, and are going to carpet the floor in the kitchen. The kitchen has size $2 \times n$, where $n$ is a positive integer. In how many ways can Bob and Laura ...
0
votes
1answer
25 views

Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
0
votes
1answer
46 views

Recursive Formula

I have found a question in my book and I have solve it, but I am not sure about the answer. The question goes like this: Find a recursive formula that will give the number of ways to order $N$ ice ...
1
vote
1answer
56 views

Need help with proving the recursion

Let $p_{k}(n)$ indicate the number of partitions of n into k parts. Prove: $$p_{k}(n) = p_{k-1}(n-1) + p_{k}(n-k)$$ Example: There are two partitions of $5$ into three parts. $5 = 3+1+1$ $5 = ...
2
votes
1answer
66 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...
2
votes
1answer
94 views

Identity involving a recursive product

Here is yet another problem related to plane partitions. Given the recursive formula $$ \begin{align*} F(0)&=1,\\ F(r)&=\prod_{i=1}^r\frac{i+2r-1}{2i+r-2}F(r-1). \end{align*} $$ How can we ...
1
vote
1answer
56 views

Combinatorial Recursion 2

Define a recursion $a(n,k)$ that gives the number of ways to choose $n$ items out of $k$ types of items, with the condition that we must choose $2, 4$, or $6$ items of each type. So $2p+4q+6r = n$ ...
0
votes
1answer
73 views

Combinatorial Recursion

Define a recursion that gives the number of sequences that include the numbers $0,1,2,3$ with an even number of $1$'s and an even number of $0$'s. So far I got $$a(n) = 2a(n-1) + 2a(n-2)$$ which ...
3
votes
1answer
109 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
1
vote
2answers
82 views

Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
1
vote
2answers
38 views

Simple linear recursion

$x_n=\frac{x_{n-1}}{a}+\frac{b}{a}$ with $a>1, b>0$ and $x_0>0$ I tried to solve it using the generating function but it does not work because of $\frac{b}{a}$, so may you have an idea.
2
votes
1answer
92 views

OEIS A000255 recursion.

I encountered the sequence A000255. $a(n)$ counts permutations of $[1,...,n+1]$ having no substring $[k,k+1]$ I am finding difficulty in proving it. Can you please give any clues or hints on how to ...
2
votes
3answers
225 views

Need to find the recurrence equation for coloring a 1 by n chessboard

So the question asks me to find the number of ways H[n] to color a 1 by n chessboard with 3 colors - red, blue and white such that the number of red squares is even and number of blue squares is at ...
7
votes
1answer
505 views

Bell numbers, recursions, bijections

The $n$th Bell number, named after Eric Temple Bell (although he was far from the first to think about them), is the number of partitions of a set of cardinality $n$. If they are written in the top ...