cp's OEIS Frontend

By 'binary tree' we mean a rooted, ordered tree which is either empty, denoted by 0, or it has both a left subtree L and a right subtree R (which can be empty), and then it is denoted by (LR) if it is attached by a contiguous edge to its parent, [LR] if attached by a non-contiguous edge, or LR if it is does not have a parent, i.e., if is the root. A contiguous edge in the pattern tree corresponds to a parent-child relation in the host tree (as in Rowland's paper), whereas a non-contiguous edge in the pattern tree corresponds to an ancestor-descendant relation in the host tree (as in the paper by Dairyko, Pudwell, Tyner, and Wynn).

Number of n-vertex binary trees that do not contain P as a subtree, where P is one of 0((00)[(00)0]), 0((0[0(00)])0), 0((0[(00)0])0), (00)(0[0(00)]), (00)(0[(00)0]).

By 'binary tree' we mean a rooted, ordered tree which is either empty, denoted by 0, or it has both a left subtree L and a right subtree R (which can be empty), and then it is denoted by (LR) if it is attached by a contiguous edge to its parent, [LR] if attached by a non-contiguous edge, or LR if it is does not have a parent, i.e., if is the root. A contiguous edge in the pattern tree corresponds to a parent-child relation in the host tree (as in Rowland's paper), whereas a non-contiguous edge in the pattern tree corresponds to an ancestor-descendant relation in the host tree (as in the paper by Dairyko, Pudwell, Tyner, and Wynn).

Number of n-vertex binary trees that do not contain P as a subtree, where P is one of 0[0(0((00)0))], 0[0((00)(00))], 0[0((0(00))0)], 0[(00)(0(00))], 0[(00)((00)0)], 0[(0(00))(00)], 0[((00)0)(00)], 0[(0((00)0))0], 0[((00)(00))0], 0[((0(00))0)0], 0(([0(00)]0)0), 0(([(00)0]0)0).

Number of restricted growth strings of set partitions of {1,...,n} that avoid the two patterns 1212 and p, where p is one of 12232, 12113, 12322, 11213.

By 'binary tree' we mean a rooted, ordered tree which is either empty, denoted by 0, or it has both a left subtree L and a right subtree R (which can be empty), and then it is denoted by (LR) if it is attached by a contiguous edge to its parent, [LR] if attached by a non-contiguous edge, or LR if it is does not have a parent, i.e., if is the root. A contiguous edge in the pattern tree corresponds to a parent-child relation in the host tree (as in Rowland's paper), whereas a non-contiguous edge in the pattern tree corresponds to an ancestor-descendant relation in the host tree (as in the paper by Dairyko, Pudwell, Tyner, and Wynn).

Number of n-vertex binary trees that do not contain 0(0[((00)0)0]) as a subtree.

The largest LCM is attained for a partition of n into powers of distinct odd primes and 1's.

The largest LCM is attained for a partition of n into powers of distinct odd primes, 2^k for some k>0, 2, and 1's.

An order-preserving Hamiltonian path in the n-cube is a listing S_1,...,S_N of all N:=2^n many subsets of [n]:={1,2,...,n}, such that if S_j is a subset of S_i then j <= i+1. For the counting we ignore paths that differ only by renaming elements of the ground set (=automorphisms of the n-cube), i.e., without loss of generality every such path starts as follows: S_1={}, S_2={1}, S_3={1,2}, S_4={2}, S_5={2,3}, S_6={3}, S_7={3,4}, S_8={4},..., S_{2n-2}={n-1}, S_{2n-1}={n-1,n}, S_{2n}={n} (after visiting the set {n}, there are multiple ways to proceed).

It is shown in [Felsner, Trotter 95] that an order-preserving Hamiltonian path is level-accurate in the following sense: After visiting a set of size k, the path will never visit a set of size (k-2) (*).

For odd n we will have S_N={1,2,...,n} (i.e., |S_N|=n) and for even n we will have |S_N|=n-1.

Hamiltonian paths that have property (*) have been constructed in [Savage, Winkler 95] for all n (but these paths are not order-preserving).

For n=8,9,10 we know that a(n)>=1. It is unknown whether a(n)>=1 for n>=11 (i.e., it is not known whether such order-preserving paths exist). Some partial results have been obtained in [Biro, Howard 09].

The game is played on an edge-colored graph by two players called Builder and Painter. The game starts with a graph on infinitely many vertices with no edges. In each step, Builder adds one new edge to the graph, but he must not create any cycles, and all components (=trees) may have at most k edges (k is fixed throughout the game). Painter immediately and irrevocably colors each new edge red or blue. Painter's goal is to avoid creating a monochromatic (i.e., completely red or completely blue) path P(n) on n edges (n is also fixed throughout the game). Builder's goal is to force Painter to create such a monochromatic P(n). a(n) is defined as the minimal k for which Builder wins this P(n)-avoidance game with two colors and tree size restriction k.