랭퍼드 페어링

Langford pairing
n = 4를 위한 Langford 페어링.

결합수학에서, 랭포드 수열이라고도 하는 랭포드 쌍은 2n 번호 1, 1, 2, 2, ...n의 순열을 순열한 것으로, 두 개의 1s가 한 단위씩 떨어져 있고, 두 개의 2s는 두 단위씩 떨어져 있으며, 보다 일반적으로 각 숫자 k의 두 복사본은 k 단위씩 떨어져 있다.랭포드 쌍은 C의 이름을 따서 지어졌다.1958년 건설 문제를 제기한 더들리 랭포드.

랭포드의 문제는 주어진 n의 값에 대한 랭포드 쌍을 찾는 일이다.[1]

스콜렘 수열의[2] 밀접하게 관련된 개념은 동일한 방식으로 정의되지만, 대신 수열 0, 0, 1, 1, ..., n - 1, n - 1을 허용한다.

예

n = 3에 대한 Langford 페어링은 2, 3, 1, 2, 1, 3의 순서로 주어진다.

특성.

Langford 쌍은 n이 0 또는 3 modulo 4와 일치할 때만 존재한다. 예를 들어, n = 1, 2, 5일 때는 Langford 쌍이 없다.

n = 1, 2, …에 대한 서로 다른 Langford 쌍의 수는, 모든 시퀀스를 역순으로 계산하면,

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, … (OEIS에서 순서 A014552).

크누스(2008)가 기술한 바와 같이, 주어진 n에 대한 모든 랭포드 쌍을 나열하는 문제는 정확한 커버 문제의 한 예로서 해결할 수 있지만, n이 큰 경우에는 대수적 방법에 의해 해답의 수를 더 효율적으로 계산할 수 있다.

적용들

스콜렘(1957)은 스콜렘 시퀀스를 이용해 슈타이너 트리플 시스템을 구축했다.

1960년대에 E. J. 그로스는 Langford 쌍을 사용하여 정수 곱셈을 위한 회로를 구성했다.[3]

참고 항목

메모들

  1. ^ 크누스(2008); 가드너(1978).
  2. ^ 노르드 (2008)
  3. ^ 크누스(2008).

참조

  • Gardner, Martin (1978), "Langford's problem", Mathematical Magic Show, Vintage, p. 70.
  • Knuth, Donald E. (2008), The Art of Computer Programming, Vol. IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley, ISBN 978-0-321-53496-5.
  • Langford, C. Dudley (1958), "Problem", Mathematical Gazette, 42: 228.
  • Nordh, Gustav (2008), "Perfect Skolem sets", Discrete Mathematics, 308 (9): 1653–1664, arXiv:math/0506155, doi:10.1016/j.disc.2006.12.003, MR 2392605.
  • Skolem, Thoralf (1957), "On certain distributions of integers in pairs with given differences", Mathematica Scandinavica, 5: 57–68, MR 0092797.

외부 링크