영-피보나치 격자

Young–Fibonacci lattice
영-피보나치 그래프, 영-피보나치 격자의 하세 도표.

수학에서 영-피보나치 그래프와 영-피보나치 격자는 알프레드 영과 레오나르도 피보나찌의 이름을 딴 두 개의 밀접하게 연관된 구조물이다.이러한 유형의 모든 숫자 시퀀스에는 순위를 할당할 수 있다. 예를 들어 11212의 순위는 1 + 1 + 2 + 1 + 2 + 2 = 7. 고대 인도에서 이미 알려진 바와 같이 주어진 순서의 수는 피보나치 숫자다.영-피보나치 격자는 이러한 자릿수 순서를 요소로 하는 무한 모듈형 격자로, 이 순위 구조와 호환된다.Young-Fibonacci 그래프는 이 격자의 그래프로, 각 자릿수 순서에 대한 꼭지점이 있다.모듈형 격자의 그래프로서 모듈형 그래프다.

영-피보나치 그래프와 영-피보나치 격자는 모두 포민(1988)과 스탠리(1988)에 의해 두 개의 논문에서 처음 연구되었다.그들은 영의 격자와 어떤 계급에서도 그들 원소의 피보나치 수에서 따온 이름이다.

지정된 순위의 숫자 시퀀스

랭크 r이 있는 자릿수 순서는 랭크 r - 2의 순서에 숫자 2를 추가하거나, 숫자 1을 r - 1의 순서에 추가하여 구성할 수 있다. 만약 f(r)가 해당 랭크의 다른 자릿수 순서의 수에 r을 매핑하는 함수라면 f(r) = f(r - 2) + f(r - 1) 피보나치 n을 정의하는 재발 관계 f(r - 1)를 만족한다.탯줄, 그러나 초기 조건이 약간 다른 경우: f(0) = f(1) = 1(랭킹 0 문자열 1개, 빈 문자열 1개, 한 자리 1개로 구성됨)이러한 초기 조건은 f의 값의 순서를 피보나치 수에서 한 위치만큼 이동하게 한다: f(r) = Fr + 1. 여기서i F는 ith 피보나치 수를 나타낸다.

고대 인도 프로소디 연구에서는 피보나치 숫자를 사용하여 주어진 총 길이를 가진 짧은 음절과 긴 음절의 순서의 수를 세었다. 숫자 1이 짧은 음절에 해당하고 숫자 2가 긴 음절에 해당하면 숫자 시퀀스의 순위는 해당 순서의 총 길이를 측정한다.음절의자세한 내용은 피보나치 번호 문서를 참조하십시오.

숫자 시퀀스 그래프

영-피보나치 그래프는 무한 그래프로서, 숫자 "1"과 "2"(빈 문자열 포함)의 각 문자열에 대한 꼭지점이 있다.문자열의 이웃은 다음 작업 중 하나에 의해 s에서 형성된 문자열이다.

  1. "1"을 가장 왼쪽 "1" 앞에 있는 s에 삽입하십시오(또는 "1"을 아직 포함하지 않은 경우 s의 아무 곳이나).
  2. 의 가장 왼쪽 "1"을 "2"로 변경한다.
  3. s에서 가장 왼쪽 "1"을 제거한다.
  4. 왼쪽에 "1"이 없는 "2"를 "1"로 변경한다.

각 연산을 반전시킬 수 있는지 확인하는 것은 간단하다. 연산 1과 연산 3은 연산 2와 4와 마찬가지로 서로 역행한다.따라서 결과 그래프는 방향을 전환하지 않은 것으로 간주할 수 있다.단, 일반적으로 각 가장자리가 하위 등급의 꼭지점에서 상위 등급의 꼭지점까지 연결되는 방향의 악순환 그래프로 간주된다.

포민(1988)과 스탠리(1988)가 모두 관찰하듯이 이 그래프에는 다음과 같은 속성이 있다.

  • 연결됨: 비어 있지 않은 문자열은 어떤 작업에 의해 순위가 감소될 수 있으므로, 빈 문자열에서 빈 문자열로 이어지는 일련의 작업이 있으며, 이는 빈 문자열에서 다른 모든 꼭지점까지의 그래프에 방향 경로를 제공한다.
  • 그것은 순위 구조와 호환된다: 모든 지시된 경로는 끝점의 순위 차이와 길이가 같다.
  • u와 v가 구별되는 두 개의 노드마다 u와 v의 공통적인 즉시 이전 노드 수는 u와 v의 공통 즉시 후임자 수와 같으며, 이 숫자는 0 또는 1이다.
  • 모든 꼭지점의 도수는 1에 그 도수를 더한 것과 같다.

포민(1988)은 이러한 속성을 가진 그래프를 Y-그래프라고 부르고, 스탠리(1988)는 이러한 속성들의 약한 버전을 가진 그래프를 차등 포셋의 그래프로 부른다.

부분순서 및 격자구조

영-피보나치 그래프의 전이적 폐쇄는 부분 순서다.스탠리(1988)가 보여주듯이, 어떤 두 꼭지점 x와 y는 이 순서(그들의 만남)에 있어서 독특한 가장 큰 공통의 전임자(그들의 만남)와 독특한 최소 공통의 후계자(그들의 합류)를 가지고 있으므로, 이 순서는 영-피보나치 격자(Young-Fibonacci lattice)라고 불리는 격자(Lattice)이다.

x와 y의 만남을 찾기 위해 먼저 x와 y 중 하나가 다른 것의 이전 버전인지 여부를 시험할 수 있다.문자열 x는 x와 y의 가장 긴 공통 접미사를 제거한 후 y에 남아 있는 "2"자리의 숫자가 공통 접미사를 제거한 후 x에 남아 있는 모든 자릿수의 숫자만큼 큰 경우 정확히 이 순서로 다른 문자열 y의 이전 버전이다.x가 이 테스트에 따라 y의 전임자인 경우 이들의 만남은 x이고, 마찬가지로 y가 x의 전임자인 경우 이들의 만남은 y이다.두 번째의 경우, x와 y가 다른 것의 전신이 아니지만, 둘 중 하나 또는 둘 다 "1"자리로 시작하는 경우, 이러한 초기 자릿수를 제거하면 만남은 변경되지 않는다.그리고 마지막으로 x와 y가 모두 숫자 "2"로 시작하는 경우, x와 y의 만남은 둘 다에서 이 숫자를 제거하고, 결과적인 접미사의 만남을 찾아내고, "2"를 다시 시작에 추가함으로써 찾을 수 있다.

x와 y의 공통 후계자(최소 공통 후계자는 아님)는 x와 y의 길이가 같은 "2"자리의 문자열을 취함으로써 찾을 수 있다.가장 흔하지 않은 후계자는 x와 y의 공통 후계자, 그리고 이 "2"의 선행자인 미세하게 많은 현들의 만남이다.

스탠리(1988)가 추가로 관찰했듯이 영-피보나치 격자는 모듈형이다.포민(1988)은 그것이 분배적이라고 잘못 주장하지만, {21,221,121,211,221} 현에 의해 형성된 하위 격자는 분배 격자에서 금지된 다이아몬드 하위 격자를 형성한다.

참조

  • Fomin, S. V. (1988), "Generalized Robinson–Schensted–Knuth correspondence", Journal of Mathematical Sciences, 41 (2): 979–991, doi:10.1007/BF01247093. 자피스키 나우치니크 세미나ov 레닌그라드스코고 Otdelenya Matematiceskogo Instituta에서 번역. V. A. Steklova AN SSSR155: 156–175, 1986.
  • Stanley, Richard P. (1988), "Differential posets", Journal of the American Mathematical Society, 1 (4): 919–961, doi:10.2307/1990995, JSTOR 1990995.