메네지 문제

결합수학에서는 남녀가 교대하지 않고 그/그녀의^[1] 파트너 옆에 아무도 앉지 않도록 남녀 커플을 원형 식탁에 앉힐 수 있는 다양한 방법을 요구한다.이 문제는 1891년 에두아르 루카스에 의해 공식화되었고 몇 년 전, 매듭 이론과 관련하여 피터 거스리 타이트에 의해 독자적으로 만들어졌다.^[2]3, 4, 5, ... 커플들의 경우 좌석 배치의 수는 다음과 같다.

12, 96, 3120, 115200, 5836320, 382072320, 3148549120, ...(OEIS의 후속 A059375).

수학자들은 이러한 숫자와 관련된 숫자의 시퀀스를 계산하기 위해 공식과 반복 방정식을 개발했다.예절과 매듭 이론에 대한 그들의 적용과 함께, 이 숫자들은 또한 그래프 이론의 이론적 해석을 가지고 있다: 그들은 특정한 그래프 패밀리의 일치와 해밀턴의 주기를 세는 것이다.

터치아드의 공식

M은_n n쌍을 위한 좌석 배치의 수를 나타내도록 한다.Touchard(1934)는 공식을 도출했다.

${\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n(1)^{k}{\frac {2n}{2n-k}{2n-k}{2n-k \k \k}(n-k) 선택!}$

많은 후속 작업은 이 공식에 대한 대안적인 증명과 문제의 다양한 일반화된 버전으로 들어갔다.

체비셰프 다항식(Cebyshev polyomials of first class)과 관련된 M의_n 다른 탯줄 공식은 와이먼&모저(1958)가 주었다.

메니지 번호 및 여성 우선 솔루션

여성을 앉히는 방법은 2×n!이 있다. 여성들을 위해 두 세트의 좌석이 있고, 특정한 세트의 좌석에 그들을 앉히는 방법은 n!이 있다.여성을 위한 좌석 배치마다,

${\displaystyle A_{n}=\sum _{k=0}^{n(1)^{k}{\frac {2n}{2n-k}{2n-k}}{2n-k \선택 k}(n-k)!}$

남자들을 앉히는 방법; 이 공식은 단순히 Touchard의 공식에서 2×n! 인자를 생략한다.결과적으로 더 작은 숫자(again, n = 3)

1, 2, 13, 80, 579, 4738, 43387, 439792, ...(OEIS에서 연속 A000179)

메니지 수라고 불린다.인자 ${\displaystyle \frac{\mathrm{2n}}{}}$ ${\displaystyle \frac{\mathrm{2n}}{}}$ -${\displaystyle \frac{k}{}}$( ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{2n}}{}}$- ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$) ${\$2n-k}}{$2n-k \선택$ k$}}}}$는 인접 좌석의 겹치지 않는 쌍을 형성하는 방법의 수 또는$$ 동등하게 2n 꼭지점의 주기 그래프에서 k 에지의 일치 수입니다.A에_n 대한 표현은 매칭의 각 가장자리의 끝점에 앉아 있는 사람들이 커플이 되어야 하는 약정에 포함-제외 원칙을 적용한 즉각적인 결과물이다.

보고르트&도일(1986년)의 작업이 있기 전까지, 메네지 문제에 대한 해결책은 먼저 여성들을 위한 모든 좌석 배치를 찾아낸 다음, 이러한 부분적인 좌석 배치 각각에 대해, 남성들을 그들의 파트너로부터 떨어져 앉힘으로써 그것을 완성하는 방법의 수를 계산하는 형태를 취했다.보고르트와 도일은 터치아드의 공식은 여성의 참여를 고려하기보다는 모든 좌석 배치를 한꺼번에 고려함으로써 직접 도출될 수 있다고 주장했다.^[3]그러나 키루시스&콘토게오르기우(2018)는 보고르트와 도일의 아이디어를 몇 가지 활용함으로써 위에서 설명한 훨씬 더 솔직한 여성 우선 해결책을 찾았다(비고문 언어로 주장을 되풀이하느라 신경을 썼다).

메니지 수치는 재발 관계를^[4] 만족시킨다.

${\displaystyle A_{n}=nA_{n-1}+{\frac{n-2}}A_{n-2}+{\frac{4(-1)^{n-1}{n-2}}:}$

그리고 더 간단한 4개월의 재발^[5].

${\displaystyle \displaystyle A_{n}=nA_{n-1}+2A_{n-2}-(n-4)A_{n-3}-A_{n-4},$

여기서부터 메니지 숫자 자체를 쉽게 계산할 수 있다.

그래프이론적 해석

메네지 문제에 대한 해결책은 크라운 그래프로 해밀턴의 주기 지시대로 그래프 이데아틱 용어로 해석될 수 있다.크라운 그래프는 완전한 양분 그래프 K에서_n,n 완벽한 일치를 제거하여 형성된다. 이 그래프는 두 가지 색의 정점 2n 정점을 가지고 있으며, 한 색의 정점 각각은 다른 색상의 정점 중 하나를 제외한 모든 정점에 연결된다.메네지 문제의 경우 그래프의 꼭지점은 남녀를 나타내며, 가장자리는 나란히 앉을 수 있는 남녀 쌍을 나타낸다.이 그래프는 모든 남자와 모든 여자를 연결하는 완전한 초당적 그래프에서 남녀 커플이 형성한 완벽한 매칭을 제거함으로써 형성된다.모든 유효한 좌석 배치는 그래프에서 해밀턴 사이클을 형성하는 테이블 주위의 순서대로 사람들의 순서로 설명될 수 있다.그러나 두 개의 해밀턴 사이클은 출발 정점에 관계없이 동일한 주기적 순서에 따라 동일한 정점을 연결하면 등가로 간주되는 반면, 메네지 문제에서는 출발 위치가 유의한 것으로 간주되는데, 앨리스의 티파티에서와 마찬가지로 모든 손님이 한 좌석씩 자리를 옮기면 다른 좌석으로 간주된다.g 배열은 같은 주기에 의해 설명된다 하더라도.따라서 크라운 그래프의 방향 해밀턴 주기 횟수는 좌석 배치 횟수보다 2n 배수로 적지만,^[6] 메니지 수보다는 (n - 1) 배수로 더 크다.이러한 그래프에서 사이클 수 순서는 다음과 같다(이전처럼 n = 3)

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (시퀀스 A094047 in OEIS).

문제에 대한 두 번째 그래프 이론적 설명도 가능하다.일단 여성이 착석한 후, 남은 남성들을 위한 가능한 좌석 배치는 완전한 초당적 그래프에서 하나의 해밀턴식 사이클을 제거함으로써 형성된 그래프에서 완벽한 일치로 묘사될 수 있다; 그래프는 개방된 좌석을 남성에게 연결하는 가장자리를 가지고 있고, 사이클의 제거는 남성들이 어느 한 쪽에도 앉는 것을 금지하는 것과 일치한다.그들의 아내와 인접한 열린 자리초당적 그래프에서 일치 항목을 계산하는 문제, 따라서 fortiori는 특정 0-1 행렬의 영속성을 사용하여 해결할 수 있다.메네지 문제의 경우, 이 문제의 견해에서 발생하는 행렬은 생성 행의 두 인접 요소를 제외한 모든 요소가 1인 순환 행렬이다.^[7]

매듭 이론

메네지 문제를 연구한 태트의 동기는 주어진 수의 교차점을 가진 수학 매듭의 완전한 목록을 찾으려고 노력한 데서 비롯되었다고 n은 말한다.매듭 다이어그램용 다우커 표기법에서는 매듭이 스스로 교차하는 2n 지점인 Tait에 의해 사용된 초기 형태는 1에서 2n까지의 2n 숫자로 표시되어 있다.축소된 다이어그램에서 교차점에서의 두 개의 라벨은 연속적일 수 없으므로, 매듭을 나타내기 위해 다우커 표기법에서 사용되는 각 교차점에서의 라벨 쌍 집합은 1 ~ 2n 범위의 모든 숫자에 대한 정점과 패리티가 다른 모든 수 쌍 사이의 에지를 갖는 그래프에서 완벽한 일치로 해석될 수 있다.비파괴 모듈로 2n 입니다.이 그래프는 완전 양분 그래프에서 해밀턴 사이클(연속 숫자 연결)을 제거하여 형성되며(모든 쌍의 패리티가 다른 숫자 연결) 따라서 메네지 숫자와 동일한 일치 수가 있다.교대 노트의 경우, 이 일치는 매듭 도표 자체를 설명하기에 충분하며, 다른 노트의 경우 교차하는 두 가닥 중 어느 가닥이 다른 가닥 위에 있는지 결정하기 위해 각 교차 쌍에 대해 추가 양 또는 음의 기호를 지정해야 한다.

그러나 매듭 목록 문제는 메니지 문제에 존재하지 않는 몇 가지 추가적인 대칭이 있다. 즉, 다른 교차점에서 라벨링을 시작하면 동일한 매듭 다이어그램에 대해 다른 다우커 표기법을 얻게 되며, 이러한 다른 표기법들은 모두 동일한 도표를 나타내는 것으로 계산되어야 한다.이 때문에 주기적인 순열에 의해 서로 다른 두 개의 성냥은 동등하게 취급하고 한 번만 세어야 한다.길버트(1956년)는 이 변형된 열거 문제를 해결하여, 서로 다른 일치의 수가 많다는 것을 보여주었다.

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ...(OEIS에서 연속 A002484).

참고 항목

• Oberwolfach 문제, 테이블에서 식사하는 사람들의 배열을 포함하는 다른 수학적 문제
• 프로블렘 데 렌컨텐트, 부분적 변색에 관련된 유사한 문제

메모들

참조

외부 링크

• Weisstein, Eric W. "Married Couples Problem". MathWorld.
• Weisstein, Eric W. "Laisant's Recurrence Formula". MathWorld.