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

[maksimla]

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

[volvo]

Ну, так и пиши, по заданию:

function count(const n: integer; s: string): integer;
begin
  if length(s) = n then begin { условие выхода: число этажей достигнуто }
	writeln(s); count := 1;
  end
  else begin
	if (s = '') or (s[length(s)] = 'f') then
	  { или первый этаж, или над девочками - могут быть кто угодно }
	  count := count(n, s + 'm') + count(n, s + 'f')
	else 
	  { над мальчиками - только девочки }
	  count := count(n, s + 'f'); 
  end;
end;

Как вызвать - разберешься?

Это работает. Для 5 этажей выдает 13 комбинаций, для 12-ти этажей - 377, ... Разберись, как оно работает, и допиши программу...

Добавлено через 1 мин.
P.S. В принципе, можно, подобрать формулу, вычисляющую ответ без перебора (в общем-то оно и без подбора ясно: это все числа Фибоначчи), но у тебя в задании именно рекурсия, придется вычислять.