กลับไปหน้าบทความ

อ่าน 5 นาที

การปูกระเบื้องโดมิโน

เชิงผสม/แบบจำลองที่แก้ไขได้อย่างแน่นอน/โมเดลขัดแตะ/การจับคู่ (ทฤษฎีกราฟ)/การแบ่งเขตสี่เหลี่ยม/กลศาสตร์ทางสถิติ/ปริศนาการปูกระเบื้อง

ในทางเรขาคณิต การปู พื้นที่ด้วยรูปโดมิโนบนระนาบยูคลิดคือการปูพื้นที่ด้วย รูป โดมิโน ซึ่ง เป็นรูปทรงที่เกิดจากการรวมกันของสี่เหลี่ยมจัตุรัสหน่วย สองรูป โดยวางขอบชนกัน...

การปูกระเบื้องโดมิโน

การเรียงโดมิโนบนพื้นที่สี่เหลี่ยมจัตุรัสขนาด 8x8

ในทางเรขาคณิต การปู พื้นที่ด้วยรูปโดมิโนบนระนาบยูคลิดคือการปูพื้นที่ด้วย รูป โดมิโน ซึ่ง เป็นรูปทรงที่เกิดจากการรวมกันของสี่เหลี่ยมจัตุรัสหน่วย สองรูป โดยวางขอบชนกัน หรือกล่าวอีกนัยหนึ่งคือ เป็นการจับคู่ที่สมบูรณ์แบบในกราฟตารางที่เกิดจากการวางจุดยอดไว้ที่กึ่งกลางของแต่ละสี่เหลี่ยมจัตุรัสในบริเวณนั้น และเชื่อมต่อจุดยอดสองจุดเมื่อจุดยอดเหล่านั้นตรงกับสี่เหลี่ยมจัตุรัสที่อยู่ติดกัน

ฟังก์ชันความสูง

สำหรับรูปแบบการปูพื้นบางประเภทบนตารางปกติสองมิติ สามารถกำหนดฟังก์ชันความสูงโดยเชื่อมโยงจำนวนเต็มกับจุดยอดของตารางได้ ตัวอย่างเช่น วาดกระดานหมากรุก กำหนดจุดหนึ่งที่มีความสูง 0 จากนั้นสำหรับทุกจุดจะมีเส้นทางจากจุดหนึ่งไปยังอีกจุดหนึ่งบนเส้นทางนี้ กำหนดความสูงของแต่ละจุด(เช่น มุมของช่องสี่เหลี่ยม) ให้เป็นความสูงของจุดก่อนหน้าบวกหนึ่งหากช่องสี่เหลี่ยมทางด้านขวาของเส้นทางจาก จุด หนึ่งไป ยังอีกจุดหนึ่ง เป็นสีดำ และลบหนึ่งหากเป็นสีอื่น

สามารถดูรายละเอียดเพิ่มเติมได้ในKenyon & Okounkov (2005 )

ภาวะความสูงของเธอร์สตัน

วิลเลียม เธอร์สตัน  ( 1990 ) อธิบายการทดสอบเพื่อพิจารณาว่าพื้นที่ที่เชื่อมต่อกันอย่างง่าย ซึ่งเกิดจากการรวมกันของสี่เหลี่ยมจัตุรัสหน่วยในระนาบนั้น สามารถปูด้วยโดมิโนได้หรือไม่ เขาสร้างกราฟแบบไม่มีทิศทางซึ่งมีจุดยอดเป็นจุด ( x , y , z ) ในแลตทิซจำนวนเต็ม สามมิติ โดยแต่ละจุดดังกล่าวเชื่อมต่อกับจุดข้างเคียงสี่จุด: ถ้าx  +  yเป็นจำนวนคู่ จุด ( x , y , z ) จะเชื่อมต่อกับ ( x  + 1, y , z  + 1), ( x  - 1, y , z  + 1), ( x , y  + 1, z  - 1) และ ( x , y  - 1, z  - 1) ในขณะที่ถ้าx  +  yเป็นจำนวนคี่ จุด ( x , y , z ) จะเชื่อมต่อกับ ( x  + 1, y , z  - 1), ( x  - 1, y , z  - 1), ( x , y  + 1, z  + 1) และ ( x , y  - 1, z  + 1) ขอบเขตของบริเวณ ซึ่งมองได้ว่าเป็นลำดับของจุดจำนวนเต็มในระนาบ ( x , y ) จะสามารถยกขึ้นได้อย่างไม่ซ้ำกัน (เมื่อเลือกความสูงเริ่มต้นแล้ว) ไปสู่เส้นทางในกราฟสามมิติเงื่อนไขที่จำเป็นสำหรับการปูพื้นที่นี้ได้คือ เส้นทางนี้จะต้องปิดตัวลงเพื่อสร้างเส้นโค้งปิดอย่างง่ายในสามมิติ อย่างไรก็ตาม เงื่อนไขนี้ไม่เพียงพอ จากการวิเคราะห์เส้นทางขอบเขตอย่างละเอียดมากขึ้น เธอร์สตันได้ให้เกณฑ์สำหรับการปูพื้นที่ได้ ซึ่งเป็นทั้งเงื่อนไขที่เพียงพอและจำเป็น

การนับจำนวนการปูพื้นของภูมิภาค

การเรียงโดมิโนบนพื้นสี่เหลี่ยมจัตุรัสขนาด 8x8 โดยใช้จำนวนคู่ขอบยาวน้อยที่สุด (1 คู่ตรงกลาง) การจัดเรียงนี้ยังเป็นการ ปู เสื่อทาทามิบนพื้นสี่เหลี่ยมจัตุรัสขนาด 8x8 ที่ถูกต้อง โดยไม่มีโดมิโนสี่ตัวใดสัมผัสกันที่จุดภายใน

จำนวนวิธีในการคลุมสี่เหลี่ยมผืนผ้าด้วยโดมิโน ซึ่งคำนวณโดยอิสระโดยTemperley & Fisher (1961)และKasteleyn (1961)นั้นกำหนดโดย (ลำดับA099390ในOEIS )

เมื่อทั้งmและnเป็นจำนวนคี่ สูตรจะลดรูปเหลือศูนย์จำนวนการปูโดมิโนที่เป็นไปได้

กรณีพิเศษเกิดขึ้นเมื่อปูสี่เหลี่ยมด้วย โดมิโน nตัว: ลำดับจะลดลงเหลือลำดับฟิโบนาชชี[ 1 ]

กรณีพิเศษอีกกรณีหนึ่งเกิดขึ้นสำหรับกำลังสองที่มีm = n = 0, 2, 4, 6, 8, 10, 12, ... คือ

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (ลำดับA004003ในOEIS )

สามารถหาตัวเลขเหล่านี้ได้โดยการเขียนให้อยู่ในรูปของPfaffianของเมทริกซ์สมมาตรเฉียงซึ่ง สามารถหา ค่าลักษณะ เฉพาะได้อย่างชัดเจน เทคนิคนี้สามารถนำไปประยุกต์ใช้ได้ในหลายสาขาคณิตศาสตร์ ตัวอย่างเช่น ในการคำนวณ ฟังก์ชันสหสัมพันธ์ไดเมอร์-ไดเมอร์แบบคลาสสิก 2 มิติในกลศาสตร์ สถิติ

จำนวนการปูพื้นของบริเวณหนึ่งมีความไวต่อเงื่อนไขขอบเขตมาก และสามารถเปลี่ยนแปลงอย่างมากได้แม้เพียงการเปลี่ยนแปลงรูปร่างของบริเวณนั้นเพียงเล็กน้อย ตัวอย่างเช่น จำนวนการปูพื้นของรูปเพชรแอซเท็กอันดับnซึ่งจำนวนการปูพื้นคือ 2 ( n  + 1) n /2หากเปลี่ยนเป็น "รูปเพชรแอซเท็กเสริม" อันดับnที่มีแถวยาว 3 แถวตรงกลางแทนที่จะเป็น 2 แถว จำนวนการปูพื้นจะลดลงเหลือจำนวนที่น้อยกว่ามาก D( n , n ) ซึ่งเป็นจำนวนเดลานอย ซึ่งมี การเติบโตแบบเลขชี้กำลังเท่านั้น ไม่ใช่ แบบเลขชี้กำลังยิ่งยวด สำหรับ " รูป เพชรแอซเท็ กลดรูป" อันดับnที่มีแถวยาวตรงกลางเพียงแถวเดียว จะมีการปูพื้นเพียงหนึ่งครั้งเท่านั้น

เสื่อทาทามิ

เสื่อทาทามิเป็นเสื่อปูพื้นของญี่ปุ่นที่มีรูปร่างคล้ายโดมิโน (สี่เหลี่ยมผืนผ้าขนาด 1x2) ใช้สำหรับปูพื้นห้อง แต่มีกฎเพิ่มเติมเกี่ยวกับการวาง โดยทั่วไปแล้ว จุดบรรจบที่เสื่อทาทามิสามผืนมาบรรจบกันถือเป็นมงคล ในขณะที่จุดบรรจบที่เสื่อทาทามิสี่ผืนมาบรรจบกันถือเป็นอัปมงคล ดังนั้นการปูพื้นด้วยเสื่อทาทามิที่ถูกต้องคือการที่เสื่อทาทามิสามผืนมาบรรจบกันที่มุมใดมุมหนึ่งเท่านั้น[ 2 ]ปัญหาของการปูพื้นห้องที่ไม่เป็นรูปทรงปกติด้วยเสื่อทาทามิที่มาบรรจบกันสามผืนที่มุมนั้นเป็นปัญหาNP- complete [ 3 ]

การประยุกต์ใช้ในฟิสิกส์เชิงสถิติ

มีการจับคู่แบบหนึ่งต่อหนึ่งระหว่างการปูพื้นโดมิโนเป็นระยะและการกำหนดค่าสถานะพื้นฐานของแบบจำลอง Ising ที่ถูกขัดขวางอย่างสมบูรณ์ บนโครงตาข่ายเป็นระยะสองมิติ[ 4 ]ที่สถานะพื้นฐาน แผ่นแต่ละแผ่นของแบบจำลองสปินจะต้องมีปฏิสัมพันธ์ที่ถูกขัดขวาง เพียงหนึ่งเดียวเท่านั้น ดังนั้น เมื่อมองจากโครงตาข่ายคู่ขนาน ขอบที่ถูกขัดขวางแต่ละขอบจะต้องถูก "ปกคลุม" ด้วย สี่เหลี่ยมผืนผ้า ขนาด 1x2โดยที่สี่เหลี่ยมผืนผ้าเหล่านั้นครอบคลุมโครงตาข่ายทั้งหมดและไม่ทับซ้อนกัน หรือการปูพื้นโดมิโนของโครงตาข่ายคู่ขนาน

ดูเพิ่มเติม

หมายเหตุ

อ่านเพิ่มเติม

  • Bodini, Olivier; Latapy, Matthieu (2003), "การปูพื้นแบบทั่วไปด้วยฟังก์ชันความสูง" (PDF) , Morfismos , 7 (1): 47– 68, arXiv : 2101.08347 , เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2021-11-25 , เรียกดูเมื่อ 2021-09-19
  • Faase, FJ (1998), "เกี่ยวกับจำนวนของกราฟย่อยที่แผ่ขยายเฉพาะของกราฟ", Ars Combinatoria , 49 : 129–154 , MR 1633083 
  • Hock, JL; McQuistan, RB (1984), "หมายเหตุเกี่ยวกับความเสื่อมของอาชีพสำหรับไดเมอร์บนพื้นที่แลตติสสองมิติอิ่มตัว", Discrete Applied Mathematics , 8 : 101–104 , doi : 10.1016/0166-218X(84)90083-0 , MR  0739603
  • Kenyon, Richard (2000), "แบบจำลองไดเมอร์ระนาบที่มีขอบเขต: บทสำรวจ", ใน Baake, Michael; Moody, Robert V. (บรรณาธิการ), ทิศทางในควาซิคริสตัลทางคณิตศาสตร์ , CRM Monograph Series, เล่มที่ 13, American Mathematical Society , หน้า  307–328 , ISBN 0-8218-2629-8, MR  1798998
  • Propp, James (2005), "Lambda-determinants and domino-tilings", Advances in Applied Mathematics , 34 (4): 871– 879, arXiv : math.CO/0406301 , doi : 10.1016/j.aam.2004.06.005 , S2CID  15679557
  • Sellers, James A. (2002), "การปูพื้นโดมิโนและผลคูณของจำนวนฟิโบนาชชีและจำนวนเพลล์" , Journal of Integer Sequences , 5 (บทความ 02.1.2): 12, Bibcode : 2002JIntS...5...12S
  • Stanley, Richard P. (1985), "เกี่ยวกับการปกคลุมไดเมอร์ของสี่เหลี่ยมผืนผ้าที่มีความกว้างคงที่", Discrete Applied Mathematics , 12 : 81–87 , doi : 10.1016/0166-218x(85)90042-3 , MR  0798013
  • เวลส์, เดวิด (1997), พจนานุกรมตัวเลขแปลกและน่าสนใจของเพนกวิน (ฉบับปรับปรุง), ลอนดอน: เพนกวิน, หน้า 182, ISBN 0-14-026149-4
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Domino_tiling&oldid=1351759258 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ การปูกระเบื้องโดมิโน

ในทางเรขาคณิต การปู พื้นที่ด้วยรูปโดมิโนบนระนาบยูคลิดคือการปูพื้นที่ด้วย รูป โดมิโน ซึ่ง เป็นรูปทรงที่เกิดจากการรวมกันของสี่เหลี่ยมจัตุรัสหน่วย สองรูป โดยวางขอบชนกัน...

ฟังก์ชันความสูง

สำหรับรูปแบบการปูพื้นบางประเภทบนตารางปกติสองมิติ สามารถกำหนดฟังก์ชันความสูงโดยเชื่อมโยงจำนวนเต็มกับ จุดยอด ของตารางได้ ตัวอย่างเช่น วาดกระดานหมากรุก กำหนดจุดหนึ่งที่มีความสูง 0 จากนั้นสำหรับทุกจุดจะมีเส้นทางจากจุดหนึ่งไปยังอีกจุดหนึ่งบนเส้นทางนี้...

ภาวะความสูงของเธอร์สตัน

วิลเลียม เธอร์สตัน ( 1990 ) อธิบายการทดสอบเพื่อพิจารณาว่าพื้นที่ที่เชื่อมต่อกันอย่างง่าย ซึ่งเกิดจากการรวมกันของสี่เหลี่ยมจัตุรัสหน่วยในระนาบนั้น สามารถปูด้วยโดมิโนได้หรือไม่ เขาสร้าง กราฟแบบไม่มีทิศทาง ซึ่งมีจุดยอดเป็นจุด ( x , y , z ) ใน แลตทิซจำนวนเต็ม...

การนับจำนวนการปูพื้นของภูมิภาค

จำนวนวิธีในการคลุมสี่เหลี่ยมผืนผ้าด้วยโดมิโน ซึ่งคำนวณโดยอิสระโดย Temperley & Fisher (1961) และ Kasteleyn (1961) นั้นกำหนดโดย (ลำดับ A099390 ใน OEIS ) ม × n {\displaystyle m\times n} ม n 2 {\displaystyle {\frac {mn}{2}}} ∏ เจ = 1 ⌈ ม 2 ⌉ ∏ เค = 1 ⌈ n 2 ⌉ ( 4...