Q47 圧縮できるパターンは何通り？

JavaScriptのソース

Solve(2,5);
Solve(6,6);

//種類と文字数を引数として解を求める
function Solve(pN,pM)
{
    var StrArr = DeriveStrArr(pN,pM);
    var Answer = 0;
    for(var EachInd in StrArr){
        var wkStr = StrArr[EachInd];
        var RunLengthStr = DeriveRunLengthStr(wkStr);
        //document.write(wkStr , 'をランレングス圧縮すると、' , RunLengthStr , '<br>');
        if (wkStr.length > RunLengthStr.length) Answer++;
    }
    document.write(pN , '種類で' , pM , '文字だと、短くなるのは' , Answer , '通り<br>');
}

//コンストラクタ
function JyoutaiDef()
{
    this.CurrStr = '';
}

//種類と文字数を引数として、文字列の配列を返す
function DeriveStrArr(pN,pM)
{
    var StrArr = new Array();

    var Stk = new Array();
    var WillPush = new JyoutaiDef();
    Stk.push(WillPush);
    while(Stk.length > 0){
        var Poped = Stk.pop();

        //クリア判定
        if(Poped.CurrStr.length == pM){
            StrArr.push(Poped.CurrStr);
            continue;
        }

        var wkStr = 'ABCDEF';
        for(var I = 0 ; I <= pN - 1 ; I++){
            WillPush = new JyoutaiDef();
            WillPush.CurrStr = Poped.CurrStr + wkStr[I];
            Stk.push(WillPush);
        }
    }
    //document.write(JSON.stringify(StrArr));
    return StrArr;
}

//ランレングス圧縮で変換した文字列を返す
function DeriveRunLengthStr(pStr)
{
    var WillReturn = '';
    var SeqCnt = 0;
    const UB = pStr.length - 1;

    for(var I = 0 ; I <= UB ; I++){
        //最初の文字の場合
        if(I == 0) {
            SeqCnt = 1;
        }
        //2文字目以降の場合
        if(0 < I){
            //同じ文字が連続している場合
            if(pStr[I - 1] == pStr[I]) {
                SeqCnt++;
            }
            //同じ文字が連続してない場合
            else{
                WillReturn += pStr[I - 1] + String(SeqCnt);
                SeqCnt = 1;
            }
        }
        //最後の文字の場合
        if(I == UB) {
            WillReturn += pStr[I] + String(SeqCnt);
        }
    }
    //document.write(pStr , 'をランレングス圧縮すると、' , WillReturn , '<br>');
    return WillReturn;
}

実行結果

2種類で5文字だと、短くなるのは10通り
6種類で6文字だと、短くなるのは156通り

解説

ナイーブにシュミレーションしてます。