경로의 수 구하기

행렬의 곱은 경로의 수 구하기에 사용되기도 합니다.
예를 들어 보겠습니다. 아래와 같은 그래프가 있습니다.
1에서 출발하여 변을 3번 지나 3에 도착하는 경로의 수는 몇가지 일까요?
직접 해보시면 1-3-1-3, 1-2-1-3, 1-2-4-3 세 가지 경우가 있습니다.

이번에는 행렬을 이용하여 풀어보겠습니다.
행렬을 정의할 때 i행 j열의 성분 를 다음과 같이 정의하겠습니다.

= i번에서 j번까지 가는 길이가 1인 경로의 수
이 경우, 행렬이 다음과 같이 만들어집니다.

그럼 이 행렬 A를 제곱하면 어떤 행렬이 될까요?
A^2의 i행 j열 성분을 bij라고 해보겠습니다.
행렬곱을 이용하여 b23을 구해보면,
입니다.
그 의미를 생각해보겠습니다.
a21 a13은 2에서 출발하여 1을 갔다가 3에 도착하는 경로의 수.
a22 a23은 2에서 출발하여 2를 갔다가 3에 도착하는 경로의 수
..
..
a25 a53은 2에서 출발하여 5를 갔다가 3에 도착하는 경로의 수 입니다.
즉, b23은 2에서 출발하여 변을 2번 지나 3에 도착하는 경로의 수입니다.

우리가 원하는 1에서 출발하여 변을 3번지나 3에 도착하는 경로의 수는
행렬 A를 세제곱 하여 1행 3열의 성분을 구하면 답이 되겠습니다!

가위바위보는 몇 번 만에 끝날까

원래 문제는 8명이었으나 간단하게 4명으로 소개하겠습니다..ㅋㅋㅋ

4명이서 가위바위보를 한 번 하면, 네 가지 경로가 가능합니다.
4명->4명(비기는 경우)/ 4명->3명/ 4명 -> 2명 / 4명 -> 1명

또, 만약에 4명이서 한 판 했는데 3명이 남았다면, 다시
3명->3명(비기는 경우)/ 3명->2명/ 3명->1명
이렇게 세 가지 경로가 가능합니다.

그리고 n명에서 가위바위보를 하여 m(<n)명이 남을 확률은
으로 쓸 수 있습니다.
(모두 비길 확률(m=n)은 1에서 나머지를 빼서 구해야 합니다.)

그럼 행렬 X의 성분을 다음과 같이 정의하겠습니다.
** xij=i명이 가위바위보를 한 번해서 j명이 남을 확률**

또한, 4명이 가위바위보를 시작할 때 1번 만에 끝날 확률은
X의 4행 1열 성분입니다.
4명이 가위바위보를 시작할 때 2번 만에 끝날 확률은
X^2의 4행 1열 성분입니다.
4명이 가위바위보를 시작할 때 N번 만에 끝날 확률은
X^N의 4행 1열 성분이 되겠습니다.