有趣的計數(shù)解題報告

1、有趣的計數(shù)解題【問題分析】這是我在看 Polya 定理的那一節(jié)書的時候出的題目。由于在 Polya 定理中有很多的概念、定理、推論，例如群的基本知識等等。所以我在這一篇解題中也不可能從一開始的概念講起。因此，我建議大家如果沒有了解 Polya 定理的話，可以先看看組合數(shù)學(xué)中的有關(guān)章節(jié)，再看解題。這道題用 Burnside 引理即可獲得解決。Burnside 引理：設(shè) G 是 N=1,2,n上的置換群，G 在 N 上可引出不同的等價類，其不同的等價類的個數(shù)為L=1/|G|*c1(a1)+c1(a2)+c1(ag)其中，c1(ak)的定義為：設(shè) G=a1,a2,ag，其中 a1=e，若把 ak 分

2、解成不相交的循環(huán)的乘積，k=1,2,g.記 c1(ak)為置換ak 中一階循環(huán)的個數(shù)，即在 ak 作用下保持不變的元素的個數(shù)，例如：G=e,(1,2),(3,4),(1,2)(3,4);a1=e=(1)(2)(3)(4),a2=(1 2)=(1 2)(3)(4),a3=(3 4)=(1)(2)(3 4),a4=(1 2)(3 4)c1(a1)=4;c1(a2)=2;c1(a3)=2;c1(a4)=0.Burnside 引理的證明比較繁瑣，這里就略去了。下面這一道題。由 N 位數(shù)的數(shù)的集合S，|S|=10N.看怎樣應(yīng)用 Burnside 引理解決對 S 的置換群 G=g1,g2，g1 是將 S

3、中的 10N 個元素變?yōu)樽陨淼牟粍又脫Q，所以，C1（g1）10N.g2 對 S 中的元素做這樣的置換：(a)若倒過來不是可讀的數(shù)，則為自身置換。如 2 4 1 6 5，倒過來讀不是一個可讀的，則不動。若倒過來可讀的數(shù)，則被倒過來讀的數(shù)所置換。例如 1 6 9 8 0，被 0 8 6 9 1 置換。則若 N 為奇數(shù)：C1(g2)=( 10N-5N)+3*5(N-1)/2若 N 為偶數(shù)：C1(g2)=( 10N-5N)+5N/2，(b)因為 0 到 9 的 10 個數(shù)字中有 2，3，4，5，7 這 5 個數(shù)，倒過來為不可讀的；另 5 個數(shù)為可讀的。其中由 5 個可讀的數(shù) 的符號串有 5N 個。10

4、N-5N是不可倒過來讀的數(shù)，即其中至少包含至少一位是 2，3，4，5，7 的數(shù)。若 N 為奇數(shù)，在由 0，1，6，8，9 取N 個 的 N 位符號串中有 3*5(N-1)/2個倒過來是自身的。即中間一位數(shù)必須是 0，1，8 中一個，前(N-1)/2 位是任意的。若 N 為偶數(shù)，在由 0，1，6，8，9 取 N 個 的N 位符號串中有 5N/2 個倒過來是自身的。因為前 N/2 位都是任意的。問題變?yōu)榍骃 中的 10N 個元素在群 G 的作用下分成的不同的等價類。倒過來可讀的兩個數(shù)屬同一類；倒過來不可讀，必須自成一類。所以要求的數(shù)目即為在群 G 的作用下分成的不同的等價類的數(shù)目。根據(jù) Burns

5、ide 引理，不同等價類的數(shù)目為：N 為奇數(shù)時：1/2*10N +( 10N-5N)+3*5(N-1)/2 N 為偶數(shù)時：1/2*10N +( 10N-5N)+ 5N/2.當(dāng)然，我把數(shù)據(jù)量出得很小，因此，編程的復(fù)雜度非常低，Long窮舉的話，恐怕較大的點還是過不了。就能解決問題了?！境绦颉縋rogram num; constTd: array 0.9 of qword= (1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000);Fd: array 0.9 of qword=(1,5,25,125,625,3125,15625,78125,390625,1953125);procedure Setup; beginassign(input,num.in); reset(input); assign(output,num.out); rewrite(output);end;procedure Endit; beginclose(input); close(output)end;proceduret; var n,t: long;beginreadln(n); if odd(n)then begint:=tdn+(3*fdn div 2-fdn) div