あらゆる言葉が載った辞書

あらゆる言葉が載った辞書を考えます。
一番最初に載っている言葉は何でしょうか?
正解は「あ」です。
次は「ああ」ですね。その次が「あああ」。
何ページかめくると、「あああああ・・・」となってますね。
それを超えると、今度は「あい」になります。
次が「あいあ」。その次が「あいああ」。
以下、「あいあああああ・・・」となってますね。
さらに超えると、次は「い」になります。
以下、「いあ」、「いああ」、「いあああ・・・」、「いあい」、「いあいあ」、「いあいああ」、「いあいあああ・・・」となります。

では、辞書を分けて、「あ」から始まる辞書を「あ巻」とし、最初の「あ」を省略します。
一番最初に載っている言葉は何でしょうか?
元の辞書の「あ」は消えるので、次の「ああ」の「あ」を省略して、「あ」になります。
次は、「あああ」を省略して、「ああ」になります。
以下、「あああ」、「ああああ」、「あああああ・・・」になります。
それを超えたら、次の「あい」を省略して、「い」になります。
以下、「いあ」、「いああ」、「いあああ・・・」となります。
つまり、「あ巻」は、「あ」、「ああ」、「あああ・・・」、「い」、「いあ」、「いああ」、「いあああ・・・」となっています。

ということは、元の辞書とあ巻は同じものになります。
辞書を分けたはずなのに、同じになるのは不思議ですね。

AIZU ONLINE JUDGEのELISP解答例(ITP1_1_A~ITP1_2_C)

ITP1_1_A:Hello World
(message "Hello World")
ITP1_1_B:X Cubic
(progn (defun cubic ()
	 (let ((x (read)))
	   (* x x x)))
       (cubic))
ITP1_1_C:Rectangle
(progn (defun rectangle ()
         (let ((a (read))
	       (b (read)))
           (cons (* a b) (* 2 (+ a b)))))
       (rectangle))
ITP1_1_D:Watch
(progn (defun watch ()
         (let ((x (read)))
           (let ((s (% x 60)))
             (let ((m (% (/ (- x s) 60) 60)))
	       (let ((h (/ (- (/ (- x s) 60) m) 60)))
	         (list h m s))))))
       (watch))
ITP1_2_A:Small, Large, or Equal
(progn (defun small ()
	 (let ((a (read))
	       (b (read)))
	   (if (< a b) (message "a<b")
	     (if (> a b) (message "a>b") (message "a=b")))))
       (small))
ITP1_2_B:Range
(progn (defun range ()
         (let ((a (read))
	       (b (read))
	       (c (read)))
           (if (and (< a b) (< b c)) (message "YES") (message "NO"))))
       (range))
ITP1_2_C:Sorting Three Numbers
(progn (defun swap (x a b)
         (let ((c (elt x a)))
           (setf (elt x a) (elt x b))
           (setf (elt x b) c)
           x))
       (defun sort ()
	 (let ((a (read)) (b (read)) (c (read)))
	   (let ((x (list a b c)))
             (dotimes (j (1- (length x)))
               (dotimes (i (1- (length x)))
                 (if (> (elt x i) (elt x (1+ i)))
	             (swap x i (1+ i)))))
	     x)))
       (sort))

Lispやってみた2

あれから少し経って、多少なりとも使えるようになりましたが、わからないことだらけです(^_^;)
例えば、文字列を出力しようとしても、カッコつきのまま出力されたり、複数の出力ができなかったり・・・
あとわかったことは、lispにもいろいろな方言があるということでしょうか。
私が使っているのは、Emacs Lisp(通称elisp)だと思います。
とりあえずは、少しでも良さげな解説サイトを探すことを
目標にしたいと思います(´-`)

Lispやってみた

Lispを学び始めたんですが、いかんせんLispの解説サイトが少ない・・・
やはりマイナーなのでしょうか?
素数判定のプログラムすらまともに動かない(´・ω・`)
なぜ興味を持ったかと言いますと、ラムダ計算ができそうなのが理由です。
良いと思った点は、とにかく簡潔に書けるということです。
カッコは"("と")"だけ使って、"{"や"}"は使いません。
あとは、Rubyと一緒で引数を区切る時に","を使いません。
ぜひLispが使える人のご教授を受けたいですね。

スターリング数

S(m,n)をm個の集合からn個の集合への全射の総数とする。
S(m,n):=|\{f\in B^A|f:全射,|A|=m,|B|=n\}|
以下の漸化式が成り立つ。
 S(m,0)=0^m\\
\displaystyle S(m,n)=n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)S(m,k)
nを固定して求める。
\displaystyle 
\begin{eqnarray}
S(m,1)&=&1^m-\sum_{k=0}^{0}\left(\begin{matrix} 1 \\k\end{matrix}\right)S(m,k)\\
&=&1^m-\left(\begin{matrix} 1 \\0\end{matrix}\right)S(m,0)\\
&=&1^mー0^m\\
S(m,2)&=&2^m-\sum_{k=0}^{1}\left(\begin{matrix}2 \\k\end{matrix}\right)S(m,k)\\
&=&2^m-\left(\begin{matrix}2 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix}2 \\0\end{matrix}\right)S(m,0)\\
&=&2^m-2(1^m-0^m)-0^m\\
&=&2^m-2\cdot1^m+0^m\\
S(m,3)&=&3^m-\sum_{k=0}^{2}\left(\begin{matrix}3 \\k\end{matrix}\right)S(m,k)\\
&=&3^m-\left(\begin{matrix}3 \\2\end{matrix}\right)S(m,2)-\left(\begin{matrix}3 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix}3 \\0\end{matrix}\right)S(m,0)\\
&=&3^m-3(2^m-2\cdot1^m+0^m)-3(1^mー0^m)-0^m\\
&=&3^m-3\cdot2^m+3\cdot1^m-0^m\\
S(m,4)&=&4^m-\sum_{k=0}^{3}\left(\begin{matrix} 4 \\k\end{matrix}\right)S(m,k)\\
&=&4^m-\left(\begin{matrix} 4 \\3\end{matrix}\right)S(m,3)-\left(\begin{matrix} 4 \\2\end{matrix}\right)S(m,2)-\left(\begin{matrix} 4 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix} 4 \\0\end{matrix}\right)S(m,0)\\
&=&4^m-4(3^m-3\cdot2^m+3\cdot1^m-0^m)-6(2^m-2\cdot1^m+0^m)\\
&&-4(1^mー0^m)-0^m\\
&=&4^m-4\cdot3^m+6\cdot2^m-4\cdot1^m+0^m
\end{eqnarray}
どうやら、S(m,n)は次の式になるようだ。
\displaystyle S(m,n)=\sum_{k=0}^n \left(\begin{matrix}n\\k\end{matrix}\right) (-1)^{n-k} k^m
以下、数学的帰納法で証明する。
\displaystyle
\begin{eqnarray}
S(m,n)&=&n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)S(m,k)\\
&=&n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)\sum_{i=0}^k \left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
&=&n^m-\sum_{k=0}^{n-1}\sum_{i=0}^k \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
\end{eqnarray}

\begin{eqnarray}
\left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right)&=&\frac{n!}{k!(n-k)!}\frac{k!}{i!(k-i)!}\\
&=&\frac{n!}{(n-k)!}\frac{1}{i!(k-i)!}\\
&=&\frac{n!}{i!}\frac{1}{(n-k)!(k-i)!}\\
&=&\frac{n!}{i!(n-i)!}\frac{(n-i)!}{(n-k)!(k-i)!}\\
&=&\left(\begin{matrix}n\\i\end{matrix}\right)\frac{(n-i)!}{(n-k)!(k-i)!}\\
\end{eqnarray}

\begin{eqnarray}
S(m,n)&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\i\end{matrix}\right)\frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i} i^m\\
&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}\\
\end{eqnarray}

\begin{eqnarray}
\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}&=&\sum_{k-i=0}^{n-i-1} \frac{(n-i)!}{(n-i-(k-i))!(k-i)!} (-1)^{k-i}\\
&=&\sum_{j=0}^{n-i-1} \frac{(n-i)!}{(n-i-j)!j!} (-1)^{j}\\
&=&\sum_{j=0}^{n-i-1} \left(\begin{matrix}n-i\\j\end{matrix}\right) (-1)^{j}\\
&=&-\left(\begin{matrix}n-i\\n-i\end{matrix}\right) (-1)^{n-i} + \sum_{j=0}^{n-i} \left(\begin{matrix}n-i\\j\end{matrix}\right) (-1)^{j}\\
&=&-(-1)^{n-i}+0^{n-i}
\end{eqnarray}

\begin{eqnarray}
S(m,n)&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}\\
&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-(-1)^{n-i}+0^{n-i})\\
&=&n^m+\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-1)^{n-i}-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m 0^{n-i}\\
&=&\sum_{i=0}^{n}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-1)^{n-i}\\
&=&\sum_{k=0}^n \left(\begin{matrix}n\\k\end{matrix}\right) (-1)^{n-k} k^m
\end{eqnarray}
ちなみに、スターリング数はS(m,n)をn!で割ったものだ。