Сразу же заметим, что раскраска всех вершин в один цвет хорошей не является; такие раскраски в дальнейшем решении не рассматриваются.
Назовём сторону многоугольника разноцветной, если её концы окрашены в разные цвета (то есть расширим определение разноцветности на стороны). Назовём раскраску вершин упорядоченной, если все чёрные вершины на границе многоугольника идут подряд (иначе говоря, у многоугольника есть ровно две разноцветных стороны).
Лемма. Раскраска вершин $n$-угольника (при $n \ge 3$) является хорошей тогда и только тогда, когда она упорядочена.
Доказательство. Индукция по $n$. При $n = 3$ доказывать нечего (напомним, что мы не рассматриваем одноцветные раскраски). Докажем теперь переход индукции. Пусть утверждение доказано для всех $m$ таких, что $3 \le m < n$, где $n \ge 4$.

Предположим, что раскраска является хорошей. Разобьём многоугольник на треугольники непересекающимися разноцветными диагоналями; рассмотрим одну из этих диагоналей $AB$. Она делит $n$-угольник на два многоугольника $P_1$ и $P_2$ с меньшим количеством сторон, причём каждый из них раскрашен хорошо — а значит, по предположению индукции, и упорядоченно. Пусть $A$ — чёрный конец диагонали, а $B$ — белый. Все чёрные вершины в $P_1$ — это несколько последовательных вершин, начиная с $A$ (но не включая $B$). Аналогично с чёрными вершинами в $P_2$. Но тогда эти два блока чёрных вершин в объединении дают один связный блок в исходном многоугольнике, то есть раскраска вершин $n$-угольника также является упорядоченной.

Пусть теперь раскраска является упорядоченной. Нетрудно видеть, что тогда в многоугольнике есть разноцветная диагональ. Она делит многоугольник на два меньших, при этом, очевидно, каждый из них также раскрашен упорядоченно. По предположению индукции, каждый из них раскрашен хорошо, а значит, и исходный $n$-угольник — тоже. $\square$

Ввиду леммы, осталось лишь посчитать число упорядоченных раскрасок $n$-угольника. Для каждого возможного количества чёрных вершин (от $1$ до $n-1$) можно $n$ способами выбрать расположение их блока среди всех $n$ вершин, то есть число способов равно $n(n-1)$.