Questions tagged [binary-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
33 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
1answer
87 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
1answer
298 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 ...
12
votes
0answers
243 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
1answer
213 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
0answers
77 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
1answer
307 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
0answers
190 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
1answer
389 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
0answers
285 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
2answers
208 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
3answers
786 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
0answers
388 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 ...