All Questions
16
questions
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
2
votes
1
answer
502
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
1
vote
0
answers
259
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
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
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
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
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
0
votes
0
answers
87
views
Transforming generating functions into algorithms that generate combinatorial objects
I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities).
However, I'm not interested ...
- 295
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 ...
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
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
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
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
1
vote
1
answer
376
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