Questions tagged [binary-tree]
The binary-tree tag has no usage guidance.
17 questions
1
vote
0
answers
112
views
Fractal dimension of a self-similar tree
Consider a binary tree constructed as the following. Given a node with a some value $x$, I construct two children nodes each having value $l(x)$ and $r(x)$ respectively. I repeat the same on the ...
- 433
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
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
331
views
What are these recursively defined sequences called?
Let $F(x,y)$ be a function of two variables, defined for all positive integers $x$ and $y$. Define a sequence $a_n$ recursively by setting $a_1 = 1$ and
$$a_n = \sum_{k=1}^{n-1} F(k, n-k) \cdot a_k ...
- 13.3k
18
votes
0
answers
429
views
Is the Frog game solvable in the root of a full binary tree?
This is a cross-post from math.stackexchange.com$^{[1]}$, since the bounty there didn't lead to any new insights.
For reference,
The Frog game is the generalization of the Frog Jumping (see it on ...
- 611
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 ...
4
votes
1
answer
122
views
Monadic second order theory of "backwards tree" -- is it decidable?
A famous result by Rabin states that the monadic second order theory of the binary tree is decidable. By the binary tree, understand the free monoid $\{0,1\}^*$ of words, with operations $S_0(w)=w0$ ...
- 2,519
0
votes
1
answer
45
views
Maximize this score function on a directed tree
Let $\mathbb N_0^\ast$ be the set of all finite words/sequences over $\mathbb N_0$ and $\varepsilon$ the empty word. For a word $a=(a_1,\ldots,a_n)$ we define $\operatorname{len}a:=n$, $\Sigma a:=\...
- 237
5
votes
1
answer
442
views
Rabin's proofs of emptiness and complementation problems for automata on infinite trees
I have originally asked this question on Math.SE, but I think it is more suitable here.
I have been reading M. Rabin's 1969 article Decidability of Second-Order Theories and Automata on Infinite ...
- 171
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
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
6
votes
0
answers
93
views
Distributions of "sequential" binomials
I have come across the following stochastic process which seems very elementary, although I do not know any appropriate terminology for it; I greatly appreciate any suggestions!
Suppose I am given ...
- 4,049
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
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