파도바 수열

수론에서, 파도바 수열(Padovan sequence)은 초기값에 의해 정의된 정수 P(n)의^[1] 수열입니다.

${\displaystyle P(0)=P(1)=P(2)=1,}$

그리고 재발 관계.

${\displaystyle P(n)=P(n-2)+P(n-3)}$

P(n)의 처음 몇 개의 값은

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... (OEIS 내 서열 A000931)

파도반 소수(Padovan prime)는 파도반 소수(Padovan prime)입니다.파도바의 첫 번째 소수는 다음과 같습니다.

2, 3, 5, 7, 37, 151, 3329, 23833, 1309204281, 3093215881333057, 1363005552466607821742128462127393362780881053358473, 155887769514160850775109894189926597511540366218119518685989164180630185566719, ...(OEIS의 A100891 시퀀스).

파도반 수열은 1994년 수필 돔에서 발견된 것을 네덜란드 건축가 한스 반 데어 란(Hans van der Laan)의 공으로 돌린 리차드 파도반(Richard Padovan)의 이름을 따서 지어졌습니다. 한스 반 데어 란: 현대 ^[2]원시인.이 순서는 1996년 6월 ^[3]이안 스튜어트가 그의 Scientific American Column Mathematical Recreations에서 설명했습니다.그는 또한 그의 책 중 하나인 "수학 히스테리:수학과 함께하는 재미있는 게임"이라고 말했습니다.

위의 정의는 Ian Stewart와 MathWorld가 제시한 정의입니다.다른 소스는 다른 위치에서 시퀀스를 시작할 수 있으며, 이 경우 이 문서의 일부 ID는 적절한 오프셋으로 조정되어야 합니다.

재발관계

나선형에서 각 삼각형은 다른 두 개와 한 변을 공유하며, 파도반 수열이 재발 관계를 만족시킨다는 시각적 증거를 제공합니다.

${\displaystyle P(n)=P(n-1)+P(n-1)}$

이를 시작으로 정의 재발 및 기타 재발이 발견되는 대로${\displaystyle }$P$)$ {\$displaystyle P($m)}를${\displaystyle P(\mathrm{m}}$ -${\displaystyle }$2) +${\displaystyle P(\mathrm{m}}$ -${\displaystyle }$3$)$ {\$displaystyle P($m - 2) + P(m - 3$)}$로 $반복적$으로 교체함으로써 무한한 수의 추가 재발을 만들 수 있습니다.

페린 수열은 초기 값이 다르지만 파도반 수열과 동일한 재발 관계를 만족합니다.

페린 수열은 다음 공식에 의해 파도반 수열로부터 얻을 수 있습니다.

${\displaystyle \mathrm {Perrin}(n)=P(n+1)+P(n-1).\,}$

음의 매개변수로 확장

재발 관계에 의해 정의된 다른 시퀀스와 마찬가지로, padovan number P(m) for m<0은 재발 관계를 다음과 같이 다시 작성하여 정의할 수 있습니다.

${\displaystyle P(m)=P(m+3)-P(m+1),}$

m = -1로 시작하여 역으로 작업하면 P(m)을 음의 지수로 확장합니다.

P−20

P−19

P−18

P−17

P−16

P−15

P−14

P−13

P−12

P−11

P−10

P−9

P−8

P−7

P−6

P−5

P−4

P−3

P−2

P−1

P0

P1

P2

7

−7

4

0

−3

4

−3

1

1

−2

2

−1

0

1

−1

1

0

0

1

0

1

1

1

항들의 합

파도바 수열의 첫 n항들의 합은 P(n + 5)보다 2 적습니다.

${\displaystyle \sum _{m=0}^{n}P(m)=P(n+5)-2.}$

대체 항의 합, 세 번째 항의 합, 다섯 번째 항의 합도 순서의 다른 항과 관련이 있습니다.

${\displaystyle \sum _{m=0}^{n}P(2m)=P(2n+3)-1}$ OEIS: A077855

${\displaystyle \sum _{m=0}^{n}P(2m+1)=P(2n+4)-1}$

${\displaystyle \sum _{m=0}^{n}P(3m)=P(3n+2)}$ OEIS: A034943

${\displaystyle \sum _{m=0}^{n}P(3m+1)=P(3n+3)-1}$

${\displaystyle \sum _{m=0}^{n}P(3m+2)=P(3n+4)-1}$

${\displaystyle \sum _{m=0}^{n}P(5m)=P(5n+1)입니다.}$ OEIS: A012772

파도반 수열의 항들의 곱을 포함하는 합은 다음 항들을 만족합니다.

${\displaystyle \sum _{m=0}^{n}P(m)^{2}=P(n+2)^{2}-P(n-1)^{2}-P(n-3)^{2}}$

${\displaystyle \sum _{m=0}^{n}P(m)^{2}P(m+1)=P(n+1)P(n+2)}$

${\displaystyle \sum _{m=0}^{n}P(m+2)=P(n+2)P(n+3)-1.}$

기타아이덴티티

파도반 수열은 그 정체성을 만족시키기도 합니다.

${\displaystyle P(n)^{2}-P(n+1)P(n-1)=P(-n-7).\,}$

파도반 수열은 다음 항등식에 의한 이항 계수의 합과 관련이 있습니다.

${\displaystyle P(k-2)=\sum _{2m+n=k}{m \choose n}=\sum _{m=\lceil k/3\rceil }^{\lfloor k/2\rfoor }{m \choose k-2m}}$

예를 들어 k = 12의 경우 2m + n = 12인 쌍(m, n)에 대한 값은 (6, 0), (5, 2) 및 (4, 4)이며 다음과 같습니다.

${\displaystyle {6 \choose 0}+{5 \choose 2}+{4 \choose 4}=1+10+1=12=P(10)\,}$

비네식

파도반 수열은 방정식의^[1] 근의 거듭제곱들로 쓰여질 수 있습니다.

${\displaystyle x^{3}-x-1=0.\,}$

이 방정식은 3개의 근을 갖습니다; 1개의 실수 근 p(가소수로 알려짐)와 2개의 복소수 켤레 근 q와 r.^[5]이 세 근이 주어졌을 때, 파도바 수열은 p, q, r을 포함하는 공식으로 표현될 수 있습니다.

${\displaystyle P(n)=ap^{n}+bq^{n}+cr^{n}}$

여기서 a, b, c는 ^[1]상수입니다.

복소근 q와 r의 절대값이 모두 1보다 작기 때문에(따라서 p는 Pisot-Vijayaraghavan 수이다), 이러한 근의 거듭제곱은 큰 n에 대해 0에 접근하고, $P{\displaystyle (n)}$ - $pn {\$ P$(n)$ -$ap$^{n$$$}$인 경향이 있습니다.

${\displaystyle \mathrm{모든}}$ $n{\displaystyle }$ ${\displaystyle \ge }$ 0$${\$displaystyle$ n$\geq$ 0$\}$에 $대하여{\displaystyle \frac{{}^{}}{}}$ P(n)은 p ${\displaystyle \frac{\mathrm{52}}{}}$p + ${\displaystyle \frac{}{}{}^{}}$ p ${\displaystyle n^{}}${\$displaystyle${\$frac {p^{5}}{2p+3}}p^{n$ 실제로 ${\displaystyle \frac{{p\mathrm{}}^{}}{}}$ ${\displaystyle \frac{{}^{}}{\mathrm{}p}}$ + ${\displaystyle \frac{3}{}}${\$displaystyle${\$frac {p^{5}}{2p+3}}$는 위 상수 a의 값이고, b와 c는 p를 각각 q와 r로 치환한 값입니다.

Padovan sequence의 연속 항의 비율은 p에 접근하며, p는 약 1.324718의 값을 갖습니다.이 상수는 피보나치 수열에 황금 비율이 있는 것처럼 파도반 수열과 페린 수열에 동일한 관계를 갖습니다.

조합해석

• P(n)은 각 항이 2 또는 3인 순서 합으로 n + 2를 쓰는 방법의 수(즉, 각 항이 2 또는 3인 n + 2의 구성의 수)입니다.예를 들어, P(6) = 4이며, 2s와 3s의 순서 합으로 8을 쓰는 방법은 4가지입니다.

2 + 2 + 2 + 2 ; 2 + 3 + 3 ; 3 + 2 + 3 ; 3 + 3 + 2

• 항이 2가 아닌 순서 합으로 n을 쓰는 방법의 수는 P(2n - 2)입니다.예를 들어, P(6) = 4이며, 4를 2가 아닌 순서 합으로 쓰는 방법은 4가지입니다.

4 ; 1 + 3 ; 3 + 1 ; 1 + 1 + 1 + 1

• 항이 2가 아닌 palindromic 순서 합으로 n을 쓰는 방법의 수는 P(n)입니다.예를 들어, P(6) = 4이고 6을 2가 아닌 회문 순서 합으로 쓰는 방법은 4가지입니다.

6 ; 3 + 3 ; 1 + 4 + 1 ; 1 + 1 + 1 + 1 + 1 + 1

• 각 항이 홀수이고 1보다 큰 순서 합으로 n을 쓰는 방법의 수는 P(n - 5)와 같습니다.예를 들어 P(6) = 4이고 각 항이 홀수이고 1보다 큰 순서 합으로 11을 쓰는 방법은 4가지입니다.

11 ; 5 + 3 + 3 ; 3 + 5 + 3 ; 3 + 3 + 5

• 각 항이 2 mod 3과 일치하는 순서 합으로 n을 쓰는 방법의 수는 P(n - 4)와 같습니다.예를 들어, P(6) = 4이고, 각 항이 2 mod 3과 일치하는 순서 합으로 10을 쓰는 방법은 4가지입니다.

8 + 2 ; 2 + 8 ; 5 + 5 ; 2 + 2 + 2 + 2 + 2

함수생성

파도반 수열의 생성함수는

${\displaystyle G(P(n);x)={\frac {x+x^{2}}}:{1-x^{2}-x^{3}}}.$

다음과 같은 기하학 용어를 사용하여 파도반 수열의 산물과 관련된 식별을 증명하는 데 사용할 수 있습니다.

${\displaystyle \sum _{n=0}^{\infty}{\frac {P(n)}{2^{n}}={\frac {12}{5}}}$

${\displaystyle \sum _{n=0}^{\infty}{\frac {P(n)}{\alpha ^{n}}}={\frac {\alpha ^{2}(\alpha +1)}{\alpha ^{3}-\alpha -1}}}$

일반화

피보나치 다항식이라고 불리는 다항식의 집합으로 일반화될 수 있는 피보나치 수와 유사한 방식으로, 파도바 수열 수는 파도바 다항식을 산출하기 위해 일반화될 수 있습니다.

파도반 L계

다음과 같은 간단한 문법을 정의하면 다음과 같습니다.

변수 : AB C

상수 : 없음

시작 : A

규칙 : (A → B), (B → C), (C → AB)

이 Lindenmayer 시스템 또는 L-system은 다음과 같은 문자열 시퀀스를 생성합니다.

n = 0 : A

n = 1 : B

n = 2 : C

n = 3 : AB

n = 4 : BC

n = 5 : CAB

n = 6 : ABC

n = 7 : BCCAB

n = 8 : CABABC

각 끈의 길이를 세어보면 파도반 숫자를 얻을 수 있습니다.

1, 1, 1, 2, 2, 3, 4, 5, ...

또한 각 문자열의 A, B, C의 개수를 세어보면 n번째 문자열의 경우 P(n - 5) As, P(n - 3) Bs 및 P(n - 4) Cs가 있습니다.BB 쌍과 CC 쌍의 수 역시 파도반 수이다.

직육면체 나선형

나선형은 3차원 직육면체 세트의 모서리를 연결하는 것을 기준으로 형성될 수 있습니다.이것은 파도반 직육면체 나선형입니다.이 나선형의 연속적인 변들은 파도반 수에 제곱근 2를 곱한 길이를 갖습니다.

파스칼의 삼각형

Erv Wilson은 그의 논문 메루산의^[6] 비늘에서 파스칼의 삼각형의 특정한 대각선을 관찰했고 (도형 참조) 1993년에 종이에 그렸습니다.파도반 숫자는 1994년에 발견되었습니다.Paul Barry(2004)는 이 대각선들이 대각선 ^{[citation needed]}수를 합함으로써 파도반 수열을 생성한다는 것을 보여주었습니다.

참고문헌

• 이안 스튜어트, 컴퓨터 데이트 안내서(피드백), 사이언티픽 아메리칸, Vol. 275, No. 5, 1996년 11월, Pg. 118

외부 링크

• OEIS 시퀀스 A000931(파도반 시퀀스)
• 파도반 계열 계산기