За­ме­тим, что за­да­ча была бы проще, если бы в корне де­ре­ва схо­ди­лись 2 ребра. Тогда де­ре­во будет би­нар­ным, то есть если его на­ри­со­вать по уров­ням  — от корня к ли­стьям, то из каж­до­го узла будут вы­хо­дить ровно две ветви. Ко­ли­че­ство би­нар­ных де­ре­вьев опи­сы­ва­ет­ся ин­те­рес­ной ком­би­на­тор­ной по­сле­до­ва­тель­но­стью  — чис­ла­ми Ка­та­ла­на.

Вот, на­при­мер, ри­су­нок со стра­нич­ки, где эти числа об­суж­да­ют­ся:

Если ли­стья про­ну­ме­ро­вать: L1, L2, ..., Ln, то опи­са­ние раз­лич­ных де­ре­вьев можно опи­сать с по­мо­щью ско­бок, опи­сы­ва­ю­щих, какие ли­стья и ветки со­еди­не­ны. На­при­мер, де­ре­вьям на кар­тин­ке со­от­вет­ству­ют такие ско­боч­ные фор­му­лы (для крат­ко­сти за­пи­си буква L опу­ще­на):

Эта идея поз­во­ля­ет на­пи­сать фор­му­лу для чисел Ка­та­ла­на:

где   — число би­нар­ных де­ре­вьев на вер­ши­нах. В преды­ду­щем при­ме­ре фор­му­ла вы­гля­дит так:

и может быть про­чи­та­но сле­ду­ю­щим об­ра­зом. От корня идут две ветви  — левая и пра­вая. Рас­пре­де­ле­ние ли­стьев между этими вет­вя­ми может быть таким: 1 + 3, 2 + 2, 3 + 1. По­сколь­ку ком­би­на­ции на каж­дой ветви не за­ви­сят от ком­би­на­ций на дру­гой, при­ме­ня­ем прин­цип умно­же­ния. По­сле­до­ва­тель­но по по­лу­чен­ной ре­кур­рент­ной фор­му­ле можно вы­чис­лить: В нашей за­да­че из корня вы­хо­дит три ветви, каж­дая из ко­то­рых уже яв­ля­ет­ся би­нар­ным де­ре­вом, по­это­му нужно рас­смот­реть рас­пре­де­ле­ние ли­стьев между тремя вет­ка­ми и далее уже при­ме­нить фор­му­лу для чисел Ка­та­ла­на:

Таких ва­ри­ан­тов 10 и их тоже можно раз­де­лить на три груп­пы:

а)  три ва­ри­ан­та со сла­га­е­мы­ми

б)  шесть ва­ри­ан­тов со сла­га­е­мы­ми

в)  один ва­ри­ант со сла­га­е­мы­ми

Таким об­ра­зом, ре­зуль­тат вы­чис­ля­ет­ся по фор­му­ле:

Ответ: 28.