হ্যালো বন্ধুগণ। এটা আমার প্রথম পোস্ট। কিন্তু এই ব্যাপারে গল্প আরেকদিন করা যাবে। আজকে চলে যাই গণিতের একটি মজার ব্যাপারে! এর নাম Permutation বা বিন্যাস!
আমরা সবাই কমবেশি গণিতের “বিন্যাস” (permutation) টপিকটি সম্পর্কে জানি। আজকে সেই বিন্যাসের একটি মজার বৈশিষ্ট্য নিয়ে আলোচনা করব।
বিন্যাসের সেই চেনা পরিচিত nPr এর সংজ্ঞাঃ
n সংখ্যক বস্তু থেকে r সংখ্যক জিনিষ নিয়ে যতভাবে সাজানো যায় সেটাই হল nPr
এখন আমরা চাই n সংখ্যক জিনিষ থেকে একটিও না নিয়ে, ১টি করে নিয়ে, ২টি করে নিয়ে, ৩টি করে নিয়ে… এরকম চলতে চলতে nটি করে নিয়ে যতগুলা বিন্যাস সম্ভব তাদের সমষ্টি। অর্থাৎ,
nP0 + nP1 + nP2 + nP3 + … … + nPn
(এখানে লক্ষণীয় যে, এই সমীকরণটি দেখে প্রথমেই আমাদের হয়ত সমাবেশের nC0 + nC1 + nC2 + nC3 + … … + nCn সমীকরণটির কথা মনে পরবে যার মান 2^n এর সমান। কিন্তু দুর্ভাগ্যবশত, বিন্যাসের ক্ষেত্রে এমন কোন সরাসরি সূত্র নেই। তবে আমরা চাইলে অন্যভাবে একটি Recurrence Relation দাঁড় করাতে পারি যা হলঃ
f(n) = 1 + n * f(n-1)
প্রথম কথা হল যে এই সংখ্যাটি চাইলে বিশাল বড় হতে পারে তাই আমি পুরো সংখ্যাটি চাই না, চাই শুধু Least Significant ৪টা ডিজিট!
যেমন, n = 10 হলে উপরের সমীকরণের ফলাফল আসবে 9864101, কিন্তু আমি চাই শুধু শেষের চার ডিজিট। সুতরাং, উত্তর হল 4101
আচ্ছা , এবার যদি আমরা n = 10010 এর জন্য বের করে ফেলি। ভয় পাবার কিছু নাই, আমি সত্যিকারের রেজাল্ট চাই নাই, শুধু ওই ৪টা মাত্র ডিজিটই চেয়েছি। যদি নিজে বের করতে না পার (অথবা আমার মত আলসে প্রকৃতির হও ), তাহলে নিচের কোডে ইনপুট দিয়ে দেখতে পার। দেখবে রেজাল্ট আসছে, 4101!!
#include<bits/stdc++.h> using namespace std; int f(int n) { if(!n) return 1; return ( 1 + n * f(n-1)) % 10000; } int main() { int n; cout << "Enter the value of n : " ; scanf("%d", &n); cout << "The last 4 digits are : " ; printf("%d\n", f(n)); return 0; }
এইটুক নিয়েই আজকের সব প্যাঁচাল। যদি একটু মজা পেয়ে থাক তাহলে আরো কয়েকবার পরীক্ষা করে দেখতে পার। In general, X এর জন্য যে রেজাল্ট দিবে, (X % 10000) এর জন্যও একই রেজাল্ট দিবে!
In আরেকটু বেশি general, যদি F(n) = nP0 + nP1 + nP2 + nP3 + … … + nPn এই সমীকরণ থেকে যেকোনো n এর জন্যে রেজাল্টের শুধুমাত্র শেষ kটা ডিজিট জানতে চাই, তবে F( n % 10^k ) এর মান বের করলেই হবে। অর্থাৎ,
শেষ kটা ডিজিটের জন্য, F(n) = F(n % 10^k) । যেখানে % হল ভাগশেষ বের করার অপারেটর । 10^k দ্বারা ভাগ করে ভাগশেষ কেন নিলাম? কারণ ৪টা ডিজিটের এই প্যাটার্নগুলা 0 থেকে 9999 ইনপুটের জন্যই পাওয়া যায়, এরপরের ইনপুটের জন্য রিপিট হতে থাকে। অর্থাৎ,
F(0) = F(10000) = F(20000) = … …
F(1) = F(10001) = F(20001) = … …
… …
… …
F(n) = F(10000 + n) = F(20000 + n) = … …
কিভাবে বুঝলাম? উপরের কোডটাতে ইনপুট দিয়ে টেস্ট করে দেখতে পার ( উক্ত কোডে k এর value 4 ধরা হয়েছে, অর্থাৎ আমরা কেবল শেষের চার ডিজিট নিয়ে চিন্তা করব)।
এখন সমস্যা হল আমার মত ব্যোমকেশ/Sherlock দের fan দের নিয়ে যারা কথায় কথায় প্রমাণ খুঁজি। ভয় নেই, আজকে সব ব্যবস্থা করেই লিখতে বসছি। প্রমাণও হবে।
প্রথমত, পুরো সমীকরণটি আবার লিখে নেই।
f(n) = nP0 + nP1 + nP2 + nP3 + … … + nPn
এক্টূ আগে পিছে করে (বিন্যাসের সূত্র অনুযায়ী) এভাবেও লেখা যায়,
f(n) = 1 + n + n*(n-1) + n*(n-1)*(n-2) + … … + n!
আরেকটু ঘুরিয়ে পেচিয়ে কমন নিয়ে টিয়ে,
f(n) = 1 + n * [ 1 + (n-1) * { 1 + (n-2) * … … … } ]
এই সমীকরণটিকে আমরা রিকারেন্স সমীকরণ আকারে লিখতে পারি,
f(n) = 1 + n * f(n-1) যখন n > 0
n=0 হলে f(n) এর মান 1 (কেন তা নিজেই চিন্তা কর)
যেহেতু আমরা চাই শেষ k সংখ্যক ডিজিট, তাই আমরা এইভাবে একটা সমীকরণ ডিফাইন করি।
F(n) = ( nP0 + nP1 + nP2 + nP3 + … … + nPn ) % 10^k
= (1 + n * F(n-1)) % 10^k //উপরের মত করে
= (1 + (n % 10^k) * (F(n-1) % 10^k)) % 10^k
// (a+b) % x = ( a%x + b%x ) % x
// (a*b) % x = ( a%x * b%x) % x
উক্ত সমীকরণটি বিস্তার করতে থাকলে ,
F(n) = (1 + (n % 10^k) * ( ( (1 + ( (n-1) % 10^k) * ( ( (1 + ( (n-2) % 10^k) * ( F(n-3) %
10^k)) % 10^k ) % 10^k)) % 10^k ) % 10^k)) % 10^k
এরকম আসতে থাকবে। এত্ত বিদ্ঘুটে সমীকরণের জন্য দুঃখিত। আর বেশি দূর নাই প্রমাণের। যাক, একটা বিষয় খেয়াল করি।
যদি n এর ভ্যালু 10^k এর চেয়ে বড় হয়, তাহলে তা থেকে শুধুমাত্র ভাগশেষ টুকু থাকবে। আরো খেয়াল করি যে, রিকারেন্স রিলেশনটিতে n এর ভ্যালু 1 করে কমছে। তার মানে তার ভাগশেষও এক করে কমতে থাকবে। এখন এই ভাগশেষ কমতে কমতে এক সময় ০ তে চলে আসবে। তখন আর F(n-1) এ ঢুকারই দরকার নাই, কারণ সেখান থেকে যাই ভ্যালু আসুক না কেন তা ০ এর সাথে গুণ হবে।
সুতরাং, আমরা F(n) দিয়ে আসলে যা বের করছি তা আসলে, F( n % 10^k ) এর সমান।
এতক্ষণে হয়ত মাথায় তালা লেগে গেছে। একটি উদাহরণ দিয়ে ক্লিয়ার করি।
ধরি আমি F(10002) এর শেষ ৪ ডিজিট বের করতে চাই। তাহলে,
F(10002) = (1 + (10002 % 10^4) * ( ( (1 + ( 10001 % 10^4) * ( ( (1 + ( 10000 % 10^4) * ( F(9999) % 10^4)) % 10^4 ) % 10^4)) % 10^4 ) % 10^4)) % 10^4
=> F(10002) = (1 + 2 * ( ( (1 + ( 1 * ( ( (1 + 0 * ( F(9999))) % 10^4 ) % 10^4)) % 10^4 ) % 10^4)) % 10^4
সমীকরণে দেখতে পাচ্ছি যে F(9999) এর সাথে ০ গুন হবে। সুতরাং, এর মান বের করার দরকারই নেই। তাহলে আমাদের Final সমীকরণ দাঁড়ায়,
F(10002) = (1 + 2 * ( 1 + 1 * ( 1 + 0 ) যা F(2) এর সমান। উপরের যেকোন সমীকরণে n = 2 বসালেই তা আমরা দেখতে পাব।
তো এই ছিল প্রমাণ।
আচ্ছা ভাইয়া, মানলাম এইটা একটা সুন্দর জিনিষ কিন্তু কি লাভ কাজে লাগাব কই?
উত্তরঃ
এই জিনিষটা মাথায় আসছে Light Online Judge এর একটি প্রব্লেম সল্ভ করতে গিয়ে। তোমরাও সেটা ট্রাই করে দেখতে পার। প্রব্লেমের লিঙ্ক নিচে দেয়া হলঃ
http://www.lightoj.com/volume_showproblem.php?problem=1322
এইটা counting ক্যাটাগরির একটা প্রব্লেম যা সল্ভ করতে পারমিউটেশনের এই সৌন্দর্যটি ব্যবহার করতে হয়।
সবাইকে অসংখ্য ধন্যবাদ।
-শাহরিয়ার হোসেন সজীব।
f(n) = 1 + n * f(n-1) এটার খুব সিমিলার একটা রিকারেন্স রিলেশন আছে ডিএরেঞ্জমেন্ট এ।যেটা হল,
D(n) = (1)^-1 + D(n-1)
ডিএরেঞ্জমেন্টের রিকারেন্স সলভ করলে approximately D(n) ~ n!/e আসে।
সেই ক্ষেত্রে f(n) ~ n! * e আসার কথা।
আরো কম কমপ্লেক্সিটিতে সলভ করতে পারার কথা যদি এটা সত্যি হয়।
আমি রিকারেন্স রিলেশন সলভ করতে পারি না।ইনটুইশন আর এক্সপেরিমেন্টাল রেজাল্ট থেকে গেস করে বলা রেজাল্টটা।
যদি হেল্প করতেন এব্যপারে বিস্তারিত বলে।
আমরা Approximation ক্যালকুলেট করতে চাচ্ছি না। শেষ কয়টা ডিজিট Exactly বলতে হলে,পুরো সংখ্যাটা Exactly generate করার উপায় দরকার। আশা করি বুঝতে পেরেছো।
D(n) = (-1)^n + D(n-1) হবে।টাইপিং মিসটেকের জন্য দুঃখিত।
সরি D(n) = (-1)^n + n*D(n-1) হবে। :3