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

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)  

Task

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

[([])()]

Now if you start with

[]

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)  

Task

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

[([])()]

Now if you start with

[]

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))

Unary-binary trees

10 Add another similar output example.
source | link
(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
source | link
8 format equivelent section.
source | link
7 Give examples of similiar output for a single case.
source | link
6 deleted 185 characters in body
source | link
5 added 6 characters in body
source | link
4 Add more detail. Explain if the answer should be a continuous sequence or sepearte sets.
source | link
3 Add more detail.
source | link
2 Add more details to explaination.
source | link
1
source | link