рекурсивнвный подсчет как распределить мальчиков и девочек, у меня даже идеи нету как ее делать Опции

[maksimla]

В поездке ученики прибыли в n (0 < n ≤ 15) этажный дом. На одном этаже могут жить только одного пола дети.Учительница должда распределить их придерживаясь правилам с этажом нижей девочки могут жить над мальчиками и над девочками но мальчики могут жить только над девачками. На первом этаже могут жить и девачки и мальчики.
Напишите программу котоорая данным n написала сколько всго можит быть вариантов расселения учеников. Два разных варианта расселения считаются разными когда на одном сперва мальчики а потом девочки живут.
Первичные данные
3
результат
5
Обьяснение
когда n = 3 то тогда вариантов расселения есть 5 ддд,мдд,дмд,мдм,ддм.
Д это девачка М это мальчик.
Но ммд и дмм так неможит быть.
Я совсем нечего непридумал как надо сделать и как останавливать сам цикл может дадите идею как это так сделать

[maksimla]

1 b) по условию count(2,'f') сравниваем s[length(s)] = 'f' да и тогда будит результат равен count(2,'fm')+count(2,'ff')
2)
a) count(2,'fm')
s = 'fm', все, дошли до второго этажа, результат = 1, он передается НАЗАД, в предыдущую формулу, в пункте (1 b),
count(2,'fm')+count(2,'ff') 1+count(2,'ff')
2 b) s = 'fm', все, дошли до второго этажа, результат = 1, он передается НАЗАД, в предыдущую формулу, в пункте (1 b), count(2,'fm')+count(2,'ff') count:=1+1;
3) count:=1+1; передается в пункт 0 и получается count:=1+2; и тогда count:=3;