কম্বিনেশন ( Combination )

কোন বড় গ্রুপ থেকে কিছু সংখ্যক জিনিস নিয়ে ছোট ছোট গ্রুপে ভাগ করাই হল কম্বিনেশন। এখানে পারমুটেশন এর মত অর্ডার এর কোন প্রভাব থাকেনা। যেমনঃ ৩ টি জিনিস থেকে আমরা ২ টি জিনিস নিতে পারি এভাবেঃ
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।

অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)

বাইনোমিয়াল কো-এফিশিয়েন্ট ( Binomial Coefficient )

বাইনোমিয়াল কোএফিশিয়েন্ট হল অর্ডার বিবেচনা না করে ভিন্ন ভিন্ন সম্ভাবনাকে নেয়া। শুনতে কঠিন লাগলেও ব্যাপারটি আসলে কিছুইনা। আমরা n জিনিস থেকে k জিনিস নিবো, অর্ডার বিবেচনা না করে। এটিকে কতভাবে নেয়া যাবে, এটিই বাইনোমিয়াল কোএফিশিয়েন্ট, অর্থাৎ কম্বিনেশন। 

আমরা কিছু সিরিজ এর এক্সপানশন দেখিঃ

(x + y)⁰ = 1
(x + y)¹ = x + y

(x + y)² = x² + 2xy + y²

(x + y)³ = x³ + 3x²y + 3xy² + y³

(x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

এসব সিরিজ কে আমরা এভাবে লিখতে পারি কমন ফর্মেঃ 

আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) ⁿ
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ

আমরা n = 4 নিয়ে দেখিঃ

(1 + x)⁴ = x⁴ + 4x³ + 6x² + 4x + 1
এখন কো-এফিশিয়েন্টগুলি হবেঃ 1  4  6  4  1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ

(x + y)ⁿ = (nC0)(xⁿy⁰) + (nC1)(x^n-11y¹) + (nC2)(x^n-22y²) + ... + (nCn)(x⁰yⁿ);  [nCk = combnation of k element from n or n choose k]

আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ

১। ফ্যাক্টরিয়াল ( Factorial )

আমরা সরাসরি nCk ফর্মুলা ব্যবহার করে nCk বের করতে পারি।
ফর্মুলাঃ nCk  =  [ n! ] / [  k! * (n-k)! ]

কিন্তু এভাবে আমরা সর্বোচ্চ ২১-২২ ফ্যাক্টরিয়াল পর্যন্ত হিসাবে করতে পারবো। এর চেয়ে বেশি আমরা সি++ এ করতে গেলে আমাদের বিগ-ইন্টিজার লাইব্রেরি ব্যবহার করতে হবে। তবে পাইথন এ আমরা হিসাব করতে পারবো এবং এই হিসাবের কমপ্লেক্সিটি হল O(n).
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।

২। রিকার্সন ( Recursion )

nCk বের করার রিকার্সন ফর্মুলা হলঃ nCk (i,k) = nCk (i-1,k-1) + nCk (i-1,k);

আমাদের টাইম এবং স্পেস কমপ্লেক্সিটি হবেঃ O(n*k) for nCk

আমরা একে একটু মডিফাই করে স্পেস কমপ্লেক্সিটি কমিয়ে আনতে পারি। আমরা আগের সারি চেক করবো, কারন আমাদের ঐ সারিগুলো আসলে দরকার হবেনা পরে আর।

৩। কম্বিনেশন এর বিস্তার ( Expansion of Combination )

আমরা জানি, nCk  =  [ n! ] / [  k! * (n-k)! ], অর্থাৎ

               [ n(n-1)(n-2) ... (n-k+1) ] [ (n-k) ... (1) ]

-------------------------------------------------------------------------

                  [ (n-k) ... (1) ] [ k(k-1)(k-2) .... (1) ]

আমরা লব এবং হর থেকে [ (n-k) ... (1) ] টার্ম কেটে ফেলতে পারি, তাহলে আমাদের ফাইনাল টার্ম হবেঃ

 n       (n-1)      (n-2)      (n-k+1)

---  *  ------  *  ------  *  ----------

 k       (k-1)      (k-2)          (1)

আমরা একে এভাবে লিখতে পারিঃ

nCk (n,k) = 1                                             ; if k == 0

                     else  (n/k) * nCk (n-1, k-1)

৪। প্রাইম এর পাওয়ার ( Power of Prime )

আমরা ফ্যাক্টরিয়াল এর কোন প্রাইম এর পাওয়ার বের করতে পারি এভাবেঃ

P_prime = floor[ n/prime ] + floor[ n/prime² ] + .....

এখানে n = factorial, prime = the prime whose power in n-factorial we are calculating
আমরা nCk এর মাঝে p প্রাইম এর পাওয়ার বের করবো এভাবেঃ
power = fact(n, p) - fact(r, p) - fact(n-r, p)
এরপরে আমরা p^power করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।

৫। চাইনিজ রিমেইন্ডার থিওরেম  ( Chinese Remainder Theorem )

যদি আমাদের এরকম বের করতে বলা হয়ঃ nCk mod m where m is not prime , সেক্ষেত্রে আমরা m কে প্রাইম এ ফ্যাক্টরাইজ করার পরে CRT(Chinese Remainder Theorem) ব্যবহার করে মান বের করবো।

Prime Numbers (sieve of Eratosthenes)

প্রাইম  (Prime ) সংখ্যা বলতে আমরা বুঝি এমন সংখ্যা যাকে ঐ সংখ্যা যার শুধুমাত্র ২ টি ফ্যাক্টর ( ১ এবং সংখ্যাটি নিজে ) আছে। অর্থাৎ যেসব সংখ্যাকে ঐ সংখ্যা এবং ১ ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায়না। যেমনঃ ২, ৩, ৫, ৭,... এগুলো প্রাইম সংখ্যা। আবার ৮ কিন্তু প্রাইম না, কারন ৮ এর ফ্যাক্টর ১, ২, ৪, ৮। প্রাইম ছাড়া যেসব সংখ্যা আছে, তাদেরকে বলা হয় কম্পোজিট (Composite) সংখ্যা।

প্রাইম এবং কম্পোজিট সংখ্যার জ্যামিতিক ব্যাখ্যা

প্রাচীনকালের গনিতবিদরা, বিশেষ করে গ্রীক গনিতবিদরা সবসময় সংখ্যাকে জ্যামিতিক ব্যাখ্যা আকারে উপস্থাপন করার চেষ্টা করতেন।যেমন বর্গ সংখ্যাগুলোকে একই সংখ্যক সারি এবং কলাম আকারে ছোট ছোট পাথরের মাধ্যমে সাজানো হত। প্রথম পাঁচটি বর্গ সংখ্যা ১, ৪, ৯, ১৬, ২৫।
আয়তাকার সংখ্যারাও অনেক জনপ্রিয়। যেমন ধরা যাক, ১২ কে নিম্নোক্ত উপায়ে আয়তাকারভাবে ছোট ছোট পাথর এর মাধ্যমে দেখানো যায়ঃ

 দেখা যাচ্ছে, ১২ কে ৩ রকমভাবে আয়তাকার আকারে সাজানো যায়।
যেসব সংখ্যাকে ১ এর বেশি আয়তাকার আকারে সাজানো যায় না, তাদেরকে প্রাইম সংখ্যা বলে। যেমন, ৩, ৫, ৭ কে শুধু একটিমাত্র সারি তে সাজানো যায়ঃ

কাজেই, জ্যামিতিকভাবে লক্ষ্য করলে আমরা দেখতে পাই যে প্রাইম সংখ্যার শুধুমাত্র ১ এবং ঐ সংখ্যা ছাড়া আর কোন ফ্যাক্টর নেই।

১ কি প্রাইম ?

ফরমালি আমরা যা শিখলাম, তাতে ১ কে প্রাইম ভাবাই স্বাভাবিক। কারন, ১ কে ১ দিয়ে ভাগ করা যায়, এবং ১ নিজেও নিজেকে দিয়ে ভাগ যায়। অবশ্য যদি আরেকভাবে খেয়াল করি, তাহলে কিন্তু ১ এর ফ্যাক্টর আসলে শুধু ১ ই, তাই এ হিসাবে আবার প্রাইম নাও বলা যায়! আসলে তাহলে ব্যাপারটা কি? আমরা নিচে এর একটা সুন্দর ব্যাখ্যা দিবো, এতে আশা করি আর সমস্যা থাকার কথা না।

সীভ অফ ইরাটোস্থেনেস(sieve of Eratosthenes)

গ্রীক দার্শনিক এবং গনিতবিদ ইরাটস্থেনেস সবার প্রথম একটি সসীম ধারায় প্রাইম সংখ্যাগুলোকে ব্রুট ফোর্স ( Brute force ) আকারে লিখতে সক্ষম হন।
তার নামানুসারে এইভাবে প্রাইম সংখ্যা বের করার অ্যালগরিদমটির নাম হল sieve of Eratosthenes.  এই অ্যালগরিদমটির মাধ্যমে আমরা ১০ কোটির নিচের সকল প্রাইম সংখ্যা খুব অল্প সময়ের মধ্যে বের করে ফেলতে পারি।
sieve শব্দের অর্থ হল ছাকনি যা অপ্রয়োজনীয় অংশ ছেটে ফেলে।

আমরা এই টেবিলটি খেয়াল করি। ধরি আমার ১ থেকে ১০০ এর মধ্যে কিকি প্রাইম সংখ্যা আছে, তা সীভ অ্যালগো ব্যবহার করে বের করতে হবে। এখন সীভ এর ব্যাপারটা হচ্ছে, শুরু থেকে এক এক করে সকল সংখ্যা দেখতে দেখতে সামনে এগিয়ে যেতে হবে। সামনে আগানোর পথে যখনি আমরা কোন সংখ্যা পাবো যাকে আগে পাইনি, সেটা আমরা কেটে ফেলে দিবো। এখন প্রথমে আমি ১ বাদ দিয়ে ২ থেকে যাত্রা শুরু করবো (১ কেন বাদ দিলাম, তা একটু পরে তোমরা নিজেরাই বুঝে যাবে)। এখন ২ যেহেতু আগে পাইনি তাই ২ প্রাইম হিসেবে মার্ক করে রাখবো, এরপরে আমরা প্রাইম এর একদম বেসিক আইডিয়া থেকে যা জানি, একটা সংখ্যা যদি প্রাইম হয়, তাহলে ঐ সংখ্যার চেয়ে বড় ঐ সংখ্যার সকল গুনিতক কে আমরা প্রাইম থেকে বাদ দিয়ে দিতে পারি। কেননা ঐ বড় সংখ্যাগুলো অবশ্যই ঐ সংখ্যা দিয়ে ভাগ যাবে, ফলে এগুলো প্রাইম হিসেবে নেয়া যাবেনা। যেমন ২ এ আসার পরে আমরা ২ এর পরের ২ এর গুনিতকগুলো যেমন ৪, ৬, ৮, ... এভাবে ১০০ পর্যন্ত সব কেটে দিবো। এরপরে আমরা আবার আগের জায়গায় ফিরে আসি। আগে আমরা ২ এ ছিলাম, এখন আমরা যাবো ৩ এ। যেহেতু ৩ কাটা পড়েনি, তাই ৩ কে প্রাইম হিসেবে মার্ক করবো এবং ৩ এর চেয়ে বড় ৩ এর গুনিতকগুলি কেটে দিবো। এরপরে কাজ শেষে আবার আমরা আসবো ৪ এ। এখন এই ৪ কিন্তু ২ এর সময় কাটা পড়ে গিয়েছিল, কাজেই আমরা ৪ কে বাদ দিয়ে সামনে আগাবো, কারন আমরা জানি, ৪ প্রাইম না। এভাবে করে আগালে আমরা সুন্দরভাবে প্রাইম সংখ্যাগুলি পেয়ে যাবো। আশা করি সবাই এতক্ষণে বুঝে ফেলেছো কেন আমরা ১ থেকে যাত্রা শুরু করিনি। ১ থেকে যদি যাত্রা শুরু করতাম, তাহলে সীভ মেথড অনু্যায়ী ১ কে আমরা প্রাইম হিসেবে মার্ক করতাম, এবং এরপরে ১ এর চেয়ে বড় ১ এর সকল গুনিতক কে কেটে ফেলতাম! তাহলে আর সংখ্যাই তো থাকলো না !! এজন্যে ১ কে প্রাইম হিসেবে ধরা হয়না। অবশ্য কোন কোন জায়গায় ১ কে প্রাইম হিসেবে ধরতেও পারে। আমরা যারা কন্টেস্ট প্রব্লেম সল্ভ করি, প্রশ্নে যদি ১ কে প্রাইম ধরে কাজ করতে বলা হয়, তাহলে তাই করতে হবে, নাহলে আসলে ১ কে প্রাইম ধরা অযৌক্তিক।
আমরা যদি দেখতে চাই, N একটি প্রাইম কিনা, তাহলে আমাদের কি আসলেই N-1 পর্যন্ত সংখ্যা বিবেচনায় আনার দরকার আছে? একটু খেয়াল করলে দেখতে পারবো যে, আমরা যদি N/2 পর্যন্ত সংখ্যা চেক করি, তাহলেই কাজ হয়ে যাচ্ছে। এখন N/2 এর চেয়েও আরো ভাল একটি উপায় হল √N ( square root of N )।

কেন স্কয়ার রুট অফ N ? ( Why square root of N? )

ধরি আমরা 24 এর জন্য চেক করবো সংখ্যাটি প্রাইম কিনা। এরজন্য আমাদের √24 = 4.89897948557 ≅ 4
অর্থাৎ আমাদের মাত্র 4-1=3 টি সংখ্যা চেক করলেই আমরা বলতে পারবো 24 প্রাইম কিনা। এই 3 টি সংখ্যা হবে 2,3,4.
আমরা 1 কে বিবেচনায় রাখিনি, তাই 1 বাদ যাবে। কেন এই স্কয়ার রুট কাজ করে তার জন্য আমরা যদি 24 এর ফ্যাক্টর গুলি বের করি, তাহলে বুঝতে পারবো।

খেয়াল করলে দেখবো যে, 24 এর উৎপাদকগুলির মাঝে আমরা যদি 4 পর্যন্ত চেক করি, তাহলেই সব সংখ্যা চেক করা হয়ে যাচ্ছে।মানে 24 একবার 2 দিয়ে ভাগ গিয়েছে, কাজেই আবার 12 দিয়ে ভাগ দেয়ার কোন দরকার নেই। আর 24 এর স্কয়ার রুট হচ্ছে 4। কাজেই স্কয়ার রুট পর্যন্ত হিসাব করা আমাদের জন্য ভালো অপশন।

সুডোকোডঃ

সীভ অ্যালগরিদম এর টাইম কমপ্লেক্সিটি O ( n log n)।