과연 이 패턴은 몇가지 경우의 수가 있을까?
규칙은 다음과 같다.
1. 최소한 4개의 점을 이어야 한다. 즉, 1개, 2개, 3개로 이루어진 패턴은 만들 수 없다.
2. 한번 지나간 점은 다시 지나갈 수 없다. 단, “꼭지점”으로 기능하지 않으면 스쳐지나갈 수는 있다.
3. 고르는 순서가 다르면 서로 구분되는 경우이다.
4개의 점을 가진 패턴을 생각해 보면, 우선 최초에 9개의 점 중에서 1개를 골라야 한다. 그 다음에는 8개의 점 중에 골라야 하고, 마찬가지로 7개중에 1개, 6개중의 1개를 고르면 된다. 이 모든 경우의 수는 9*8*7*6가지 경우인데, 계산해보면 3024가지 경우이다.
5개의 점은 여기에 5개중의 1개를 더 골라야 하므로 15120가지 경우가 가능하다.
마찬가지로 6개의 점은 4개중의 1개를 고를 수 있다. 이것은 60480가지 경우이다.
7개의 점을 잇는 경우는 181440가지 경우, 8개의 점을 잇는 경우는 362880가지 경우가 있다.
9개의 점을 잇는 경우는 8개의 점을 고른 상황에서 선택할 점이 1개밖에 없으므로 8개의 점인 경우와 마찬가지로 362880가지 경우가 있다. 물론 8개의 점을 고르느냐 9개의 점을 고르느냐의 차이가 있기 때문에 두가지 종류의 경우는 경우의 수는 같더라도 서로 다른 경우로 처리된다.
따라서 전체적으로 3024+15120+60480+181440+362880+362880=985824가지 경우가 존재한다.
물론 이 경우의 수는 4자리수 비밀번호인 10000가지보다 98배 이상 많은 경우의 수이다.
수식으로 멋있게 쓰면, N개의 점 중에 k개 이상의 점을 사용하여 패턴을 만드는 경우의 수 $F_N(k)$는
$F_N(k)=\Sum_{i=k}^N \frac{N!}{(N-i)!}$
이 된다.
유명한 보너스 문제. 선분 4개만 사용해서 9개의 점을 모두 잇는 방법은?
더보기
댓글 남기기