직관 — 버튼을 누른 뒤에도 버튼은 남는다
문자 버튼을 누르면 기록 칸에 그 문자가 남는 장치를 떠올려 보자. 한 번 누른 버튼도 다음 칸에서 다시 누를 수 있다. 같은 버튼들을 눌렀어도 기록 순서가 바뀌면 다른 기록이다.
버튼의 종류는 고를 대상, 기록 칸은 순서가 있는 자리다. 이 글의 문자 장치와 숫자 코드는 계산을 위해 만든 가상 예다. 순열에서 한 번 고른 대상을 제외했다면, 이번에는 다음 자리에서도 그 대상을 고를 수 있다. 반복을 허용하는 비밀번호, 숫자 만들기, 여러 사람이 각자 하나씩 고르는 결과를 셀 때 이 방법을 쓴다.
중복순열은 반복을 허용하는 순서 있는 선택이다
중복순열은 서로 다른 개에서 중복을 허락하여 개를 택해 일렬로 나열하는 순열이다. 교과서는 이를 '개에서 개를 택하는 중복순열'이라 하고, 그 수를 로 쓴다. 이 글에서는 개를 '고를 수 있는 종류'로 읽는다. 같은 종류를 몇 번 골랐는지는 미리 정하지 않는다.
예를 들어 A, B에서 세 자리를 채우면 AAA도, ABA도 가능하고 AAB와 ABA는 다르다. 과 은 양의 정수로 시작하자. 중복순열의 수는 다음과 같다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 종류의 수 | number of types | 각 자리에서 고를 수 있는 서로 다른 종류의 수 | |
| 자리의 수 | number of positions | 순서대로 채울 자리의 수 | |
| 중복순열의 수 | permutations with repetition | 반복을 허용한 길이 의 배열 수 | |
| 순열의 수 | permutations without repetition | 반복 없이 고르는 배열 수, |
는 영어 P에 해당하는 그리스 문자 대문자 파이다. 곱을 뜻하는 product를 떠올리면 기억하기 쉽지만, 순열의 와는 다른 기호다.
중복순열의 수는 왜 거듭제곱일까?
앞자리를 어떻게 채웠든 다음 자리의 선택지가 똑같이 개이기 때문이다. 각 완성 배열은 첫 자리부터 마지막 자리까지 고르는 경로 하나와 정확히 대응한다. 경로가 겹쳐 같은 배열을 두 번 세지 않으며, 가능한 배열은 모두 그 경로로 만들어진다. 따라서 곱의 법칙을 자리에 차례로 적용하면 식 (1)을 얻는다.
A, B의 세 자리 기록은 첫 칸 2가지, 다음 칸 2가지, 마지막 칸 2가지다.
figures/repetition_tree.py그림 1은 식 (2)의 여덟 기록을 빠짐없이 보여 준다. 이것은 작은 예의 확인이고, 임의의 에 대한 근거는 앞 문단의 선택 경로와 배열의 대응이다. 세 문자 A, B, C로 네 자리를 채우면 같은 이유로 가지다.
중복순열과 순열은 고른 것을 다시 쓰는지에서 갈린다
순열은 고른 대상을 후보에서 빼고 다음 자리를 채우지만, 중복순열은 후보를 그대로 둔다. 그래서 A, B, C로 두 자리를 채우면 중복순열은 9가지, 순열은 6가지다.
figures/pair_grid.py그림 2에서 두 수의 차이 3은 대각선의 AA, BB, CC다. 첫 자리의 선택은 둘 다 3가지이고, 둘째 자리에서 중복순열만 3가지를 유지한다. 자리가 늘수록 중복순열은 매번 을 곱하므로 차이가 커진다. A, B, C로 세 자리를 채우면 중복순열은 가지, 순열은 가지다.
중복순열에서는 종류보다 많이 골라도 되나요?
중복순열은 반복을 허용하므로 종류 수보다 많은 자리를 채울 수 있다. A, B 두 종류로 세 자리를 채우는 식 (2)가 그 예로 8가지다. 반복을 금지한 순열에서는 두 종류로 세 자리를 채울 수 없어 0가지다.
중복순열에서 밑과 지수는 누가 고르는지로 정한다
선택을 하는 쪽의 수가 지수이고, 각자 고를 수 있는 선택지의 수가 밑이다. 학생 4명이 동아리 A, B, C 중 하나씩 고른다면 학생 한 명이 기록 칸 하나다.
figures/choice_arrows.py그림 3에서 학생마다 화살표 후보는 3개이고, 한 동아리에 여러 학생이 몰려도 된다. 아무도 고르지 않은 동아리가 있어도 된다. 학생 1, 2, 3, 4가 고른 동아리를 차례로 적으면 ACAB 같은 네 자리 기록이 되므로, 식 (4)는 앞의 81가지와 같은 수다.
서로 다른 공을 서로 다른 상자에 넣는 문제도 같다. 공 하나하나가 자기 상자를 고르므로 공의 수가 지수, 상자의 수가 밑이다. 문제에 3과 4가 함께 나오면 무엇이 기록 칸인지부터 정해야 밑과 지수를 바꿔 쓰지 않는다.
함수의 개수는 중복순열로 구하나요?
그렇다. 함수는 정의역의 원소마다 공역의 원소를 하나씩 고르므로, 정의역 원소가 기록 칸이고 공역 원소가 선택지다. 에서 로의 함수는 개이고, 서로 다른 값을 고르는 일대일함수는 개다. 그림 2의 행을 , 열을 의 값으로 읽으면 대각선 세 칸이 일대일이 아닌 함수다.
중복순열도 첫 자리 조건을 먼저 읽는다
숫자 0, 2, 5, 7을 반복하여 네 칸의 가상 코드를 만들자. 0000처럼 0으로 시작해도 되는 코드라면 각 칸에 네 숫자가 올 수 있어 가지다. 그러나 네 자리 자연수라면 첫 자리에 0이 올 수 없다.
figures/leading_zero_slots.py그림 4에서 아래 줄은 첫 자리만 선택 수가 줄었다. 0으로 시작하는 코드는 나머지 세 칸이 자유로운 가지이므로, 로도 식 (5)를 확인할 수 있다.
이 자연수가 짝수여야 한다면 마지막 숫자는 0, 2 중 하나다. 따라서 가지다. 반복이 허용되므로 첫 자리에 쓴 숫자를 마지막 자리에 또 써도 된다. 반복이 없는 순열에서는 끝자리에 0을 썼는지에 따라 첫 자리 후보가 달라져 경우를 나눴다. 중복순열에서는 자리끼리 후보를 빼앗지 않으므로 자리별 선택 수를 바로 곱한다.
조건 때문에 각 자리의 선택 수가 달라도 곱의 법칙을 쓸 수 있다. 다만 앞선 선택마다 다음 선택 수가 일정한지 확인해야 한다. '중복 가능'이라는 말만 보고 첫 자리에도 4를 적으면 0257 같은 코드까지 자연수로 센다.
중복순열은 서로 다른 종류를 각 자리에서 제한 없이 다시 고르는 순서 있는 선택이며, 양의 정수 에 대해 그 수는 이다. 자리 조건이나 재고 제한이 있으면 각 단계의 실제 선택 수부터 다시 확인한다.
중복순열에서 같은 문자를 최대 두 번만 써도 되나요?
사용 횟수의 상한 때문에 일부 배열이 금지되면 중복순열의 수 보다 결과가 줄어든다. A, B로 세 칸을 채우되 각 문자를 최대 두 번만 쓰면, 여덟 기록에서 AAA와 BBB를 제외한 6가지다. 정해진 개수를 모두 배열하는 문제는 같은 것이 있는 순열에서 따로 다룬다.
중복순열에서 '적어도 한 번'은 왜 전체에서 빼서 셀까?
'한 번도 없는 경우'가 다시 중복순열이 되어 세기 쉽기 때문이다. A, B, C로 네 자리를 채울 때 A가 한 번도 없으면 각 자리에 B, C만 오므로 가지다.
A가 적어도 한 번 들어간 기록은 식 (6)처럼 65가지다. 그림 2의 두 자리 기록으로 확인하면, A가 없는 칸은 B, C로만 된 칸이다. A가 있는 칸은 첫 행과 첫 열을 합친 칸이다.
A가 들어갈 자리를 먼저 고르는 방법은 A가 두 번 이상인 기록을 여러 번 센다. 이 오류는 '중복순열의 흔한 오해'에서 숫자로 확인한다.
길이가 정해지지 않은 중복순열은 길이별로 더한다
기록의 길이가 하나로 정해지지 않으면 길이마다 중복순열의 수를 구해 더한다. 점과 선 두 기호를 1개 이상 3개 이하 늘어놓아 신호를 만들면 길이 1, 2, 3의 신호가 각각 가지다.
길이가 다른 두 신호는 같을 수 없으므로 합의 법칙으로 더한다. 아무 기호도 없는 길이 0의 신호는 '1개 이상'이라는 조건에 따라 넣지 않는다.
중복순열에서 아무것도 고르지 않으면 0가지인가요?
양의 정수 종류에서 아무것도 고르지 않는 길이 0의 기록은 빈 기록 하나다. 이 경계까지 넓히면 로 쓸 수 있다. 이는 만들 수 있는 기록이 전혀 없다는 뜻의 0가지와 다르다.
중복순열의 흔한 오해
- 반복 가능하면 AAB와 ABA도 같은 결과다 — 중복순열에서는 자리 순서를 구별하므로 둘은 다른 기록이다. 종류별 개수만 기록하는 문제는 중복조합이다.
- 학생이 넷, 동아리가 셋이면 이다 — 학생이 동아리를 고르면 학생 수 4가 지수라서 식 (4)의 이다. 는 한 학생이 여러 동아리의 대표를 맡아도 될 때, 동아리 세 곳이 각각 학생 넷 중 대표를 고르는 다른 상황의 답이다.
- A가 적어도 한 번이면 A의 자리를 고르고 나머지를 곱한다 — A, B, C로 네 자리를 채울 때 은 전체 81보다도 크다. AABC처럼 A가 두 번 이상인 기록을 A의 개수만큼 거듭 세었기 때문이며, 바른 답은 식 (6)의 65다.
직접 해보기
다음은 모두 가상 장치나 선택 상황이다. 각 문항에서 순서를 구별하는지, 반복 제한이 있는지, 무엇이 기록 칸인지 먼저 적어 보자.
- 다섯 문자 중에서 반복을 허용하여 세 칸의 기록을 만들면 몇 가지인가?
- 0, 1, 3을 반복하여 만드는 세 자리 자연수는 몇 개인가?
- A, B로 네 칸을 채우되 이웃한 두 칸은 항상 다른 문자여야 한다. 몇 가지인가?
- 서로 다른 공 5개를 서로 다른 상자 2개에 넣는다. 빈 상자가 있어도 되면 몇 가지인가? 두 상자 모두 공이 하나 이상 들어가야 하면 몇 가지인가?
- 빨강, 파랑, 노랑 깃발 중 하나를 한 번에 하나씩 들어 신호를 만든다. 깃발을 1번 이상 3번 이하 들어 만들 수 있는 신호는 몇 가지인가?
답과 풀이
- 각 칸에서 다섯 선택이 유지되므로 가지다.
- 첫 자리는 1, 3의 2가지, 나머지는 각각 3가지다. 개다.
- 첫 칸은 2가지이고 이후에는 바로 앞 문자와 다른 문자 하나만 가능하다. 가지이며 ABAB, BABA다.
- 공마다 상자 2개 중 하나를 고르므로 공이 기록 칸이다. 빈 상자를 허용하면 가지다. 모든 공이 한 상자에 몰린 2가지를 빼면 두 상자 모두 공이 있는 경우는 가지다.
- 길이 1, 2, 3의 신호가 각각 가지다. 길이가 다르면 다른 신호이므로 더해서 가지다.
더 읽기
- 지학사 2022 개정 고등 확률과 통계 교과서 — 「중복순열과 같은 것이 있는 순열」 12–13쪽. 중복순열의 표기, 자리별 곱과 첫 자리 0의 제한을 확인했다.
- College Algebra 2e — Counting Principles — OpenStax. 곱의 법칙과 자리별 선택을 다루는 절을 읽었다. 본문의 문자·숫자 예제는 별도로 구성했다.
영상 노트
- 00:00 A, B 버튼을 세 번 누르는 기록을 만들고, 같은 버튼을 다시 누를 수 있음을 보여 준다.
- 00:25 그림 1의 경로를 따라 식 (2)의 여덟 기록을 센다.
- 00:55 모든 단계의 선택 수가 일정한 이유로 식 (1)을 설명한다.
- 01:20 그림 2의 대각선을 가리며 식 (3)의 9와 6을 비교한다.
- 01:50 그림 3의 화살표로 학생이 기록 칸임을 보이고 식 (4)를 쓴다. 과 무엇이 다른지 묻는다.
- 02:30 그림 4의 첫 칸 조건으로 식 (5)를 계산하고, 64를 빼는 검산과 짝수 96을 덧붙인다.
- 03:10 식 (6)처럼 전체에서 빼는 계산과 108의 중복 세기를 나란히 쓴다.
- 03:40 식 (7)로 길이별 신호를 더하고 새 연습을 푼다.
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 순열과의 비교표, 누가 고르는지로 밑과 지수를 정하는 절, 적어도 한 번(전체에서 빼기)과 길이별 신호 합 절, 함수의 개수 질문, 오해를 밑·지수 혼동(대표 겸임 조건 명시)과 '적어도'의 중복 세기로 교체, 연습 두 문항을 공 나누기·깃발 신호로 바꿈, 자리 수식 아래 여백 조정 (에이전트 수정, 그림 2→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림