並べ方についての問題ですが、どうとけばよいですか。

質問

＜問題＞
(a)から１個取り出して並べる
(a,a,b)から２個取り出して並べる
(a,a,a,b,b,c)から３個取り出して並べる
(a,a,a,a,b,b,b,c,c,d)から４個取り出して並べる
というように、n種類の文字からn個取り出して並べるとき並べ方は何通りになるか求めよ。

　自分で考えたところ、１から４まではn^n-(n-1)^n通りとなりましたが、もしこれであっているのなら証明を教えてください。間違っているのならどうなるのか教えてください。

回答No.3

stomachman

{a} から1個とって並べる
{a,b,b}から2個とって並べる
{a,b,b,c,c,c}から3個とって並べる
…
としても同じ．「というように」の部分は，ですから一般に，A[1]が1個，A[2]が2個, .... あるとして，

P(n) = A[1]～A[n](合計(n+1)n/2個）の中からn個を取って並べる場合の数

ということですが，うーむ，こりゃ難しいなあ．

Q(n,m) = A[1]～A[n](合計(n+1)n/2個）の中からm個を取って並べる場合の数

としますと，P(n) = Q(n,n)であり，

Q(n,0) = 1
m>(n(n+1))/2 のとき　Q(n,m)=0
m≦(n(n+1))/2 のとき　Q(n,m) = Σ{j=0...m} ((m-j+1)^j)Q(n-1,m-j)

という漸化式が成り立つ訳で，これを積み上げて計算するぐらいしか思いつかん．

回答No.2

nag0720

問題のn種類の文字からk個取り出して並べるとき並べ方の数をS(n,k)とすると、
S(n,k)=Σ[i=0・・・n]S(n-1,k-i)*kCi　　（0≦k≦n(n+1)/2）
の漸化式が成り立ちます。（一般形までは分かりません）

これを使って計算すると、S(5,5)=2111となります。

n^n-(n-1)^nの式は、n=1,2,3,4までは合っていますが、
5^5-(5-1)^5=2101なので間違っているようです。

回答No.1

tac351115

まず、（）の中の文字が全て区別できるとした場合の順列を計算します。
（つまり、同じａでも、ａ１、ａ２というように区別できると仮に考えた場合です）
例えば、(a,a,b)なら、3の階乗＝3×2×1　です。

次に、同じ字の数の順列を計算します。
例えば、(a,a,b)なら、同じ字の数はａのみで2個なので、２の階乗＝2×1　です。
これは、ａ１、ａ２の並び方の数です。上ではこの順序を区別しましたが、実際には区別できず同じ並びになってしまうので、

最初に計算した数を２番目に計算した数で割ってやれば、本来の並びの種類の数が得られます。

つまり、(a,a,b)の場合には、3の階乗／２の階乗＝3　通り

になります。