Permutation
বিন্যাস
`n` টা থেকে `k` টা বাছা যেখানে **ক্রম গুরুত্বপূর্ণ** এবং পুনরাবৃত্তি নেই — `P(n,k) = n!/(n−k)!`।
P(n,k) = n(n−1)(n−2)⋯(n−k+1) = n!/(n−k)!প্রথম position-এ n টা পছন্দ, দ্বিতীয়তে n−1, ইত্যাদি।
k = n হলে P(n,n) = n! — পুরো সাজানোর সংখ্যা।
গোনার চারটা মৌলিক ক্ষেত্র:
| ক্রম গুরুত্বপূর্ণ | ক্রম নয় | |
|---|---|---|
| পুনরাবৃত্তি হয় | n^k | C(n+k−1, k) |
| পুনরাবৃত্তি নয় | P(n,k) | C(n,k) |
দুইটা প্রশ্ন করলেই সঠিকটা বেরিয়ে আসে: ক্রম বদলালে ভিন্ন উত্তর? একই জিনিস দুইবার নেওয়া যায়?
n! কত দ্রুত বাড়ে: 52! ≈ 8×10⁶⁷ — দৃশ্যমান মহাবিশ্বের
পরমাণুর সংখ্যার কাছাকাছি। তাই একটা তাসের প্যাকেট ভালো shuffle
করলে সেই বিন্যাস প্রায় নিশ্চিতভাবে মানব ইতিহাসে আগে ঘটেনি।
Comparison sort-এর Ω(n log n) lower bound সরাসরি এখান থেকে:
n! টা সম্ভাব্য output মানে decision tree-তে n! টা leaf,
তাই height অন্তত log₂(n!) = Θ(n log n)।