2つの待ち行列を処理する順列

質問

長さm、nの2つの待ち行列A={a1,a2,...,am}とB={b1,b2,...,bn}があるとき、
処理する順番が何通りあるかをm、nで表せないかと悩んでおります。

m=1,n=1とすると、
a1→b1とb1→a1で2通りなので、
f(1,1)=2です。

m=1,n=2とすると、、
a1→b1→b2 と b1→a1→b2 と b1→b2→a1の3通りなので、
f(1,2)=3です。

このようなf(m,n)をmとnの式で表せないでしょうか。
今のところ私がわかっているのは、

f(m,n) = f(m,n-1) + f(m-1,n)
f(m,n) = f(n,m)
f(m,1) = m + 1

ということです。
私は数学家ではないので、難しいことは分かりませんが、
どうかお力添えのほどお願いいたします。

回答No.1

kumoringo · ベストアンサー

AAABBABのようにAをm個、Bをn個並べると考えれば、
(m+n)個からm個選ぶ組み合わせ、すなわち (m+n)!/m!n! で求まります。

お礼

(m+n)席の一本の待ち行列のうちのm席に
Aを配置する組み合わせを数えれば、
Bは残った席に着くということですね！
大変よくわかりました。
上記の式もすべて満たしていて目から鱗です。
ありがとうございましたm(_ _)m