26. 여러 항 사이의 점화 관계

[eqn: sum_k=1^11 a_k = a_1 + a_2 + (a_3 +a_4 +a_5 )][eqn: +(a_6 +a_7 +a_8 )]

[eqn: +(a_9 +a_10 +a_11 ) = 1+2+6+6+6= 21]

[정답] ③

27. 최적화와 알고리즘

주어진 작업의 순서 관계를 그림으로 나타내면 우와 같다. (괄호 안의 숫자는 작업 시간이다.)

위 그림에서 가능한 경로를 모두 생각하여 최소 작업시간의 경로를 찾으면 [eqn: A ->C ->D ->F ->G]이고, 그 때 걸리는 시간은 [eqn: 2+5+3+4+3 = 17](일)이다.

[정답] ⑤

28. 그래프

{[eqn: X,Y,Z]}와 {[eqn: A,B,C,D]} 간에는 모든 경우의 변이 그려져 있는 상태이므로, 추가하는 변은 각 집합의 원소끼리 연결한 변이 될 것이다. 이 때 필요한 색의 수가 4가 되도록 하기 위해서는 각 집합에서 한 변씩만 추가하면 된다. 한 변을 위해서는 서로 다른 두 꼭지점이 필요하므로, 가능한 그래프의 개수는 [eqn: `_3 C_2 times `_4 C_2 = 18]개이다.

[정답] ④

29. 포함 배제의 원리

문자 [eqn: A,B,C,D,E,F]를 모두 사용해 만들 수 있는 모든 6자리의 문자열의 집합을 전체집합 [eqn: U]라고 하고, (가)를 만족하지 않는 집합을 [eqn: A], (나)를 만족하지 않는 집합을 [eqn: B], (다)를 만족하지 않는 집합을 [eqn: C]라고 하면, 주어진 조건을 모두 만족하는 경우의 수는

[eqn: n(A ^{C} SMALLINTER B ^{C} SMALLINTER C ^{C} )][eqn: =n(U)-n(A)+n(B)+n(C)]

[eqn: +n(A cap B) +n(B capC)+n(C capA) - n(A cap B cap \C )]

[eqn: =6! - 3 times 5! + 3 times 4! - 0][eqn: = 432]

[정답] ②

30. 생성수형도

주어진 생성수형도에서 경우를 잘 나누어 총 개수를 세어야 하는데, 삼각형 [eqn: ABC]의 세 변 중 몇 개의 변이 제거되는지 경우를 나누어 문제를 풀자.

(1) [eqn: ABC] 모두 제거될 때, 그 자체로 생성수형도가 된다. [eqn: therefore 1] 가지.

(2) [eqn: ABC] 중 두 변이 제거될 때, 나머지 한 변이 [eqn: D]와 단 한 경로로만 이어져야 하는데, 그 변에서 [eqn: D]로 가는 변은 총 4개가 있으므로 그 변 중 하나를 지워야 한다.

[eqn: therefore][eqn: `_3 C_1 times ``_4 C_1 = 12] 가지.

(3) [eqn: ABC] 중 한 변이 제거될 때, 회로를 없애기 위해 [eqn: D]와 직접 연결된 한 변을 지워야 한다. 이 때 어떤 변을 지우더라도 회로가 아직도 남아있고, 남은 7개의 변 중 지우지 못하는 변이 3개 존재하므로 나머지 4개 중 하나를 지워 회로를 제거해야 한다. 그렇게 해서 구한 결과는 생성수형도이다. 따라서

[eqn: therefore `_3 C_1 times `_3 C_1 times `_ 4 C_1][eqn: = 36] 가지.

(4) [eqn: ABC] 중 어떤 변도 제거되지 않으면 회로가 생겨서 수형도가 아니다. [eqn: therefore] 0 가지.

따라서 구하는 생성수형도의 총 개수는 [eqn: 1+12 +36 = 49]가지이다.

[정답] 49