| [ QuizWit ] in KIDS 글 쓴 이(By): khjeong (mathwhiz) 날 짜 (Date): 1997년12월13일(토) 16시20분56초 ROK 제 목(Title): Re: # 3x3 grid spanning tree 이것도 우선 쉬운 것부터. N=3인 경우만 해야지. o--o--o | | | o--o--o | | | o--o--o 꼴의 grid를 구성하는 12 개의 선분 중, 4개를 제거하여 tree가 되는 것의 개수를 구하는 경우군요. o--o--o | | o o o | | | o--o--o 꼴에서 바깥변 하나를 제거한 것 ==> 4x8=32가지 o--o--o | | o o--o | | | o--o--o 꼴에서 바깥변 두 개를 제거한 경우 ==> 4x6x2=48가지 o--o--o | | | o o o | | | o--o--o 꼴에서 바깥변 두 개를 제거한 경우 ==> 2x4x4=32가지 o--o--o | | o--o--o | | | o--o--o 꼴에서 바깥변 세 개를 제거한 경우 ==> 4x4x2x2=64가지 o--o--o | | | o--o--o | | | o--o--o 의 바깥변 네 개를 제거한 경우 ==> 2x2x2x2=16가지 따라서 192=32+48+32+64+16가지가 N=3인 경우에는 답. -- I owe you the sunlight in the morning. |