甚麼是鬼腳函數?(有20點喔)

Question

之前有再一個地方看到一個叫"鬼腳函數"這是甚麼東西阿?

Answer 1

首先觀察最簡單的空白鬼腳圖，它的對應關係 是一種排列。對於任意對應關係為排列f的鬼腳圖，新的鬼腳圖的對應關係為 的一個排列函數。由於每個鬼腳圖橫線的數目都是有限，每條橫線皆是一個移項，鬼腳圖起點與終點的對應關係為每條橫線所代表的移項合成之排列函數。本文將利用移項的運算做為探討鬼腳圖性質的基本工具。此鬼腳圖起點與終點的對應關係可表示成下列移項之合成。由於每個鬼腳圖可寫成一個排列，根據排列的定義可得鬼腳函數是對映函數即一對一函數。首先觀察最簡單的移項是由生成元素所構成，因為內包含所有的移項，而且每個排列都是有限個數移項的合成，因此可以利用這個方法將結果推廣到任意給定的N定理。任何排列都可以利用足夠多的橫線來畫出所對應的鬼腳 圖。造出鬼腳圖 f 的方法並非唯一，下文將討論鬼腳圖的方法數。固定橫線數,組成特定對應關係鬼腳圖的方法數,由前面的部分可知，給定任意的排列a，都可以用有限條橫線畫出對應關係為a的鬼腳圖，問題是最少需要多少條橫線才足夠畫出？若橫線數目足夠，總共有多少種不同的畫？為了簡化問題，首先假設鬼腳圖的橫線有順序性，把(a)與(b)看作是不同的鬼腳圖。可算出最靠近終點的橫線為其他不同移項時，鬼腳圖a的畫法數。就是將靠近終點橫線所有可能性的方法數通通加起來，得到下面的遞迴關係式。因此對於可以利用遞迴式開始計算，即可求出值。要先對每個不同參數的結果逐一計算，最後才能得到答案，下面將簡化 的運算方式。根據定義，他的值表示g是否為 的生成元素；所以 是一對一映成函數，分別代入所有 的元素，得到下面方程組,可用矩陣方程式來表示上面的方程組。考慮 的Cayley graph，利用Cayley graph可以幫助我們了解。在G中沒有生成元素將 與 這兩個點直接連接。因此可將M視為G的adjacency matrix，所以,他的值解釋可為由e走t步至a的方法數，畫出對應關係為a的鬼腳圖所需的最少橫線數也可解釋為由e走至a的最短距離，利用Cayley graph讓我們不需直接計算矩陣M的次方即可求出 的值。下面將介紹一種方法，藉由計算排列的反序數，求出排列與e的距離。下面的預理描述反序數與排列間的關係，我們將排列一次交換一個來排序，就可以使反序數減少至0，即為要證明的內容。我們可藉由反序數計算Cayley graph中任一點到 e 的距離。當N很大而很難畫出Cayley graph時，可藉由引理7算出組成所有排列所需的最少橫線數。若鬼腳圖的性質，先畫出Cayley graph。可以利用反序數計算各個排列與e間的距離。同樣也可以求出其他排列與所需最少橫線的關係，即為排列的反序數。所以4條縱線的鬼腳圖至少需要6條橫線才有可能組合成所有情況的排列,Cayley graph可以幫助我們藉由圖型了解排列群及鬼腳圖的性質。容易發現 任意路徑長度皆為奇數，所以只能用奇數條橫線畫出所對應的鬼腳圖；由走到 的任意路徑長度皆為偶數，所以只能用偶數條橫線畫出。同時在圖八及其他任意的N也可觀察到同樣的現象。這驗證了奇排列不可能用偶數個移項合成，同樣的偶排列無法用奇數個移項合成。固定橫線數,組成特定對應關係鬼腳圖的機率，若是橫線數很少，勢必很難從最右邊的起點走到最左邊的終點；當橫線數越多，則越容易由最右邊的起點走到最左邊的終點。所以由不同的起點走向不同的終點的機率不盡然相同，而且與橫線數及縱線的多寡有關。若是要詳細計算鬼腳圖由某個起點走向某個終點的機率，可以利用類似第五節的方法加入機率來進行計算。N條縱線的鬼腳圖，畫上任意t條橫線。假設對於所有的與互為獨立事件。由於互為互斥事件，所以對於任意也是互為互斥事件。又因為樣本空間也可以寫成一個矩陣關係式，可知M為G的weighted adjacency matrix，每個邊所代表的數值就是在鬼腳圖上畫該條橫線的機率。若是要計算從特定起點a連接到特定終點b鬼腳圖的機率，先找到符合 的所有排列 。由前面的方法，可以求出每個 的値，因此就可算出由a連接至b的機率 的値了。假設某人比較喜歡畫(2,3)的橫線於3條縱線鬼腳圖中，畫的機率為2/3，可畫出 的Weighted Cayley Graph。三條縱線的鬼腳圖的結果整理為發現在橫線數較少的情況之下，由第2個起點走到各個終點的機率不盡然相同，所以遊戲不是完全公正的；而橫線越多，走到各個終點的機率越接近，遊戲也就公平,若Cayley Graph會變的很複雜，可以利用矩陣進行運算。觀察可發現，橫線數越少時，越難由中央的起點走至越遠的終點，一直要到橫線數非常多，走到各個終點的機率才會接近。一般鬼腳圖的橫線不會很多，所以由不同起點走到不同終點的機率不相等。如果想要走到特定的終點，可以選擇與該終點附近的橫線為起點，走到你想要的終點的機會就會比較大。利用排列群原理分析鬼腳圖的各種可能組合情形，並利用Cayley Graph分析特定橫線數組成特定對應關係鬼腳圖的方法數。最後由機率的方法，發現鬼腳圖在橫線數少的情況下，不是一個公平的抽籤方法。若要使抽籤達到公平，可將遊戲規則稍作改變，抽籤項目遮住，可使遊戲達到公平，而且不失鬼腳圖的趣味性。鬼腳函數是用來探討機率的函數.

2006-11-21 08:53:31 補充：
有整理過啊!

Answer 2

一個一大堆沒有分段，一個只是引用參考連結沒有說明，還真是～～～唉
～～～

Answer 3

simon
你PO的答案....是不是沒有整理過...

Answer 4

由鬼腳圖所衍生出的函數. You can have some details about it in:
http://www.math.sinica.edu.tw/media/media.jsp?voln=293

Answer 5

是不是這個
http://www.ntsec.gov.tw/activity/race-2/International2004/pdf/0110.pdf