# Questions tagged [binary-tree]

The binary-tree tag has no usage guidance.

17
questions

1
vote

1
answer

137
views

### Binary combinatorics rank with condition

Lets take an example of the range of N = 8 bits
2^8 = 256
00000000
00000001
00000010
00000011
...
11111100
11111101
11111110
11111111
Now lets consider a subset ...

2
votes

1
answer

70
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
votes

0
answers

91
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 ...

6
votes

1
answer

249
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 ...

0
votes

1
answer

40
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:=\...

4
votes

1
answer

103
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$ ...

6
votes

1
answer

312
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 ...

17
votes

0
answers

378
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 ...

2
votes

1
answer

245
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 ...

6
votes

0
answers

78
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 ...

7
votes

1
answer

347
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$ ...

5
votes

1
answer

327
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 ...

1
vote

1
answer

483
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 ...

9
votes

0
answers

287
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....

2
votes

2
answers

209
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 ...

10
votes

3
answers

814
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 ...

14
votes

0
answers

392
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 ...