最近看了一篇文章Enumerative And Algebraic Combinatorics，寫得很不錯，在此推介（不過我想比較適合已經學過combinatorics的人）。
在此quote其中一段，用了現實中的例子說明了Burnside Lemma：
Suppose that there is a picnic consisting of many families and we want to count the number of families. One way would be to define some "canonical head" of each family, say "mother", and count the number of mothers. But some daughters look like mothers, so this is not so easy. On the other hand, you cannot just count everybody , since then you would count each family several times. The problem is that "naive" counting of people is giving a credit of 1 to each person, and this is inappropriate if we are trying to count families. If instead we were to ask each person "How big is your family?" and add to our count the reciprocal of that number, then the calculation would come out just right, since a family of size k would get a credit of 1/k for each of its members, and would therefore have been counted exactly once by the end.
Going back to counting orbits, we see by the same reasoning that their number is \sum_{a \in A} 1 / | Orbit(a) | ......
3 則留言:
這文章確實很不錯啊。印象中沒看過這個關於 Fibonacci number 的等式：
a_n = sum(k=0 to [n/2]) C(n-k,k)
有沒有一個「很組合」的證明？（當然，我們可以用
(*) C(n,k) + C(n,k+1) = C(n+1,k+1)
來證明以上等式，但這樣證明「很代數」，縱使 (*) 本身可以「很組合」地解釋亦然。）
我看的時候並未有為意這個等式，幸好你提一提。
這個等式的「組合」證法可以借助這個經典的問題作一一對應：
A rabbit can jump up one stair or two stairs each time. The number of ways to jump to the n-th stairs is exactly a_n. Another way to count it can be considering n-k as the number of jumps,
Wow, very nice!
張貼留言