3
votes
2answers
89 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
0
votes
1answer
75 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
0
votes
2answers
31 views

Can I write a Non Homogenerous equation as homogenous

Say I have Fibonacci R.Relation, $$ r^2=r+1 $$ Can I write it as $r^2-r-1=0$? From what I know a homogeneous equation is an equation equated to zero.
10
votes
2answers
477 views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
0
votes
1answer
30 views

I have a recursively defined function, and another function involving powers of a matrix. How can I show that they are equal?

The problem is Let $A$ be the $n \times n$ adjacency matrix of a graph $G=(V,E)$ on $n$ vertices, i.e. $A=(a_{ij})$ and $$a_{ij}=\begin{cases} 1 & ij\in E \\ 0 & ij\notin E ...
0
votes
2answers
140 views

Mathematical formula to find adjacent items in a grid

I have a 3x3 grid of dots. Selecting any one of the 9 dots, I need to find out which of the remaining dots are adjacent to the first dot. So, if for example we chose the first dot in the first row ...
-1
votes
1answer
78 views

Recurrence Relation Over Paths [closed]

Let $v$ and $w$ be distinct vertices in $K_n$. Let $p_m$ denote the number of paths of length $m$ from $v$ to $w$ in $K_n$, $1\leq m \leq n$. $(a)$ $\hspace{1cm}$Derive a recurrence relation for ...
3
votes
1answer
111 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} ...
17
votes
2answers
862 views

Self-avoiding walk on $\mathbb{Z}$

How many sequences $a_1,a_2,a_3,\dotsc$, satisfy: i) $a_1=0$ ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$) iii) $a_i\neq a_j$ for $i\neq j$ iiii) $\mathbb{Z}=\{a_i\}_{i>0}$ Are the two alternating ...