この問題での順列組み合わせの使い方は？

質問

ｎ進数ｍ桁の数字列を考える。
全部でｎ＾ｍ通りのパターンがある。
このうち、一回も現れない数字のあるパターンＱは何通りか。

自分で立てた問題です（というか興味があるので知りたい）
けど、どうしても分かりません。
解き方を教えて下さい。

以下は自分の考えた履歴です
－－－
ある数字に着目して、それが選ばれないパターンは（ｎ－１）＾ｍ通り
これを数字の種類だけｎ倍すると、同じパターンを重複して数えてしまう気がする。
どうやって除去するか？

－－－
【ｎ＞ｍのとき】
ｍ＝１のとき、Ｑ＝ｎ－１通り
ｍ＝２のとき、
一回目と二回目で数字が同じパターンはｎ通り
異なるパターンはｎ＊（ｎ－１）通り
・・・ここから先が分からない

回答No.4

MagicianKuma · ベストアンサー

厳密に言うと問題にやや曖昧なところがあります。n進数m桁の数字列を考える。と書かれています。n進数といった場合はこれは数字列ではなく数値を意味します。するとm桁の数値といった場合は、最上位桁は0を含みません。ですが、数字列とかかれてますし、全部でn^mとおりのパターンがある。とも書かれていますので、n進数m桁は忘れることにします。問題を以下に変えます。n種類の記号を（重複を許して）m個並べてとき1回も現れない記号があるパターンは何通りか？

n>m　のとき　
　Q=n^m
n≦m のとき
　ある1種類の記号がない場合の数=残りの(n-1)種類からm個選ぶ(n-1)^m　これの nC1倍　とすると。次が重複
　ある2種類の記号がない場合の数=残りの(n-2)種類からm個選ぶ(n-2)^m　これの nC2倍を引くと、次が余分に引かれる
　ある3種類の記号がない場合の数=残りの(n-3)種類からm個選ぶ(n-3)^m
そんなこんなをまとめると
　Q = Σ-((-1)^k)・nCk・(n-k)^m k=1～n-1の和

n=4,m=6の例：Q=4C1・3^6 - 4C2・2^6 + 4C3・1^6 = 2536 通り

お礼

思っていたより複雑な式になるのですね。
これは自分で考えては分からないはずです。
まだ教えてもらって理解は出来ていないのですが、
ぼちぼち考えていきます。
どうもありがとうございました。

回答No.3

MagicianKuma

>－#(A∩Ｃ)-#(B∩Ｄ)が抜けているのでしょうか？
失礼しました。その通りです。

お礼

いえいえ、
あのように細かく打ち込むのは手間のかかることですから。
ありがとうございます。
なかなか分からない人に教えるのはほんと大変なことですから恐縮です

回答No.2

MagicianKuma

>同じパターンを重複して数えてしまう気がする。どうやって除去するか？
そうそう。そういう風に考えて言って良いですよ。今集合の元の数を#(集合)で表すとします。
2つの集合の場合、#(A∪B)=#(A)+#(B)-#(A∩B)
3つの集合の場合、#(A∪B∪C)=#(A)+#(B)+#(C)-#(A∩B)-#(B∩C)-#(C∩A)+#(A∩B∩C)
4つの集合の場合、#(A∪B∪C∪D)=#(A)+#(B)+#(C)+#(D)-#(A∩B)-#(B∩C)-#(C∩D)-#(D∩A)+#(A∩B∩C)+#(B∩C∩D)+#(C∩D∩A)-#(A∩B∩C∩D)
一般化して、#(∪Ai)=Σ#(Ai) - Σ#(Ai∩Aj) + Σ#(Ai∩Aj∩Ak) - ・・・ #(A1∩・・・∩An) 　です。　+-が交互に出てきます。これを「包除原理」といいます。検索すると出てくると思います。

この問題でいうと、「ある数字に着目して選ばれないパターン」これが上のA1になります。「これを数字の種類だｎ倍すると」が上のΣ#(Ai) に当たります。
「どうやって除去するか？」が- Σ#(Ai∩Aj) に当たります。２つのペアの重複をすべて除去すると、 Σ#(Ai∩Aj∩Ak) を除去しすぎるのでまた足します。こんな風に引いたり足したり繰り返していきます。
例：1～100までの整数のうち、３の倍数または５の倍数または７の倍数の数は何個あるか？
#(３の倍数または５の倍数または７の倍数)=#(３の倍数)+#(5の倍数)+#(7の倍数)-#(３の倍数∩5の倍数)-#(5の倍数∩7の倍数)-#(7の倍数∩3の倍数)+(３の倍数∩5の倍数∩7の倍数)

お礼

『4つの集合の場合、#(A∪B∪C∪D)=#(A)+#(B)+#(C)+#(D)-#(A∩B)-#(B∩C)-#(C∩D)-#(D∩A)+#(A∩B∩C)+#(B∩C∩D)+#(C∩D∩A)-#(A∩B∩C∩D)』
・・・この部分は、右辺に、
－#(A∩Ｃ)-#(B∩Ｄ)
、が抜けているのでしょうか？

とりあえず全般的には、わたくし的には結構難しい、ということが分かりました。
決して真剣に考えていないわけではありません。自分なりに引き続き考えてみます。
ありがとうございます！

回答No.1

MagicianKuma

n＞mのとき は　どのパターンも　1回も現れない数字があるのでは？
m=1のとき、Q=n-1通り　ではなく　n通り
m=2の時　　Q=n^2
結局 n>m のとき　Q=n^m　では？

お礼

『n＞mのとき は　どのパターンも　1回も現れない数字があるのでは？』
仰るとおりですね。まったく気が付きませんでした（悲）
ｍ＝１のときＱ＝ｎ通り・・・３分後に理解できました。
ｍ＝２のときＱ＝ｎ＾２通り・・・５分後に理解できました。
－－－
引き続き自分でも考えてみますが、この調子ではずっと分からなさそうな気もします（悲）