가능한 조합. 조합론의 요소
조합은 고정된 수를 갖고 요소가 반복되지 않는 유한 집합의 요소를 순서 없이 선택하는 것입니다. 다양한 조합은 적어도 하나의 요소에서 달라야 하며 요소의 순서는 중요하지 않습니다. 예를 들어, 라틴 문자의 모든 모음(AEIOU) 세트에서 3개의 문자로 구성된 10가지의 서로 다른 조합을 만들어 다음과 같은 순서 없는 세 쌍을 만들 수 있습니다.
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
동일한 5개의 문자에서 한 번에 2개의 문자를 결합하면 다음과 같은 순서가 없는 쌍을 만들면 10개의 다른 조합을 얻을 수도 있다는 점은 흥미롭습니다.
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
그러나 동일한 모음 라틴 문자를 4로 결합하면 다음과 같은 5가지 다른 조합만 얻을 수 있습니다.
AEIO, AEIU, AIOU, EIOU, AEOU.
일반적으로 m개의 요소 중 n개의 서로 다른 요소의 조합 수를 표시하기 위해 다음과 같은 기능적, 인덱스 또는 벡터(Appel) 기호가 사용됩니다.
표기 형식에 관계없이 n개 요소와 m개 요소의 조합 수는 다음과 같은 곱셈 및 계승 공식을 사용하여 결정할 수 있습니다.
이러한 공식을 이용한 계산 결과가 위에서 설명한 라틴 문자 모음 조합의 예 결과와 일치하는지 쉽게 확인할 수 있습니다. 특히, n=5 및 m=3인 경우 이러한 공식을 사용한 계산은 다음과 같은 결과를 제공합니다.
일반적인 경우, 조합 수에 대한 공식은 조합적 의미를 가지며 n > m > 0과 같은 n과 m의 모든 정수 값에 유효합니다. m > n 및 m인 경우< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
또한, 곱셈 및 계승 공식에 직접 대입하여 쉽게 확인할 수 있는 다음과 같은 제한된 수의 조합을 기억하는 것이 유용합니다.
n이 실수인 경우에도 m이 여전히 정수 값인 한 곱셈 공식은 유효하다는 점에 유의해야 합니다. 그러나 이를 사용한 계산 결과는 형식적 타당성을 유지하면서 조합적 의미를 잃습니다.
조합의 정체성
n과 m의 임의 값에 대한 조합 수를 결정하기 위해 곱셈 및 계승 공식을 실제로 사용하는 것은 분자와 분모의 계승 곱이 기하급수적으로 증가하기 때문에 생산성이 거의 없는 것으로 나타났습니다. 상대적으로 작은 n과 m 값의 경우에도 이러한 제품은 현대 컴퓨팅 및 소프트웨어 시스템에서 정수를 표현하는 기능을 초과하는 경우가 많습니다. 더욱이 그 값은 상대적으로 작을 수 있는 조합 수의 결과 값보다 훨씬 더 큰 것으로 나타났습니다. 예를 들어 n=10과 m=8 요소의 조합 수는 45개에 불과합니다. 하지만 계승 공식을 사용하여 이 값을 구하려면 먼저 훨씬 더 큰 10의 값을 계산해야 합니다! 분자와 8! 분모에:
대량 처리에 시간이 많이 걸리는 작업을 없애고 조합 수를 결정하기 위해 곱셈 및 계승 공식을 직접 따르는 다양한 반복 관계를 사용할 수 있습니다. 특히, 다음과 같은 반복 관계는 곱셈 공식을 따르며, 이를 통해 조합 수의 부호를 넘어 지수의 비율을 취할 수 있습니다.
마지막으로, 아래 첨자를 일정하게 유지하면 다음과 같은 반복 관계가 제공되며, 이는 조합 수에 대한 계승 공식에서 쉽게 얻을 수 있습니다.
기본 변환 후 결과로 나타나는 세 가지 반복 관계는 다음 형식으로 표현될 수 있습니다.
이제 처음 2개의 공식의 왼쪽과 오른쪽을 더하고 결과를 n만큼 줄이면 조합 숫자 추가의 항등식이라고 하는 중요한 반복 관계를 얻게 됩니다.
덧셈 항등식은 계승 곱의 곱셈 연산을 더 간단한 덧셈 연산으로 대체할 수 있고 더 적은 수의 조합에 대해 허용하므로 n과 m의 큰 값에 대한 조합 수를 효율적으로 결정하기 위한 기본 반복 규칙을 제공합니다. 특히, 덧셈 항등식을 사용하면 다음과 같은 반복 변환 시퀀스를 수행하여 위에서 논의한 n=10 x m=8 요소의 조합 수를 쉽게 결정할 수 있습니다.
또한 유한합을 계산하는 데 유용한 몇 가지 관계는 덧셈 항등식, 특히 다음 형식을 갖는 첨자에 의한 합산 공식에서 파생될 수 있습니다.
이 관계는 덧셈 항등식에서 아래 첨자가 0보다 큰 동안 가장 큰 위 첨자가 있는 항을 따라 반복을 확장하면 얻어집니다. 다음 수치 예는 이 반복 변환 과정을 보여줍니다.
첨자 합 공식은 자연수의 거듭제곱의 합을 계산하는 데 자주 사용됩니다. 특히 m=1이라고 가정하면 이 공식을 사용하여 자연 계열의 처음 n개 숫자의 합을 쉽게 찾을 수 있습니다.
합산 공식의 또 다른 유용한 버전은 가장 작은 위첨자가 있는 항을 따라 덧셈 항등식의 반복을 확장하여 얻을 수 있습니다. 다음 수치 예는 이 버전의 반복 변환을 보여줍니다.
일반적으로 이러한 변환의 결과로 조합 수의 합이 얻어지며, 두 인덱스는 이웃 항과 하나씩 다르며 인덱스의 차이는 일정하게 유지됩니다(고려된 예에서는 다음과 같습니다). 또한 1과 같습니다). 따라서 우리는 조합 숫자의 두 인덱스에 대해 다음과 같은 합계 공식을 얻습니다.
위에서 논의한 반복 관계 및 합산 공식 외에도 조합 분석에서 조합 수에 대한 다른 많은 유용한 항등식을 얻었습니다. 그 중에 가장 중요한 것은 대칭 정체성, 이는 다음과 같습니다.
대칭성 동일성의 타당성은 다음 예에서 5개 요소의 조합 수를 2와 (5 2) = 3으로 비교하여 확인할 수 있습니다.
대칭 동일성은 n개의 요소에서 m개의 요소를 선택하기 위한 옵션 수를 결정함으로써 동시에 선택되지 않은 나머지(nm) 요소의 조합 수를 설정하므로 명백한 조합적 의미를 갖습니다. 표시된 대칭은 조합 수에 대한 계승 공식에서 m을 (nm)로 대체하여 즉시 얻습니다.
숫자와 조합 항등식은 현대 계산 수학의 다양한 영역에서 널리 사용됩니다. 그러나 가장 널리 사용되는 응용 분야는 뉴턴의 이항식 및 파스칼의 삼각형과 관련이 있습니다.
이항 정리
다양한 수학적 변환과 계산을 수행하려면 대수적 이항식(binomial)의 자연적인 힘을 다항식의 형태로 표현할 수 있는 것이 중요합니다. 거듭제곱이 작은 경우에는 이항식을 직접 곱하여 원하는 다항식을 쉽게 얻을 수 있습니다. 특히, 두 항의 합의 제곱과 세제곱에 대한 다음 공식은 초등 수학 과정에서 잘 알려져 있습니다.
일반적으로 이항식의 임의 차수 n에 대해 필요한 다항식 형태의 표현은 뉴턴의 이항 정리에 의해 제공되며, 이는 다음 동등성이 참임을 선언합니다.
이러한 평등을 일반적으로 뉴턴의 이항식이라고 합니다. 우변의 다항식은 좌변의 이항식의 n 항 X와 Y의 곱의 합으로 구성되며, 그 앞의 계수를 이항식이라고 하며 지수와의 조합 수와 같습니다. 그들의 힘으로부터 얻어집니다. 조합 분석에서 뉴턴의 이항식의 특별한 인기를 감안할 때, 이항 계수와 조합 수라는 용어는 일반적으로 동의어로 간주됩니다.
분명히, 제곱합과 세제곱합 공식은 각각 n=2와 n=3에 대한 이항 정리의 특별한 경우입니다. 더 높은 차수(n>3)를 처리하려면 뉴턴의 이항 공식을 사용해야 합니다. 4차 이항식(n=4)에 대한 적용은 다음 예에서 보여줍니다.
이항 공식은 뉴턴 이전에도 아랍 동부와 서유럽의 중세 수학자에게 알려졌습니다. 따라서 일반적으로 인정되는 이름은 역사적으로 정확하지 않습니다. 뉴턴의 장점은 이 공식을 임의의 실수 지수 r의 경우로 일반화했다는 것입니다. 이는 임의의 양수 또는 음수 유리수 값과 무리수 값을 취할 수 있습니다. 일반적인 경우, 이러한 뉴턴 이항식은 우변에 무한합이 있고 일반적으로 다음과 같이 작성됩니다.
예를 들어, 이항 계수의 값을 고려하여 지수 r=1/2의 양의 분수 값을 사용하면 다음과 같은 확장이 얻어집니다.
일반적인 경우, 모든 지수에 대한 뉴턴의 이항 공식은 임의의 함수를 거듭제곱 급수로 확장하는 Maclaurin 공식의 특수 버전입니다. 뉴턴은 |z|에 대해 이를 보여주었습니다.< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . 이제 Z=X/Y로 설정하고 왼쪽과 오른쪽에 Yn을 곱하면 위에서 설명한 뉴턴 이항식의 버전을 얻을 수 있습니다.
보편성에도 불구하고, 이항 정리는 이항의 음이 아닌 정수 거듭제곱에 대해서만 조합적 의미를 유지합니다. 이 경우 이항 계수에 대한 몇 가지 유용한 항등식을 증명하는 데 사용할 수 있습니다. 특히, 아래 첨자와 두 지수로 조합 수를 합산하는 공식은 위에서 논의되었습니다. 누락된 위첨자 합산 항등식은 뉴턴의 이항식에 X = Y = 1 또는 Z = 1을 넣으면 쉽게 얻을 수 있습니다.
또 다른 유용한 항등식은 짝수 및 홀수를 갖는 이항 계수의 합이 같음을 확립합니다. X = 1이고 Y = 1이거나 Z = 1인 경우 뉴턴의 이항식에서 즉시 구해집니다.
마지막으로, 고려된 두 항등식으로부터 짝수 또는 홀수만 있는 이항 계수의 합의 항등식을 얻습니다.
고려된 항등식과 조합 수의 부호 아래에서 인덱스를 제거하는 반복 규칙을 기반으로 여러 가지 흥미로운 관계를 얻을 수 있습니다. 예를 들어, 위 첨자 합계 공식에서 n을 모든 위치에서 (n1)로 바꾸고 각 항의 색인을 제거하면 다음 관계를 얻습니다.
짝수와 홀수의 이항 계수 합에 대한 공식에서 유사한 기술을 사용하면 예를 들어 다음 관계의 타당성을 증명할 수 있습니다.
또 다른 유용한 항등식을 사용하면 다음 Cauchy 공식을 사용하여 임의 차수 n과 k의 두 이항식의 대칭적으로 위치한 이항 계수의 곱의 합을 쉽게 계산할 수 있습니다.
이 공식의 타당성은 다음 동일한 관계의 왼쪽과 오른쪽에 있는 변수 Z의 임의 차수 m에 대한 계수의 필수 동일성에서 따릅니다.
n=k=m인 특별한 경우에 대칭 항등성을 고려하면 이항 계수의 제곱합에 대해 더 널리 사용되는 공식이 얻어집니다.
이항 계수에 대한 다른 많은 유용한 항등식은 조합 분석에 관한 광범위한 문헌에서 찾을 수 있습니다. 그러나 가장 유명한 실제 적용은 파스칼의 삼각형과 관련이 있습니다.
파스칼의 삼각형
파스칼의 산술삼각형은 이항계수로 구성된 무한한 수치표를 형성합니다. 그 선은 위에서 아래로 이항식의 거듭제곱에 따라 정렬됩니다. 각 줄에는 해당 조합번호의 윗첨자가 왼쪽에서 오른쪽으로 오름차순으로 이항계수가 배열되어 있다. 파스칼의 삼각형은 일반적으로 이등변 또는 직사각형 형태로 작성됩니다.
더 시각적이고 일반적인 것은 이항 계수가 엇갈려 무한 이등변 삼각형을 형성하는 이등변 형식입니다. 최대 4차 이항식(n=4)에 대한 초기 조각의 형식은 다음과 같습니다.
일반적으로 파스칼의 이등변삼각형은 덧셈의 동일성과 숫자 조합의 대칭성을 기반으로 하는 이항 계수를 결정하기 위한 편리한 기하학적 규칙을 제공합니다. 특히, 덧셈 항등식에 따르면 모든 이항 계수는 이에 가장 가까운 이전 행의 두 계수의 합입니다. 대칭 항등식에 따르면 파스칼의 이등변삼각형은 이등분선을 기준으로 대칭입니다. 따라서 각 선은 이항 계수의 수치 회문입니다. 표시된 대수적 및 기하학적 특징을 통해 파스칼의 이등변삼각형을 쉽게 확장하고 임의 거듭제곱의 이항 계수 값을 일관되게 찾을 수 있습니다.
그러나 파스칼 삼각형의 다양한 속성을 연구하려면 공식적으로 더 엄격한 직사각형 형식을 사용하는 것이 더 편리합니다. 이 형식에서는 무한 직각삼각형을 형성하는 이항 계수의 하삼각 행렬로 지정됩니다. 최대 9차(n=9)의 이항식에 대한 파스칼 직각삼각형의 초기 조각은 다음 형식을 갖습니다.
기하학적으로 이러한 직사각형 테이블은 파스칼의 이등변삼각형을 수평 변형하여 얻습니다. 결과적으로 파스칼의 이등변삼각형의 옆변에 평행한 수열은 파스칼의 직각삼각형의 수직선과 대각선으로 변하고, 두 삼각형의 수평선은 일치한다. 동시에, 파스칼의 직각 삼각형이 이등변 대응의 시각적 대칭 특성을 잃더라도 이항 계수의 덧셈 및 대칭 규칙은 유효합니다. 이를 보완하기 위해서는 파스칼의 직각삼각형의 가로, 세로, 대각선에 대한 이항계수의 다양한 수치적 성질을 형식적으로 분석하는 것이 더욱 편리해진다.
파스칼의 직각 삼각형의 가로 분석을 시작하면 위 첨자로 이항식을 합산하는 공식에 따라 숫자 n이 있는 행의 요소 합이 2n과 같다는 것을 쉽게 알 수 있습니다. 따라서 숫자 n을 갖는 수평선 위의 요소의 합은 (2n 1)과 같습니다. 이 결과는 각 수평 요소의 합 값이 이진수 시스템으로 쓰여지면 매우 분명해집니다. 예를 들어 n=4인 경우 이 추가는 다음과 같이 작성할 수 있습니다.
다음은 2의 거듭제곱과 관련된 수평의 몇 가지 흥미로운 속성입니다. 수평 숫자가 2의 거듭제곱(n=2k)이면 모든 내부 요소(외부 요소 제외)는 짝수입니다. 반대로, 수평선의 수가 2의 거듭제곱보다 1이 작은 경우(n=2k 1) 수평선의 모든 수는 홀수가 됩니다. 이러한 속성의 유효성은 내부 이항 계수의 패리티를 확인하여 확인할 수 있습니다(예: 수평 n=4 및 n=3 또는 n=8 및 n=7).
이제 파스칼의 직각삼각형의 행 번호를 소수 p로 둡니다. 그런 다음 모든 내부 이항 계수는 p로 나눌 수 있습니다. 이 속성은 소수 등고선 숫자의 작은 값을 쉽게 확인할 수 있습니다. 예를 들어, 다섯 번째 수평(5, 10, 5)의 모든 내부 이항 계수는 분명히 5로 나누어집니다. 임의의 수평 소수 p에 대해 이 결과를 증명하려면 다음과 같이 이항 계수에 대한 곱셈 공식을 작성해야 합니다.
p는 소수이고 따라서 m!으로 나누어지지 않기 때문에 이 공식의 분자의 나머지 인수의 곱은 이항 계수의 정수 값을 보장하기 위해 m!으로 나누어져야 합니다. 대괄호 안의 비율은 자연수 N이며 원하는 결과가 분명해집니다.
이 결과를 사용하여 내부 요소가 주어진 소수 p로 나누어지는 파스칼 삼각형의 모든 수평선의 수가 p의 거듭제곱, 즉 n=p k 형식을 갖는다는 것을 확인할 수 있습니다. 특히 p=3인 경우 소수 p는 위에서 설정한 대로 행 3의 모든 내부 요소뿐만 아니라 예를 들어 9번째 가로(9, 36, 84 및 126)도 나눕니다. 반면에 파스칼의 삼각형에서는 내부 요소가 모두 합성수로 나누어지는 수평선을 찾는 것이 불가능합니다. 그렇지 않으면, 그러한 수평선의 수는 동시에 모든 내부 요소를 나누는 합성수의 소인수의 거듭제곱이어야 하지만 이는 명백한 이유로 불가능합니다.
고려된 고려 사항을 통해 우리는 파스칼 삼각형의 수평 요소의 분할 가능성에 대한 다음과 같은 일반적인 기준을 공식화할 수 있습니다. n이 n인 파스칼 삼각형의 수평선의 모든 내부 요소의 최대 공약수(GCD)는 n=pk인 경우 소수 p와 같고 다른 모든 경우에는 1입니다.
GCD(Cmn) = ( ) 0에 대해< m < n .
수평 분석의 결론에서는 수평을 구성하는 일련의 이항 계수가 갖는 흥미로운 특성을 하나 더 고려해 볼 가치가 있습니다. 숫자 n을 갖는 임의의 수평선의 이항 계수에 숫자 10의 연속 거듭제곱을 곱하고 이 모든 곱을 더하면 결과는 11n입니다. 이 결과에 대한 형식적인 정당성은 X=10 및 Y=1(또는 Z=1) 값을 뉴턴 이항식으로 대체하는 것입니다. 다음 수치 예는 n=5에 대한 이 속성의 충족을 보여줍니다.
파스칼의 직각 삼각형의 수직 특성 분석은 구성 요소의 개별 특성에 대한 연구로 시작할 수 있습니다. 공식적으로, 각 수직 m은 상수 위 첨자(m)와 아래 첨자의 증분을 갖는 다음과 같은 이항 계수의 무한 시퀀스로 구성됩니다.
분명히, m=0일 때 일련의 1이 얻어지고, m=1일 때 일련의 자연수가 형성됩니다. m=2일 때 수직은 삼각형 숫자로 구성됩니다. 각 삼각형 숫자는 정삼각형 형태로 평면에 표시될 수 있으며, 여기에는 바둑판 패턴으로 배열된 임의의 물체(핵)가 채워져 있습니다. 이 경우, 각 삼각수 Tk의 값에 따라 커널을 표현하는 개수가 결정되며, 인덱스는 이를 표현하는 데 필요한 커널 행 수를 나타냅니다. 예를 들어, 4개의 초기 삼각형 숫자는 해당 개수의 핵 "@" 기호에 대한 다음 구성을 나타냅니다.
비슷한 방식으로 자연수를 제곱하여 얻은 제곱수 Sk 를 고려할 수 있으며 일반적으로 정다각형을 규칙적으로 채워서 형성된 다각형 숫자를 도입할 수 있습니다. 특히 4개의 초기 제곱수는 다음과 같이 나타낼 수 있습니다.
파스칼 삼각형의 수직 분석으로 돌아가면 m=3의 다음 수직이 사면체(피라미드) 숫자로 채워져 있음을 알 수 있습니다. 각각의 숫자 P k는 사면체 모양으로 배열할 수 있는 코어의 수를 지정하고, 지수는 이를 3차원 공간에서 표현하는 데 필요한 코어 행의 수평 삼각형 층 수를 결정합니다. 이 경우 수평 레이어는 모두 연속된 삼각형 숫자로 표현되어야 합니다. m>3에 대한 파스칼 삼각형의 다음 수직 요소는 평면이나 3차원 공간에서 시각적인 기하학적 해석을 갖지 않지만 형식적으로는 삼각형 및 사면체 숫자의 다차원 유사체에 해당하는 일련의 초사각형 숫자를 형성합니다.
파스칼 삼각형의 수직 숫자 시리즈는 개별적인 모양의 특징을 고려하지만, 첨자로 조합 수를 합산하는 공식을 사용하여 동일한 방식으로 초기 요소 값의 부분 합을 계산할 수 있습니다 . 파스칼의 삼각형에서 이 공식은 다음과 같은 기하학적 해석을 갖습니다. 임의의 수직의 n개의 상위 이항 계수 값의 합은 한 줄 아래에 있는 다음 수직의 요소 값과 같습니다. 이 결과는 삼각형, 사면체 및 초사면체 숫자의 기하학적 구조와도 일치합니다. 왜냐하면 각 숫자의 표현은 낮은 차수를 나타내는 코어 레이어로 구성되기 때문입니다. 특히, n번째 삼각수 Tn은 선형 레이어를 나타내는 모든 자연수를 합하여 얻을 수 있습니다.
마찬가지로, 수평 코어 레이어를 구성하는 처음 n개의 삼각형 수의 다음 합을 계산하여 사면체 수 Pn을 찾는 것은 어렵지 않습니다.
파스칼의 직각 삼각형의 가로와 세로 외에도 요소의 대각선 행을 추적할 수 있으며 그 속성에 대한 연구에도 관심이 있습니다. 이 경우 일반적으로 하강 대각선과 상승 대각선을 구분합니다. 아래쪽 대각선은 파스칼 직각삼각형의 빗변과 평행합니다. 이는 두 지수가 모두 증가하는 일련의 이항 계수로 구성됩니다. 대칭의 동일성으로 인해 하강하는 대각선은 요소 값이 파스칼 삼각형의 해당 수직 행과 일치하므로 위에서 설명한 모든 속성을 반복합니다. 표시된 대응 관계는 수직 영점을 고려하지 않은 경우 하강 대각선 요소 값과 숫자 n의 수직 요소 값의 일치로 추적할 수 있습니다.
상승 대각선은 파스칼 직각삼각형의 빗변에 기하학적으로 수직인 수열을 형성합니다. 이는 하한값이 감소하고 위 첨자가 증가하는 이항 계수로 채워집니다. 특히, 7개의 위쪽 상승 대각선은 후행 0을 고려하지 않고 다음과 같은 숫자 시퀀스를 형성합니다.
일반적으로 오름차순 대각선 수 n에는 다음과 같은 이항 계수가 포함되며, 각 계수의 인덱스 합은 (n1)과 같습니다.
조합 숫자의 덧셈 항등식으로 인해 각 대각선 요소는 이전 두 개의 오름차순 대각선의 인덱스에 해당하는 두 요소의 합과 같습니다. 이를 통해 이전 두 대각선의 인접한 수평 요소를 쌍으로 합산하여 각 후속 상승 대각선을 구성할 수 있으며 대각선을 따라 파스칼의 삼각형을 무한히 확장할 수 있습니다. 다음 파스칼의 삼각형 조각은 6번과 7번 대각선을 따라 상승하는 대각선 번호 8을 구성하는 것을 보여줍니다.
이 구성 방법을 사용하면 3번째부터 시작하는 모든 상승 대각선 요소의 합은 이전 두 개의 상승 대각선 요소의 합과 같고 처음 2개의 대각선은 하나의 요소, 즉 값으로만 구성됩니다. 해당 계산의 결과는 다음과 같은 숫자 계열을 형성하며, 이에 따라 파스칼 직각삼각형의 상승 대각선의 고려된 속성의 유효성을 확인할 수 있습니다.
이 숫자를 분석하면 유사한 법칙에 따라 잘 알려진 피보나치 수열이 형성된다는 것을 알 수 있습니다. 여기서 다음 각 숫자는 이전 두 숫자의 합과 같고 처음 두 숫자는 1과 같습니다.
따라서 우리는 다음과 같은 중요한 결론을 내릴 수 있습니다. 파스칼 삼각형 요소의 대각선 합은 피보나치 수열을 구성합니다. 이 속성을 통해 우리는 파스칼 삼각형의 또 다른 흥미로운 특징을 확립할 수 있습니다. 피보나치 공식을 재귀적으로 확장하면 처음 n개의 피보나치 수의 합이 (F n+2 1)과 같다는 것을 쉽게 증명할 수 있습니다.
따라서 상위 n 대각선을 채우는 이항 계수의 합도 (F n+2 1)과 같습니다. 따라서 파스칼 삼각형의 처음 n 대각선의 합은 숫자(n+2)의 대각선에 있는 이항 계수의 합보다 1이 작습니다.
결론적으로, 파스칼 삼각형의 가로, 세로 및 대각선의 고려된 속성은 언뜻 보기에 공통점이 없는 다양한 수학적 측면을 함께 연결하는 다양한 가능성을 소진하지 않는다는 점에 유의해야 합니다. 이러한 특이한 속성을 통해 우리는 파스칼의 삼각형을 가장 완벽한 수치 시스템 중 하나로 간주할 수 있으며, 모든 기능을 나열할 수 없고 과대평가하기 어렵습니다.
파스칼의 삼각형을 사용하여 조합 수를 계산하는 알고리즘은 다음과 같습니다.
전용 함수 SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 다음 For i = 2 To n For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) 다음 다음 SochTT = TT(n, k) 끝 함수
여러 번 조합 수를 계산해야 하는 경우에는 파스칼의 삼각형을 한 번 구성한 다음 배열에서 데이터를 받는 것이 더 편리할 수 있습니다.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j 정수로 ReDim 보존 TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
먼저 CreateTT 프로시저를 호출해야 합니다. 그런 다음 SochTT 기능을 사용하여 조합 수를 얻을 수 있습니다. 삼각형이 더 이상 필요하지 않으면 TerminateTT 프로시저를 호출하세요. 위 코드에서 SochTT 함수를 호출할 때 삼각형이 아직 필요한 수준까지 완성되지 않은 경우 BuildTT 절차를 사용하여 완성됩니다. 그런 다음 함수는 TT 배열의 원하는 요소를 가져와서 반환합니다.
Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 j = 1의 경우 N으로 X1(j)인 경우<>0 Then n1 = n1 + 1 If n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 종료 For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) 다음 txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
자연수의 조합 나열
많은 실제 문제를 해결하려면 주어진 유한 집합의 요소에서 얻을 수 있는 고정 카디널리티의 모든 조합을 나열해야 하며 단순히 그 수를 결정하는 것이 아닙니다. 유한 집합의 요소에 대한 정수 번호 매기기의 항상 존재하는 가능성을 고려하면 대부분의 경우 자연수 조합을 열거하는 알고리즘의 사용으로 제한하는 것이 허용됩니다. 그 중 가장 자연스럽고 간단한 것은 자연수 조합을 나열하는 알고리즘입니다. 사전순.
이 알고리즘을 공식적으로 설명하기 위해 m개 요소의 모든 조합이 나열되어야 하는 기본 집합이 1부터 n까지 연속적인 자연수를 형성한다고 가정하는 것이 편리합니다. 그런 다음 m의 임의의 조합 순서를 정한 결과 이러한 조합 벡터의 각 위치에 있는 값은 자연스럽게 다음과 같이 위와 아래에서 값이 제한되는 것으로 나타났습니다. 사전식 알고리즘은 사전적으로 가장 작은 벡터부터 시작하여 이러한 조합 벡터를 순차적으로 생성합니다. 여기서 모든 위치에는 해당 인덱스와 동일한 요소의 가능한 최소 값이 다음과 같이 포함됩니다. 각 연속 조합 벡터는 아직 한계 값에 도달하지 않은 가장 오른쪽 요소를 찾기 위해 해당 요소를 왼쪽에서 오른쪽으로 스캔한 후 현재 조합 벡터로부터 형성됩니다. 이러한 요소의 값은 1씩 증가해야 합니다. 오른쪽에 있는 각 요소에는 왼쪽에 있는 요소보다 1이 큰 가능한 가장 작은 값이 할당되어야 합니다. 이러한 변경 후 다음 조합 벡터는 다음과 같은 요소 구성을 갖게 됩니다. 따라서 다음 조합 벡터는 초기 (j1) 요소의 값이 동일하고 위치 j의 요소 값이 이전 요소의 값보다 1 크기 때문에 사전 식으로 이전 벡터보다 커집니다. . 증가하는 사전순의 지정된 관계는 알고리즘의 모든 반복에서 충족되는 것이 보장됩니다. 결과는 사전적으로 가장 큰 조합 벡터에 의해 완성되는 증가하는 사전순서이며, 여기서 모든 위치의 요소는 다음과 같은 최대값을 갖습니다. 고려된 사전식 알고리즘은 다음 예에 의해 설명됩니다. 여기서 n=6 첫 번째 자연수 x m=4 숫자의 모든 15개 조합, 즉 주 생성의 가능한 모든 4개 요소 하위 집합을 사전식 순서로 증가시키면서 나열해야 합니다. 6개 요소에서 (1, 2, 3, 4, 5, 6)을 설정합니다. 계산 결과는 다음 표에 나와 있습니다. 이 예에서 조합 벡터 위치에 허용되는 최대 숫자 값은 각각 3, 4, 5 및 6입니다. 결과를 쉽게 해석할 수 있도록 각 조합 벡터에서 가장 오른쪽 요소는 다음과 같습니다. 아직 최대값에 도달하지 않은 경우에는 밑줄이 그어져 있습니다. 조합 벡터의 숫자 인덱스는 사전순으로 숫자를 결정합니다. 일반적인 경우, n 요소를 m으로 조합한 사전 문자 수 N은 다음 공식을 사용하여 계산할 수 있습니다. 여기서 미용상의 이유로 Appel 기호는 조합 수를 나타내는 데 사용됩니다. 특히, 사전순으로 m=4인 n=6 요소의 조합 수(1, 3, 4, 6)에 대해 이 공식을 사용하는 다음 계산은 위에서 설명한 예에 해당하는 N=8 결과를 제공합니다. 일반적인 경우, 두 지수의 조합 개수의 합에 대한 항등식을 이용하면, 이를 이용하여 계산할 때 사전적으로 가장 작은 조합(1,...i,...m)의 개수를 나타내는 것이 가능하다. 수식은 항상 1과 같습니다. 또한 이 공식을 사용하여 계산할 때 사전적으로 가장 큰 조합의 수(m, … nm+i, … n)는 m만큼 n 요소의 조합 수와 동일할 것임이 분명합니다. 사전식 조합 숫자를 계산하는 공식을 사용하면 사전식 순서의 숫자로 조합 벡터를 결정해야 하는 역 문제를 해결할 수 있습니다. 이러한 역 문제를 해결하려면 원하는 조합(C 1, ... C i, ... C m)의 벡터 요소에 대한 모든 알려지지 않은 값이 방정식 형식으로 작성되어야 합니다. )는 오른쪽의 조합 수에 집중되어 있으며 조합 수의 알려진 차이 L은 n 요소 각각 m과 필요한 조합 수 N의 왼쪽에 기록됩니다. 이 방정식에 대한 해법은 반복 중에 원하는 조합의 벡터 요소 값이 순차적으로 선택되는 다음과 같은 "탐욕스러운" 알고리즘에 의해 제공됩니다. 초기 반복에서는 C 1의 가능한 최소값(한계 내에서)이 선택되며, 여기서 오른쪽의 첫 번째 항은 L을 초과하지 않는 최대값을 갖습니다. 이제 L의 왼쪽은 선택한 C 1 값을 사용하여 오른쪽의 첫 번째 조합 수만큼 감소해야 하며, 마찬가지로 두 번째 반복에서 C 2 값을 결정해야 합니다. 마찬가지로, 원하는 조합의 다른 모든 요소 C i의 값을 마지막 요소 C m까지 선택하려면 모든 후속 반복을 수행해야 합니다. 명백한 이유로 마지막 요소 Cm의 값은 L의 왼쪽 잔차 값에 대한 조합 수의 동일성을 기반으로 결정될 수 있습니다. 조합 C m의 마지막 요소 값은 가능한 값을 열거하지 않고도 훨씬 더 간단하게 찾을 수 있다는 점에 유의해야 합니다. 고려된 알고리즘의 반복 구현은 다음 예에서 설명됩니다. 여기서 n=6이고 m=4인 경우 사전순으로 숫자 N=8의 조합을 결정해야 합니다. 사전순으로 주어진 숫자로 조합을 결정하는 알고리즘 기능은 다양한 방향으로 사용될 수 있습니다. 특히 사전순으로 조합을 나열하는 경우 이전에 얻은 조합으로의 반환을 보장해야 하며 해당 번호만 알면 충분합니다. 또한 임의의 순서로 조합을 생성하는 것이 가능해지며, 이는 임의로 주어진 사전 번호 순서에 따라 규제됩니다. 이제 사전순으로 조합을 생성하는 알고리즘을 제시합니다. 2 for i:= 1 to k do A[i] := i; 5 쓰기 시작(A, …, A[k]); 6 A[k] = n이면 p:= p 1이면 p:= k; 8 for i:= k 아래로 p do A[i] := A[p] + i p + 1 반복 요소와의 조합 모든 요소가 다른 기존 조합과 달리 반복 조합은 유한 집합의 요소를 순서 없이 선택하는 방식으로 구성되며, 여기서 모든 요소는 무한정 자주 나타날 수 있으며 반드시 단일 복사본에 존재할 필요는 없습니다. 이 경우 요소의 반복 횟수는 일반적으로 조합의 길이에 의해서만 제한되며 적어도 하나의 요소가 다른 조합은 다른 것으로 간주됩니다. 예를 들어, 1, 2, 3 세트에서 선택적으로 다른 숫자 4개를 선택하면 반복을 통해 다음과 같은 15가지 조합을 만들 수 있습니다. 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
일반적으로 반복이 포함된 조합은 임의 유형의 n개 요소를 선택하여 구성할 수 있습니다. 그러나 항상 1부터 n까지 연속된 자연수와 연관될 수 있습니다. 그런 다음 이 범위에서 선택적으로 다른 숫자 m의 조합을 벡터 형식으로 작성할 수 있으며 왼쪽에서 오른쪽으로 감소하지 않는 순서로 정렬할 수 있습니다. 당연히 이러한 형식의 표기법을 사용하면 무제한 반복 가능성으로 인해 모든 인접 요소가 동일할 수 있습니다. 그러나 m만큼 n개의 요소가 반복되는 각 조합 벡터는 다음과 같이 구성되는 (n+m−1)개의 요소가 m만큼 반복되는 조합 벡터와 연관될 수 있습니다. 벡터 f의 요소 값에 대해 벡터 C의 요소는 서로 다르며 1에서 (n+m1)까지 값의 오름차순으로 엄격하게 정렬된다는 것이 분명합니다. : 결합 벡터 f와 C의 요소 사이에 일대일 대응이 존재하면 n 요소가 m만큼 반복되는 조합을 체계적으로 나열하기 위한 다음과 같은 간단한 방법을 제안할 수 있습니다. 예를 들어 m의 (n+m1) 요소의 모든 C 조합을 사전순으로 나열하고 다음 공식을 사용하여 각 요소를 반복 f를 사용하여 해당 조합 요소로 순차적으로 변환하면 됩니다. 그 결과, 요소가 반복되는 조합의 벡터 시퀀스가 형성되며, 요소의 반복 없이 해당 조합을 나열하여 생성된 순서대로 배열됩니다. 특히 위의 3자리 1, 2, 3의 조합을 4자리의 반복으로 얻기 위해서는 6자리의 1,2,3,4, 5의 반복이 없는 모든 조합을 사전순으로 나열해야 한다. 6은 각각 4자리이므로 표시된 대로 변환합니다. 다음 예에서는 (1,3,4,6) 조합과 사전식 숫자 8의 변환을 보여줍니다. 요소의 반복이 있는 조합과 없는 조합 간의 일대일 대응을 고려한다는 것은 해당 집합이 똑같이 강력하다는 것을 의미합니다. 따라서 일반적인 경우 n개의 요소가 m만큼 반복되는 조합의 수는 (n+m1)개의 요소가 m만큼 반복되지 않는 조합의 수와 동일하다. 반복 f가 있고 반복 C가 없는 조합의 수를 나타내기 위해 동일한 기호를 사용하면 이 동등성은 다음과 같이 작성할 수 있습니다. 위에서 고려한 예에서 n=3이고 m=4인 경우 반복 조합 수가 15와 같으며 이는 직접 나열 결과와 일치한다는 것을 쉽게 확인할 수 있습니다. 기존 버전과 달리 반복 n과 m이 포함된 조합 매개변수의 값은 서로 직접적으로 관련되지 않으므로 양수 값의 모든 조합에 대해 f(n,m)>0이라는 점에 유의해야 합니다. 해당 경계 조건은 (n+m1)과 (n1) 또는 (n+m1)과 m 값 사이의 동일성으로 결정됩니다. m이 1과 같으면 요소의 반복이 불가능하므로 n>0의 양수 값에 대해 다음 동등성이 참이 된다는 것도 매우 분명합니다. 또한, n과 m의 임의의 양수 값에 대한 반복이 있는 조합의 수에 대해 다음과 같은 반복 관계가 유효하며, 이는 요소의 반복이 없는 조합의 수에 대한 덧셈 항등식과 유사합니다. 실제로, 왼쪽과 오른쪽에 반복 없이 해당 조합 수를 형식적으로 대체하면 표시된 덧셈 항등식으로 변합니다. 고려된 반복 관계는 팩토리얼 곱을 계산하는 노동 집약적인 작업을 제거하고 이를 보다 간단한 덧셈 작업으로 대체하는 것이 중요한 경우 반복이 있는 조합 수를 효과적으로 결정하는 데 사용될 수 있습니다. 이 경우 f(n,m)의 값을 계산하려면 f(1,m) 및 f(i,1) 형식의 항의 합을 얻을 때까지 이 반복 관계만 적용하면 됩니다. 여기서 i n에서 1까지의 범위의 값을 취합니다. 양의 정의에 따르면 이러한 항은 각각 1과 i와 같습니다. 다음 예에서는 n=3 및 m=4인 경우에 이 변환 기술을 사용하는 방법을 보여줍니다. 바이너리 조합 나열 하드웨어에서 조합을 구현하거나 어셈블리 언어로 프로그래밍할 때 조합 기록을 바이너리 형식으로 처리할 수 있는 것이 중요합니다. 이 경우 m의 n개 요소 조합은 n비트 이진수(Bn,...Bj,...B1) 형식으로 지정되어야 합니다. 여기서 m 단위 숫자는 해당 요소를 나타냅니다. 조합이고 나머지(nm) 자리는 0 값을 갖습니다. 분명히 이러한 형식의 표기법을 사용하면 1의 숫자 배열이 서로 다른 조합이 달라야 하며 n 비트 이진 집합에서 m개의 1 또는 (nm)개의 0을 배열하는 방법은 C(n,m)뿐입니다. 예를 들어, 다음 표에는 임의 집합(E 1 , E 2 , E 3 , E 4 )의 4개 요소의 모든 조합에 대해 2에 의한 4비트 이진수를 제공하는 6개의 이진 조합이 모두 나열되어 있습니다. 일반적으로 이러한 이진 조합을 열거하는 작업은 m 1 비트와 (nm) 0 비트의 서로 다른 배열을 가진 모든 n 비트 이진 집합을 체계적으로 검색하는 것으로 귀결됩니다. 가장 간단한 형태로, 이러한 검색은 인접한 비트를 시프트로 전치하는 다양한 방법(양성 시프트 알고리즘)으로 구현됩니다. 이는 반복 알고리즘이며 해당 이름은 각 단계에서 수행되는 작업의 특성을 반영합니다. 전치 이동 알고리즘의 반복 절차는 이진 집합으로 시작하는 이진 조합 시퀀스를 형성합니다. 여기서 모든 값은 낮은 순서의 숫자(오른쪽)에 집중되어 있고 모든 1이 높은 순서의 숫자에 있을 때 끝납니다( 왼쪽에): 초기 및 최종 조합에서는 일치하지만 이러한 시퀀스는 중간 바이너리 집합이 나열되는 순서가 다릅니다. 그러나 모든 경우에 각 후속 이진 조합은 해당 전치 및 이동 작업을 수행한 결과 이전 조합에서 형성됩니다. 동시에 다양한 전치 이동 알고리즘은 전치를 위한 비트 쌍과 이동을 위한 비트 그룹을 선택하는 방식이 다릅니다. 이 특이성은 왼쪽 및 오른쪽 시프트가 있는 전치 알고리즘에 대해 아래에서 설명됩니다. 왼쪽 시프트가 있는 전치 알고리즘에서는 각 단계에서 가장 왼쪽 숫자 쌍 01을 10(전치)으로 바꾸고 선행 단위 숫자 그룹(있는 경우)을 해당 숫자에 가깝게 이동하여 현재 조합에서 다음 이진 조합을 얻습니다. 조옮김(시프트) 후에 얻은 쌍 10입니다. 이 경우 현재 이진 조합의 선행 숫자에 단위가 없으면 이 단계에서 전치 후 선행 단위를 얻은 경우에도 이동이 수행되지 않습니다. 전치 후 얻은 쌍 10 이전의 최상위 비트에 0이 없는 경우에도 시프트가 수행되지 않습니다. 고려된 작업은 이 알고리즘의 두 번의 연속 반복을 수행하는 다음 예에 의해 설명됩니다. 여기서 한 반복(15)에서는 전치(T")만 수행되고 다른 반복(16)에서는 전치가 시프트(16)로 보완됩니다. T"+S"): 오른쪽 시프트 전치 알고리즘에서는 각 단계에서 개념적으로 유사한 단계가 수행됩니다. 전치만이 01의 가장 오른쪽 비트가 (가장 왼쪽 비트 대신) 10으로 대체되고 그 오른쪽에 있는 모든 비트가 최하위 비트로 이동되도록 보장합니다. 이전과 마찬가지로 오른쪽으로 이동 가능한 유닛이 있을 경우에만 이동이 수행됩니다. 고려된 작업은 이 알고리즘의 두 번의 연속 반복을 수행하는 다음 예에 의해 설명됩니다. 여기서 한 반복(3)에서는 전치(T")만 수행되고 다른 반복(4)에서는 전치가 시프트( T"+S"): 이진 조합이 기본 2 수 체계에서 정수로 해석되는 경우 두 알고리즘의 반복이 덧셈 형식으로 작성될 수 있다는 점에 유의해야 합니다. 특히 오른쪽 시프트가 있는 전치 알고리즘의 경우 다음 각 이진 조합(B" n ,…B" j , …B" 1)은 다음 덧셈 공식을 사용하여 정수를 더하는 연산을 수행하여 현재 조합(B n,…B j,…B 1)에서 항상 얻을 수 있습니다. 이 덧셈 공식에서 2의 거듭제곱 f와 t의 지수는 각각 현재 이진 조합의 하위 0 자리 수와 그 왼쪽 행에 있는 1의 수를 나타냅니다. 예를 들어, n=6자리의 네 번째 이진 조합(001110)의 경우 f =1 및 t =3입니다. 따라서 반복 5에서 덧셈 공식을 사용하여 다음 이진 조합을 계산하면 전치 및 이동 작업을 수행하는 것과 동일한 다음 결과가 제공됩니다. 왼쪽 및 오른쪽 이동을 사용하여 고려된 전치 알고리즘을 비교 분석하려면 반복에서 생성되는 이진 조합의 시퀀스를 비교하는 것이 좋습니다. 다음 표는 각각 왼쪽(TSL) 및 오른쪽(TSR) 시프트 알고리즘으로 얻은 2개의 4개 요소의 이진 조합 시퀀스 2개를 보여줍니다. 이 2개의 시퀀스를 비교해 보면 역미러임을 알 수 있습니다. 이는 시퀀스의 서로 반대쪽 끝에서 동일한 거리에 있는 두 개의 이진 조합이 서로의 거울 이미지라는 것을 의미합니다. 즉, 비트의 인덱싱이 반전될 때 일치합니다. 예를 들어, TSL 시퀀스의 시작 부분(0101)에서 두 번째 바이너리 패턴은 TSR 시퀀스의 끝 부분에서 두 번째인 바이너리 패턴(1010)의 거울 이미지이다. 일반적으로 한 시퀀스의 번호 i를 갖는 모든 이진 조합은 다른 시퀀스의 번호 (ni+1)를 갖는 이진 조합의 거울상입니다. 이러한 시퀀스 간의 이러한 관계는 이진 조합을 열거하기 위해 고려된 두 가지 알고리즘의 전치 및 이동 작업의 대칭적 특성의 결과입니다. 요소가 반복되는 조합을 기록하는 데에도 이진 형식을 사용할 수 있다는 점에 유의해야 합니다. 이를 위해서는 반복이 있는 조합과 이진 조합 사이에 일대일 대응 관계를 확립하는 것이 필요하며, 이는 다음과 같이 구성된다. 생성 세트의 n개 요소 중에서 선택적으로 다른 m개 요소를 선택하여 얻어지는 반복을 통한 임의의 조합이 있다고 가정합니다. 원하는 일치 항목을 설정하려면 먼저 구성 세트(cat)의 모든 요소를 조합에 추가한 다음 모든 동일한 요소가 나란히 있도록 결과 연결(sort)을 정렬해야 합니다. 결과는 동일한 요소로 구성된 n 그룹이 있는 (n+m) 요소의 시퀀스입니다. 요소 사이에는 총 (n+m1)개의 간격이 있으며, 그 중 동일한 요소 그룹 간에는 (n1)개의 간격이 있고 그룹 내 요소 간에는 m개의 간격이 있습니다. 명확성을 위해 표시된 공간에 "|" 기호를 배치할 수 있습니다. 그에 따라. 이제 그룹 사이의 공백(|)에 1을 일치시키고 다른 모든 공백()에 0을 일치시키면 이진 조합을 얻게 됩니다. 이는 (n+m1) 비트의 이진 집합으로 구성됩니다. 여기서 (n1)은 1이고 m은 0 비트이며, 그 위치는 요소 n에서 m까지 반복되는 원래 조합에 고유하게 해당합니다. 고려된 변환 기술은 처음 5개의 라틴 문자의 생성 세트에서 요소가 선택되는 반복 조합(BBD)을 사용하여 이진 조합(1001101)을 구성하는 다음 예에 의해 설명됩니다. 일반적으로 이러한 이진 집합의 수는 (n+m1) 이진수에서 (n1)개의 1(또는 m개의 0)을 배열하는 방법의 수를 결정합니다. 이 값은 분명히 (n+m1)에서 (n1) 또는 m으로 이루어진 조합의 수, 즉 C(n+m1,n1) 또는 C(n+m1,m)과 같습니다. n개 요소의 반복 f(n,m)을 사용한 조합 수, 각각 m. 따라서 반복이 있는 조합과 이진 조합 사이에 일대일 대응이 있으면 예를 들어 왼쪽 또는 오른쪽 시프트가 있는 전치 알고리즘을 사용하여 반복이 있는 조합의 열거를 이진 조합의 열거로 줄이는 것이 타당합니다. 그런 다음 결과 바이너리 조합을 사용하여 반복을 통해 필요한 조합을 복원하기만 하면 됩니다. 이 작업은 항상 다음 복구 기술을 사용하여 수행할 수 있습니다. m개의 반복 조합이 반드시 다른 요소를 형성할 필요는 없는 요소로부터 기본 세트를 임의의 방식으로 정렬하여 각 요소가 1에서 n까지의 특정 일련 번호를 갖도록 합니다. 또한 (n+m1) 이진수 조합의 열거를 구현해 보겠습니다. 여기서 (n1)은 1이고 m은 0입니다. 각각의 결과 이진 조합은 가상의 단위 숫자로 왼쪽에 보충될 수 있으며, 모든 단위 숫자는 1부터 n까지의 정수를 사용하여 왼쪽에서 오른쪽으로 번호가 매겨질 수 있습니다. 그런 다음 이진 조합의 각 i 번째 단위 이후 행의 0 수는 해당 조합의 반복 조합에서 기본 집합의 i 번째 요소 인스턴스 수와 같습니다. 고려된 기술은 다음 예에서 설명됩니다. 여기서 이진 조합(1001101)을 사용하여 BBD의 반복 조합이 복원됩니다. 해당 요소는 알파벳 순서로 작성된 처음 5개 라틴 문자의 생성 세트에서 선택됩니다. , 윗줄은 이 조합에 없는 요소를 나타냅니다. 이 예의 조건에서 유사한 작업을 수행하면 7비트 이진 집합을 구성하는 35개의 이진 조합(여기서 4개의 1과 3개의 0이 있음)을 모두 나열하고 3의 5개 요소를 반복하여 해당 조합을 복원할 수 있습니다. 겨울이 다가오고 있었고 Khoma와 Suslik은 완두콩을 비축하기로 결정했습니다. 그들은 하루 종일 헛간으로 달려가서 꼬투리 여러 개를 들고 다녔습니다. 코마(4개)와 수슬릭(2개)이었습니다. 저녁이 되자 그들은 수확한 모든 꼬투리의 수를 세었고 이제 이 완두콩을 어떻게 나눌지 궁금해했습니다. Khoma는 Suslik보다 한 번에 두 배의 양을 끌면 완두콩의 두 배를 얻어야한다고 주장했습니다. Suslik은 이에 대해 합리적으로 반대했습니다. 첫째, Khoma의 속도는 Suslik의 속도보다 눈에 띄게 낮고, 둘째, Khoma는 한두 번만 도망갔고 나머지 시간은 유휴 상태였을 것입니다... 친구들이 이 어려운 상황을 조금이라도 이해할 수 있도록 도와주세요. Suslik이 가져온 포드 수와 Khoma 수에 대한 가능한 모든 옵션을 결정합니다. 첫 번째 줄에는 자연 짝수 M(훔친 꼬투리 수, 2 ≤ M ≤ 1000)이 있습니다. Suslik과 Khoma가 가져온 포드 수량의 가능한 모든 조합(한 줄에 하나씩). 각 조합은 공백으로 구분된 두 개의 음수가 아닌 정수를 나타냅니다. 첫 번째 숫자는 Suslik이 가져온 포드 수이고, 두 번째 숫자는 Khoma가 가져온 포드 수입니다. 첫 번째 숫자의 내림차순으로 조합을 정렬합니다. #포함하다 네임스페이스 std 사용; 정수 메인()( 정수 a, b = 0; 신 >> ; 동안 (a >= 0 ) ( 시합<<
a
<<
" "
<<
b
<<
"\n"
;
a -= 4 ; b += 4 ; 0을 반환합니다; a를 Homa가 가져온 Pod 수, b를 Suslik이 가져온 Pod 수라고 하겠습니다. 문제의 조건에 따라 Khoma는 4개의 꼬투리만을 운반했기 때문에 Suslik과 Khoma가 가져온 꼬투리 수의 가능한 모든 조합을 열거하기 위해 a = a-4 및 b = b + 4를 고려합니다. 루프도 사용해보자 ~하는 동안, 이는 \geq 0이 될 때까지 위에서 설명한 작업을 반복합니다. 대답에서 우리는 친구가 가져온 포드 수의 가능한 모든 조합을 한 줄에 하나씩 인쇄하고 첫 번째 숫자의 내림차순으로 정렬합니다. 예 // 52개 중 3개의 조합 for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
여기서 우리는 RuNet에서 찾을 수 없는 더 복잡한 문제를 살펴보겠습니다(단, 하나의 링크를 제공하지만 해당 공식은 분명히 올바르지 않습니다). 조합 자체(이 경우에는 일련의 세 개의 숫자) 해당 색인을 찾습니다. 명확성을 위해 i1 = 3, i2 = 7, i3 = 12를 순서대로 가정해 보겠습니다. 일반적인 생성 알고리즘은 52개 중 2개의 조합을 생성하고 중첩 루프의 각 조합에 대해 50개 중 3개의 조합을 생성하고 중첩된 조합의 인덱스(i3, i4, i5)가 올바른지 확인하는 것입니다. 외부 조합에서 인덱스(i1, i2)와 일치하지 않음: C++ 코드 // 외부 조합 for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
C++ 코드 if (i3 >= i1) --i3; if (i3 >= i2) --i2; // i4, i5와 유사 2, 3, 47로 인덱스를 분할하는 예제 코드 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // 52개 중 2개 조합의 인덱스에 C(3, 50)을 곱한 값 int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // 번호가 0...49가 되도록 내부 그룹을 "재인덱싱"합니다. if (i3 > = i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5 ; if (i5 >= i2) --i5; // 이제 조합의 인덱스를 3으로 추가합니다. // 0: // SUM for n = 0 by i3-1 COMBINATIONS (2, 49-n) // = SUM m = 50-i3 x 49 (m * (m-1) / 2) 오프셋 += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // n에 대한 SUM = i3+1 ~ i4-1 조합 (1, 49-n) 오프셋 += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // n에 대한 SUM = i4+1 ~ i5-1 (1) 오프셋 + = (i5 - i4 - 1); 오프셋 반환 ; ) 일반적으로 조합 알고리즘을 다음 클래스로 나눕니다. 조합 수 콤비네이션~에서 N에 의해 케이세트라고 함 케이데이터에서 선택된 요소 N강요. 구성 요소가 아닌 요소의 순서만 다른 세트는 동일한 것으로 간주됩니다. 이것이 바로 조합이 배치와 다른 이유입니다. 조합 수 N에 의해 케이
이항 계수와 같음 고정된 값의 경우 N반복을 통해 여러 조합의 함수 생성 N에 의해 케이이다: 반복이 있는 조합 수의 2차원 생성 함수는 다음과 같습니다. 위키미디어 재단. 2010. 70 칠십 67 68 69 70 71 72 73 40 50 60 70 80 90 100 인수분해: 2×5×7 로마 표기법: LXX 이진수: 100 0110 ... 위키피디아 빛번호(Light Number), 외부를 고유하게 표현하는 조건부 숫자 촬영 중 조건(일반적으로 피사체의 밝기와 사용된 사진 재료의 감광성). E.h.의 값은 여러 번 선택할 수 있습니다. 조합 조리개 번호... ... 큰 백과사전 폴리테크닉 사전 단일 개체 및 여러 개체와 관련하여 두 개체를 구별하는 숫자 형식입니다. 이 형식은 현대 러시아어에는 존재하지 않지만 그 영향의 잔재는 남아 있습니다. 그래서 두 테이블의 조합(복수형 참조... ... 언어 용어 사전 조합 수학, 조합론, 주어진 규칙에 따라 특정, 일반적으로 유한 집합의 요소를 선택하고 배열하는 문제를 해결하는 데 전념하는 수학 분야입니다. 각각의 규칙에 따라 구성 방법이 결정됩니다... ... 수학백과사전 조합론에서 by의 조합은 서로 다른 요소를 포함하는 주어진 집합에서 선택된 요소 집합입니다. 요소의 순서만 다른 세트(구성은 아님)는 동일한 것으로 간주됩니다. 이러한 조합은 ... ... Wikipedia 발생 여부가 확실하게 알려지지 않은 사건 연구에 참여했습니다. 사건의 확률에 수치적 값을 할당하는 것이 종종 불필요하더라도 이를 통해 다른 사건과 비교하여 일부 사건의 발생을 예상하는 것이 합리성을 판단할 수 있습니다. 콜리어의 백과사전 1) 수학적 조합 분석과 동일합니다. 2) 특정 조건에 따라 주어진 유한한 객체 집합으로 구성될 수 있는 조합의 수를 연구하는 것과 관련된 초등 수학의 한 부분입니다.... 위대한 소련 백과사전 - (그리스어 역설 예상치 못한, 이상한) 넓은 의미에서: 일반적으로 받아들여지고 확립된 의견과 급격히 다른 진술, "무조건적으로 옳은" 것처럼 보이는 것에 대한 거부; 더 좁은 의미에서는 두 가지 반대 진술이 있습니다. ... ... 철학백과사전 -(또는 포함 및 제외의 원리) 일반적으로 서로 교차할 수 있는 유한 수의 유한 집합의 합집합의 카디널리티를 결정할 수 있는 조합 공식 ... Wikipedia 주어진 객체를 알려진 순서로 배포하는 다양한 방법의 수를 결정하는 것과 관련된 수학적 이론입니다. 방정식 이론과 확률 이론에서 특히 중요합니다. 이런 종류의 가장 간단한 작업은 다음과 같습니다. 백과사전 F.A. 브록하우스와 I.A. 에브론입력 데이터
산출
테스트
입력 데이터
산출
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
프로그램 코드
문제의 해결
조합지수
각 조합, 순열, 배열 및 기타 조합 개체는 인덱스와 연관될 수 있습니다. 이는 이 알고리즘을 반복할 때 나타나는 숫자입니다.
"head-on"을 검색하는 옵션이 있습니다. 조합 카운터를 켜고 위의 알고리즘을 사용하여 원하는 옵션에 도달할 때까지 모든 것을 시도합니다. 이 옵션은 시간 복잡도가 매우 높으므로 이 옵션을 삭제하겠습니다.
입력에 숫자 i1, i2, i3이 포함되어 있다고 가정해 보겠습니다. 우선, 우리는 그것들을 오름차순으로 배열해야 합니다. ("조합"이라는 개념 자체가 임의의 순서를 의미하지만 위에 주어진 생성 알고리즘 자체는 항상 순서대로 생성합니다.)
이는 i1이 0, 1, 2인 모든 조합을 "거쳤다"는 의미입니다.
i1 = 0인 경우 인덱스 i1, i2는 51개 숫자 중 2개의 모든 조합을 거치므로 C(2, 51) 조합을 거쳤습니다.
i1 = 1인 경우 C(2, 50)개의 조합을 거쳤습니다.
i1 = 2인 경우 C(2, 49) 조합을 거쳤습니다.
전체적으로 SUM(n = 0에서 n = i1-1) C(2, 51-n)을 거쳤습니다.
i1 = 3인 경우, 인덱스 i2를 실행하는 동안 겪은 조합을 고려해 보겠습니다(우리의 경우 i2 = i1+1 = 4로 시작함).
i2 = 4이면 C(1, 47)개의 조합이 통과되고, i2 = 5이면 C(1, 46)개의 조합이 통과되고, i2 = 6이면 C(1, 45)개의 조합이 통과됩니다.
완전히 비유하자면, i2 = 7인 경우 인덱스 i3이 통과한 조합을 고려합니다.
우리는 일반 공식을 얻습니다.
필요한 조합 지수 = SUM (n = 0 ~ i1-1) C(2, 51-n) + SUM (n = i1+1 ~ i2-1) C(1, 51-n) + SUM ( ~ n = i2+1 ~ i3-1)C(0, 51-n).부분집합 지수
조합론에는 하위 집합으로 분할하는 더 복잡한 개체가 있습니다. 예를 들어, 52개 요소 집합을 각각 2, 3, 47개 요소로 구성된 세 개의 하위 집합으로 분할하는 경우 각 하위 집합 내의 요소 순서는 중요하지 않습니다. (그런데, 52개 중 2개의 조합은 단순히 각각 2개 요소와 50개 요소로 구성된 두 개의 하위 집합으로 분할되는 특별한 경우입니다.)
다시 말하지만, 이러한 각 파티션에는 자체 인덱스가 있습니다.
조합 인덱스를 찾는 알고리즘을 수정하여 파티션 인덱스를 찾을 수 있다는 것이 밝혀졌습니다.
"외부 조합"의 인덱스 i1, i2를 서로 정렬하고 인덱스 i3, i4, i5를 서로 정렬해야 하지만 처음 두 개와는 독립적으로 정렬해야 한다는 점에 유의해야 합니다.
또한 "중첩 조합"에서는 본질적으로 50개 요소 세트로 작업하지만 인덱스 i3, i4, i5는 0에서 변경되지 않도록 특정 방식으로 "이동"해야 한다는 점도 고려해야 합니다. 51까지, 0부터 49까지:
(즉, 52개 요소 세트에서 인덱스 i1, i2를 잘라낸 다음 나머지 세트를 이동하여 구멍을 닫고 인덱스 i3-i5는 이동합니다.)
각 "외부" 조합 내에는 정확히 C(3, 50)개의 "중첩" 조합이 있다는 점을 고려해야 합니다.
그러면 알고리즘은 다음과 같이 축소됩니다.
COMBINATION_INDEX(i1, i2/52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX(인덱스 이동 후 i3, i4, i5/50). 알고리즘을 지속적으로 복잡하게 만들기
예를 들어, i1 = 0(n = 0에서 -1까지의 합 계산) 또는 i2 = 1(1에서 0까지 합 계산)인 경우 공식에서 "오류"가 발생한다는 점을 즉시 확인해야 합니다. 실제로 이러한 경우 해당 합계는 0과 같아야 하며 결과는 정확합니다.
또한 우리 알고리즘의 시간 복잡도에도 주의를 기울여야 합니다. C를 상수 시간으로 간주하면 알고리즘은 선형 복잡도를 갖습니다. 이것은 이미 무차별 대입보다 훨씬 낫습니다.
하지만 실제로는 (우리의 경우 52) 알고리즘을 지속적인 복잡성으로 줄이는 것을 방해하는 것은 없습니다. 이를 위해 우리는 수학 지식을 적용하고 모든 금액을 분석적으로 계산할 것입니다.
예를 들어, 수식 K의 형태로 "확장"하면 조합 수 C(2, K)! / ((K-2)! * 2!), 2차 다항식으로 축소됩니다. 그리고 합 기호 아래에 이 값이 있기 때문에 자연 계열 숫자의 N제곱합에 대한 공식을 적용할 수 있으며(Wikipedia 참조) 단일 3차 다항식을 얻을 수 있습니다. 분명히 일정한 시간 복잡도가 있습니다. (게다가 제가 자막 시작 부분에 언급한 "오류"는 어떤 식으로도 나타나지 않으며 공식은 그대로 유지됩니다.)
반복한다, 이것은 기본 세트의 고정된 치수의 경우. 그러나 메타프로그래밍의 도움으로 컴파일러가 이 작업을 수행하도록 "가르칠" 수 있다고 확신합니다. 후문
내 포커 시뮬레이터(텍사스 홀덤)에서 내 핸드 카드(2장)와 모든 플롭 카드(테이블 위의 카드 3장)의 가능한 모든 조합에 대해 미리 승리 확률을 계산하고 저장하고 싶었습니다. 52개 세트는 2, 3, 47개의 하위 세트로 구성됩니다.
계산되어 저장되었습니다.
그러나 특정 조합에 대해 파일에서 데이터를 읽어야 할 때가 되었을 때, 나는 오랫동안 무언가를 계산하거나 기가바이트 파일에서 검색하고 싶지 않았습니다. 이제 파일의 오프셋을 결정하고 필요한 내용을 직접 읽습니다.
순열, 조합, 배치, 하위 집합, 반복이 있는 조합, 반복이 있는 배치를 포함하여 모든 조합 개체에 대한 조합 알고리즘에 대한 참고서를 갖는 것은 흥미로울 것입니다. 명시적 수식
연결
다른 사전에 "조합 수"가 무엇인지 확인하십시오.
서적