Hi Eric,

Interesting topic, but I have to contradict your definition:

Combinators are a kind of function which are interesting to me because there are just two combinator functions, called the "S" and "K" combinators, with which one can in principle write any program (they are together "Turing complete.")

According to my dictionary ( not the standard ): A combinator is any function-valued function where each argument is itself a function. This definition is sufficient to ensure that: any evaluation of a combinator is again a combinator. Then, combinatory logic is a system for ennumerating combinators given a set of function definitions and an axiom. The {S,K} system is a special combinatory logic with two combinators, each having one definition. As noted in NKS it's possible to emulate the same system using one combinator with two definitions, for example:

AXIOM = F[F][F[F]][F[F]][F[F][F[F][F]]][F[F][F]];
RULE = {F[F][x_][y_][z_] :> x[z][y[z]], F[F[F]][x_][y_] :> x};

CountF[Comp_] := Length@DeleteCases[Characters[ToString[Comp]], "]" | "["]
CountF /@ NestList[# /. RULE &, AXIOM, 24]
Out[] = {14, 17, 18, 26, 37, 48, 62, 89, 130, 185, 257, 351, 510, 747, 1046, 
1405, 1873, 2577, 3598, 5004, 6804, 9016, 11820, 15729, 21134}

Lately I've been thinking that it's advantageous to just use one combinator. With only one function head, the range of valid combinators is in a one-to-one map with rooted ordered trees, which can be constructed in subsets according to number of nodes:

RootedTrees[0] = {F[]}
RootedTrees[N_] := Union@Flatten[ Flatten[
Outer[F, Sequence @@ (# /. n_Integer :> RootedTrees[n - 1]), 
1]] & /@ Flatten[Permutations /@ IntegerPartitions[N], 1], 1]
(*Catalan Numbers*)Length@RootedTrees[#] & /@ Range[10]

Some people may prefer to write function composition as:

AlternateForm[Combination_] := Combination //. { F[x__] :> Fold[#1@#2 &, F, {x}]} //. {F[] -> F}
AlternateForm[RootedTrees[3]] 
Out[]={F[F[F[F]]], F[F[F, F]], F[F][F[F]], F[F[F]][F], F[F][F][F]}

Defining an ordering for rooted trees puts each combinator into one-to-one mapping with the integers, for example

MapThread[Rule, {Range[0, 22], Prepend[Flatten[RootedTrees[#] & /@ Range[4]], F[]]}]
Out[] ={
0 -> F[], 
1 -> F[F[]], 
2 -> F[F[F[]]], 
3 -> F[F[], F[]], 
4 -> F[F[F[F[]]]], 
5 -> F[F[F[], F[]]], 
6 -> F[F[], F[F[]]], 
7 -> F[F[F[]], F[]], 
8 -> F[F[], F[], F[]], 
9 -> F[F[F[F[F[]]]]], 
10 -> F[F[F[F[], F[]]]], 
11 -> F[F[F[], F[F[]]]], 
12 -> F[F[F[F[]], F[]]], 
13 -> F[F[F[], F[], F[]]], 
14 -> F[F[], F[F[F[]]]], 
15 -> F[F[], F[F[], F[]]], 
16 -> F[F[F[]], F[F[]]], 
17 -> F[F[F[F[]]], F[]], 
18 -> F[F[F[], F[]], F[]], 
19 -> F[F[], F[], F[F[]]], 
20 -> F[F[], F[F[]], F[]], 
21 -> F[F[F[]], F[], F[]], 
22 -> F[F[], F[], F[], F[]]}

Ideally, the ordering would make it easy to take a combinator and return an integer. I haven't quite figured that out yet, but considering the prevalence of Catalan Numbers, I'm sure the answer is out there.

As for Combinator projects, I think there are many interesting possibilities. Highest on the list for me is a computable document solution manual for Smullyan's "To Mock a Mockingbird". I've written algorithms to solve a few of the problems, but haven't had time to get completely through the book. Another possibility along the lines of "integer base" is to identify F ( or other combinators ) with arithmetical functions, and try to compute integers. For example, here are three ways to compute integer 11:

(* 11 =  3*3 + 1 + 1*)
F[F[F[F[F]], F[F[F]]], F, F] //.  F[x_] :> x + 1 //. {F[x_, y_] :> Times[x, y], 
F[x_, y_, z_] :> Plus[x, y, z]} /. F -> 1
(* 11 = 1 + 1 + 1 + 1 +1 + 1 +1 + 1 + 1 + 1 +1 *)
F[F, F, F, F, F, F, F, F, F, F, F] /. {F[x__] :> Plus[x]} /. F -> 1
(* 11 = 1 + (1 + 1) + (1 + 1) + (1 + (1 + (1 + 1))) + (1 + 1)  *)
CommaForm[Comp_] := Comp //. F[x___][y___] :> F[x, y]
CommaForm[Nest[# /. RULE &, AXIOM, 2]]
% //. F[x__] :> Plus[x] /. F -> 1

It would also be awesome to see combinator systems somehow tied in with substitution tilings. What a dream that would be.