いよいよ,明日は2次試験ですね.その前に,ちょっと目に留まった問題のメモを残しておきます.
問題
のうち,を満たさないような がただ つだけある順列の総数を とする.例えば,の場合,条件を満たす順列全体は であるので,である.と の関係式を求めよ.
なぜ目に留まったか
この問題と同じ方針で解けるのでは?と思ったからです.
miwotukusi.hatenablog.jp
この記事では,
- 完全順列になっている列に,新たな数を付け足す.
- 完全順列になり損ねている(1つだけ重なっている)列に,新たな数を付け足す.(→重なっている数と新たな数を入れ替える)
という方針で,漸化式を導出していました.
似て非なりなところもありますが,
- となっている列に,新たな数:を付け足す.
- すでに条件を満たしている列に,新たな数:を付け足す.
という方法で攻められるのでは?と考えた次第です.
まずは手を動かしてみる
というわけで,がいくつになるかを考えてみます.での順列が列挙されていますし,方針も上のように考えているので,
- 「123」に「4」を付け足す → 1243, 1423, 4123
- 「132」に「4」を付け足す → 1324, 1342
- 「213」に「4」を付け足す → 2134, 2413
- 「231」に「4」を付け足す → 2314, 2341
- 「312」に「4」を付け足す → 3124, 3412
と導くことができ,となります.これを求めておけば,答えとして導出した漸化式の検算にも使えますね.
そして,この様子を見ていると,やはり「123」の場合とそれ以外の場合で付け足し方が変わりそうです.ただ,これだけではまだよくわかりません.が大きくなったときに,どうなるか.できれば,もうちょっと例を見たいところですが,だいぶと時間がかかってしまいそうです.
いつもの「可視化」で考えてみると,
数字の列ばかりを見てると,大きい小さいの感覚もわからなくなってくるかもしれません.そこで,図にしてみると,
というわけで,*1
- となっている列に,新たな数:を付け足す場合は,一番前に置けることにも注意して とおり.
- すでに条件を満たしている列に,新たな数:を付け足す場合は,それぞれについて とおりずつあるので,全部で とおり.
となって,答えは となります.
さて,問題はここで終わっていますが,やはり漸化式解きたいですよね.ただ,ちょっと「わな」が多いです.
延長戦:漸化式を解く.
まず,わかっている内容を整理しておきます.
第1ラウンド:を消す
(1式)の右辺には が含まれていますが,幸い 1次式なので簡単に消すことができます.
(2式)-(1式)より,
ここで,と置けば,*2
ここからが「トラップゾーン」です.なぜならば,「を 以上の自然数とする.」からです.
(3式)は数列:が等比数列であることを示していますが,初項が であるので,
となります.こういうときは数列~その1~にも書いたように植木算の考えで「間隔」がいくつあるかを考えるのがいいと思います.これで は,
となります.
第2ラウンド:階差数列
(A式)は,数列:の階差数列を表しています.が,やはり初項は なので,そこに注意しなければなりません.
さらに,と置き換えると,*3
も満たしているので,これが一般項となります.
ちなみに,を代入してみると,となっていてある意味正しい値を出しています(笑).
漸化式を解くところも含めて,骨のある問題だと思います.