ในทางคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีลำดับk- ปกติ (k -regular sequence ) คือลำดับที่สอดคล้องกับสมการเวียนเกิดเชิงเส้นที่สะท้อนถึงการแทนค่าฐานkของจำนวนเต็ม กลุ่มของ ลำดับ k-ปกติเป็นการขยายความของกลุ่ม ลำดับ k-อัตโนมัติ (k -automatic sequences)ไปสู่ตัวอักษรที่มีขนาดอนันต์

ลำดับ k- ปกติ มีลักษณะเฉพาะอยู่หลายแบบซึ่งทั้งหมดนั้นเทียบเท่ากัน ลักษณะเฉพาะที่ใช้กันทั่วไปบางส่วนมีดังต่อไปนี้ สำหรับแต่ละแบบ เรากำหนดให้R ′ เป็นวงแหวนโนเธอร์เรียนแบบสลับที่ได้ และกำหนดให้Rเป็นวงแหวนที่บรรจุR ′ ไว้

ให้k  ≥ 2 k-kernelของลำดับนี้คือเซตของลำดับย่อย ${\displaystyle s(n)_{n\geq 0}}$

${\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ และ }}0\leq r\leq k^{e}-1\}.}$

ลำดับนี้เป็น ( R ′, k )-ปกติ (มักย่อเป็น " k -ปกติ") หากโมดูลที่สร้างโดยK _k ( s ) เป็นโมดูลR ′ ที่สร้างขึ้นอย่างจำกัด^{[ 1 ]}${\displaystyle s(n)_{n\geq 0}}$${\displaystyle R'}$

ในกรณีพิเศษเมื่อลำดับจะเป็น-ปกติ ถ้าบรรจุอยู่ในปริภูมิเวกเตอร์มิติจำกัดเหนือ ${\displaystyle R'=R=\mathbb {Q} }$${\displaystyle s(n)_{n\geq 0}}$${\displaystyle k}$${\displaystyle K_{k}(s)}$${\displaystyle \mathbb {Q} }$

ลำดับs ( n ) เป็นk-ปกติ ถ้ามีจำนวนเต็มE อยู่ เช่นนั้น สำหรับทุกe _j > Eและ 0 ≤ r _j ≤ k ^{e _j}  − 1 ลำดับย่อยทุกลำดับของsในรูปแบบs ( k ^{e _j} n  +  r _j ) สามารถแสดงได้ในรูปของการรวมเชิงเส้นR ′ โดยที่c _ijเป็นจำนวนเต็มf _ij ≤ Eและ 0 ≤ b _ij ≤ k ^{f _ij}  − 1 ^{[ 2 ]}${\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})}$

หรืออีกทาง หนึ่งลำดับs ( n ) จะเป็นk-ปกติ ถ้ามีจำนวนเต็มrและลำดับย่อยs1 ₍ n ), ..., sr ( n ) อยู่ซึ่งสำหรับทุก 1 ≤ i ≤ rและ 0 ≤ a ≤ k  − 1 ลำดับs _i ( kn  +  a ) _ทุก ตัว ในเคอร์เนลk K _k ( s ) เป็น ผลรวมเชิงเส้น R ′ ของลำดับย่อยs _i ( n ) ^{[ 2 ]}

ให้x ₀ , ..., x _{k  − 1}เป็นเซตของ ตัวแปร k ตัวที่ไม่สลับที่กัน และให้ τ เป็นแผนที่ที่ส่งจำนวนธรรมชาติn บางตัว ไปยังสตริงx _{a 0} ... x _{a e  − 1}โดยที่การแสดงฐานkของxคือสตริงa _{e  − 1} ... a ₀จากนั้นลำดับs ( n ) จะเป็นk-ปกติก็ต่อเมื่ออนุกรมอย่างเป็นทางการ เป็น- ตรรกยะ^{[ 3 ]}${\displaystyle \sum _{n\geq 0}s(n)\tau (n)}$${\displaystyle \mathbb {Z} }$

นิยามอนุกรมอย่างเป็นทางการของ ลำดับ k-ปกติ นำไปสู่ลักษณะเฉพาะของออโตมาตอนที่คล้ายคลึงกับเครื่องเมทริกซ์ของSchützenberger ^{[ 4 ] [ 5 ]}

แนวคิดของ ลำดับ k-ปกติได้รับการศึกษาครั้งแรกในเอกสารสองฉบับโดย Allouche และ Shallit ^{[ 6 ]}ก่อนหน้านี้ Berstel และ Reutenauer ได้ศึกษาทฤษฎีของอนุกรมตรรกยะซึ่งมีความเกี่ยวข้องอย่างใกล้ชิดกับลำดับk- ปกติ ^{[ 7 ]}

ให้เป็นการประเมินค่าแบบ -adicของลำดับของไม้บรรทัด( OEIS :  A007814 ) เป็นแบบ -regular และ-kernel ${\displaystyle s(n)=\nu _{2}(n+1)}$${\displaystyle 2}$${\displaystyle n+1}$${\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }$${\displaystyle 2}$${\displaystyle 2}$

${\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ และ }}0\leq r\leq 2^{e}-1\}}$

บรรจุอยู่ในปริภูมิเวกเตอร์สองมิติที่สร้างขึ้นโดยและลำดับคงที่องค์ประกอบพื้นฐานเหล่านี้ทำให้เกิดความสัมพันธ์เวียนเกิด ${\displaystyle s(n)_{n\geq 0}}$${\displaystyle 1,1,1,\dots }$

${\displaystyle {\begin{aligned}s(2n)&=0,\\s(4n+1)&=s(2n+1)-s(n),\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}}$

ซึ่งร่วมกับเงื่อนไขเริ่มต้นและจะกำหนดลำดับได้อย่างเฉพาะเจาะจง^{[ 8 ]}${\displaystyle s(0)=0}$${\displaystyle s(1)=1}$

ลำดับThue–Morse t ( n ) ( OEIS :  A010060 ) เป็นจุดคงที่ของมอร์ฟิซึม 0 → 01, 1 → 10 เป็นที่ทราบกันว่าลำดับ Thue–Morse เป็น 2-อัตโนมัติ ดังนั้นจึงเป็น 2-ปกติ และเคอร์เนล 2 ของมันด้วย

${\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ และ }}0\leq r\leq 2^{e}-1\}}$

ประกอบด้วยลำดับย่อย และ${\displaystyle t(n)_{n\geq 0}}$${\displaystyle t(2n+1)_{n\geq 0}}$

ลำดับของจำนวนแคนเตอร์c ( n ) ( OEIS :  A005823 ) ประกอบด้วยจำนวนที่มี การขยายเลข ฐานสามที่ไม่มีเลข 1 อยู่เลย สามารถแสดงได้อย่างตรงไปตรงมาว่า

${\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}$

ดังนั้นลำดับของจำนวนแคนเตอร์จึงเป็นลำดับปกติ 2 ตัว ในทำนองเดียวกันลำดับสแตนลีย์ ก็เป็นลำดับปกติเช่นกัน

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (ลำดับA005836ในOEIS )

จำนวนที่มีการขยายไตรภาคที่ไม่มีเลข 2 อยู่ด้วยนั้น ก็เป็น 2-ปกติเช่นกัน^{[ 9 ]}

การประยุกต์ใช้แนวคิดเรื่องk -regularity ในการศึกษาอัลกอริทึมในวงกว้างนั้นค่อนข้างน่าสนใจ พบได้ในการวิเคราะห์ อัลกอริทึม merge sortเมื่อกำหนดรายการ ค่า nค่า จำนวนการเปรียบเทียบที่ทำโดยอัลกอริทึม merge sort คือจำนวนการเรียงลำดับซึ่งควบคุมโดยความสัมพันธ์เวียนเกิด

${\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}$

ดังนั้น ลำดับที่กำหนดโดยความสัมพันธ์เวียนเกิดสำหรับการเรียงลำดับแบบผสานT ( n ) จึงเป็นลำดับปกติ 2 ตัว^{[ 10 ]}

ถ้าเป็นพหุนามที่มีค่าเป็นจำนวนเต็มแล้วจะเป็น พหุ นาม k-ปกติ สำหรับทุกค่า ${\displaystyle f(x)}$${\displaystyle f(n)_{n\geq 0}}$${\displaystyle k\geq 2}$

ลำดับ Glaisher –Gouldเป็นลำดับปกติ 2 ตัว ลำดับ Stern–Brocot เป็นลำดับปกติ 2 ตัว

Allouche และ Shallit ได้ยกตัวอย่างลำดับ k- ปกติ เพิ่มเติมอีกหลายตัวอย่างในเอกสารของพวกเขา^{[ 6 ]}

ลำดับ k -regular มีคุณสมบัติที่น่าสนใจหลายประการ

• ลำดับk- อัตโนมัติ ทุกตัวเป็นk-ปกติ^{[ 11 ]}
• ลำดับที่มีการซิงโครไนซ์kทุกตัวจะเป็น ลำดับ ปกติk ตัว
• ลำดับk-ปกติจะมีค่าจำกัดจำนวนหนึ่งก็ต่อเมื่อเป็นk-อัตโนมัติ^{[ 12 ]}นี่เป็นผลสืบเนื่องโดยตรงจากการที่คลาสของ ลำดับ k-ปกติเป็นการวางนัยทั่วไปของคลาสของ ลำดับ k-อัตโนมัติ
• คลาสของ ลำดับ k-ปกติจะปิดภายใต้การบวกแบบเทอม การคูณแบบเทอม และการสังเคราะห์คลาสของ ลำดับ k-ปกติยังปิดภายใต้การปรับขนาดแต่ละเทอมของลำดับด้วยจำนวนเต็ม λ อีกด้วย^{[ 12 ] [ 13 ] [ 14 ] [ 15 ]}โดยเฉพาะอย่างยิ่ง เซตของอนุกรมกำลังk-ปกติจะก่อตัวเป็นวงแหวน^{[ 16 ]}
• ถ้าเป็นk-ปกติ แล้วสำหรับจำนวนเต็มทั้งหมดจะเป็นk-อัตโนมัติ อย่างไรก็ตาม บทกลับไม่เป็นจริง^{[ 17 ]}${\displaystyle s(n)_{n\geq 0}}$${\displaystyle m\geq 1}$${\displaystyle (s(n){\bmod {m}})_{n\geq 0}}$
• สำหรับk ที่เป็นอิสระเชิงการคูณ l   ≥ 2 ถ้าลำดับเป็นทั้งk-ปกติและl- ปกติ ลำดับนั้นจะสอดคล้อง กับความสัมพันธ์เวียนเกิดเชิงเส้น^{[ 18 ]}นี่เป็นการสรุปผลลัพธ์ทั่วไปของ Cobham เกี่ยวกับลำดับที่เป็นทั้งk-อัตโนมัติและl-อัตโนมัติ^{[ 19 ]}
• พจน์ ที่nของ ลำดับจำนวนเต็ม k- ปกติจะเติบโตอย่างมากที่สุด ^แบบพหุนามในn ^{[ 20} ]
• ถ้าเป็นฟิลด์และลำดับของกำลังจะเป็นk-ปกติก็ต่อเมื่อหรือเป็นรากของเอกภาพ^{[ 21 ]}${\displaystyle F}$${\displaystyle x\in F}$${\displaystyle (x^{n})_{n\geq 0}}$${\displaystyle x=0}$${\displaystyle x}$

เมื่อกำหนดลำดับผู้สมัครที่ไม่ทราบว่าเป็นk -regular แล้วโดยทั่วไปสามารถพิสูจน์ความเป็นk -regular ได้โดยตรงจากนิยามโดยการคำนวณองค์ประกอบของเคอร์เนลของ และพิสูจน์ว่าองค์ประกอบทั้งหมดในรูปแบบที่มีค่า และ มากพอสามารถเขียนเป็นผลรวมเชิงเส้นขององค์ประกอบเคอร์เนลที่มีเลขชี้กำลังน้อยกว่าแทนที่ ได้ ซึ่งโดยปกติแล้วการคำนวณนี้ทำได้ง่าย ${\displaystyle s=s(n)_{n\geq 0}}$${\displaystyle s}$${\displaystyle (s(k^{r}n+e))_{n\geq 0}}$${\displaystyle r}$${\displaystyle 0\leq e<2^{r}}$${\displaystyle r}$

ในทางกลับกัน การพิสูจน์ว่าลำดับผู้สมัครไม่มีความสม่ำเสมอแบบkมักจะต้องสร้างเซตย่อยที่เป็นอิสระเชิงเส้นในเคอร์เนลของซึ่งโดยทั่วไปแล้วทำได้ยากกว่า นี่คือตัวอย่างหนึ่งของการพิสูจน์ดังกล่าว ${\displaystyle s}$${\displaystyle \mathbb {Z} }$${\displaystyle s}$

ให้แทนจำนวนของ's ในการขยายเลขฐานสองของให้แทนจำนวนของ's ในการขยายเลขฐานสองของลำดับสามารถแสดงได้ว่าเป็นลำดับ 2-ปกติอย่างไรก็ตาม ลำดับ ไม่ใช่ลำดับ 2-ปกติ ด้วยเหตุผลดังต่อไปนี้ สมมติว่าเป็นลำดับ 2-ปกติ เราอ้างว่าองค์ประกอบสำหรับและของ 2-เคอร์เนลของเป็นอิสระเชิงเส้นเหนือฟังก์ชันเป็นฟังก์ชันทั่วถึงบนจำนวนเต็ม ดังนั้นให้เป็นจำนวนเต็มที่น้อยที่สุดที่โดยความเป็น 2-ปกติของมีอยู่และ ค่าคงที่ที่สำหรับแต่ละ ${\displaystyle e_{0}(n)}$${\displaystyle 0}$${\displaystyle n}$${\displaystyle e_{1}(n)}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle f(n):=e_{0}(n)-e_{1}(n)}$${\displaystyle g=g(n):=|f(n)|}$${\displaystyle (g(n))_{n\geq 0}}$${\displaystyle g(2^{k}n)}$${\displaystyle n\geq 1}$${\displaystyle k\geq 0}$${\displaystyle g}$${\displaystyle \mathbb {Z} }$${\displaystyle n\mapsto e_{0}(n)-e_{1}(n)}$${\displaystyle x_{m}}$${\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m}$${\displaystyle (g(n))_{n\geq 0}}$${\displaystyle b\geq 0}$${\displaystyle c_{i}}$${\displaystyle n\geq 0}$

${\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}$

ให้เป็นค่าต่ำสุดที่ทำให้แล้วสำหรับทุกๆ ${\displaystyle a}$${\displaystyle c_{a}\neq 0}$${\displaystyle n\geq 0}$

${\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}$

เมื่อประเมินนิพจน์นี้ที่โดยที่และต่อไปเรื่อยๆ เราจะได้ ทางด้านซ้ายมือ ${\displaystyle n=x_{m}}$${\displaystyle m=0,-1,1,2,-2}$

${\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}$

และทางด้านขวามือ

${\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

ดังนั้นสำหรับจำนวนเต็มทุกตัว ${\displaystyle m}$

${\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

แต่สำหรับด้านขวาของสมการเป็นโมโนโทนเนื่องจากมีรูปแบบสำหรับค่าคงที่บางค่าในขณะที่ด้านซ้ายไม่ใช่ ดังที่สามารถตรวจสอบได้โดยการแทนค่า, , และ ตามลำดับ ดังนั้น จึงไม่ใช่ 2-ปกติ^{[ 22 ]}${\displaystyle m\geq -a-1}$${\displaystyle Am+B}$${\displaystyle A,B}$${\displaystyle m=-a-1}$${\displaystyle m=-a}$${\displaystyle m=-a+1}$${\displaystyle (g(n))_{n\geq 0}}$