같은 것이 있는 순열

모두 다르다고 가정한 뒤 중복 지우기

A,A,B를 A₁,A₂,B로 임시 구분하면 3!=6가지입니다. 하지만 A₁A₂B와 A₂A₁B는 같은 AAB입니다. 각 결과가 2!번씩 세어졌으므로 3!÷2!=3가지가 됩니다.

격자 위 최단 경로

오른쪽으로 3번, 위로 2번 이동하는 최단 경로는 R,R,R,U,U의 배열과 일대일 대응합니다. 따라서 5!/(3!2!)=C(5,2)입니다. 한 점을 반드시 지나면 그 점 앞과 뒤의 경로 수를 곱합니다.

이웃 조건과 묶기

두 B가 붙어 있어야 하면 BB를 하나의 덩어리로 봅니다. 단, 나머지 A가 반복되면 A의 반복도 나누어야 합니다. 붙지 않는 경우는 전체에서 붙는 경우를 빼거나 다른 문자 사이의 틈을 이용할 수 있습니다.

직접 해 보기

같은 것이 있는 배열 실험

A, B, C의 개수를 바꾸고 서로 다른 배열을 직접 확인합니다.

원본 학습서에서 크게 열기 →

해 볼 것 · 같은 문자끼리 번호를 붙이면 몇 번씩 중복해서 세게 될까요? 분모의 팩토리얼과 연결해 설명하세요.

풀이 예제

같이 풀어 보기 1BANANA 배열

BANANA의 6개 문자를 모두 나열하는 방법은?

▸ 풀이 보기

1. A가 3개, N이 2개, B가 1개입니다.
2. 6!에서 A의 내부 순서 3!, N의 내부 순서 2!를 나눕니다.
3. 720÷(6×2)=60입니다.

답: 60가지

같이 풀어 보기 2최단 경로

(0,0)에서 (3,2)까지 오른쪽 또는 위쪽으로만 가는 방법은?

▸ 풀이 보기

1. 오른쪽 3번, 위 2번으로 총 5번 이동합니다.
2. 위로 가는 2개의 위치를 고르면 경로가 정해집니다.
3. C(5,2)=10입니다.

답: 10가지

같이 풀어 보기 3경유점

(0,0)에서 (4,3)까지 최단 경로로 가되 (2,1)을 지나는 방법은?

▸ 풀이 보기

1. (2,1)까지는 R 2번과 U 1번이므로 C(3,1)=3입니다.
2. 그 이후는 R 2번과 U 2번이므로 C(4,2)=6입니다.
3. 두 부분을 이어 붙여 3×6=18입니다.

답: 18가지

같이 풀어 보기 4붙지 않는 B

A,A,A,B,B를 나열하되 B끼리 붙지 않는 방법은?

▸ 풀이 보기

1. 전체는 5!/(3!2!)=10입니다.
2. BB가 붙으면 BB와 A,A,A를 배열하므로 4!/3!=4입니다.
3. 붙지 않는 경우는 10−4=6입니다.

답: 6가지

한 장 요약

1. 같은 것이 있는 순열 — n! / (p!q!⋯), p+q+⋯=n
2. 격자 최단 경로 — C(a+b,a)
3. 경유점 통과 — 앞부분 경로 수 × 뒷부분 경로 수