All Questions
Tagged with binary-tree co.combinatorics
10 questions
2
votes
1
answer
76
views
Finding the best binary tree with a general property
Let $N=\{1,\dots,n\}$. Let $M$ be the set of all binary trees $B$ formed from all elements of $N$ (i.e of size $n$). Let $P$ be a numeric property defined for all $B\in M$. Let $O\in M$ be the optimal ...
- 4,829
4
votes
0
answers
100
views
Approximating the "magic" tree rotation: P or NP?
Background. (tl;dr, skippable)
"Dynamic" binary search trees are well researched.
The "magic" rotation algorithm (="offline") knows the query sequence beforehand and ...
- 4,829
6
votes
1
answer
260
views
Tanglegrams and functional equations of M. Somos
Recent references on the matter at hand include, a lecture slide The Konvalinka-Amdeberhan conjecture
and plethystic inverses and a preprint on Counting tanglegrams with species by I. Gessel; the ...
- 43.2k
2
votes
1
answer
315
views
Is this model of converting integers to Gray code correct?
The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim.
Here is some ...
7
votes
1
answer
394
views
Counting some binary trees with lots of extra stucture
While working on some computations on Hilbert schemes, I came across the following combinatorial problem.
Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...
- 1,509
1
vote
1
answer
537
views
Ratio between number of nodes and leaves in a rooted binary tree
I want to know if there exists a positive constant $c$ such that:
Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:
$$\frac{[\sum_{v \in ...
- 11
9
votes
0
answers
292
views
Weighted sum of the Simsun (Andre) permutations
Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$
$$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, \hspace{0....
user83150
2
votes
2
answers
220
views
Removing subtrees
Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:
$G$ has no complete subtrees (the graph below any ...
- 11.3k
10
votes
3
answers
872
views
Combinatorial interpretation of composition of power series?
This is a minor curiosity that came up in a joint project recently.
Consider the sequence $a_n=3\frac {(2n)!}{(n+2)!(n-1)!}$ (A000245 in OEIS).
It has multiple combinatorial descriptions.
One can ...
- 5,186
14
votes
0
answers
417
views
Monotone embedding of complete binary tree in hypercube
Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...
- 19k