読者です 読者をやめる 読者になる 読者になる

理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

「2017年早稲田大教育学部数学[1](2)」のメモ

Math Exam

いよいよ,明日は2次試験ですね.その前に,ちょっと目に留まった問題のメモを残しておきます.

問題

n2以上の自然数とする.1から nまでの自然数の順列
 a_1 a_2 \cdots a_n

のうち,a_k < a_{k+1}を満たさないような kがただ 1つだけある順列の総数を P_nとする.例えば,n=3の場合,条件を満たす順列全体は \{ 132, 213, 231, 312 \} であるので,P_3=4である.P_{n+1}P_nの関係式を求めよ.

なぜ目に留まったか

この問題と同じ方針で解けるのでは?と思ったからです.
miwotukusi.hatenablog.jp

この記事では,

  • 完全順列になっている列に,新たな数を付け足す.
  • 完全順列になり損ねている(1つだけ重なっている)列に,新たな数を付け足す.(→重なっている数と新たな数を入れ替える)

という方針で,漸化式を導出していました.

似て非なりなところもありますが,

  1. 123 \ \cdots \ nとなっている列に,新たな数:N=n+1を付け足す.
  2. すでに条件を満たしている列に,新たな数:N=n+1を付け足す.

という方法で攻められるのでは?と考えた次第です.

まずは手を動かしてみる

というわけで,P_4がいくつになるかを考えてみます.n=3での順列が列挙されていますし,方針も上のように考えているので,

  • 「123」に「4」を付け足す → 1243, 1423, 4123
  • 「132」に「4」を付け足す → 1324, 1342
  • 「213」に「4」を付け足す → 2134, 2413
  • 「231」に「4」を付け足す → 2314, 2341
  • 「312」に「4」を付け足す → 3124, 3412

と導くことができ,P_4=11となります.これを求めておけば,答えとして導出した漸化式の検算にも使えますね.

そして,この様子を見ていると,やはり「123」の場合とそれ以外の場合で付け足し方が変わりそうです.ただ,これだけではまだよくわかりません.nが大きくなったときに,どうなるか.できれば,もうちょっと例を見たいところですが,だいぶと時間がかかってしまいそうです.

いつもの「可視化」で考えてみると,

数字の列ばかりを見てると,大きい小さいの感覚もわからなくなってくるかもしれません.そこで,図にしてみると,
f:id:miwotukusi:20170224190001p:plain

というわけで,*1

  1. 123 \cdots nとなっている列に,新たな数:N=n+1を付け足す場合は,一番前に置けることにも注意して nとおり.
  2. すでに条件を満たしている列に,新たな数:N=n+1を付け足す場合は,それぞれについて 2とおりずつあるので,全部で 2P_nとおり.

となって,答えは  P_{n+1} = 2P_n + nとなります.



さて,問題はここで終わっていますが,やはり漸化式解きたいですよね.ただ,ちょっと「わな」が多いです.

延長戦:漸化式を解く.

まず,わかっている内容を整理しておきます.
  P_2=1, \ P_3=4, \ P_4=11
  P_{n+1} = 2P_n + n \ \ \cdots (1)

第1ラウンド:nを消す

(1式)の右辺には nが含まれていますが,幸い 1次式なので簡単に消すことができます.
  P_{n+2} = 2P_{n+1} + (n+1) \ \ \cdots (2)

(2式)-(1式)より,
  P_{n+2} - P_{n+1} = 2( P_{n+1} - P_n ) + 1

ここで, Q_n = P_{n+1} - P_nと置けば,*2
  \begin{align} Q_{n+1} &= 2Q_n + 1 \\ Q_{n+1} + 1 &= 2(Q_n + 1) \ \ \cdots (3) \end{align}

ここからが「トラップゾーン」です.なぜならば,「n2以上の自然数とする.」からです.

(3式)は数列:\{ Q_n + 1 \}等比数列であることを示していますが,初項が  Q_2 + 1であるので,
  Q_n + 1 = 2^{n-2} (Q_2 + 1)

となります.こういうときは数列~その1~にも書いたように植木算の考えで「間隔」がいくつあるかを考えるのがいいと思います.これで Q_nは,
  Q_n = P_{n+1} - P_n = 2^n - 1 \ \ \cdots (A)

となります.

第2ラウンド:階差数列

(A式)は,数列:\{ P_n \}の階差数列を表しています.が,やはり初項は P_2なので,そこに注意しなければなりません.
f:id:miwotukusi:20170224193819p:plain

さらに, i = j+1と置き換えると,*3

  \begin{align} P_n = P_2 + \sum_{i=2}^{n-1} Q_i &= P_2 + \sum_{j=1}^{n-2} Q_{j+1} \\ &= P_2 + \sum_{j=1}^{n-2} \left\{ 2^{j+1} - 1 \right\} \\ &= 2^n - n - 1 \end{align}

 P_2 = 1も満たしているので,これが一般項となります.
ちなみに,n=1を代入してみると,P_1=0となっていてある意味正しい値を出しています(笑).


漸化式を解くところも含めて,骨のある問題だと思います.

*1:N=n+1はグラフ上で「一番高い位置にある点」であることに注意すればわかりやすいと思う.

*2:特性方程式は, q= 2q+1

*3:等比数列の和のところは,数列~その3~を参考に.