# Questions tagged [binary-tree]

The binary-tree tag has no usage guidance.

**6**

votes

**0**answers

64 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

248 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

**0**answers

130 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

266 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

278 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

204 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

749 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

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