확률·통계중복순열#240

중복순열

Permutations with Repetition

중복순열은 서로 다른 n개에서 중복을 허락하여 r개를 택해 일렬로 나열하는 순열이고, 그 수는 n의 r제곱이다. 자리마다 선택 수를 곱하는 이유, 순열과의 차이, 누가 고르는지로 밑과 지수를 정하는 법, 첫 자리·적어도 한 번·길이별 합·재고 제한 조건을 다룬다.

읽는 시간
약 8분
선수 개념
순열

직관 — 버튼을 누른 뒤에도 버튼은 남는다

직관

문자 버튼을 누르면 기록 칸에 그 문자가 남는 장치를 떠올려 보자. 한 번 누른 버튼도 다음 칸에서 다시 누를 수 있다. 같은 버튼들을 눌렀어도 기록 순서가 바뀌면 다른 기록이다.

버튼의 종류는 고를 대상, 기록 칸은 순서가 있는 자리다. 이 글의 문자 장치와 숫자 코드는 계산을 위해 만든 가상 예다. 순열에서 한 번 고른 대상을 제외했다면, 이번에는 다음 자리에서도 그 대상을 고를 수 있다. 반복을 허용하는 비밀번호, 숫자 만들기, 여러 사람이 각자 하나씩 고르는 결과를 셀 때 이 방법을 쓴다.

중복순열은 반복을 허용하는 순서 있는 선택이다

중복순열은 서로 다른 nn개에서 중복을 허락하여 rr개를 택해 일렬로 나열하는 순열이다. 교과서는 이를 'nn개에서 rr개를 택하는 중복순열'이라 하고, 그 수를 nΠr{}_n\Pi_r로 쓴다. 이 글에서는 nn개를 '고를 수 있는 nn종류'로 읽는다. 같은 종류를 몇 번 골랐는지는 미리 정하지 않는다.

예를 들어 A, B에서 세 자리를 채우면 AAA도, ABA도 가능하고 AAB와 ABA는 다르다. nn과 rr은 양의 정수로 시작하자. 중복순열의 수는 다음과 같다.

nΠr=n×n×⋯×n⏟r개=nr.(1){}_n\Pi_r=\underbrace{n\times n\times\cdots\times n}_{r\text{개}}=n^r. \tag{1}
정의
기호이름원어뜻
nn종류의 수number of types각 자리에서 고를 수 있는 서로 다른 종류의 수
rr자리의 수number of positions순서대로 채울 자리의 수
nΠr{}_n\Pi_r중복순열의 수permutations with repetition반복을 허용한 길이 rr의 배열 수
nPr{}_nP_r순열의 수permutations without repetition반복 없이 고르는 배열 수, 0≤r≤n0\le r\le n

Π\Pi는 영어 P에 해당하는 그리스 문자 대문자 파이다. 곱을 뜻하는 product를 떠올리면 기억하기 쉽지만, 순열의 nPr{}_nP_r와는 다른 기호다.

중복순열의 수는 왜 거듭제곱일까?

앞자리를 어떻게 채웠든 다음 자리의 선택지가 똑같이 nn개이기 때문이다. 각 완성 배열은 첫 자리부터 마지막 자리까지 고르는 경로 하나와 정확히 대응한다. 경로가 겹쳐 같은 배열을 두 번 세지 않으며, 가능한 배열은 모두 그 경로로 만들어진다. 따라서 곱의 법칙을 rr자리에 차례로 적용하면 식 (1)을 얻는다.

A, B의 세 자리 기록은 첫 칸 2가지, 다음 칸 2가지, 마지막 칸 2가지다.

2Π3=2×2×2=8.(2){}_2\Pi_3=2\times2\times2=8. \tag{2}
A와 B를 세 번 고르는 수형도. 뿌리에서 끝까지의 경로마다 오른쪽의 서로 다른 기록 하나가 생기며, 모든 단계에서 두 갈래가 유지된다.
그림 1 A와 B를 세 번 고르는 수형도. 뿌리에서 끝까지의 경로마다 오른쪽의 서로 다른 기록 하나가 생기며, 모든 단계에서 두 갈래가 유지된다. figures/repetition_tree.py

그림 1은 식 (2)의 여덟 기록을 빠짐없이 보여 준다. 이것은 작은 예의 확인이고, 임의의 n,rn,r에 대한 근거는 앞 문단의 선택 경로와 배열의 대응이다. 세 문자 A, B, C로 네 자리를 채우면 같은 이유로 34=3×3×3×3=813^4=3\times3\times3\times3=81가지다.

중복순열과 순열은 고른 것을 다시 쓰는지에서 갈린다

순열은 고른 대상을 후보에서 빼고 다음 자리를 채우지만, 중복순열은 후보를 그대로 둔다. 그래서 A, B, C로 두 자리를 채우면 중복순열은 9가지, 순열은 6가지다.

3Π2=3×3=9,3P2=3×2=6.(3){}_3\Pi_2=3\times3=9,\qquad {}_3P_2=3\times2=6. \tag{3}
A, B, C로 만든 두 자리 기록의 표. 행은 첫째 자리, 열은 둘째 자리이며 아홉 칸이 모두 중복순열이다. 같은 문자를 다시 쓴 대각선의 세 칸을 빼면 순열의 여섯 칸이 남는다.
그림 2 A, B, C로 만든 두 자리 기록의 표. 행은 첫째 자리, 열은 둘째 자리이며 아홉 칸이 모두 중복순열이다. 같은 문자를 다시 쓴 대각선의 세 칸을 빼면 순열의 여섯 칸이 남는다. figures/pair_grid.py

그림 2에서 두 수의 차이 3은 대각선의 AA, BB, CC다. 첫 자리의 선택은 둘 다 3가지이고, 둘째 자리에서 중복순열만 3가지를 유지한다. 자리가 늘수록 중복순열은 매번 nn을 곱하므로 차이가 커진다. A, B, C로 세 자리를 채우면 중복순열은 33=273^3=27가지, 순열은 3×2×1=63\times2\times1=6가지다.

중복순열에서는 종류보다 많이 골라도 되나요?

중복순열은 반복을 허용하므로 종류 수보다 많은 자리를 채울 수 있다. A, B 두 종류로 세 자리를 채우는 식 (2)가 그 예로 8가지다. 반복을 금지한 순열에서는 두 종류로 세 자리를 채울 수 없어 0가지다.

중복순열에서 밑과 지수는 누가 고르는지로 정한다

선택을 하는 쪽의 수가 지수이고, 각자 고를 수 있는 선택지의 수가 밑이다. 학생 4명이 동아리 A, B, C 중 하나씩 고른다면 학생 한 명이 기록 칸 하나다.

3×3×3×3=34=81.(4)3\times3\times3\times3=3^4=81. \tag{4}
학생 1, 2, 3, 4가 동아리 A, B, C 중 하나씩 고르는 대응. 학생마다 나가는 화살표 후보가 세 개이고, 굵은 화살표는 그중 한 결과인 ACAB다.
그림 3 학생 1, 2, 3, 4가 동아리 A, B, C 중 하나씩 고르는 대응. 학생마다 나가는 화살표 후보가 세 개이고, 굵은 화살표는 그중 한 결과인 ACAB다. figures/choice_arrows.py

그림 3에서 학생마다 화살표 후보는 3개이고, 한 동아리에 여러 학생이 몰려도 된다. 아무도 고르지 않은 동아리가 있어도 된다. 학생 1, 2, 3, 4가 고른 동아리를 차례로 적으면 ACAB 같은 네 자리 기록이 되므로, 식 (4)는 앞의 81가지와 같은 수다.

서로 다른 공을 서로 다른 상자에 넣는 문제도 같다. 공 하나하나가 자기 상자를 고르므로 공의 수가 지수, 상자의 수가 밑이다. 문제에 3과 4가 함께 나오면 무엇이 기록 칸인지부터 정해야 밑과 지수를 바꿔 쓰지 않는다.

함수의 개수는 중복순열로 구하나요?

그렇다. 함수는 정의역의 원소마다 공역의 원소를 하나씩 고르므로, 정의역 원소가 기록 칸이고 공역 원소가 선택지다. X={1,2}X=\{1,2\}에서 Y={A,B,C}Y=\{A,B,C\}로의 함수는 32=93^2=9개이고, 서로 다른 값을 고르는 일대일함수는 3P2=6{}_3P_2=6개다. 그림 2의 행을 f(1)f(1), 열을 f(2)f(2)의 값으로 읽으면 대각선 세 칸이 일대일이 아닌 함수다.

중복순열도 첫 자리 조건을 먼저 읽는다

숫자 0, 2, 5, 7을 반복하여 네 칸의 가상 코드를 만들자. 0000처럼 0으로 시작해도 되는 코드라면 각 칸에 네 숫자가 올 수 있어 44=2564^4=256가지다. 그러나 네 자리 자연수라면 첫 자리에 0이 올 수 없다.

3×4×4×4=3×64=192.(5)3\times4\times4\times4=3\times64=192. \tag{5}
0, 2, 5, 7로 만드는 네 칸 코드와 네 자리 자연수의 비교. 위는 첫 칸에도 0을 허용하고, 아래는 첫 칸에서만 0을 제외한다. 칸 안 숫자는 가능한 선택의 수다.
그림 4 0, 2, 5, 7로 만드는 네 칸 코드와 네 자리 자연수의 비교. 위는 첫 칸에도 0을 허용하고, 아래는 첫 칸에서만 0을 제외한다. 칸 안 숫자는 가능한 선택의 수다. figures/leading_zero_slots.py

그림 4에서 아래 줄은 첫 자리만 선택 수가 줄었다. 0으로 시작하는 코드는 나머지 세 칸이 자유로운 43=644^3=64가지이므로, 256−64=192256-64=192로도 식 (5)를 확인할 수 있다.

이 자연수가 짝수여야 한다면 마지막 숫자는 0, 2 중 하나다. 따라서 3×4×4×2=963\times4\times4\times2=96가지다. 반복이 허용되므로 첫 자리에 쓴 숫자를 마지막 자리에 또 써도 된다. 반복이 없는 순열에서는 끝자리에 0을 썼는지에 따라 첫 자리 후보가 달라져 경우를 나눴다. 중복순열에서는 자리끼리 후보를 빼앗지 않으므로 자리별 선택 수를 바로 곱한다.

조건 때문에 각 자리의 선택 수가 달라도 곱의 법칙을 쓸 수 있다. 다만 앞선 선택마다 다음 선택 수가 일정한지 확인해야 한다. '중복 가능'이라는 말만 보고 첫 자리에도 4를 적으면 0257 같은 코드까지 자연수로 센다.

핵심

중복순열은 서로 다른 nn종류를 각 자리에서 제한 없이 다시 고르는 순서 있는 선택이며, 양의 정수 n,rn,r에 대해 그 수는 nrn^r이다. 자리 조건이나 재고 제한이 있으면 각 단계의 실제 선택 수부터 다시 확인한다.

중복순열에서 같은 문자를 최대 두 번만 써도 되나요?

사용 횟수의 상한 때문에 일부 배열이 금지되면 중복순열의 수 nrn^r보다 결과가 줄어든다. A, B로 세 칸을 채우되 각 문자를 최대 두 번만 쓰면, 여덟 기록에서 AAA와 BBB를 제외한 6가지다. 정해진 개수를 모두 배열하는 문제는 같은 것이 있는 순열에서 따로 다룬다.

중복순열에서 '적어도 한 번'은 왜 전체에서 빼서 셀까?

'한 번도 없는 경우'가 다시 중복순열이 되어 세기 쉽기 때문이다. A, B, C로 네 자리를 채울 때 A가 한 번도 없으면 각 자리에 B, C만 오므로 24=162^4=16가지다.

34−24=81−16=65.(6)3^4-2^4=81-16=65. \tag{6}

A가 적어도 한 번 들어간 기록은 식 (6)처럼 65가지다. 그림 2의 두 자리 기록으로 확인하면, A가 없는 칸은 B, C로만 된 2×2=42\times2=4칸이다. A가 있는 칸은 첫 행과 첫 열을 합친 9−4=59-4=5칸이다.

A가 들어갈 자리를 먼저 고르는 방법은 A가 두 번 이상인 기록을 여러 번 센다. 이 오류는 '중복순열의 흔한 오해'에서 숫자로 확인한다.

길이가 정해지지 않은 중복순열은 길이별로 더한다

기록의 길이가 하나로 정해지지 않으면 길이마다 중복순열의 수를 구해 더한다. 점과 선 두 기호를 1개 이상 3개 이하 늘어놓아 신호를 만들면 길이 1, 2, 3의 신호가 각각 21,22,232^1, 2^2, 2^3가지다.

2+22+23=2+4+8=14.(7)2+2^2+2^3=2+4+8=14. \tag{7}

길이가 다른 두 신호는 같을 수 없으므로 합의 법칙으로 더한다. 아무 기호도 없는 길이 0의 신호는 '1개 이상'이라는 조건에 따라 넣지 않는다.

중복순열에서 아무것도 고르지 않으면 0가지인가요?

양의 정수 nn종류에서 아무것도 고르지 않는 길이 0의 기록은 빈 기록 하나다. 이 경계까지 넓히면 nΠ0=n0=1{}_n\Pi_0=n^0=1로 쓸 수 있다. 이는 만들 수 있는 기록이 전혀 없다는 뜻의 0가지와 다르다.

중복순열의 흔한 오해

  • 반복 가능하면 AAB와 ABA도 같은 결과다 — 중복순열에서는 자리 순서를 구별하므로 둘은 다른 기록이다. 종류별 개수만 기록하는 문제는 중복조합이다.
  • 학생이 넷, 동아리가 셋이면 434^3이다 — 학생이 동아리를 고르면 학생 수 4가 지수라서 식 (4)의 34=813^4=81이다. 43=644^3=64는 한 학생이 여러 동아리의 대표를 맡아도 될 때, 동아리 세 곳이 각각 학생 넷 중 대표를 고르는 다른 상황의 답이다.
  • A가 적어도 한 번이면 A의 자리를 고르고 나머지를 곱한다 — A, B, C로 네 자리를 채울 때 4×33=1084\times3^3=108은 전체 81보다도 크다. AABC처럼 A가 두 번 이상인 기록을 A의 개수만큼 거듭 세었기 때문이며, 바른 답은 식 (6)의 65다.

직접 해보기

다음은 모두 가상 장치나 선택 상황이다. 각 문항에서 순서를 구별하는지, 반복 제한이 있는지, 무엇이 기록 칸인지 먼저 적어 보자.

  1. 다섯 문자 중에서 반복을 허용하여 세 칸의 기록을 만들면 몇 가지인가?
  2. 0, 1, 3을 반복하여 만드는 세 자리 자연수는 몇 개인가?
  3. A, B로 네 칸을 채우되 이웃한 두 칸은 항상 다른 문자여야 한다. 몇 가지인가?
  4. 서로 다른 공 5개를 서로 다른 상자 2개에 넣는다. 빈 상자가 있어도 되면 몇 가지인가? 두 상자 모두 공이 하나 이상 들어가야 하면 몇 가지인가?
  5. 빨강, 파랑, 노랑 깃발 중 하나를 한 번에 하나씩 들어 신호를 만든다. 깃발을 1번 이상 3번 이하 들어 만들 수 있는 신호는 몇 가지인가?
답과 풀이
  1. 각 칸에서 다섯 선택이 유지되므로 53=5×5×5=1255^3=5\times5\times5=125가지다.
  2. 첫 자리는 1, 3의 2가지, 나머지는 각각 3가지다. 2×3×3=182\times3\times3=18개다.
  3. 첫 칸은 2가지이고 이후에는 바로 앞 문자와 다른 문자 하나만 가능하다. 2×1×1×1=22\times1\times1\times1=2가지이며 ABAB, BABA다.
  4. 공마다 상자 2개 중 하나를 고르므로 공이 기록 칸이다. 빈 상자를 허용하면 25=322^5=32가지다. 모든 공이 한 상자에 몰린 2가지를 빼면 두 상자 모두 공이 있는 경우는 32−2=3032-2=30가지다.
  5. 길이 1, 2, 3의 신호가 각각 31,32,333^1, 3^2, 3^3가지다. 길이가 다르면 다른 신호이므로 더해서 3+9+27=393+9+27=39가지다.

더 읽기

영상 노트

영상 노트
  • 00:00 A, B 버튼을 세 번 누르는 기록을 만들고, 같은 버튼을 다시 누를 수 있음을 보여 준다.
  • 00:25 그림 1의 경로를 따라 식 (2)의 여덟 기록을 센다.
  • 00:55 모든 단계의 선택 수가 일정한 이유로 식 (1)을 설명한다.
  • 01:20 그림 2의 대각선을 가리며 식 (3)의 9와 6을 비교한다.
  • 01:50 그림 3의 화살표로 학생이 기록 칸임을 보이고 식 (4)를 쓴다. 434^3과 무엇이 다른지 묻는다.
  • 02:30 그림 4의 첫 칸 조건으로 식 (5)를 계산하고, 64를 빼는 검산과 짝수 96을 덧붙인다.
  • 03:10 식 (6)처럼 전체에서 빼는 계산과 108의 중복 세기를 나란히 쓴다.
  • 03:40 식 (7)로 길이별 신호를 더하고 새 연습을 푼다.

지도에서의 위치

곱의 법칙확률·통계순열확률·통계중복순열지금 이 페이지중복조합확률·통계
선수 개념
이 페이지
다음 개념
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 순열과의 비교표, 누가 고르는지로 밑과 지수를 정하는 절, 적어도 한 번(전체에서 빼기)과 길이별 신호 합 절, 함수의 개수 질문, 오해를 밑·지수 혼동(대표 겸임 조건 명시)과 '적어도'의 중복 세기로 교체, 연습 두 문항을 공 나누기·깃발 신호로 바꿈, 자리 수식 아래 여백 조정 (에이전트 수정, 그림 2→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림