คณิตศาสตร์เชิงนับ (Enumerative combinatorics)เป็นสาขาหนึ่งของคณิตศาสตร์เชิงการจัดเรียง (combinatorics)ที่เกี่ยวข้องกับจำนวนวิธีที่สามารถสร้างรูปแบบบางอย่างได้ ตัวอย่างของปัญหาประเภทนี้ ได้แก่ การนับจำนวนการจัดหมู่ (combinations)และการนับ จำนวนการเรียง สับเปลี่ยน (permutations ) โดยทั่วไปแล้ว เมื่อกำหนดเซตจำกัดจำนวนอนันต์S _{_i} ที่มีดัชนีเป็นจำนวนธรรมชาติคณิตศาสตร์เชิงนับจะพยายามอธิบายฟังก์ชันการนับที่นับจำนวนวัตถุในS_{_n}สำหรับแต่ละnแม้ว่าการนับจำนวนองค์ประกอบในเซตจะเป็นปัญหาทางคณิตศาสตร์ ที่ค่อนข้างกว้าง แต่ปัญหาหลายอย่างที่เกิดขึ้นในการประยุกต์ใช้มีคำอธิบายเชิงการจัดเรียงที่ ค่อนข้างง่าย วิธีการสิบสองทาง (Twelvefold way)ให้กรอบการทำงานที่เป็นเอกภาพสำหรับการนับจำนวนการเรียงสับเปลี่ยนการจัดหมู่และการแบ่งส่วน (partitions )

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

บ่อยครั้งที่สูตรปิดที่ซับซ้อนมักให้ข้อมูลเชิงลึกเพียงเล็กน้อยเกี่ยวกับพฤติกรรมของฟังก์ชันการนับเมื่อจำนวนวัตถุที่นับเพิ่มขึ้น ในกรณีเหล่านี้ การประมาณเชิง อะซิมโทติก อย่างง่าย อาจเหมาะสมกว่า ฟังก์ชันเป็นการประมาณเชิงอะซิมโทติกของถ้าเมื่อในกรณีนี้ เราเขียน${\displaystyle g(n)}$${\displaystyle f(n)}$${\displaystyle f(n)/g(n)\rightarrow 1}$${\displaystyle n\rightarrow \infty }$${\displaystyle f(n)\sim g(n).\,}$

ฟังก์ชันก่อกำเนิดใช้เพื่ออธิบายกลุ่มของวัตถุเชิงการจัดเรียง ให้ แทนกลุ่มของวัตถุ และให้F ( x ) เป็นฟังก์ชันก่อกำเนิดของกลุ่มนั้น แล้ว ${\displaystyle {\mathcal {F}}}$

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}}$

โดยที่แทนจำนวนของวัตถุเชิงการจัดเรียงที่มีขนาดnจำนวนของวัตถุเชิงการจัดเรียงที่มีขนาดnจึงกำหนดโดยสัมประสิทธิ์ของต่อไปนี้จะกล่าวถึงการดำเนินการทั่วไปบางอย่างกับตระกูลของวัตถุเชิงการจัดเรียงและผลกระทบต่อฟังก์ชันก่อกำเนิดฟังก์ชันก่อกำเนิดแบบเลขชี้กำลังก็ถูกนำมาใช้บ้างในบางครั้ง ในกรณีนี้จะมีรูปแบบดังนี้ ${\displaystyle f_{n}}$${\displaystyle x^{n}}$

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}}$

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

กำหนดให้ตระกูลเชิงคอมบินาทอริกสองตระกูลและมีฟังก์ชันก่อกำเนิดF ( x ) และG ( x ) ตามลำดับการรวมกันแบบไม่ทับซ้อนของตระกูลทั้งสอง ( ) จะมีฟังก์ชันก่อกำเนิดF ( x ) + G ( x ) ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle {\mathcal {F}}\cup {\mathcal {G}}}$

สำหรับตระกูลเชิงการจัดเรียงสองตระกูลดังข้างต้นผลคูณคาร์ทีเซียน (คู่) ของสองตระกูล ( ) มีฟังก์ชันก่อกำเนิดF ( x ) G ( x ) ${\displaystyle {\mathcal {F}}\times {\mathcal {G}}}$

ลำดับ (จำกัด) เป็นการขยายแนวคิดของคู่ตามที่นิยามไว้ข้างต้น ลำดับคือผลคูณคาร์ทีเซียนใดๆ ของวัตถุเชิงการจัดเรียงกับตัวมันเอง ในทางคณิตศาสตร์:

${\displaystyle {\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \cdots }$

กล่าวโดยสรุปคือ ลำดับว่างเปล่า หรือลำดับที่มีองค์ประกอบเดียว หรือลำดับที่มีองค์ประกอบสองตัว หรือลำดับที่มีองค์ประกอบสามตัว เป็นต้น ฟังก์ชันก่อกำเนิดจะเป็นดังนี้:

${\displaystyle 1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}.}$

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

ต้นไม้ไบนารีและต้นไม้ระนาบเป็นตัวอย่างของโครงสร้างเชิงผสมที่ไม่มีป้ายกำกับ ต้นไม้ประกอบด้วยโหนดที่เชื่อมต่อกันด้วยขอบในลักษณะที่ไม่มีวงจรโดยทั่วไปจะมีโหนดหนึ่งเรียกว่าโหนดราก ซึ่งไม่มีโหนดแม่ ในต้นไม้ระนาบแต่ละโหนดสามารถมีลูกได้จำนวนเท่าใดก็ได้ ในต้นไม้ไบนารี ซึ่งเป็นกรณีพิเศษของต้นไม้ระนาบ แต่ละโหนดสามารถมีลูกได้สองคนหรือไม่มีลูกเลยก็ได้ ให้แทนตระกูลของต้นไม้ระนาบทั้งหมด จากนั้นตระกูลนี้สามารถกำหนดแบบเวียนเกิดได้ดังนี้: ${\displaystyle {\mathcal {P}}}$

${\displaystyle {\mathcal {P}}=\{\bullet \}\times \,{\mbox{Seq}}({\mathcal {P}})}$

ในกรณีนี้แสดงถึงกลุ่มของวัตถุที่ประกอบด้วยโหนดเดียว ซึ่งมีฟังก์ชันก่อกำเนิดxให้P ( x ) แทนฟังก์ชันก่อกำเนิดกล่าวโดยสรุปคือ ต้นไม้ระนาบประกอบด้วยโหนดหนึ่งซึ่งมีต้นไม้ย่อยจำนวนหนึ่งติดอยู่ โดยแต่ละต้นไม้ย่อยก็เป็นต้นไม้ระนาบเช่นกัน เมื่อใช้การดำเนินการกับกลุ่มของโครงสร้างเชิงคอมบินาทอริกที่พัฒนาขึ้นก่อนหน้านี้ จะได้ฟังก์ชันก่อกำเนิดแบบเรียกซ้ำดังนี้: ${\displaystyle \{\bullet \}}$${\displaystyle {\mathcal {P}}}$

${\displaystyle P(x)=x\,{\frac {1}{1-P(x)}}}$

หลังจากแก้หาค่าP ( x ) แล้ว:

${\displaystyle P(x)={\frac {1-{\sqrt {1-4x}}}{2}}}$

ขณะนี้สามารถกำหนดสูตรที่ชัดเจนสำหรับจำนวนต้นไม้ระนาบขนาดn ได้แล้ว โดยการดึงค่าสัมประสิทธิ์ของ x ⁿ ออกมา :

${\displaystyle {\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}}$

หมายเหตุ: สัญลักษณ์ [ x ⁿ ] f ( x ) หมายถึงสัมประสิทธิ์ของx ⁿในf ( x ) การกระจายอนุกรมของรากที่สองนั้นอิงตามทฤษฎีบททวินามทั่วไปของนิวตัน เพื่อให้ได้ผลลัพธ์จากบรรทัดที่สี่ถึงบรรทัดที่ห้า จำเป็นต้อง มีการจัดการโดยใช้สัมประสิทธิ์ทวินามทั่วไป

นิพจน์ในบรรทัดสุดท้ายเท่ากับจำนวนคาตาลันลำดับ ^{ที่ (} n  − 1) ดังนั้นp _n = c _{n −1}