30人31脚に挑戦！

awk

awkネタ

「30人31脚」を有利に戦うための並べ方を考えます。
女の子が続いて並ぶと体力的に不利なので、女の子は隣り合わないようにします。
(男の子は何人並んでもよいものとします)
30人を1列に並べる時、その並べ方が何通りあるかを求めてください。
男女の並び方だけを考えるものとし、誰がどの位置かは考えないものとします。
例えば、4人(4人5脚)の場合は次の8通りがあります
  • 男男男男
  • 男男男女
  • 男男女男
  • 男女男男
  • 女男男男
  • 男女男女
  • 女男男女
  • 女男女男

考え方としては、必ず男子を追加出来るので、右端が男子の場合のみ女子を追加するという考えです。

#!/usr/bin/awk -f

BEGIN{
    # 男子と女子を文字で設定
    boy = "B";girl = "G";
    N = 30;

    print add(boy) + add(girl);
}

function add(seq,   cnt){
    # 並べる人数に達したら終了
    if(length(seq) == N){
        return 1;
    }
    # 30人未満の場合、男子を追加するか、右端が男子の場合女子を追加
    cnt = add(seq  boy);
    if(substr(seq,length(seq)) == boy){
        cnt += add(seq girl);
    }
    return cnt;
}

実行してみます

awk -f q17.awk 
2178309

膨大な数ですね。