Tag Info

Hot answers tagged

5

If we let $p$ be the probability that the algorithm stops, then note that at step 1 (i.e., after one iteration), then half the time it has stopped; and half the time it has three new nodes; in which case the original node stops if and only if all three subnodes stop. In the latter case, the chance that that all three subnodes will stop is $p^3$; so we can ...


4

While I believe that Chas Brown has essentially given the correct answer plus an intuitive derivation, I just want to point out that you can link this question to a standard result about Galton-Watson branching processes. A Galton-Watson branching process is a discrete-time stochastic process describing the evolution of a population and it is characterized ...


3

Let there be $1$ vertex at time $0$. At time $n$, take all vertices that currently exist and either replace them with three new vertices or delete them, with equal probability. We are interested in the probability that all vertices die out at some point. Let $p_n$ be the probability that all vertices die out in $n$ or less steps. As has been observed by ...


3

What about the sequence of trees of which the first three are shown below? None is a subtree of any other.


2

You need to distinguish $n!$ outcomes, and you need at least one leaf for each thing that you distinguish, so you need at least $n!$ leaves; this has nothing to do with the lemma. The lemma comes into play at the next step: if the height were less than $\lg n!$, the tree would have fewer than $n!$ leaves, so it must have height at least $\lg n!$. Added: To ...


2

If you want your operations to be 1,2,1,2,1,2,1,2, then such an order will ensure that all your trees will have either $n$ or $(n+1)$ vertices, and since there is only a finite number of non-isomorphic trees of size $n$, you will get infinitely many copies of at least one of them. On the other hand, if the order of operations is unconstrained, then an ...


2

HINT: The forest must consist of exactly two trees. Partition $V$ into two disjoint non-empty subsets, $V_0$ and $V_1$, and let $V_0$ be the subset containing the vertex $1$. $V_0$ and $V_1$ will be the vertex sets for the two trees. Let $k=|V_0|$. Since we’ve decided that vertex $1$ will be in $V_0$, how many ways are there to choose the rest of $V_0$? ...


1

Let $k$ be the number of vertices in the component containing vertex $1$. Then $1\le k\le n-1$. For each such $k$, choose the other $k-1$ of $n-1$ available vertices to be in the same component as $1$; choose one of the $k^{k-2}$ possible trees on these vertices; choose one of the possible trees on the other $n-k$ vertives. See if you can fill in the ...


1

1) Because you want the expected depth, you need a way to control the depth of the decision tree and by knowing that you will have at least $n!$ leaves(possible orders) it seems fair that you want $\frac{n!log(n!)}{n!}$ to happen. 2) When you glue together the 2 subtrees you are creating a new level. Because of that, every path from a leave to the root ...


1

Because A binary tree of height $h$ has at most $2^h$ leaves. implies A binary tree with at least $2^h$ leaves has a height at least $h$.


1

First, the graph may not be connected, so it should be pointed out that $T(1,1)$ counts the number of maximal spanning forests, not the number of spanning trees. The answer to your question is that not all summands of $T(1,1)$ are zero. Sometimes a summand will be of the form $0^00^0$, and in combinatorics, we make the convention that $0^0=1$. See here for ...


1

Hint: Pre-order traversal is root; left; right so your preorder is ok. r, j, h, g, e, d, b, a, c, f, i, k, m, p, s, n, q, t, v, w, u The in-order traversal is left; root; right. I have h, e, a, b, d, c, g, f, j, i, r, m, s, p, k, n, v, t, w, q, u so your in-order is definitely wrong. Post order: left; right; root a, b, c, d, e, f, g, h, i, j, s, p, m, v, ...


1

Probability of stopping in exactly n steps is the probability of $n-1$ no-stopping events times probability of last stopping event, as they are independent. Hence the probability of stopping exactly at step n is $(1/2)^{n-1} (1/2)$ = $(1/2)^n$ for n = 1,.... Then add all of those $\sum^\infty_1 (1/2)^k$ = $1/2 + 1/4 + 1/8 + ...$ = 1, so it will stop almost ...


1

We note a tree $T$ with $n$ vertices has $n-1$ edges. So let $F = \bigcup_{i=1}^{k} T_{i}$ be the forest- a union of trees. Let $n_{i}$ be the number of vertices in each tree. So we have: $|V(F)| = \sum_{i=1}^{k} n_{i} = n$ Since each component of the forest is a tree, we have $n_{i} - 1$ edges for $T_{i}$, giving us: $|E(F)| = \sum_{i=1}^{k} (n_{i} - 1) ...



Only top voted, non community-wiki answers of a minimum length are eligible