피보나치어

피보나치 워드는 2진수(또는 두 글자 알파벳의 기호)의 특정 시퀀스다. 피보나치 단어는 피보나치 수가 반복적인 덧셈에 의해 형성되는 것과 같은 방식으로 반복된 결합에 의해 형성된다.

그것은 스터미어 단어의 패러다임적인 예로서 구체적으로는 형태적인 단어들이다.

'피보나치 단어'라는 명칭은 0의 문자열과 2개의 반복되지 않는 문자열로 구성된 정식 언어 L의 구성원을 가리키는 말로도 사용되어 왔다. 특정 피보나치 단어의 접두사는 L에 속하지만, 다른 많은 문자열도 마찬가지다. L은 각각의 가능한 길이에 대해 피보나찌의 멤버 수를 가지고 있다.

정의

$S{\displaystyle {}_{}}$ ${\$을 "0"으로$$ 하고 S ${\displaystyle {1\mathrm{}}_{}}$ ${\$}을 "01"로$$ 한다. 이제 ${\displaystyle {Sn}_{}{}_{}}$= ${\displaystyle {}_{}}$n - ${\displaystyle 1_{}}$ S ${\displaystyle n_{}}$- ${\displaystyle 2_{}}$ ${\$이전 순서와 그 이전의 순서의 연결).

무한 피보나치 워드는 한계 $∞{\$},$$즉 $유한{\displaystyle }$ n$$${\displaystyle$ $s_{$n$}$을 접두사로 하는 각 ${\displaystyle {Sn}_{}}$ ${\$displaystyle $s_${$n$를 포함하는 (유일) 무한 시퀀스다.

위 정의의 항목을 열거하면 다음과 같은 결과가 나온다.

${\displaystyle {S\mathrm{}}_{}}$ 0 ${\$ 0

${\displaystyle {S\mathrm{}}_{}}$ 1 ${\$01$$

${\displaystyle {S\mathrm{}}_{}}$ 2 ${\$}} 010$$

${\displaystyle {S\mathrm{}}_{}}$ 3 ${\$ 01001$$

${\displaystyle {S\mathrm{}}_{}}$ 4 ${\$ 01001010$$

${\displaystyle {S\mathrm{}}_{}}$ 5 ${\$ 0100101001$$

...

무한 피보나치 단어의 처음 몇 가지 요소는 다음과 같다.

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ... (sequence A003849 in the OEIS)

개별 자릿수에 대한 닫힘 형식 식

그 말의 n번째 숫자가 2+⌊ nφ ⌋ − ⌊(n+1)φ ⌋{\displaystyle 2+\left\lfloor{{n}\,\varphi}\right\rfloor -\left\lfloor{\left({n+1}\right)\,\varphi}\right\rfloor}이φ{\displaystyle \varphi}은 황금 비율과⌊)⌋{\displaystyle \left\lfloor x\right\rfloor}이 바닥 함수이다. (sOEIS의 등가 A003849). 그 결과 무한 피보나치 단어는 경사 $1{\displaystyle \mathrm{}}$ / ${\displaystyle /}$ ${\displaystyle 1/\phi }$ 또는$$ ${\displaystyle \mathrm{\varphi }}$- 1 ${\displaystyle \pi -1$}의 절단 시퀀스로 특징지어질 수 있다$.$ 위의 그림을 보라.

대체 규칙

S에서_n S로_{n + 1} 가는 또 다른 방법은 각 기호 0을 S에서_{nn + 1} 연속 기호 0의 쌍으로 교체하고, 각 기호 1을 S에서_{nn + 1} 단일 기호 0으로 교체하는 것이다.

또는 다음 프로세스에 의해 무한 피보나치 단어 전체를 직접 생성하는 것을 상상할 수 있다: 한 자리 0을 가리키는 커서로 시작한다. 그런 다음 각 단계에서 커서가 단어 끝에 0을 가리키면 1, 0을 추가하고 커서가 1을 가리키면 단어 끝에 0을 추가한다. 어느 경우든 커서를 오른쪽으로 한 위치 이동하여 단계를 완료하십시오.

토끼 시퀀스라고도 하는 유사한 무한 단어는 커서가 0, 1을 가리킬 때마다, 그리고 커서가 1, 추가 0, 1을 가리킬 때마다, 다른 대체 규칙을 가진 유사한 무한 프로세스에 의해 생성된다. 결과 시퀀스가 시작됨

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, ...

그러나 이 순서는 0s를 1초로 바꾸고 위치를 1로 바꾸는 등 사소한 것만으로 피보나치 단어와 다르다.

소위 토끼 시퀀스에 대한 닫힌 폼 표현식:

The n^th digit of the word is ${\displaystyle \left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1}$ where ${\displaystyle \varphi }$ is the golden ratio and ${\displaystyle \left\lfloor x\right\rfloor }$ is the floor function.

토론

이 단어는 귀납적 정의에서 정수의 추가가 끈 결합으로 대체된다는 의미에서 동명의 유명한 순서(피보나치 수열)와 관련이 있다. 이로 인해 S의_n 길이가 F_{n + 2}, (n + 2)번째 피보나치 수(Fibonacci number)가 된다. 또한 S에서_n 1의 수는 F이고_n S에서_n 0의 수는 F이다_{n + 1}.

기타 속성

• 무한 피보나치 단어는 주기적이지 않고 궁극적으로 주기적이지 않다.
• 피보나치 단어의 마지막 두 글자는 "01"과 "10"이 번갈아 나타난다.
• 피보나치 단어의 마지막 두 글자를 억압하거나, 마지막 두 글자의 보어 앞에 접두사를 붙이면 회문이 만들어진다. 예: 01 ${\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$ $$= 0101001010은 회문이다. 따라서 무한 피보나치 단어의 팔린드로믹 밀도는 1/2로 여기서 φ은 황금 비율: 이것은 주기적인 단어에 대해 가능한 가장 큰 값이다.^[2]
• 무한 피보나치 단어에서 0과 0의 비율과 마찬가지로 비율(글자 수)/(영점 수)은 is이다.
• 무한 피보나치 단어는 균형 잡힌 순서다. 피보나치 단어 어디든 같은 길이의 두 가지 요인을 취하라. 해밍 웨이트("1"의 발생 횟수)의 차이는 결코 1을 초과하지 않는다.^[3]
• 11과 000의 하위 단어는 결코 발생하지 않는다.
• 무한 피보나치 단어의 복잡함수는 n+1: 길이 n의 n+1 구별되는 하위단어를 포함한다. 예: 길이 3 : "001", "010", "100", "101"의 4개의 뚜렷한 하위 단어가 있다. 또한 비주기적이기 때문에, 그것은 "최소한의 복잡성"을 가지고 있고,^[4] 따라서 $기울기{\displaystyle \mathrm{}}$ 1 /${\displaystyle {\varphi \mathrm{}}^{}}$ 2${\$ 1$/\phi ^{2$ 무한 피보나치 워드는 지시 순서(1,1,1,....)에 의해 생성된 표준 워드다.
• 무한 피보나치 단어는 반복된다. 즉, 모든 하위 단어는 무한히 자주 발생한다.
• $u{\displaystyle }$ ${\displaystyle u}$이(가) 무한 피보나치 단어의 하위 단어라면, 그 반전도 마찬가지인데, ${\displaystyle u^{}}$ R$${\$displaystyle u^{R}$로 표시된다$.$
• $u{\displaystyle }$ ${\displaystyle u}$이(가) 무한 피보나치 단어의 하위 단어라면$$, $u{\displaystyle }${\$displaystyle u}$의 최소 기간은 피보나치 숫자다$$.
• 두 개의 연속적인 피보나치 단어들의 결합은 "거의 거의 일치"이다. ${\displaystyle {Sn}_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle {}_{}}$ n ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {\mathrm{n}}_{}}$- 1$${\$displaystyle S_{n+1}=S_{n}S_{n-1}$와 ${\displaystyle S_{}}$n - ${\displaystyle 1_{}}$ ${\displaystyle S_{}}${\$displaystyle S_{n-1}S_{n}}}}$는 마지막 두 문자로만 다르다$$.
• 0.010010100이라는 숫자는 무한 피보나치 단어의 숫자로 소수점들이 만들어지고, 초월적이다.
• 문자 "1"은 Upper Wythoff 시퀀스(OEIS의 시퀀스 A001950)의 연속적인 값으로 주어진 위치에서 찾을 수 있다. $\lfloor {\displaystyle n}$ ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle \lllloor n\pi ^{2}\rfloor }$
• 문자 "0"은 Lower Wythoff 시퀀스(OEIS의 시퀀스 A000201)의 연속적인 값으로 주어진 위치에서 찾을 수 있다. $):{\displaystyle n}$ $ϕ$ ⌋ ${\displaystyle \rfloor }$ { { $\lfloor \lfloor }$
• The distribution of ${\displaystyle n=F_{k}}$ points on the unit circle, placed consecutively clockwise by the golden angle ${\displaystyle {\frac {2\pi }{\phi ^{2}}}}$, generates a pattern of two lengths ${\displaystyle {\frac {2\pi }{\phi ^{k-1}}},{\frac {2\p$$i}{\phi ^{k}}}$단위 원 위에$$. 위 피보나치 워드의 생성과정은 원의 연속적인 분할에 직접적으로 대응하지는 않지만, 패턴이 시계방향으로 첫 번째 점에 가장 가까운 지점에서 시작되면 이$$ 패턴은 S ${\displaystyle {\mathrm{k}}_{}}$- 1 ${\$이며, 여기서 0은 장거리와 1에 해당하고 1은 짧은 디스패치에 해당된다.탠스
• 무한 피보나치 단어에는 3개의 연속적인 동일한 하위 단어들이 반복되어 있지만, 4개의 단어 중 어느 것도 들어 있지 않다. 무한 피보나치 단어의 임계 지수는 $2{\displaystyle \mathrm{}}$+ $[\displaystyle 2+\phi$\ 약 $3.618}$이다$.$^[5] 모든 스터미어 단어 중에서 가장 작은 지수(또는 임계 지수)이다.
• 무한 피보나치 단어는 종종 문자열에서 반복을 감지하는 알고리즘의 최악의 경우로 언급된다.
• 무한 피보나치 단어는 내형성 0 → 01, 1 → 0에 의해 {0,1}*에서 생성된 형태어다.^[6]
• 그 n피보나치 단어의 ${\displaystyle {요소}_{}}$ s n ${\$는 Zeckendorf 표현(피보나치 숫자의 특정 집합의 합계)이 1이면 1이다$.$ n 1을 포함하지 않을 경우 1을 포함하며, 0을 포함하지 않을 경우 0을 포함한다.
• 피보나치 단어의 자릿수는 섬유수 모드 2의 순서를 취함으로써 얻을 수 있다.^[7]

적용들

피보나치 기반 구조는 현재 퀘이시크리스탈과 같은 주기적인 순서로 물리적 시스템을 모델링하는 데 사용되고 있으며, 이러한 맥락에서 피보나치 단어는 피보나치 퀘이시크리스탈이라고도 불린다.^[8] 수정 성장 기술은 피보나치 층의 결정체를 배양하고 그 빛 산란 특성을 연구하기 위해 사용되어 왔다.^[9]

참고 항목

• 수학과 미술
• 트리보나치어

메모들

참조

• Adamczewski, Boris; Bugeaud, Yann (2010), "8. Transcendence and diophantine approximation", in Berthé, Valérie; Rigo, Michael (eds.), Combinatorics, automata, and number theory, Encyclopedia of Mathematics and its Applications, vol. 135, Cambridge: Cambridge University Press, p. 443, ISBN 978-0-521-51597-9, Zbl 1271.11073.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, ISBN 978-0-521-82332-6.
• Bombieri, E.; Taylor, J. E. (1986), "Which distributions of matter diffract? An initial investigation" (PDF), Le Journal de Physique, 47 (C3): 19–28, doi:10.1051/jphyscol:1986303, MR 0866320.
• Dharma-wardana, M. W. C.; MacDonald, A. H.; Lockwood, D. J.; Baribeau, J.-M.; Houghton, D. C. (1987), "Raman scattering in Fibonacci superlattices", Physical Review Letters, 58 (17): 1761–1765, doi:10.1103/physrevlett.58.1761, PMID 10034529.
• Kimberling, 클라크(2004년),":피보나치 경우와 단어와 숫자 세트 주문했고요", 하워드에, 프레데리크 T.(교육.), 피보나치 넘버스의 응용권 9:열번째 국제 연구 회의 피보나치 넘버스에 응용 프로그램에서는 본 도르드레흐트:Kluwer 학술 출판사,를 대신하여 서명함의 회보. 137–144, doi:10.1007/978-0-306-48517-6_14,. MR2076798.
• Lothaire, M. (1997), Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 17 (2nd ed.), Cambridge University Press, ISBN 0-521-59924-5.
• Lothaire, M. (2011), Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 90, Cambridge University Press, ISBN 978-0-521-18071-9. 2002년 하드백의 재인쇄.
• de Luca, Aldo (1995), "A division property of the Fibonacci word", Information Processing Letters, 54 (6): 307–312, doi:10.1016/0020-0190(95)00067-M.
• Mignosi, F.; Pirillo, G. (1992), "Repetitions in the Fibonacci infinite word", Informatique théorique et application, 26 (3): 199–204, doi:10.1051/ita/1992260301991.
• Ramírez, José L.; Rubiano, Gustavo N.; De Castro, Rodrigo (2014), "A generalization of the Fibonacci word fractal and the Fibonacci snowflake", Theoretical Computer Science, 528: 40–56, arXiv:1212.1368, doi:10.1016/j.tcs.2014.02.003, MR 3175078.

외부 링크

• Ron Knott의 사이트에 있는 상세하고 접근하기 쉬운 설명
• Weisstein, Eric W., "Rabbit Sequence", MathWorld
• 유튜브에서 피보나치 워드(최초 20만 비트)