12 replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/
11 Moved out of sandbox.

## Unary-binary trees

A unary-binary tree is a tree with nodes of three types: terminal nodes, which have no children; unary nodes, which have one child each; and binary nodes, which have two children each. We can represent them with the following grammar, given in BNF:

<e> ::=
<terminal>
| <unary>
| <binary>

<terminal> ::=
"0"

<unary> ::=
"(1" <e> ")"

<binary> ::=
"(2" <e> " " <e> ")"


In this grammar the nodes are given in preorder and each node is represented by a digit which is the number of children it has.

## Motzkin numbers

Motzkin numbers (OEIS) (Wikipedia) have many interpretations, but one interpretation is that the nth Motzkin number is the number of distinct unary-binary trees with n nodes. A table of Motzkin numbers starts

N          Motzkin number M(N)
1          1
2          1
3          2
4          4
5          9
6         21
7         51
8        127
...


e.g. M(5) is 9, and the nine distinct unary-binary trees with 5 nodes are

1      (1 (1 (1 (1 0))))
2      (1 (1 (2 0 0)))
3      (1 (2 0 (1 0)))
4      (1 (2 (1 0) 0))
5      (2 0 (1 (1 0)))
6      (2 0 (2 0 0))
7      (2 (1 0) (1 0))
8      (2 (1 (1 0)) 0)
9      (2 (2 0 0) 0)


Take a single positive integer n as input and output all of the distinct unary-binary trees with n nodes.

Examples for n from 1 to 5 with parenthesis included for readability

0

(1 0)

(1 (1 0))
(2 0 0)

(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)

(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)


## Input

The input will be one positive integer.

## Output

The output should be an intelligible representation of the distinct unary-binary trees with that many nodes. It is not compulsory to use the exact string given by the BNF grammar above: it is sufficient that the syntax used give an unambiguous representation of the trees. E.g. you could use [] instead of (), an extra level of brackets [[]] instead of [], outer parenthesis are present or missing, extra commas or no commas, extra spaces, parenthesis or no parenthesis, etc.

All of these are equivalent:

(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11


Also a variation purposed by @xnor in a comment. Since there is a way to translate this to a format that can be understood it is acceptable.

[[[]][]]  is (2 (1 0) 0)


To make this easier to understand convert some of the [] to () like so

[([])()]


[]


then insert a binary which needs two expression you get

 [()()] which is 2


and then for the first () insert a unary which needs one expression you get

 [([])()] which is 21


but since [] or () with no inner bracketing can represent 0 which needs no more expressions you can interpret it as

 2100


Note that answers should work theoretically with infinite memory, but will obviously run out of memory for an implementation-dependent finite input.

## A possible place to check for duplicate trees

One place to check for a duplicate is with M(5).
This one tree was generated twice for M(5) from M(4) trees

(2 (1 0) (1 0))


the first by adding a unary branch to

(2 (1 0) 0)


and second by adding a unary branch toUnary-binary trees

(2 0 (1 0))


## Unary-binary trees

A unary-binary tree is a tree with nodes of three types: terminal nodes, which have no children; unary nodes, which have one child each; and binary nodes, which have two children each. We can represent them with the following grammar, given in BNF:

<e> ::=
<terminal>
| <unary>
| <binary>

<terminal> ::=
"0"

<unary> ::=
"(1" <e> ")"

<binary> ::=
"(2" <e> " " <e> ")"


In this grammar the nodes are given in preorder and each node is represented by a digit which is the number of children it has.

## Motzkin numbers

Motzkin numbers (OEIS) (Wikipedia) have many interpretations, but one interpretation is that the nth Motzkin number is the number of distinct unary-binary trees with n nodes. A table of Motzkin numbers starts

N          Motzkin number M(N)
1          1
2          1
3          2
4          4
5          9
6         21
7         51
8        127
...


e.g. M(5) is 9, and the nine distinct unary-binary trees with 5 nodes are

1      (1 (1 (1 (1 0))))
2      (1 (1 (2 0 0)))
3      (1 (2 0 (1 0)))
4      (1 (2 (1 0) 0))
5      (2 0 (1 (1 0)))
6      (2 0 (2 0 0))
7      (2 (1 0) (1 0))
8      (2 (1 (1 0)) 0)
9      (2 (2 0 0) 0)


Take a single positive integer n as input and output all of the distinct unary-binary trees with n nodes.

Examples for n from 1 to 5 with parenthesis included for readability

0

(1 0)

(1 (1 0))
(2 0 0)

(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)

(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)


## Input

The input will be one positive integer.

## Output

The output should be an intelligible representation of the distinct unary-binary trees with that many nodes. It is not compulsory to use the exact string given by the BNF grammar above: it is sufficient that the syntax used give an unambiguous representation of the trees. E.g. you could use [] instead of (), an extra level of brackets [[]] instead of [], outer parenthesis are present or missing, extra commas or no commas, extra spaces, parenthesis or no parenthesis, etc.

All of these are equivalent:

(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11


Also a variation purposed by @xnor in a comment. Since there is a way to translate this to a format that can be understood it is acceptable.

[[[]][]]  is (2 (1 0) 0)


To make this easier to understand convert some of the [] to () like so

[([])()]


[]


then insert a binary which needs two expression you get

 [()()] which is 2


and then for the first () insert a unary which needs one expression you get

 [([])()] which is 21


but since [] or () with no inner bracketing can represent 0 which needs no more expressions you can interpret it as

 2100


Note that answers should work theoretically with infinite memory, but will obviously run out of memory for an implementation-dependent finite input.

## A possible place to check for duplicate trees

One place to check for a duplicate is with M(5).
This one tree was generated twice for M(5) from M(4) trees

(2 (1 0) (1 0))


the first by adding a unary branch to

(2 (1 0) 0)


and second by adding a unary branch to

(2 0 (1 0))

10 Add another similar output example.
(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11

(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55

(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11

9 Explain varation purposed by xnor
8 format equivelent section.
7 Give examples of similiar output for a single case.
6 deleted 185 characters in body
5 added 6 characters in body
4 Add more detail. Explain if the answer should be a continuous sequence or sepearte sets.