0
votes
1answer
42 views

Finding the parent of a node in recombining binomial tree

I have posted an earlier question: Finding the child node in the recombining binomial tree. Now I would like to find the parent of a node in recombining tree. The tree looks like this: Now I need ...
0
votes
1answer
389 views

counting cycles in an undirected graph

here is the problem: http://oi39.tinypic.com/30lkpvp.jpg this is the solution: http://oi41.tinypic.com/14wgleo.jpg my question is this. how did they know that it has edges between all ${n \choose ...
2
votes
1answer
139 views

Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. ...
7
votes
5answers
203 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
6
votes
3answers
243 views

Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is $${n \choose k} {n-1 \choose k} k!.$$ Is there a ...
3
votes
4answers
235 views

Computing a sum of binomial coefficients

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a lot ...
3
votes
1answer
974 views

Counting the number of directed graphs with $N$ vertices and $E$ edges?

Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even ...
5
votes
2answers
148 views

An identity on the number of trees

Let $T_n$ be the number of labelled trees on $n$ vertices, then $$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$ Using this question, I was able to prove that $$ T_n= \frac{n}{2} \ ...
9
votes
2answers
327 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...