組み合わせの個数を数える質問(yahoo知恵袋)

元の質問は, a,b,c,d,e,fの6文字から重複を許してn個選び,
選んだn個をそれぞれ2倍に複製した2n個を並べる並べ方の個数を求めたいとのこと.
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12151668017

例えば, n=3で最初に「aが1個とbが2個 (a,b,b)」が選ばれたら,
並べるときはそれぞれ2倍に複製してa,a,b,b,b,bを一列に並べる.

結論から書くと, n個選ぶときの並べ方の個数は
$3 \cdot 16^{n-1} + \left( 9^n-1 \right)/8 \cdot 4^{n-1} + 2^{2n-1}$
で求められる.
漸化式を立てて泥臭く求めたけれど, 以外に綺麗な形なので, エレガントな求め方がありそう.

数列A[i] = {a,b,c,d,e,f}として
A[1]=a,...,A[6]=fを表すとする.

f(n,k)でA[1],...,A[k]のk文字から重複を許してn個選んだときの並べ方の個数を表す.
つまり, f(n,6)の一般項を求めたい.

f(n,1) = 1
f(1,k) = k
はすぐ分かる.

また, A[1],...,A[k],A[k+1]のk+1文字から重複を許してn個選んだときの並べ方は
(1) n文字全部A[k+1]を選んだときの並び
(2) A[1],..,A[k]からm個選んでA[k+1]を(n-m)個選んだときの並び
(ただし, m=1,2,...,n)
に分けられる.

A[1],..,A[k]からm個選んでA[k+1]を(n-m)個選んだときの並びは
f(m,k)で数えた長さ2mの並びのそれぞれにA[k+1]を2(n-m)個挿入して作ることができる.
長さ2mの並びに2(n-m)個挿入する場合の数は ${_{2m+1}\mathrm{H}_{2(n-m)}} = {_{2n}\mathrm{C}_{2m}}$ 通りあるから
(1)の並びは1個
(2)の並びは各mに対して, ${_{2n}\mathrm{C}_{2m}} f(m,k)$ 個ずつある

よって並びの個数を求める漸化式は
$f(n,k+1) = 1 + \sum_{m=1}^{n} {_{2n}\mathrm{C}_{2m}} f(m,k)$
$f(n,1) = 1$
$f(1,k) = k$
となる

以下, ひたすらに一般項を計算する
$S(x)=\sum_{m=0}^{n}{_{2n}\mathrm{C}_{2m}} x^{2m}$ とすると,
$\left(1+x \right)^{2n} = \sum{m=0}^{n}{_{2n}\mathrm{C}_{2m}} x^{2m} + \sum{m=1}^{n}{_{2n}\mathrm{C}_{2m-1}} x^{2m-1}$
$\left(1-x \right)^{2n} = \sum{m=0}^{n}{_{2n}\mathrm{C}_{2m}} x^{2m} - \sum{m=1}^{n}{_{2n}\mathrm{C}_{2m-1}} x^{2m-1}$
より
$S(x) = \frac{(1+x)^{2n}+(1-x)^{2n}}{2}$
と表せる.

$f(n,2) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,1) = S(1) = 2^{2n-1}$
$f(n,3) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,2) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} 2^{2m-1} = \frac{1}{2} \left( 1 + S(2) \right) = \frac{1}{2} \left( 3^{2n}+3 \right)$
$f(n,4) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,3) = \frac{1}{4} \left(S(3) + 3S(1) \right) = \frac{1}{8} \left(4^{2n} + 4 \cdot 2^{2n} \right)$
$f(n,5) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,4) = \frac{1}{8} \left(S(4) + 4S(2) + 3 \right) = \frac{1}{16} \left(5^{2n} + 5 \cdot 3^{2n} + 10 \right)$
$f(n,6) = 1+\sum_{m=1}^n {_{2n}\mathrm{C}_{2m}} f(m,5) = \frac{1}{16} \left(S(5) + 5S(3) + 10S(1) \right) = \frac{1}{32} \left(6^{2n}+6 \cdot 4^{2n} + 15 \cdot 2^{2n} \right)$
最後の式を整理して最初に書いた一般項が得られる.

次のf(n,7)は
(1/32)(S(6)+6S(4)+15S(2)+ 定数)という形だろうし, うまい規則がありそう.