Re: [分析] 請問 R、2^N、N! 的對應方法

[mgtsai ()]

※ 引述《loteslogin (張三立)》之銘言：
:     已知 R、2^N、N! 的數量是相同的。
:         其中 2^N 是全部的Ｎ之子集
:               N! 是全部的Ｎ任意排列
:     有沒有什麼方法可以比較輕鬆的讓他們一一對應且映滿 (bijection) ？

:          R   →   2^N
:         2^N  →    R

先給 2^N <-> R 的 bijective mapping，其它的可以嘗試自行建構


f: 2^N -> R

           g(S)
f(S) = ------------
        1 - g^2(S)

其中
            ∞         -n
g(S) = -1 + Σ I(S,n) 2  ，if both S and N\S are infinite
            n=0

            ∞         -n-1
       -1 + Σ I(S,n) 2    ，if N\S is finite
            n=0

       max(S)        -n-1
        Σ   I(S,n) 2    ，if 1 < |S| < ∞
        n=0

        -m-2
       2    ，if S = {m}

       1/2，if S is an empty set

I(S,n) = 1, if n is an element of S
         0, if n is not an element of S



:          R   →    N!
:          N!  →    R
:         2^N  →    N!
:          N!  →   2^N
:     請高手不吝提供輕鬆的方法，在上述中提供任一個對應方法。
:     例如說

:             (1)  √2 可對應到 子集{....} 或者是

        -1 + x
解 ---------------- = √2
    1 - (-1 + x)^2

得 x = 1 + 1/√2，化為以二進位表示的小數為 1.101101010000010011110.....

其對應的集合則為 {0, 1, 3, 4, 6, 8, 14, 17, 18, 19, 20, ....}


:             (2)  可將 N 的 3 與 5 交換後形成的排列可對應到 R 的什麼數
:             之類的

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.250.129.52
※ 編輯: mgtsai          來自: 60.250.129.52        (09/10 16:46)
推 loteslogin  :謝謝你！只是…有更輕鬆一點的方法嗎…？