問題が正しいとわかりません。最終的に、私はそれを移行します。連結数
リストを検討してください[1; 2; ..; n] 2つのリストを連結して表現できる方法はいくつありますか？
私がこれに与えた答えはn + 1です。私の答えの問題は、経験的な観察だけに基づいているということです。
I.e.
[] @ [1; 2; 3]
[1] @ [2; 3;]
[1; 2] @ [3]
[1; 2; 3] @ []
が私の仮説が正しいです：長さ3など[1; 2; 3]などのリストを与え、私は私のようにそれを表現することができると思いますか？あなたはそれをより強くテストするようにどのように提案しますか？
あなたはリストの建設からこれを証明することができます
リストが空リスト[]またはaが要素であり、Lがリストであるペア(a, L)のいずれかです。
正式
今L := []
| (a, L)
は、連結でのあなたの数を定義します
ncat(L) := 1 if L=[]
ncat(M)+1 if L=(a, M)
両方のケースが見やすいです。 []=cat([], [])以外の2つのリストを空のリストに連結する方法は他にありません。そして、建設によって、L = cat([a], M)、したがって、多くの分割と比較してLを分割するちょうどもう1つの方法は、すでにM（すなわち、aの後）にあります。
空リストを別のリストの先頭または末尾に連結することができるという専門は、この証明に安全に含まれ、勤勉な読者に委ねられています。
誘導によってこれを証明できます。 あなたはn個から行くとき、あなたの式が成り立つことを示し、その後
（あなたはイプシロンケースを考慮したい場合やn = 0）あなたは、あなたの式はn = 1成立することを示すために、N = N +は1
それから、次のそれがすべてのnに対して正しいこと。