수학정리(Applications, Combinatorics)

*Applications

*Combinatorics

-About counting, p:permutation on J, |J|=n, P:permutation groups on J

-def

-the cycle index monomial of p is a monomial in variables a_i, prod over j=1 to j=n a_j^b_j, where a_j:variables, b_j:p를 cycle decomposition했을 때 길이가 j인 cycle의 개수

-ex) p=(1)(234)(5)(67)인경우 the cycle index monomial of p = a_1^2 * a_2^1 * a_3^1

-the cycle index polynomial of P := 1/|P| * sum over p in P (the cycle index monomial of p)

(즉, the average of the cycle index monomials of its elements)

(어떤 permutation on J는 permutation on J'으로 바꿔서 생각할 수 있다. 가령 C_4:반시계 방향 rotation, e, 90, 180, 270, 같은 경우 J={1,2,3,4}에서 action을 생각할 수도 있지만, J'={{1,2}, {2,3}, {3,4}, {1,4}}, J는 Square 1개에 각 꼭짓점에 시계방향으로 1,2,3,4를 새긴 경우, J'은 같은 square의 선분을 가리킴

the cycle index polynomial of C_4 on J와 the cycle index polynomial of C_4 on J'은 다르다.

전자는 C_4의 원소를 J에서의 permutation으로 보고, 후자는 C_4의 원소를 J'에서의 permutation으로 본다.)

(따라서 the cycle index는 단순히 Group에만 의존하는게 아니라 Group action에 의존, 즉 acting되는 set도 중요)

(Z(G,X)라 쓰도록 하자.)

-G acts on X일 때, for each x in X, wt:X->Y s.t. wt(x)=wt(gx) for all g in G, 즉 X의 orbit은 같은 값가지는 function

-ex)G=C_4, X={all squares with each vertex with colored black or white}, wt(x)=b^i * w^j, where i=# of blacks, j=# of whites

-G acts on X with wt, wt(Orbit)=wt(x) for some x in Orbit, well-defined

-G acts on X with wt, the wt enumerator := sum over all orbit O wt(O)

-thm

-(Burnside Lemma)

G acts on X일 때 the number of orbits = the average number of points fixed by an element of G(link)

-(Weighted Version of Burnside Lemma)

G acts on X with wt일 때 the wt enumerator = the average wt of points fixed by an element of G(link)

-(Polya Enumeration Theorem)(link)

-G acts on X, Y=finite colors={c_1,c_2,...,c_k}, then G acts on Y^X

-G acts on Y^X with wt:=prod over i=1 to i=k c_i^d_i, where d_i:=# of c_i in element of Y^X일 때

the wt enumerator := Z(G,X) with a_i replaced by (c_1^i + c_2^i + ... + c_3^i)

(좌변을 구하기 위해서 우변을 이용하란 의미고, 우변의 전개식에서 원하는 (c_1^d_1, c_2^d_2,..., c_k^d_k)조합의 계수를 읽어 냄으로써 counting

-Examples, Burnside, Weighted Burnside, Polya 구분하기 위한 예제모음

-회전하여 같으면 같은 것으로 간주, 정사각형에 4명의 사람 배열, 서로 다른 배열의 개수?

->Burnside, G=C_4, X={일렬로 4명을 배열한 모든 경우}, |X|=24, the number of orbits이 답,

1/4*4!=3!

-회전하여 같으면 같은 것으로 간주, 정사각형에 각 꼭짓점에 black, white 둘중 1개 색칠, 서로 다른 배열의 개수?

->Burnside, G=C_4, X={일렬로 4개의 점을 색칠한 모든 경우}, |X|=16, the number of orbits이 답,

1/4*(16+2+4+2)=6

-회전하여 같으면 같은 것으로 간주, 정사각형에 각 꼭짓점에 R,G,B 셋중 1개 색칠, 서로 다른 배열의 개수?

->Burnside, G=C_4, X={일렬로 4개의 점을 색칠한 모든 경우}, |X|=3^4=81, the number of orbits이 답,

1/4*(3^4 + 3 + 3^2 + 3)=24

-회전하여 같으면 같은 것으로 간주, 정사각형에 각 꼭짓점에 R,G,B 셋중 1개 색칠, (R,G,B)=(2,1,1)개 사용된 서로 다른 배열의 개수?

->Polya, G=C_4, X={1,2,3,4}, Z(G,X)구한 다음 a_i에 (r^i + g^i + b^i)대입하여 r^2g^1b^1의 계수구하면 됨

-회전 및 대칭하여 같으면 같은 것으로 간주, 정사각형에 각 꼭짓점에 R,G,B 셋중 1개 색칠, (R,G,B)=(2,1,1)개 사용된 서로 다른 배열의 개수?

->Polya, G=D_8, X={1,2,3,4}, Z(G,X)구한 다음 a_i에 (r^i + g^i + b^i)대입하여 r^2g^1b^1의 계수구하면 됨

-About gf

-Motive:

sequence자체나 recursive formula는 양이 너무 많다. 따라서 대응되는 gf의 explicit는 간단하고 정보를 다 담고 있다.

-Basic

-From {a_n} to gf

-recursive formula 양변에 적당히 x^sth을 곱하고 더하고 하면 얻을 수 있다.

-From gf to {a_n}

-partial fraction

-About prod of gf

-A(x):gf_{a_n}, B(x):gf_{b_n}, C(x):gf_{c_n}, where c_n:=the cauchy prod of a_n and b_n일 때

A(x)B(x)=C(x)

-A(x):gf_{a_n}, B(x):gf_{b_n}, C(x):gf_{c_n}, D(x):gf_{d_n}, where d_n:=...일 때

A(x)B(x)C(x)=D(x)

-About composition of gf

Case 1(link)

a_n:=# of ways to build a certain structure on a set E, |E|=n, a_0 = 0

h_n:=# of ways to split [n] into an unspecified number of disjoint nonempty intervals, then build a structure of the given kind on each of these intervals, h_0 = 1

Then A(x):gf_{a_n}, H(x):gf_{h_n}일 때 H(x)=1/(1-A(x))

Case 2(link)

a_n:=# of ways to build a certain structure on a set E, |E|=n, a_0 = 0

b_n:=# of ways to build a second structure on a set J, |J|=n, b_0 = 1

g_n:=# of ways to split [n] into an unspecified number of nonempty intervals, then build a structure of the given kind on each of these intervals, and then build a structure of the second kind on the set of the intervals, h_0 = 1

Then G(x) = B(A(x))

-분할 관련

-gf_#ptt(n)(x) = sum over n>=0 #ptt(n)x^n 

= prod over n>=1 1/(1-x^n) = (ef(x))^(-1)(link)(link, 수렴성관련)

=1+ sum over k>=1 q^k / (1-q)(1-q^2)...(1-q^k)

=1+ sum over k>=1 q^k / (1-q^k)(1-q^(k+1))...(link)

-ef(q) = gf_(#ptt(n) with distinct even parts - #ptt(n) with distinct odd parts)(q)

-(PTT, <_lexi):total order

-(PTT, <_d):partial order

-{ptt s.t. ptt=ptt(n)}

bijective {conjugacy classes of S_[n]}

bijective {irreducible characters of S_[n]}

bijective {Ferrar diagram, boxes 개수 = n}

-gf_#ptt(n)_o = gf_#ptt(n)_d (link)

-ptt(n)_o = ptt(n)_d

-Q-analogue관련

-DF(m,n)_q관련

-analytic on unit disk on C

-(Pentagonal Number Theorem)DF(q,inf)_q = ef(q) = sum over k in [-inf,inf] (-1)^k * q^P(5,k)(link)

-Polygonal Number관련

-P(5,n)=(3n-1)*n*1/2

-

-Tableaux관련

-(Hook Length Formula)shape을 보고 가능한 ST를 count하는 formula, link참조(link)

-SST:associative monoid

-x _r> sst is a sst

-(Inverse Process of Row bumping)

:added box의 위치와 그 숫자(y)를 안다면, inverse가능(원래 sst와 무엇을 insert했는지 알 수 있음)

-y의 row 바로 윗 row에서 y보다 작은 놈들 중 가장 오른쪽에 있는 놈을 y로 바꾸고 원래 y'을 그 윗 row에 apply

(Inverse Process of Column bumping도 가능)

-(Robinson-Schested Correspondence, RS-correspondence)

:Row or Column bumping이 inversible이므로 다음의 Bijection을 얻는다. {all words of length n} bijective SST_(ptt(n)) x ST_(ptt(n)) for any ptt(n) in PTT(n)

-{all words of length n on [n]} bijective ST_(ptt(n)) x ST_(ptt(n)) for any ptt(n) in PTT(n)

-(Row Bumping Lemma)for a sst, a _r> sst with bumping route R_a by a and new box A, b _r> (a _r> sst) with bumping route R_b by b and new box B

:if a<=b, then R_b is strictly right of R_a 이고 B:strictly right of A 이고 B:weakly above A

:if a>b, then R_b is weakly left of R_a 이고 B:weakly left of A 이고 B:strictly below A

(한 경우만 외우면 나머지는 완전 반대임)

-sliding of skew sst is also skew sst

-계속하면 sst를 얻음

-(Inverse Process of Sliding)

:sliding의 result와 removed된 empty box의 마지막 위치를 안다면 inverse가능

-empty box의 left, above를 비교하여 큰것과 위치이동, left와 above가 같다면 above를 이동

-(Unique of Rect(skew sst))for any skew sst, any choice of series of inside corners, the result sst is same.

-for any sst, positive integer x, word_r(x _r> sst) is knuth equivalent to word_r(sst)x

-word_r(sst1*sst2 using def1) is knuth equivalent to word_r(sst1)word_r(sst2)

-sliding해도 word는 knuth equivalent

-Rect(skew sst) is the unique sst s.t. word_r(sst) is knuth equivalent to word_r(skew sst)

-Every word is knuth equivalent to the word of a unique sst

-word=x1x2x3...xk인 경우 xk _r> (...(x2 _r> x1)...)인 sst의 word와 knuth equivalent, 이 sst를 sst(word)라 쓰자.

(construction of sst는 위의 방법대로 하면되는데 uniqueness is not obvious)

-If word_r(skew sst1) is knuth equivalent to word_r(skew sst2), then Rect(skew sst1) = Rect(skew sst2)

-About TbR_[m]

-Z-Md, associative ring, not commutative

-TbR_[m] riso to Z[x1,x2,...xm] and as Z-Md, using f:TbR_[m]->Z[x1,x2,...,xm] f(sst)=x^sst

-K_(shape, weight)를 해석하는 방법

-정의대로, shape, weight를 가지는 sst 개수

-shape을 weight=(a1,a2,...,al), l개로 partition하는 방법의 수, 

-(Stirling's Formula)

:lim n->inf n!/{(sqrt(2*pi*n) * n^n * e^(-n)}=1, 즉 n!을 근사할 수 있음

-proof(using PD(1) and chf)(link1)(link2)