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

[maksimla]

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

[maksimla]

Вот кажется разобрался как вызвать

program varenti_raspredilenija;

  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)] = 'Д') then  
	  count := count(n, s + 'М') + count(n, s + 'Д')
	else
	  count := count(n, s + 'Д');
  end;
end;
var x:integer;
begin
  WriteLn('Vvedi cislo ot 0 do 15');
  Readln(x);
  writeln(count(x,''));
  readln;
end.

кажется все правильно и вызывает и результат выводит
и разобрался вот с этим s[length(s)] = 'Д'

program Bevarde2;
var s:string;
begin
   s:='МД';
  WriteLn(s[length(s)] = 'Д');
  Readln;
end.

но запутался в рекурсии как она так считает нечего непонял хоть выполнял с n=2 и пошагово
count := count(n, s + 'М') + count(n, s + 'Д') и тут ведь наверное ошибка должна быть это мне просто так кажется вот и незнаю как тут складывается и как выполняется все остальное

Добавлено через 6 мин.
И тут если взять что я вижу то только n=2 то тогда результат МД все
s + 'М' это так понимаю

Добавлено через 2 мин.
а я даже и неподумал что это числа Фибоначчи