0
votes
0answers
18 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
0
votes
1answer
24 views

Finding the number of spanning trees on a set of vertices.

I need to find the number of spanning trees on $V = \{1,2,3,4,5,6,7,8,9\}$, where $\{1,2,3,4\}$ are leaves. Can anyone tell me how?
2
votes
1answer
162 views

Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem: Consider a planar tree with $n$ non-root vertices. Give a generating function for vertices distance $d$ from the root. Proof that the total ...
1
vote
2answers
164 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is ...
1
vote
1answer
117 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
1
vote
1answer
19 views

How many spanning trees of a complete graph with an even number of vertices can be split in half by removing a single edge?

We have a complete Graph G with |V|=n . We know it has n^(n-2) possible spanning trees. How many of them could be split into two equal halves by removing a single edge?
0
votes
1answer
43 views

calculate the proportion of n-node trees whose root has only one or two subtrees.

Could we use combinatorics and generating functions to calculate the proportion of n-node trees whose root has only one or two subtrees? Here is what I tried: The combinatorial construction for the ...
3
votes
2answers
104 views

Number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves.

I've been trying to do the following exercise: The problem Find the number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves. I know that I should try to write an ...
0
votes
1answer
281 views

Minimum number of nodes in balanced binary search tree

I'd like to know if anyone could help me verify a recursive formula for the minimum possible number of nodes a binary search tree would require to be balanced. So far, I know that the recursive ...
5
votes
1answer
73 views

Finding graphs with a given number of spanning trees

All of the graphs considered in this question are connected. We can find the number of spanning trees $t(G)$ of $G$ using Kirchhoff's matrix-tree theorem or the deletion-contraction method. I'm ...
1
vote
1answer
47 views

Variance of Height of Tree

What is the asymptotic variance of the height of rooted plane trees (ie rooted, unlabelled, ordered trees with unbounded node degree) and of ordered binary trees (ie rooted, unlabelled, plane trees, ...
2
votes
1answer
37 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
0
votes
1answer
27 views

Transforming spanning trees through a sequence of intermediate trees

the problem is as follows: Let $G$ be a connected graph, and let $T_1$ and $T_2$ be two of its spanning trees. Prove that $T_1$ can be transformed into $T_2$ through a sequence of intermediate trees, ...
1
vote
0answers
102 views

Software/Applet to Draw Tree Diagrams (for Enumeration Problems)

I need a software/applet/flash file which easily draws tree diagrams for simple enumeration problems: I want to give number of the vertices in each layer, and it draws the diagram which shows all the ...
1
vote
1answer
33 views

Number of binary trees with same X-order and Y-order

What is the number of binary trees which have the same X-order and Y-order as the given tree? Example: X-order: POSTORDER(T) = POSTORDER(TL) POSTORDER(TR) root Y-order: ANTIORDER(T) = ...
4
votes
2answers
262 views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
2
votes
1answer
234 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
1
vote
4answers
833 views

How many labeled trees exist on n vertices with exactly 3 vertices of degree 1?

My combinatorics class is covering spanning trees right now and one of the questions being asked is "What is the number of labeled trees on n vertices with exactly $3$ vertices of degree $1$?" I've ...
0
votes
1answer
59 views

Counting the number of trees on $[n]$

Let $T_{n}$ be the number of trees on $[n]$. Explain the identity below in terms of $T_{n}$ and prove it. $2(n-1)n^{n-2}=\sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}(n-k)^{n-k-1}.$ So far I've got that ...
1
vote
2answers
93 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
2
votes
1answer
70 views

Given an $n$ level tree with $b$ branches at each node, how many unique paths are there from the root to the leaves?

I have a tree where, at each node, it splits into $b$ branches for a total number of $n$ levels. I enumerate the paths from the root to the leaf nodes. For example, if $n = b = 2$ then I have the ...
1
vote
0answers
113 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
3
votes
2answers
76 views

Number of undirected trees

Given n numbered vertices I want to know the number of different trees that can be created with them. I know that cayley's theorem says it's $n^{n-2}$, but why can't it also be: ...
2
votes
1answer
49 views

Is there a tree $T$ such that $\text{diam}(T) \geq k$, where $k$ is the number of vertices with degree less than 3?

Let $T$ be an undirected tree, let $d$ be the diameter of $T$, and let $s$ be the number of vertices in $T$ with degree less than 3. Recall the diameter of a graph is the length of the longest ...
5
votes
2answers
481 views

How many vertices of degree 1 in a tree?

How many vertices of degree 1 are there in a tree with no vertices of degree more than 4? The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
4
votes
1answer
229 views

How many vertices of degree 3 or more can have a tree have at most?

It is known that a tree $T=(V,E)$ has at least $\Delta$ leaves, where $\Delta$ is the maximum degree of $T$. But how many vertices of specific degree at least $k$ can a tree have at most? I'm ...
1
vote
1answer
241 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...
2
votes
1answer
50 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
0
votes
1answer
205 views

Relationship between ordered and binary trees

I am looking for a formula for the number of ordered trees with $n$ vertices and $l$ leaves as well as for a formula for the number of binary trees with $l$ left and $r$ right children. Finally, I ...
3
votes
2answers
232 views

Bijection between binary trees and plane trees?

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node ...
3
votes
2answers
186 views

Why for number of leaves in a tree (all types of trees) is it true

I have to prove the following claim, given the tree $T=(V,E)$, $|V|\geq3$: $$|V_1| \leq \frac { |V| \times (\Delta (V) - 2) + 2 }{ \Delta (V) - 1 } $$ where $|V_1| - $ number of leaves in a tree, and ...
2
votes
1answer
148 views

Probability of passing through 3 specific nodes along a binomial tree

Consider a re-combining binomial tree with probability of up = $p$ and probability of down = $(1-p)$. Let $n$ be the number of time steps in the binomial tree (the $x$-axis is time, and each column of ...
2
votes
1answer
88 views

About finiteness of trees

I am reading a book of Michael Sipser "Introduction to the theory of computation", and there is a theorem, which he gives without a proof: "If every node of a tree has only finitely many children and ...
0
votes
1answer
77 views

Number of leaves in a tree that represents a kind of permutations

Consider the following rooted tree, each of whose vertices (except for the root) is labeled with an integer $\in\{1,\dots,n\}$: let $s(v)$ be the sequence consists of the labels on the path from the ...
9
votes
2answers
599 views

“Ballot numbers” sum up to Catalan numbers

Summing certain numbers and comparing the results with OEIS, I found that $ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n}, $ where $C_n$ denotes the $n^{\textrm{th}}$ Catalan ...
4
votes
3answers
305 views

Counting $k$-ary labelled trees

The (full) binary counting tree problems gives the number of binary trees can be formed using $N$ nodes $T(n)= C_n$, where $C_i$ are the Catalan numbers. The recursion form is $T_n = ...
2
votes
5answers
8k views

The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

I am confused with this statement The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$. How come this is true. Lets say I have the following tree ...
0
votes
2answers
1k views

About balanced and complete binary tree

I found this and I just couldn't verify it. How come it is true? The maximum number of nodes that a balanced binary tree with depth $d$ is a complete binary tree with $2^d-1$ nodes. Let say I have ...
2
votes
1answer
310 views

Evaluating 'combinatorial' sum

Help me please to calculate the following sum. I have seen such kind of formulas in the papers related to combinatorics, specifically 'trees'. I am curious how to calculate or approximate this sum: ...
2
votes
3answers
380 views

Applications of the number of spanning trees in graphs

Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$. There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to ...
1
vote
0answers
52 views

Keeping consistency in subjective ranking

I'm doing some work on a computer program that aids in ranking items which don't have a way to objectively compare to each other. As it is now, it takes each item and pairs it up with each other ...
1
vote
0answers
209 views

Finding the number of spanning trees of a given height

I hope I can avoid being confusing, but here goes. I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. ...
1
vote
1answer
377 views

Number of possible Prüfer codes

I am trying to solve the following problem in my book: (Code stands for Prüfer code) Consider labelled trivalent rooted trees $T$ with $2n$ vertices, counting the root labeled $2n$. The labels are ...
3
votes
0answers
139 views

Number of spanning arborescences

I am trying to prove the following result from my book: Let $G$ be a directed graph with vertices $x_1,x_2,\cdots x_n$ for which a directed Eulerian circuit exists. A spanning arborescence with root ...
4
votes
2answers
207 views

On the number of caterpillars

A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ ...
2
votes
1answer
376 views

Recursive Generating function for enumerating leaf labeled binary trees

Let be B(z) the exponential generating function for the number $b_n$ of different rooted unordered binary trees with exactly n leaves labeled only at their leaves (so the internal nodes are ...
4
votes
3answers
618 views

Spanning trees in a ladder graph

Let $L_n$ be the ladder graph formed from two $n$-vertex paths by joining corresponding vertices. For example $L_4$ is the following I have to find a recurrence $<t>$ where $t_n$ is the ...
0
votes
1answer
316 views

Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?
1
vote
2answers
106 views

A bijection between ordered trees and ballot lists

Could you help me to prove that there is a bijection between ordered trees with $n+1$ leaves and ballot lists with $n$ A's and $n$ B's? A ballot list is a sequence of A's and B's such that all ...
5
votes
2answers
142 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} \ ...