এক-এক এবং উপরিপূর্ণ প্রমাণ
গণনা শাস্ত্র, এক-এক এবং উপরিপূর্ণ প্রমাণ একটি প্রমাণ কৌশল যা দুটি সেটের মধ্যে সমান সংখ্যক উপাদান আছে, অথবা দুটি গণনামূলক শ্রেণীর সেটগুলোর আকার সমান আছে তা প্রমাণ করতে ব্যবহৃত হয়, একটি এক-এক ফাংশন খুঁজে বের করে যা একটি সেটকে অন্য সেটের উপরে এক-একভাবে মানচিত্রিত করে। এই কৌশলটি নির্দিষ্ট সেটের উপাদানের সংখ্যা নির্ধারণের জন্য একটি সূত্র খুঁজে বের করার উপায় হিসেবে কার্যকর হতে পারে, যখন সেটগুলিকে অন্যান্য সেটগুলির সাথে মিলিত করা হয় যেগুলো গণনা করা সহজ। তদ্বারা, এক-এক মানচিত্রের প্রকৃতিটি প্রায়ই দুটি বা উভয় সেটের মধ্যে শক্তিশালী অন্তর্দৃষ্টি প্রদান করে।
মৌলিক উদাহরণ
বিনোমিয়াল সহগের সিমেট্রি প্রমাণ
বিনোমিয়াল সহগের সিমেট্রি বলছে যে
এর মানে হল যে একটি সেটের মধ্যে টেমপ্লেট:Math জিনিস বেছে নেওয়ার যেসব উপায় আছে, সেটের আকার টেমপ্লেট:Math হলে, ঠিক তেমনি টেমপ্লেট:Math জিনিস বেছে নেওয়ার উপায়ও সমান।
এক-এক প্রমাণের মূল ধারণাটি একটি সাধারণ উদাহরণ থেকে বোঝা যেতে পারে: টেমপ্লেট:Mathটি শিশুকে আইসক্রিম কন দেওয়ার জন্য বেছে নেওয়া, যদি টেমপ্লেট:Mathটি শিশুদের একটি দলের মধ্যে, ঠিক তেমনি টেমপ্লেট:Math শিশুকে আইসক্রিম কন দেওয়া থেকে বঞ্চিত করা হয়।
অন্যান্য উদাহরণ
যেসব সমস্যা এক-এক প্রমাণ গ্রহণযোগ্য তা শুধু বিনোমিয়াল সহগের পরিচয়েই সীমাবদ্ধ নয়। সমস্যার জটিলতা বাড়ানোর সাথে সাথে, এক-এক প্রমাণ আরও জটিল হতে পারে। এই কৌশলটি বিন্যস্ত গাণিতিক শাস্ত্র যেমন গণনা শাস্ত্র, গ্রাফ তত্ত্ব, এবং সংখ্যা তত্ত্ব ক্ষেত্রে বিশেষভাবে কার্যকরী।
গণনা শাস্ত্রে এক-এক প্রমাণের সবচেয়ে প্রাচীন উদাহরণগুলির মধ্যে রয়েছে:
- প্রুফার সিকুয়েন্স, যা কেলির সূত্র প্রমাণ করে, যা লেবেলড গাছর সংখ্যা দেয়।
- রবিনসন-শেনস্টেড অ্যালগরিদম, যা বার্নসাইড'স সূত্র প্রমাণ করে, যা সামমিতিক গোষ্ঠীর সংখ্যা দেয়।
- কনজুগেশন ইয়ং ডায়াগ্রামদের, যা একটি ঐতিহ্যবাহী ফলাফল প্রমাণ করে, কিছু ইন্টিজার পার্টিশন এর সংখ্যা সম্পর্কে।
- পেন্টাগোনাল নাম্বার থিওরেম এর এক-এক প্রমাণ।
- ক্যাটালান নাম্বার এর সূত্রের এক-এক প্রমাণ।
আরও দেখুন
- বিনোমিয়াল থিওরেম
- শ্রোডার-বার্নস্টাইন সূত্র
- ডাবল কাউন্টিং (প্রমাণ কৌশল)
- গণনামূলক নীতি
- গণনামূলক প্রমাণ
- ক্যাটাগোরিফিকেশন
তথ্যসূত্র
অতিরিক্ত পাঠ
- লোহের, নিকোলাস এ. (২০১১)। Bijective Combinatorics. CRC Press. টেমপ্লেট:ISBN, টেমপ্লেট:ISBN.
বাইরের লিঙ্ক
- "Division by three" – ডয়েল এবং কনওয়ে দ্বারা।
- "A direct bijective proof of the hook-length formula" – নভেলি, পাক এবং স্টোইয়ানোভস্কি দ্বারা।
- "Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees" – গিলেস শাফার দ্বারা।
- "Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials" – ডোরোন জেইলবার্গ দ্বারা।
- "Partition Bijections, a Survey" – ইগর পাক দ্বারা।
- Garsia-Milne Involution Principle – MathWorld থেকে।