며칠 전에 LeetCode 연습문제 441. Arranging Coins를 풀면서 1부터 n까지의 합을 구하는 공식을 다시 보았다. 학교에서 1부터 100까지 더하는 문제로 한 번쯤 배웠던, 가우스가 어릴 때 떠올렸다고 알려진 그 공식이다.

1부터 n까지의 합은 n(n+1)/2로 구할 수 있다. 이 공식의 유도 과정은 인터넷에 많이 있으니 여기서는 따로 정리하지 않겠다. 그런데 이 식을 보고 어디선가 비슷한 형태를 본 것 같다는 생각이 들었다. 그러다 문득 n(n-1)/2라는 공식을 배운 기억이 떠올라 찾아보았다.

$\frac{n(n-1)}{2}$ n개 중에서 가능한 조합

검색해 보니 배열의 가능한 부분 구간 개수나, n개의 원소로 만들 수 있는 서로 다른 pair의 개수를 설명할 때 등장하는 공식이었다. 관련 설명은 이 링크에서도 볼 수 있다.

대표적인 예가 악수 문제다. n명이 서로 한 번씩만 악수한다고 생각해 보자.

한 사람이 악수할 수 있는 상대는 자기 자신을 제외한 n - 1명이다. 그렇다면 전체 악수 횟수는 n(n-1)일까? 아니다. 이 값에는 중복이 들어 있다. 예를 들어 AB와 BA, AC와 CA는 같은 악수를 두 번 센 것이다.

그래서 중복을 제거하려면 2로 나누어야 한다. 따라서 서로 다른 두 사람을 고르는 경우의 수는 n(n-1)/2가 된다.

Permutation

조합 문제를 공부하다 보니 순열도 다시 정리할 필요가 있었다. 예전에 문제를 풀면서 순열을 배운 적은 있지만, 지금은 많이 잊어버렸다. 순열과 조합은 비슷해 보여서 가끔 헷갈리기 때문에 다시 정리해 본다.

$n^r$ n개중에서 r개를 중복가능, 순서를 고려해서 고른다.

A, B, C 세 개가 있고, 이 중에서 중복을 허용하면서 순서를 고려해 3개를 고른다고 하자. 그러면 다음과 같은 경우가 가능하다.

AAA, AAB, AAC ABA, ABB, ABC ACA, ACB, ACC BAA, BAB, BAC BBA, BBB, BBC BCA, BCB, BCC CAA, CAB, CAC CBA, CBB, CBC CCA, CCB, CCC

$\frac{n!}{(n-r)!}$ n개 중에서 r개를 중복불가, 순서를 고려해서 고른다.

이번에는 중복을 허용하지 않고 순서를 고려해 고르는 경우다. 중복이 불가능하므로 하나를 고를 때마다 다음 선택지의 개수가 1씩 줄어든다.

예를 들어 16개의 당구공 중에서 순서를 고려해 3개를 고른다면, 첫 번째는 16개 중에서 고르고, 두 번째는 남은 15개 중에서 고르고, 세 번째는 남은 14개 중에서 고른다. 따라서 가능한 순열의 수는 16 x 15 x 14 = 3360이다.

이 16 x 15 x 14를 일반화하기 위해 팩토리얼을 사용한다.

$\frac{16 * 15 * 14 * 13 * 12 * 11..3 * 2 * 1}{13 * 12 * 11 ... 3 * 2 * 1}$ => $\frac{n!}{(n-r)!}$

Combination

$\frac{n!}{r!(n-r)!}$ 조합, 순열에서 순서를 제외한다

조합은 순서를 고려하지 않는다. ABC, CBA, BCA는 모두 A, B, C 세 원소로 이루어진 같은 선택이다. 그래서 이 경우들을 하나의 ABC 조합으로 본다.

앞에서 $\frac{n!}{(n-r)!}$로 중복 없이 순서를 고려하는 순열의 수를 구했다. 여기에서 순서만 제거하면 조합이 된다.

다시 당구공 예제로 돌아가 보자. 16개의 공 중에서 순서를 고려해 3개를 고르는 경우는 16 x 15 x 14 = 3360가지였다. 그런데 공 3개를 고른 뒤의 배치 순서는 3!가지다. 조합에서는 이 배치 순서를 모두 같은 선택으로 보기 때문에 3!로 나누어야 한다.

따라서 3360 / 3! = 560이 되고, 이것이 16개 중에서 3개를 고르는 조합의 수다.