[過去ﾛｸﾞ] 有限数列上の変換について [無断転載禁止]©2ch.net (84ﾚｽ)

有限数列上の変換について [無断転載禁止]©2ch.net http://rio2016.5ch.net/test/read.cgi/math/1453437840/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

71: ◆tAo.kQ2STk [sage] 2016/01/26(火) 12:01:41.04 ID:C203oPVR ふと思いついたんで書いてみる。チラ裏失礼。 y=C(x)に対し、その定義域が0からN-1までの整数であり、又、値域が0からN-1までの整数であり、かつ全単射であると仮定する。 定理 1 Cによるm回の写像をC^m(・)とする時、全ての整数i<Nについて、ある整数m>0が存在し、i = C^m(i)が成り立つ。 直感としては、任意の全単射の整数関数及び任意の整数に対して長さmのループが存在する。 この時、D(i)=C^{m-1}(i)によりDを表現できる。 証明 1 背理法により、ループが存在しないと仮定する。つまり、ある整数iが存在し、全てのmについて、i \neq C^m(i) 鳩の巣の原理より、m>Nについて、系列C^m(i)には重複が存在する筈である。 つまり、C^{m+n}(i) = C^{m+n+h}(i)となるような整数n, hが存在する。 両辺にD^{m+n}を合成すると i = C^h(i) よって、全てのmについてi \neq C^m(i)が成り立つような整数iは存在しない。 定理 2 任意のCについて、全てのiに対して最小の整数mを計算した時、その値の集合MのサイズはO(√N)で押さえられる 証明 2 明らかに、あるループ長m_jに対して、そのループ長であるようなループの個数k_jが存在し、 N = \sum_j m_jk_j M = \{m_1, m_2, ..., m_{M.size}\} が成り立つ。今各ループ長及び個数に対してm_j = j, k_j = 1を仮定すると、 N \simeq (M.size)^2 / 2 となる。 http://rio2016.5ch.net/test/read.cgi/math/1453437840/71

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.539s*