Questions tagged [binary-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

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

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

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

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

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
4 votes
1 answer

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,327
6 votes
1 answer

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 ...
  • 12.7k
17 votes
0 answers

Is the Frog game solvable in the root of a full binary tree?

This is a cross-post from$^{[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 ...
  • 591
2 votes
1 answer

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

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 ...
  • 3,858
7 votes
1 answer

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,471
5 votes
1 answer

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
1 vote
1 answer

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

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....
user avatar
2 votes
2 answers

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.1k
10 votes
3 answers

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,126
14 votes
0 answers

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 ...
  • 17.9k