Простая комбинаторика. Построение в 2 шеренги.

[Day]

Вот такая простая комбинаторика, и никак не пойму с какого бока ее укусить.
2n солдат надо построить в 2 шеренги по росту. Причем i-тый солдат 1-й шеренги
должен быть выше i-того во 2-й шеренге. Сколькими способоми можно произвести
такое построение.
Роста у всех разные.

Даже программку написал.

#include <stdio.h>
#define NN 16
long F(int a, int b)  // Кол-во способов, которыми можно заполнить первый ряд
    // a солдатами, 2-ряд - b солдатами с соблюдением условий роста
{
  if (a<=1 && b<=1) return 1;
  if (b==0) return 1;
  if (a==b) return F(a, b-1);
  else return F(a-1, b) + F(a, b-1);
}
main()
{ int i;
  for(i=2; i<NN; i++) {
     printf("N=%2d Sp=%9ld\n", i, F(i, i));
  }
}

А вот результат

N= 2 Sp=       2
N= 3 Sp=       5
N= 4 Sp=      14
N= 5 Sp=      42
N= 6 Sp=     132
N= 7 Sp=     429
N= 8 Sp=    1430
N= 9 Sp=    4862
N=10 Sp=   16796
N=11 Sp=   58786
N=12 Sp=  208012
N=13 Sp=  742900
N=14 Sp= 2674440
N=15 Sp= 9694845

Закономерности не видно...

[Tlalok]

А в одной шеренге они тоже должны быть по росту построены или это не обязательно?

[Sonic86]

Числа Каталана

[VAL]

Day в сообщении #428856 писал(а):

А вот результат

N= 2 Sp=       2
N= 3 Sp=       5
N= 4 Sp=      14
N= 5 Sp=      42
N= 6 Sp=     132
N= 7 Sp=     429
N= 8 Sp=    1430
N= 9 Sp=    4862
N=10 Sp=   16796
N=11 Sp=   58786
N=12 Sp=  208012
N=13 Sp=  742900
N=14 Sp= 2674440
N=15 Sp= 9694845

Закономерности не видно...

Про числа Каталана уже Sonic написал.
А закономерностей для них - море!
Простейшая - $C_n=\frac1{n+1}{2n\choose n}$

Еще несколько можно найти здесь

[Day]

Tlalok в сообщении #428862 писал(а):

А в одной шеренге они тоже должны быть по росту построены или это не обязательно?

Конечно! И обязательно!

Цитата:

Про числа Каталана уже Sonic написал.
А закономерностей для них - море!
Простейшая -
Еще несколько можно найти здесь

Спасибо. Попробую осмыслить.
О Каталане где-то что-то слышал. Даже задачки решал.
То есть это - не теорема Ферма. Уже хорошо.