All possible Red Black Trees with this set {1,2,3,4,5}
Testing all 120 insertion orders is indeed much to much work in order to check out all trees. Moreover, there might be trees that are valid, but which are not found by inserting keys in some order.

A better appraoch would be to designing the trees by level. The number of black nodes on each path is equal, so a RB-tree with five keys can at most have two levels with black nodes: three levels would need seven keys. 

It is perhaps helpful to consider a black node together with its red children as one single node with 1,2 or 3 keys (and 2,3 or 4 children). (In that way we get 2-3-4-trees.) Now either (1) the root has 2 keys and three children with each a single child, or (2) the root has 1 key with 2 children with a total of 4 keys. Remember a node with two keys can be represented in two ways as a RB-tree (the red child can be left or right.)  

According to the OEIS there are eight such trees. Good luck.