По­счи­та­ем ко­ли­че­ство всех по­ез­дов, ко­то­рые можно со­брать в дан­ном на­бо­ре. За­фик­си­ру­ем число k и по­счи­та­ем, сколь­ко всего по­ез­дов с ровно k крас­ны­ми ва­го­на­ми. Жел­тых ва­го­нов может быть от 0 до 3n, и для каж­до­го числа l жел­тых ва­го­нов от 0 до 3n мы вы­би­ра­ем k мест в стро­ке длины k + l. Таким об­ра­зом, ис­ко­мое ко­ли­че­ство по­ез­дов с k крас­ны­ми ва­го­на­ми равно сумме

До­ка­жем, что эта сумма равна Рас­пи­шем каж­дое сла­га­е­мое, поль­зу­ясь сле­ду­ю­щим тож­де­ством Пас­ка­ля:

Мы по­лу­чим:

Здесь раз­ло­же­ны и вы­пи­са­ны явно пер­вые три и по­след­ние два члена вы­чис­ля­е­мой суммы. В каж­дой скоб­ке вы­чи­та­е­мое равно умень­ша­е­мо­му из преды­ду­щей скоб­ки. Не­тро­ну­тым оста­нет­ся лишь умень­ша­е­мое в по­след­ней скоб­ке, рав­ное   — это и есть ис­ко­мый ре­зуль­тат сло­же­ния. За­ме­тим, что этот ре­зуль­тат равен в силу сим­мет­рии би­но­ми­аль­ных ко­эф­фи­ци­ен­тов. Те­перь нужно сло­жить эти числа по всем k от 0 до 2n. По­лу­чим сумму

ко­то­рая сум­ми­ру­ет­ся ана­ло­гич­ным об­ра­зом, и ре­зуль­тат этого сум­ми­ро­ва­ния равен

Мы по­счи­та­ли ко­ли­че­ство всех по­ез­дов. Оста­лось лишь вы­честь ко­ли­че­ство по­ез­дов, в ко­то­рых не более ва­го­нов, но для каж­до­го ко­ли­че­ство по­ез­дов длины l оче­вид­но равно  а всего в сумме таких по­ез­дов  Таким об­ра­зом, длин­ных по­ез­дов

Ответ: