การนับแบบหนึ่งต่อหนึ่งทั่วถึง

Q: คำนิยาม

ระบบ การนับแบบหนึ่งต่อหนึ่ง ฐาน k ใช้ชุดตัวเลข {1, 2, ..., k } ( k ≥ 1) เพื่อแทนจำนวนเต็มที่ไม่เป็นลบทุกจำนวนอย่างไม่ซ้ำกัน ดังนี้:

Q: คุณสมบัติของจำนวน ฐาน k ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง

สำหรับ ฐานที่กำหนด เค ≥ 2 {\displaystyle k\geq 2}

ระบบตัวเลขแบบหนึ่งต่อหนึ่งทั่วถึง (Bijective numeration ) คือระบบตัวเลข ใดๆ ที่จำนวนเต็มที่ ไม่เป็นลบทุกจำนวน สามารถแทนได้ด้วยวิธีเดียวเท่านั้น โดยใช้ชุดตัวเลข ที่มีจำนวนจำกัด ชื่อนี้หมายถึง การจับคู่แบบหนึ่งต่อหนึ่ง ( bijection ) ที่มีอยู่ในกรณีนี้ระหว่างเซตของจำนวนเต็มที่ไม่เป็นลบและเซตของชุดตัวเลขที่มีจำนวนจำกัด โดยใช้สัญลักษณ์ (ตัวเลข) จำนวนจำกัด

ระบบตัวเลขทั่วไปส่วนใหญ่ เช่น ระบบ เลขฐานสิบ ไม่ใช่ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง (bijective) เพราะมีลำดับตัวเลขมากกว่าหนึ่งชุดที่สามารถแทนจำนวนเต็มบวกเดียวกันได้ โดยเฉพาะอย่างยิ่ง การเติมเลขศูนย์นำหน้าจะไม่เปลี่ยนแปลงค่าที่แสดง ดังนั้น "1", "01" และ "001" จึงแทนเลขหนึ่งเหมือนกัน แม้ว่าจะมีเพียงแบบแรกเท่านั้นที่ใช้กันทั่วไป แต่ข้อเท็จจริงที่ว่าแบบอื่นๆ ก็เป็นไปได้เช่นกัน หมายความว่าระบบเลขฐานสิบไม่ใช่ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง อย่างไรก็ตามระบบเลขฐานหนึ่งซึ่งมีเพียงหลักเดียวเป็น ฟังก์ชันหนึ่งต่อ หนึ่งทั่วถึง

ระบบตัวเลขฐาน k แบบหนึ่งต่อหนึ่ง (bijective base - k numeration )เป็นระบบตัวเลขเชิงตำแหน่ง แบบหนึ่งต่อหนึ่ง โดยใช้สตริงของตัวเลขจากเซต {1, 2, ..., k } (โดยที่k ≥ 1) เพื่อเข้ารหัสจำนวนเต็มบวกแต่ละจำนวน ตำแหน่งของตัวเลขในสตริงจะกำหนดค่าของตัวเลขนั้นเป็นผลคูณของกำลังของk Smullyan (1961)เรียกสัญกรณ์นี้ว่าk -adic แต่ไม่ควรสับสนกับจำนวน p -adic : ระบบตัวเลขแบบหนึ่งต่อหนึ่งเป็นระบบสำหรับแสดงจำนวนเต็ม ธรรมดา ด้วยสตริงจำกัดของตัวเลขที่ไม่ใช่ศูนย์ ในขณะที่ จำนวน p -adic เป็นระบบของค่าทางคณิตศาสตร์ที่มีจำนวนเต็มเป็นเซตย่อย และอาจต้องการลำดับของตัวเลขที่ไม่มีที่สิ้นสุดในการแสดงตัวเลขใดๆ

คำนิยาม

ระบบ การนับแบบหนึ่งต่อหนึ่ง ฐานkใช้ชุดตัวเลข {1, 2, ..., k } ( k ≥ 1) เพื่อแทนจำนวนเต็มที่ไม่เป็นลบทุกจำนวนอย่างไม่ซ้ำกัน ดังนี้:

เลขศูนย์แทนด้วยสตริงว่าง
จำนวนเต็มที่แสดงด้วยสตริงตัวเลขที่ไม่ว่างเปล่า

a n a n -1 ... a 1 a 0

เป็น

a n k n + a n -1 k n -1 + ... + a 1 k 1 + a 0 k 0

.

สตริงตัวเลขที่แทนจำนวนเต็มm > 0 คือ

a n a n -1 ... a 1 a 0

ที่ไหน

{\begin{aligned}a_{0}&=m-q_{0}k,&q_{0}&=f\left({\frac {m}{k}}\right)&\\a_{1}&=q_{0}-q_{1}k,&q_{1}&=f\left({\frac {q_{0}}{k}}\right)&\\a_{2}&=q_{1}-q_{2}k,&q_{2}&=f\left({\frac {q_{1}}{k}}\right)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k}}\right)=0\end{aligned}}

และ

f(x)=\lceil x\rceil -1,

\lceil x\rceil

โดยเป็นจำนวนเต็มที่น้อยที่สุดที่ไม่น้อยกว่าx ( ฟังก์ชันปัดขึ้น )

ในทางตรงกันข้ามสัญกรณ์ตำแหน่ง มาตรฐาน สามารถกำหนดได้ด้วยอัลกอริทึมแบบเรียกซ้ำที่คล้ายกัน โดยที่

f(x)=\lfloor x\rfloor ,

การขยายไปสู่จำนวนเต็ม

สำหรับฐาน ระบบการนับ ฐานแบบหนึ่งต่อหนึ่งทั่วถึงสามารถขยายไปยังจำนวนเต็มลบได้ในลักษณะเดียวกับ ระบบการนับ ฐานมาตรฐาน โดยใช้ตัวเลขจำนวนอนันต์ โดยที่แสดงเป็นลำดับตัวเลขอนันต์ทางซ้ายเนื่องจากผลรวมของออยเลอร์ $k>1$ $k$ $b$ $d_{k-1}$ $f(d_{k-1})=k-1$ $\ldots d_{k-1}d_{k-1}d_{k-1}={\overline {d_{k-1}}}$

g({\overline {d_{k-1}}})=\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=-{\frac {k-1}{k-1}}=-1

หมายความว่า

g({\overline {d_{k-1}}}d_{k})=f(d_{k})\sum _{i=1}^{\infty }f(d_{k-1})k^{i}=1+\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=0

และสำหรับจำนวนบวกทุกจำนวนที่มีการแสดงตัวเลขแบบหนึ่งต่อหนึ่งทั่วถึง จะ ถูกแทนด้วยสำหรับฐานจำนวนลบจะถูกแทนด้วยโดยที่ ในขณะที่สำหรับฐานจำนวนลบจะถูกแทนด้วยซึ่งคล้ายกับวิธีการแทนจำนวนเต็มแบบ มี เครื่องหมาย ที่จำนวนเต็มทั้งหมดที่มีการแสดงตัวเลขแบบจะถูกแทนด้วย โดยที่การแทนแบบนี้จะไม่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงอีกต่อไป เนื่องจากเซตทั้งหมดของลำดับอนันต์ซ้ายของตัวเลขถูกใช้เพื่อแทนจำนวนเต็มซึ่งจำนวนเต็ม เป็นเพียงเซตย่อยเท่านั้น $n$ $d$ ${\overline {d_{k-1}}}d_{k}d$ $k>2$ $n<-1$ ${\overline {d_{k-1}}}d_{i}d$ $i<k-1$ $k=2$ $n<-1$ ${\overline {d_{k}}}d$ $n$ $d$ ${\overline {d_{0}}}d$ $f(d_{0})=0$ $k$

คุณสมบัติของจำนวน ฐาน k ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง

สำหรับ ฐานที่กำหนด $k\geq 2$

จำนวนหลักในจำนวนฐานk ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง ซึ่งแทนจำนวนเต็มที่ไม่เป็นลบnคือ
$\lfloor \log _{k}((n+1)(k-1))\rfloor$ [ ¹^]ตรงกันข้ามกับตัวเลข ฐาน kทั่วไปถ้าk = 1 (เช่น ^เลขฐานหนึ่ง) จำนวนหลักก็จะเป็นnเท่านั้น $\lceil \log _{k}(n+1)\rceil$
จำนวนเต็มที่ไม่เป็นลบที่เล็กที่สุด ซึ่งสามารถแทนได้ในระบบเลขฐานk ที่มีฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง และมีความยาวคือ $\ell \geq 0$
$\mathrm {min} (\ell )={\frac {k^{\ell }-1}{k-1}}$ ;
จำนวนเต็มที่ไม่เป็นลบที่ใหญ่ที่สุด ซึ่งสามารถแทนได้ในระบบเลขฐานk ที่มีฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง และมีความยาวคือ $\ell \geq 0$
$\mathrm {max} (\ell )={\frac {k^{\ell +1}-k}{k-1}}$ เทียบเท่ากับหรือ; $\mathrm {max} (\ell )=k\times \mathrm {min} (\ell )$ $\mathrm {max} (\ell )=\mathrm {min} (\ell +1)-1$
ตัวเลข ฐานk ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง และตัวเลขฐานk ทั่วไป สำหรับจำนวนเต็มที่ไม่เป็นลบn จะเหมือนกันก็ต่อเมื่อตัวเลขทั่วไปนั้นไม่มีเลข0 (หรือกล่าวอีกนัยหนึ่งคือ ตัวเลขที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงนั้น ไม่ใช่ทั้งสตริงว่างและไม่มีเลขk )

สำหรับ ฐานที่กำหนด $k\geq 1$

มีจำนวนฐานk ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งที่มีความยาว ; ^[²^] $k^{\ell }$ $\ell \geq 0$
รายการของตัวเลขฐานk ที่มีฟังก์ชันหนึ่งต่อ หนึ่งทั่วถึง เรียงตามลำดับธรรมชาติของจำนวนเต็มที่แสดง จะอยู่ในลำดับ shortlex โดยอัตโนมัติ (สั้นที่สุดก่อน เรียงตามพจนานุกรมภายในแต่ละความยาว) ดังนั้น เมื่อใช้ λ แทนสตริงว่างตัวเลขฐาน 1, 2, 3, 8, 10, 12 และ 16 จะเป็นดังนี้ (โดยที่ตัวเลขในรูปแบบปกติแสดงไว้เพื่อเปรียบเทียบ):

ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 1:	`λ`	`1`	`11`	`111`	`1111`	`11111`	`111111`	`1111111`	`11111111`	`111111111`	`1111111111`	`11111111111`	`111111111111`	`1111111111111`	`11111111111111`	`111111111111111`	`1111111111111111`	`...`	( ระบบเลขฐานหนึ่ง )
ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 2:	`λ`	`1`	`2`	`11`	`12`	`21`	`22`	`111`	`112`	`121`	`122`	`211`	`212`	`221`	`222`	`1111`	`1112`	`...`
ไบนารี:	`0`	`1`	`10`	`11`	`100`	`101`	`110`	`111`	`1000`	`1001`	`1010`	`1011`	`1100`	`1101`	`1110`	`1111`	`10000`	`...`
ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 3:	`λ`	`1`	`2`	`3`	`11`	`12`	`13`	`21`	`22`	`23`	`31`	`32`	`33`	`111`	`112`	`113`	`121`	`...`
ไตรภาค:	`0`	`1`	`2`	`10`	`11`	`12`	`20`	`21`	`22`	`100`	`101`	`102`	`110`	`111`	`112`	`120`	`121`	`...`
ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 8:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`11`	`12`	`13`	`14`	`15`	`16`	`17`	`18`	`...`
เลขฐานแปด:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`10`	`11`	`12`	`13`	`14`	`15`	`16`	`17`	`20`	`...`
ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 10:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`11`	`12`	`13`	`14`	`15`	`16`	`...`
ทศนิยม:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`10`	`11`	`12`	`13`	`14`	`15`	`16`	`...`
ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 12:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`C`	`11`	`12`	`13`	`14`	`...`
เลขฐานสอง:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`10`	`11`	`12`	`13`	`14`	`...`
ฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงฐาน 16:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`C`	`D`	`E`	`F`	`G`	`...`
เลขฐานสิบหก:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`C`	`D`	`E`	`F`	`10`	`...`

ตัวอย่าง

34152 (ในฟังก์ชันหนึ่งต่อหนึ่งฐาน 5) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (ในระบบเลขฐานสิบ)

119A (ในฟังก์ชันหนึ่งต่อหนึ่งฐาน 10 โดยที่ "A" แทนค่าหลักสิบ) = 1×10³ ⁺ 1×10² ⁺ 9× ^10¹ + 10×1 = 1200 (ในระบบเลขฐานสิบ)

รายการตัวอักษรทั่วไปที่มีองค์ประกอบมากกว่า 26 ตัว จะเป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง (bijective) โดยใช้ลำดับ A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC...

ระบบฐานสิบแบบหนึ่งต่อหนึ่ง

ระบบเลขฐานสิบแบบหนึ่ง ต่อ หนึ่ง (bijective base-10 system) เป็นระบบเลข ฐาน สิบ แบบ ตำแหน่งที่ไม่ใช้ตัวเลขใดๆ แทนเลขศูนย์แต่ใช้ตัวเลขหนึ่งตัวแทนเลขสิบ เช่นA

เช่นเดียวกับเลขฐานสิบ แบบดั้งเดิม ตัวเลขแต่ละหลักแสดงถึงกำลังของสิบ ตัวอย่างเช่น 123 คือ "หนึ่งร้อย บวกสองสิบ บวกสามหน่วย" จำนวนเต็มบวก ทั้งหมด ที่แสดงด้วยตัวเลขที่ไม่ใช่ศูนย์เท่านั้นในเลขฐานสิบแบบดั้งเดิม (เช่น 123) จะมีการแสดงแบบเดียวกันในระบบเลขฐานสิบแบบหนึ่งต่อหนึ่ง ส่วนจำนวนที่ใช้ศูนย์จะต้องเขียนใหม่ ตัวอย่างเช่น 10 กลายเป็น A, 20 แบบดั้งเดิมกลายเป็น 1A ("หนึ่งสิบ บวกสิบหน่วย"), 100 แบบดั้งเดิมกลายเป็น 9A, 101 แบบดั้งเดิมกลายเป็น A1, 302 แบบดั้งเดิมกลายเป็น 2A2, 1000 แบบดั้งเดิมกลายเป็น 99A, 1110 แบบดั้งเดิมกลายเป็น AAA, 2010 แบบดั้งเดิมกลายเป็น 19AA และอื่นๆ

การบวกและการคูณในระบบนี้โดยพื้นฐานแล้วเหมือนกับระบบเลขฐานสิบแบบดั้งเดิม ยกเว้นว่าการทดจะเกิดขึ้นเมื่อหลักนั้นเกินสิบ แทนที่จะเป็นเมื่อหลักนั้นเกินเก้า ดังนั้นในการคำนวณ 643 + 759 จะมีหลักหน่วยสิบสองหลัก (เขียน 2 ทางด้านขวาและทด 1 ไปยังหลักสิบ) หลักสิบสิบหลัก (เขียน A โดยไม่ต้องทดไปยังหลักร้อย) หลักร้อยสิบสามหลัก (เขียน 3 และทด 1 ไปยังหลักพัน) และหลักพันหนึ่งหลัก (เขียน 1) เพื่อให้ได้ผลลัพธ์ 13A2 แทนที่จะเป็น 1402 แบบเดิม

ระบบฐาน 26 แบบหนึ่งต่อหนึ่ง

ในระบบเลขฐาน 26 แบบหนึ่งต่อหนึ่ง เราสามารถใช้ตัวอักษรละติน "A" ถึง "Z" แทนค่าตัวเลข 26 หลัก คือ1ถึง26ได้ (A=1, B=2, C=3, ..., Z=26)

ด้วยการเลือกใช้สัญลักษณ์นี้ ลำดับตัวเลข (เริ่มต้นจาก 1) จะเริ่มจาก A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ...

แต่ละตำแหน่งของตัวเลขแสดงถึงกำลังของยี่สิบหก ตัวอย่างเช่น ตัวเลข WI แทนค่า2³ × 2⁶¹ ⁺ 9 × ^2⁶⁰ = 60⁷ ในฐานสิบ

สเปรดชีตหลาย โปรแกรม รวมถึงMicrosoft Excelใช้ระบบนี้ในการกำหนดป้ายกำกับให้กับคอลัมน์ของสเปรดชีต โดยเริ่มจาก A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA เป็นต้น ตัวอย่างเช่น ใน Excel 2013 อาจมีคอลัมน์ได้มากถึง 16384 คอลัมน์ (2¹⁴ ^ในรหัสไบนารี) โดยมีป้ายกำกับตั้งแต่ A ถึง XFD ^{[ 3 ]}มัลแวร์หลายเวอร์ชันก็ได้รับการตั้งชื่อโดยใช้ระบบนี้เช่นกัน ตัวอย่างเช่น ไวรัสมาโคร Microsoft Word ตัวแรกที่แพร่หลายอย่าง Concept มีชื่ออย่างเป็นทางการว่า WM/Concept.A เวอร์ชันที่ 26 คือ WM/Concept.Z เวอร์ชันที่ 27 คือ WM/Concept.AA เป็นต้น ระบบนี้ยังใช้ในการตั้งชื่อดาวแปรแสงอีกด้วย^{[ 4 ]}สามารถนำไปใช้กับปัญหาใดๆ ที่ต้องการการตั้งชื่ออย่างเป็นระบบโดยใช้ตัวอักษร ในขณะที่ใช้สตริงที่สั้นที่สุดเท่าที่จะเป็นไปได้

บันทึกทางประวัติศาสตร์

ข้อเท็จจริงที่ว่าจำนวนเต็มที่ไม่เป็นลบทุกจำนวนมีตัวแทนที่ไม่ซ้ำกันในฐานk ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง ( k ≥ 1) เป็น " ทฤษฎีบทพื้นบ้าน " ที่ถูกค้นพบซ้ำแล้วซ้ำเล่า ตัวอย่างในยุคแรกๆ ได้แก่Foster (1947)สำหรับกรณีk = 10 และSmullyan (1961)และBöhm (1964) สำหรับ k ≥ 1 ทั้งหมดSmullyan ใช้ระบบนี้เพื่อกำหนดหมายเลข Gödelให้กับสตริงของสัญลักษณ์ในระบบตรรกะ ในขณะที่ Böhm ใช้ตัวแทนเหล่านี้ในการคำนวณในภาษาโปรแกรมP′ ′ Knuth (1969)กล่าวถึงกรณีพิเศษของk = 10 และSalomaa (1973)กล่าวถึงกรณีk ≥ 2 Forslund (1995)ดูเหมือนจะเป็นการค้นพบใหม่ และตั้งสมมติฐานว่าหากระบบการนับในสมัยโบราณใช้ฐานk ที่เป็นฟังก์ชันหนึ่งต่อหนึ่ง อาจจะไม่ได้รับการยอมรับเช่นนั้นในเอกสารทางโบราณคดี เนื่องจากความไม่คุ้นเคยกับระบบนี้โดยทั่วไป

หมายเหตุ

^ "จำนวนเต็มฐาน k ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงสำหรับ n มีกี่หลัก?" Stackexchange สืบค้นเมื่อ22 กันยายน 2018
^ฟอร์สลุนด์ (1995 )
^ฮาร์วีย์, เกร็ก (2013), Excel 2013 สำหรับมือใหม่ , จอห์น ไวลีย์ แอนด์ ซันส์, ISBN 9781118550007.
^ Hellier, Coel (2001), "ภาคผนวก D: การตั้งชื่อดาวแปรแสง", ดาวแปรแสงหายนะ - วิธีการและเหตุผลที่พวกมันแปรแสง , Praxis Books in Astronomy and Space, Springer, หน้า 197, ISBN 9781852332112.

[1] "จำนวนเต็มฐาน k ที่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงสำหรับ n มีกี่หลัก?" Stackexchange สืบค้นเมื่อ22 กันยายน 2018

[FOOTNOTEForslund1995-2] ฟอร์สลุนด์ (1995 )

[3] ฮาร์วีย์, เกร็ก (2013), Excel 2013 สำหรับมือใหม่ , จอห์น ไวลีย์ แอนด์ ซันส์, ISBN 9781118550007.

[4] Hellier, Coel (2001), "ภาคผนวก D: การตั้งชื่อดาวแปรแสง", ดาวแปรแสงหายนะ - วิธีการและเหตุผลที่พวกมันแปรแสง , Praxis Books in Astronomy and Space, Springer, หน้า 197, ISBN 9781852332112.

1

[

[ 3 ]

[ 4 ]