순열의 기본과 직순열

저는 수학 중에서 분야로 따지면 기하학이 제일 좋습니다.

잘한다는 의미는 아니고, 그냥 좋아하는 분야가 기하학이라는 말입니다.

제일 못하는 분야는...확률 부분입니다.

사실 개수를 잘 못 세서 엉뚱하게 틀리는 경우가 많더라고요.

분명히 공식은 잘 썼는데 공식을 적용하는 방법이 틀렸죠. ^^;;

그래서 오늘은 순열에 대해 이야기해보고자 합니다.

그런데 순열 다 하는 것은 힘드니 직순열만요..^^

먼저, 순열의 정의가 무엇인지부터 살펴봅시다.

보통 수학적으로 정의하자면...

"서로 다른 n개에서 r(0＜r≤n)개를 선택하여 일렬로 나열하는 것을

n개에서 r개를 택하는 순열이라고 한다."

...라고 정의되어있습니다.

간단히 말하면 그냥 뽑아서 순서 매기는 것, 혹은 역할 주는 것입니다.

예를 들어볼까요.

저희 반이 31명인데, 여기서 회장, 부회장, 멀티미디어 도우미, 윤독도서 도우미 등

4명을 뽑아야 한다고 합시다.

그러면 31명 중 4명을 뽑아서 각각 하나씩 역할을 주면 되죠?

이런 경우를 순열을 이용해서 풀어주면 됩니다.

n개 중 r개를 택하는 순열은 nPr이라고 표기하는데요,

이 때 공식은 n(n-1)(n-2)....(n-r+1)이라고 합니다.

더 세련되게 표시하는 방법은 n!/(n-r)! 이죠.

!는 팩토리얼(factorial)이라고 하는데 n!이면 1부터 n까지 모두 곱하라는 기호입니다.

단, 주의해야 할 점은 0!은 1로 정의하게 됩니다.

왜냐하면 n!=(n-1)!*n이므로 1!=0!*1이 됩니다.

그래서 1=0!이 되지요.

물론 n이 1이 아니라고 해도 됩니다만 0!이 1이 될 경우

다양한 계산에서 적용할 수 있어서 그렇게 정의했다고 하네요.

그런데 어떻게 해서 이런 공식이 나왔는가 살펴보면

위에서 제가 든 예시에서 먼저 회장을 뽑는다고 합시다.

그러면 31명 중에서 선택할 수 있죠.

그런데 회장을 뽑은 후에 부회장 뽑으려고 하면 한 아이에게 둘 다 시킬 수 없으니

30명 중에서 선택할 수 있습니다.

마찬가지로 멀티 도우미는 회장, 부회장을 제외한 29명 중,

도서도우미는 28명 중에서 선택하게 되므로 31부터 거꾸로 28까지 곱하면 됩니다.

그러면 31P4=31*30*29*28이고 이것은 (31-0)(31-1)(31-2)(31-3)이 됩니다.

일반적인 식으로 바꿔보면 n(n-1)(n-2)...(n-r+1)이 되고

이것은 1에서 n까지 곱한 후 1에서 n-r까지 곱한 식으로 나누면 되기 때문에

n!/(n-r)!이라고 표현할 수 있는 것입니다.

우아...뭔가 복잡해 보이나요?

뭐, 우리가 예전부터 했던 거잖아요.

죽어라고 나뭇가지 그림 그리는 것....기억하시나요?

제가 예시로 A, B, C,  중 3명을 택해서 줄세우는 방법을 그려보겠습니다.

그러면 이해가 가실 겁니다.

1번 자리에는 A, B, C, D 넷 중에 하나고

2번 자리는 1번 자리 빼고 3개고

3번 자리는 1, 2번 자리 빼고 2개씩 가능하니

4*3*2라고, 간단히 24라고 노가다 할 필요 없이 계산이 됩니다.

이제 공식이 이해 가시지요??

어쨌든, 이 순열에서 우리가 약속한 것이 있습니다.

nPn=n!, nP0=1

약속했다기 보다 그냥 상식적으로 생각해보면 됩니다.

n명 중 n명을 뽑아 줄세워? 그러면 n부터 1까지 곱하면 되잖아요.

n명 중 아무도 안 뽑아 줄세워? 그러면 아무것도 없는 거 1가지밖에 안 되잖아요.

그래서 이렇게 약속을 한 것입니다.

지금까지 순열의 기본에 대해서 알아보았는데요,

이렇게 그냥 단순히 일렬로 나열하는 것을 '직순열'이라고 합니다.

줄세우세요, 반장과 부반장을 뽑으세요, 문자를 나열하세요,

숫자카드로 만들 수 있는 자연수는 몇개일까요, 사전식으로 배열하세요 등의 키워드는

이런 직순열 문제라고 보시면 됩니다.

직순열 문제는 그냥 순열의 정의만 이용해서 풀리는 경우도 있지만 아닌 경우도 있습니다.

가장 대표적인 예가 '누구누구를 이웃하게 하세요'라는 문제입니다.

이럴 경우는 이웃하는 사람들을 한 사람이라고 생각하고 푼 후

그 사람들끼리 자리를 바꾸는 경우를 곱해줘서 계산합니다.

예를 들어, 여학생 3명과 남학생 4명을 일렬로 세우는데

여학생 3명을 이웃하게 세우라고 했다고 칩시다.

그러면 '여학생 3명=여학생 세트로 1명'이라고 먼저 생각합니다.

그러면 총 5명이 있는 셈이라서 5P5를 먼저 계산하고

여학생 3명의 순서가 바뀌는 경우를 생각해보면

3명 내에서 그 3명을 줄세우는 것이니까 3P3입니다.

그래서 5!*3!=120*6=720이 되겠군요.

또한, 이웃하지 않게 세우라는 경우도 있는데

그것은 전체에서 이웃하는 경우를 빼서 구하는 것이 가장 쉽습니다.

아니면 문자 배열할 때 조건이 있는 경우가 있어요.

누가 맨 앞에, 누가 맨 뒤에, 뭐 그러면 조건에 맞는 것들을 먼저 배열하고

나머지를 배열하는 순열만 계산해주시면 됩니다.

그런데 이런 조건도 나옵니다.

a와 b사이 2개의 문자가 있어야 할 것!

그러면 (a○○b)를 한 묶음으로 보고 계산한 후

동그라미 안에 들어갈 수 있는 경우를 곱해 준 후 a와 b순서 바뀐 경우도 생각해야 하니

곱하기 2를 해주시면 됩니다.

또 예를 들어볼까요.

abcdefgh에서 a와 b사이 2개의 문자가 있게 일렬로 나열하시오...

그러면 (a○○b)와 나머지 문자 4개해서 5개를 일렬로 나열하는 경우: 5!

동그라미 안에 들어갈 수 있는 경우: (8-2)P2=6P2=30

그러면 5!*30*2=7200

이런 조건 말고도 그나마 더 쉬운 조건은 적어도 ____인 순열입니다.

왜냐하면 전체에서 ____이지 않은 경우를 빼면 되거든요.

적어도라는 말이 가지는 장점이죠.^^

이 외에도 다양한 유형의 직순열이 있는데

직순열을 잘 풀려면 문제 조건을 잘 확인한 후에

어떤 것을 하나로 보아서 풀어야 할까?

전체에서 빼는 형식이 쉬울까, 그냥 푸는 것이 쉬울까?

몇 가지로 분류를 해서 푸는 것이 더 쉬울까?

...등의 질문을 던져보면 잘 풀 수 있을겁니다.

음...좀 글이 길게 되었네요.

하긴, 말로 하지 않고 글로 하려면 그림이 많아야 좋은데

포토샵을 잘 못하는지라....-_-;;