I have corrected the problem. There was a terrible typo.

I have invented a solution using recurrences. We will prove that $T_{n+1}=\sum_{k=0}^{n}C_n^kT_kT_{n-k}$, $T_0=1$, $T_1=1$, where $T_n$ is a required number of colorings. (1) Indeed, let $A$ be a set of numbers s.t. arrow $(1,a)$ is red for all $a\in A$ and $B$ is a set of numbers s.t. arrow $(1,b)$ is blue for all $b\in B$. Suppose $a\in A$ and $b\in B$ then it is necessary $(a,b)$ is blue if $a<b$ and $(b,a)$ is red if $b<a$ (2). Thus we defined colors of all arrows connecting sets $A$ and $B$. And the restriction of the coloring to the sets $A$ or $B$ are monochromatic colorings. And vice versa. If we define arbitrary proper colorings within $A$ and $B$ and extend them to the whole set using (2), then we will obtain a monochromatic coloring (check it! ). Let $|A|=k$. We have $C_n^k$ choices to select $A$. For each choice we have $T_kT_{n-k}$ monochromatic colorings. Those (1) is correct. It is easy to see that $T_n=n!$ satisfies (1). That's all. P.S. The official solution I have just read uses some lemmas on transitive graphs. Bleh...

Hi! Sorry Myth, but I don't have time to read your solution . My idea that leads to the same answer is as follows: Consider the red edges and invert them. Now we have an arbitrary acyclic oriented graph. The question is how many such graphs we have. The idea is that the structure degrees of the vertices is : $n,n-1,\ldots 1$, this follows by induction, so now we just have to pick the vertices in one of the $n!$ ways to generate a valid coloring. Hope it is clear enough. If necessary, I'll be back with details

I don't need details. I saw it in the official solution. And all necessary explanations took 2 pages long!