ในทางคณิตศาสตร์คำว่าการพิสูจน์เชิงการจัดเรียง มักใช้เพื่อหมายถึง การพิสูจน์ทางคณิตศาสตร์สองประเภท ได้แก่:

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

คำว่า "การพิสูจน์เชิงการจัดเรียง" อาจใช้ในความหมายกว้างๆ เพื่อหมายถึงการพิสูจน์เบื้องต้น ทุกประเภท ในคณิตศาสตร์เชิงการจัดเรียง อย่างไรก็ตาม ดังที่Glass (2003)เขียนไว้ในบทวิจารณ์ของเขาเกี่ยวกับBenjamin & Quinn (2003) (หนังสือเกี่ยวกับการพิสูจน์เชิงการจัดเรียง) เทคนิคสองอย่างง่ายๆ เหล่านี้ก็เพียงพอที่จะพิสูจน์ทฤษฎีบทหลายข้อในคณิตศาสตร์เชิงการจัดเรียงและทฤษฎีจำนวนได้

ตัวอย่างการพิสูจน์โดยการนับสองครั้งที่เป็นแบบอย่างคือสูตรที่รู้จักกันดีสำหรับจำนวนk - combinations (กล่าวคือ เซตย่อยที่มีขนาดk ) ของ เซตที่มีสมาชิก nตัว: ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}.}$

ในที่นี้ การพิสูจน์แบบหนึ่งต่อหนึ่งโดยตรงเป็นไปไม่ได้ เพราะด้านขวามือของเอกลักษณ์เป็นเศษส่วน จึงไม่มีเซตใดที่ ถูกนับ อย่างชัดเจน (แม้แต่การคิดวิเคราะห์สักเล็กน้อยก็แสดงให้เห็นว่าตัวส่วนหารตัวเศษลงตัวเสมอ) อย่างไรก็ตาม ตัวเศษนับผลคูณคาร์ทีเซียนของ เซตจำกัด kเซตที่มีขนาดn , n − 1 , ..., n − k + 1ในขณะที่ตัวส่วนนับการเรียงสับเปลี่ยนของ เซตที่มี kสมาชิก (เซตที่ถูกนับอย่างชัดเจนที่สุดโดยตัวส่วนจะเป็นเซตจำกัด k เซตที่เป็นผลคูณคาร์ทีเซียนอีกเซต หนึ่ง หากต้องการ เราสามารถแมปการเรียงสับเปลี่ยนไปยังเซตนั้นได้โดยใช้การจับคู่แบบหนึ่งต่อหนึ่งอย่างชัดเจน) ทีนี้ ให้Sเป็นเซตของลำดับของkสมาชิกที่เลือกจากเซตที่มีn สมาชิกของเราโดยไม่มีการซ้ำกัน ในด้านหนึ่ง มีการจับคู่แบบหนึ่งต่อหนึ่งอย่างง่ายระหว่างSกับผลคูณคาร์ทีเซียนที่สอดคล้องกับตัวเศษและในอีกด้านหนึ่ง มีการจับคู่แบบหนึ่งต่อหนึ่งจากเซตCของคู่ของ การจัดหมู่ kและการเรียงสับเปลี่ยนσของkไปยังSโดยการนำองค์ประกอบของCมาเรียงลำดับจากน้อยไปมาก แล้วเรียงสับเปลี่ยนลำดับนี้ด้วย  σเพื่อให้ได้องค์ประกอบของ  Sวิธีการนับทั้งสองแบบนี้ให้สมการ ${\displaystyle n(n-1)\cdots (n-k+1)}$

${\displaystyle n(n-1)\cdots (n-k+1)={\binom {n}{k}}k!,}$

และหลังจากหารด้วยk ! แล้ว จะได้สูตรที่ระบุไว้สำหรับโดยทั่วไปแล้ว หากสูตรการนับเกี่ยวข้องกับการหาร การให้เหตุผลแบบนับซ้ำสองครั้งที่คล้ายกัน (ถ้ามี) จะให้การพิสูจน์เอกลักษณ์เชิงการจัดเรียงที่ตรงไปตรงมาที่สุด แต่การให้เหตุผลแบบนับซ้ำสองครั้งไม่ได้จำกัดเฉพาะสถานการณ์ที่สูตรอยู่ในรูปแบบนี้เท่านั้น ${\displaystyle {\tbinom {n}{k}}}$

ต่อไปนี้เป็นการพิสูจน์เชิงการจัดเรียงที่เรียบง่ายกว่าและไม่เป็นทางการของเอกลักษณ์เดียวกัน:

${\displaystyle {\binom {n}{k}}k!(nk)!=n!}$

สมมติว่ามีคน n คนต้องการเข้าชมพิพิธภัณฑ์ แต่พิพิธภัณฑ์มีที่ว่างสำหรับคนเพียงk คนเท่านั้น ขั้นแรกให้เลือก คน kคนจากจำนวน คน nคนที่จะได้รับอนุญาตให้เข้าไป มี k! วิธีในการทำเช่นนี้ตามนิยาม จากนั้นจัดเรียง คน kคนให้อยู่ในแถวเดียวเพื่อให้พวกเขาสามารถจ่ายเงินทีละคนได้ มีk ! วิธีในการเรียงสับเปลี่ยนกลุ่มคนขนาด  k นี้ ต่อไป จัดเรียงคนn  −  kคนที่ต้องอยู่ข้างนอกให้อยู่ในแถวเดียวเพื่อให้พวกเขาสามารถเข้าไปทีละคนได้ในภายหลังเมื่อคนอื่นๆ ออกไป มี ( n  −  k )! วิธีในการทำเช่นนี้ แต่ตอนนี้เราได้จัดเรียงกลุ่มคนทั้งหมด n คนแล้ว ซึ่งสามารถทำได้ในn ! วิธี ดังนั้นทั้งสองข้างจึงนับจำนวนวิธีในการจัดเรียงคนnคน การหารจะได้สูตรที่รู้จักกันดีสำหรับ ${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {n}{k}}}$

สแตนลีย์ (1997)ยกตัวอย่าง ปัญหา การนับเชิงการจัดเรียง (การนับจำนวนลำดับของเซต ย่อย kเซตS ₁ , S ₂ , ... S _kที่สามารถสร้างขึ้นจากเซตของ รายการ nรายการ โดยที่จุดตัดของเซตย่อยทั้งหมดเป็นเซตว่าง) พร้อมด้วยวิธีพิสูจน์สองวิธีที่แตกต่างกันสำหรับคำตอบ วิธีพิสูจน์แรก ซึ่งไม่ใช่เชิงการจัดเรียง ใช้การอุปมานทางคณิตศาสตร์และฟังก์ชันก่อกำเนิดเพื่อหาว่าจำนวนลำดับประเภทนี้คือ (2 ^k  −1) ⁿวิธีพิสูจน์ที่สองนั้นอิงจากการสังเกตว่ามีเซตย่อยแท้ 2 ^k  −1 เซต ของเซต {1, 2, ..., k } และฟังก์ชัน (2 ^k  −1) ⁿฟังก์ชันจากเซต {1, 2, ..., n } ไปยังตระกูลของเซตย่อยแท้ของ {1, 2, ..., k } ลำดับที่จะนับสามารถจับคู่แบบหนึ่งต่อหนึ่งกับฟังก์ชันเหล่านี้ได้ โดยที่ฟังก์ชันที่สร้างขึ้นจากลำดับของเซตย่อยที่กำหนดจะแมปแต่ละองค์ประกอบiไปยังเซต { j  |  i  ∈  S _j }

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

สแตนลีย์ไม่ได้แยกแยะความแตกต่างระหว่างการพิสูจน์แบบหนึ่งต่อหนึ่งทั่วถึงและการพิสูจน์แบบนับสองครั้งอย่างชัดเจน และให้ตัวอย่างของทั้งสองประเภท แต่ความแตกต่างระหว่างการพิสูจน์เชิงการจัดเรียงสองประเภทนี้สามารถเห็นได้จากตัวอย่างที่Aigner & Ziegler (1998) นำเสนอ ซึ่งเป็นการพิสูจน์สูตรของ Cayleyที่ระบุว่ามีต้นไม้ที่แตกต่างกันn ^{n  − 2} ต้น ที่สามารถสร้างขึ้นจากเซตของ โหนด nโหนดที่กำหนดให้ Aigner และ Ziegler แสดงรายการการพิสูจน์ทฤษฎีบทนี้สี่แบบ โดยแบบแรกเป็นการพิสูจน์แบบหนึ่งต่อหนึ่งทั่วถึง และแบบสุดท้ายเป็นการพิสูจน์แบบนับสองครั้ง พวกเขายังกล่าวถึง แต่ไม่ได้อธิบายรายละเอียดของการพิสูจน์แบบหนึ่งต่อหนึ่งทั่วถึงแบบที่ห้า

วิธีที่เป็นธรรมชาติที่สุดในการหาบทพิสูจน์แบบหนึ่งต่อหนึ่งของสูตรนี้คือการหาความสัมพันธ์แบบหนึ่งต่อหนึ่งระหว่าง ต้นไม้ที่มี nโหนดกับกลุ่มของวัตถุที่มี สมาชิก n ^{n  − 2 ตัว}เช่น ลำดับของ ค่า n  − 2 ค่าแต่ละค่าอยู่ในช่วงตั้งแต่ 1 ถึง  nความสัมพันธ์แบบหนึ่งต่อหนึ่งดังกล่าวสามารถหาได้โดยใช้ลำดับ Prüferของแต่ละต้นไม้ ต้นไม้ใดๆ ก็สามารถเข้ารหัสเป็นลำดับ Prüfer ได้อย่างไม่ซ้ำกัน และลำดับ Prüfer ใดๆ ก็สามารถถอดรหัสเป็นต้นไม้ได้อย่างไม่ซ้ำกัน ผลลัพธ์ทั้งสองนี้รวมกันแล้วให้บทพิสูจน์แบบหนึ่งต่อหนึ่งของสูตรของ Cayley

การพิสูจน์แบบหนึ่งต่อหนึ่งทั่วถึงอีกวิธีหนึ่ง ซึ่งเสนอโดย Aigner และ Ziegler และให้เครดิตแก่André Joyalนั้น เกี่ยวข้องกับการจับคู่แบบหนึ่งต่อหนึ่งทั่วถึงระหว่าง ต้นไม้ nโหนดที่มีโหนดที่กำหนดไว้สองโหนด (ซึ่งอาจเหมือนกันก็ได้) กับป่าเทียมแบบมีทิศทางnโหนดถ้ามี ต้นไม้ _n โหนดจำนวน T nต้น ก็จะมี ต้นไม้ที่มีโหนดที่กำหนดไว้สองโหนดจำนวน n ² T _nต้น และป่าเทียมอาจถูกกำหนดได้โดยการระบุจุดปลายของขอบที่ยื่นออกมาจากโหนดนั้นสำหรับแต่ละโหนด มี ตัวเลือกที่เป็นไปได้ nตัวเลือกสำหรับจุดปลายของขอบเดียว (โดยอนุญาตให้มีวงวนในตัวเอง) ดังนั้นจึง มีป่าเทียมที่เป็นไปได้จำนวน n ⁿ ป่า โดยการหาการจับคู่แบบหนึ่งต่อหนึ่งทั่วถึงระหว่างต้นไม้ที่มีโหนดที่มีป้ายกำกับสองโหนดและป่าเทียม การพิสูจน์ของ Joyal แสดงให้เห็นว่าT _n  =  n ^{n  −} 2

สุดท้ายนี้ บทพิสูจน์ที่สี่ของสูตรของเคย์ลีย์ที่นำเสนอโดยไอเนอร์และซีเกลอร์ เป็นบทพิสูจน์แบบนับสองครั้งโดยจิม พิตแมนในบทพิสูจน์นี้ พิตแมนพิจารณาลำดับของขอบที่มีทิศทางซึ่งอาจเพิ่มเข้าไปในกราฟว่างที่มีnโหนดเพื่อสร้างต้นไม้ที่มีรากเดียว และนับจำนวนลำดับดังกล่าวในสองวิธีที่แตกต่างกัน โดยการแสดงวิธีการหาลำดับประเภทนี้โดยการเลือกต้นไม้ รากของต้นไม้ และลำดับของขอบในต้นไม้ เขาแสดงให้เห็นว่ามี ลำดับที่เป็นไปได้ T _n n ! ลำดับ และโดยการนับจำนวนวิธีที่ลำดับบางส่วนสามารถขยายได้ด้วยขอบเดียว เขาแสดงให้เห็นว่ามี ลำดับที่เป็นไปได้ n ^{n  − 2} n ! ลำดับ การเทียบสูตรสองสูตรที่แตกต่างกันนี้สำหรับขนาดของเซตลำดับขอบเดียวกันและตัดตัวประกอบร่วมn ! ออกไป จะนำไปสู่สูตรของเคย์ลีย์

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