All Questions
16
questions
7
votes
4
answers
4k
views
What is the number of full binary trees of height less than $h$
Given a integer $h$
What is $N(h)$ the number of full binary trees of height less than $h$?
For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't find ...
- 13.8k
3
votes
1
answer
2k
views
what' is the number of full subtrees of a full binary tree?
I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are:
Now my question is:
What is $N(h)$ the maximum number of full sub-trees of a full ...
- 13.8k
2
votes
2
answers
2k
views
For each edge in a tree, counting paths passing through this edge
I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (...
- 195
2
votes
1
answer
3k
views
How to prove that number of unlabelled binary trees $n$ nodes is given by Catalan number
Suppose i have 1 nodes hence total number of binary trees is 1.Suppose i have 2 nodes then total number of binary trees is 2.Then suppose i have 3 nodes then total number of binary trees is 5.
How to ...
user694626
2
votes
1
answer
510
views
(Upper bound on) Tree width of an $n \times n$ grid graph
Given any $n \geq 1$ consider the $n \times n$ grid graph.
For example, for $n = 3$, this looks like:
$$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&...
- 21
2
votes
1
answer
77
views
Minimum Steiner Arborescenes approximation: intuitions?
Given a (positively) weighted directed graph G, a set of query nodes T and a root r, finding the minimum steiner arborescence containing the query nodes and rooted at r is an NP-hard problem
However, ...
- 383
2
votes
1
answer
50
views
Need combinatorial formula
Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$
Let $...
- 8,204
1
vote
1
answer
377
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 ...
- 21
1
vote
0
answers
260
views
Find a maximum vertex-disjoint path cover in a tree.
Let $T = (V, E)$ be a undirected tree on $n$ vertices with an arbitrary root. Let the nodes be given weights, by some pre-determined function $W : V(T) \rightarrow \{1, \dots, 10^9\}$. Furthermore, ...
- 21
1
vote
0
answers
185
views
Determine Huffman Tree Depth Using any combinactory ways?
I see this link for determining depth (height) of Huffman tree, but not useful for me.
My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
1
vote
0
answers
33
views
Yet another curious convolution
Some time ago, I found the following algorithmic problema:
Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors.
Given that the ...
- 5,653
0
votes
1
answer
279
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 ...
- 7,290
0
votes
1
answer
63
views
Determining all possible values of $n$ in terms of $x$ of the following tree.
Let $T$ be a maximal heap tree. Let $T$ hold the integers $1$ to $n$ as its nodes without duplicates. Let $x$ be a child of the root. What are the possible values that $n$ could take, in terms of $x$?
...
- 1
0
votes
2
answers
313
views
Sum of roots of binary search trees of height $\le H$ with $N$ nodes
Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees.
For example, for $N$ = 3, $H$ = 3: ...
- 412
0
votes
0
answers
185
views
Greedy Algorithm on Knockout Tournaments: Proof of Correctness
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
- 11