Combinatorics Workshop: Day 2 (05.12.13)
Posted: Thu Dec 05, 2013 12:11 am
আজকের পড়া: B-Combinations-এর 'Combinations Allowing Repetition'-এর আগ পর্যন্ত। (মানে B17* পর্যন্ত)
কম্বিনেশন ক্লাসেই বোঝানো হয়েছে বহুবার। B5 পর্যন্ত আশা করি সবারই ক্লিয়ার। (যদি কেউ থেকে থাকে ) পিএমএসের বাইরে যদি কারও সাহায্যের প্রয়োজন হয়, জানিও। প্যাসকেলের ত্রিভুজও সহজ। জাফর ইকবাল স্যারের গণিতের মজা মজার গণিতও দেখতে পারো।
রেখার কোন শুরু নাই আর প্যাসকেলের ত্রিভুজের বৈশিষ্ট্যের কোন শেষ নাই। এই ওয়ার্কশপের সাথে সম্পর্ক নাই তবু কেউ এটার উপরে ব্যক্তিগতভাবে আগ্রহী হলে "Proofs that really count: The art of combinatorial proof" দেখতে পারো।
রেকারেন্স রিলেশন (recurrence relation): কোন ধারার পদগুলোর মাঝে এমন একধরনের সম্পর্ক যেটা দিয়ে ধারার আগের কিছু পদ থেকে পরের কোন পদ বের করা যায়। যেমন: ফিবনাক্কি ধারার রেকারেন্স রিলাশন: $f_{n+2}=f_{n+1}+f_n$. এই রেকারেন্স রিলেশন দিয়ে $f_{150}$ ও $f_{151}$ জানা থাকলে $f_{152}$ বের করা যাবে। প্যাসকেলের ত্রিভুজ যে রেকারেন্স রিলেশন মেনে চলে সেটা হচ্ছে:
\[ \binom n k + \binom n {k+1} = \binom {n+1}{k+1}\]
B8 এবং B9-এ এটা প্রুফ করতে বলা হয়েছে। বিশেষত B9 বিশেষভাবে লক্ষ্য করার মতো। এখানে খুব গুরুত্বপূর্ণ একটা জিনিসের ব্যবহার করা হয়েছে- একই সংখ্যক জিনিস পৃথক দুইভাবে গোনা আর এভাবে কোন আইডেন্টিটি প্রমাণ করা।
B7-ও গুরুত্বপূর্ণ। আর আমি A6*-এর সাথে আরেকটা প্রবলেম করতে দিয়েছিলাম না? সেটাই হচ্ছে B10*. এটা অবশ্যই করতে হবে। বাইনোমিয়াল এক্সপ্যানশন বোঝা অনেকটাই নির্ভর করছে এর উপর।
বাইনমিয়াল এক্সপ্যানশন: আমরা এটা স্টেপ বাই স্টেপ বোঝার চেষ্টা করবো।
প্রথমে আমরা $(A+B)(A+B)$ সমান কত সেটা বের করি। (ক্লাস সেভেনে শেখা সূত্র ভুলে যাও)
প্রথম (A+B)-র A-র সাথে দ্বিতীয় (A+B)-র B যদি গুণ করি তবে আমরা পাব AB. এটা অবশ্যই গুণফলের একটা পদ হবে। আবার প্রথম (A+B)-র B-র সাথে দ্বিতীয় (A+B)-র B গুণ করলে পাওয়া যাবে BB. এটাও গুণফলে থাকবে। প্রকৃতপক্ষে A এবং B ব্যবহার করে ২ লেংথের যে $২^২=৪$ টি স্ট্রিং তৈরি করা যায় তার প্রতিটিই গুণফলে থাকবে। সুতরাং
\[(A+B)(A+B)=AA+AB+BA+BB\]
এখন $(A+B)^3$-কে বিস্তৃত বের করো। (মানে গুণফল বের করো)
এবারও আগের মতো A এবং B ব্যবহার করে ৩ লেংথের যে $২^৩=৮$ টি স্ট্রিং তৈরি করা যায় সেগুলো নিয়েই গুণফল তৈরি হবে।
\[(A+B)^3=AAA+ABA+BAA+BBA+AAB+ABB+BAB+BBB\]
সাধারণভাবে, A,B দিয়ে n লেংথের যে $2^n$-টি স্ট্রিং পাওয়া যায় তাদের যোগফলই হচ্ছে $(A+B)^n$.
তাহলে $(A+B)^n$-এর বিস্তৃতিতে পদগুলো কি কি হবে?
কিছু পদ হতে পারে যাতে n-টি প্লেসেই A। আরেকরকম পদ থাকবে যাতে B থাকবে ১টা আর n-1টা থাকবে A. আবার কিছু পদ থাকবে যাতে B থাকবে ২টা, আর A থাকবে n-2টা... এভাবে চলবে। অর্থাৎ
\[(A+B)^n=k_1A^n+k_2A^{n-1}B+k_3A^{n-2}B^2+...k_nAB^{n-1}+k_{n+1}B^n\]
$k_1,k_2,...$ হচ্ছে প্রতিটা পদের সহগ যার মান নির্ণয় করতে হবে।
ধর যদি বলা হয় $(A+B)^3$-এর বিস্তৃতে $AB^2$ এর সহগ কত হবে?
১টা A আর ২টা B দিয়ে স্ট্রিং বানানো যায় মোট $\binom 3 1$-ভাবে। (B10* দেখ) সুতরাং সহগের মান হবে $\binom 3 1=3$. এখন $(A+B)^n$-এর বিস্তৃতিতে $A^kB^{n-k}$-র সহগ কত হবে? kটি A আর n-kটি B দিয়ে স্ট্রিং তৈরি করা যায় $\binom{n}{n-k}$-টি। তাহলে $A^kB^{n-k}$-র সহগও হবে এটাই।
সুতরাং,
\[(A+B)^n=\binom n 0A^n+\binom n 1A^{n-1}B+\binom n 2A^{n-2}B^2+...+\binom n nB^n\]
#Expand $(A+B)^4$ and $(A+B)^5$. বিস্তৃত করে আমার সাথে মিলাও।
B6-B17*, B30-B42 পর্যন্ত করো।
কম্বিনেশন ক্লাসেই বোঝানো হয়েছে বহুবার। B5 পর্যন্ত আশা করি সবারই ক্লিয়ার। (যদি কেউ থেকে থাকে ) পিএমএসের বাইরে যদি কারও সাহায্যের প্রয়োজন হয়, জানিও। প্যাসকেলের ত্রিভুজও সহজ। জাফর ইকবাল স্যারের গণিতের মজা মজার গণিতও দেখতে পারো।
রেখার কোন শুরু নাই আর প্যাসকেলের ত্রিভুজের বৈশিষ্ট্যের কোন শেষ নাই। এই ওয়ার্কশপের সাথে সম্পর্ক নাই তবু কেউ এটার উপরে ব্যক্তিগতভাবে আগ্রহী হলে "Proofs that really count: The art of combinatorial proof" দেখতে পারো।
রেকারেন্স রিলেশন (recurrence relation): কোন ধারার পদগুলোর মাঝে এমন একধরনের সম্পর্ক যেটা দিয়ে ধারার আগের কিছু পদ থেকে পরের কোন পদ বের করা যায়। যেমন: ফিবনাক্কি ধারার রেকারেন্স রিলাশন: $f_{n+2}=f_{n+1}+f_n$. এই রেকারেন্স রিলেশন দিয়ে $f_{150}$ ও $f_{151}$ জানা থাকলে $f_{152}$ বের করা যাবে। প্যাসকেলের ত্রিভুজ যে রেকারেন্স রিলেশন মেনে চলে সেটা হচ্ছে:
\[ \binom n k + \binom n {k+1} = \binom {n+1}{k+1}\]
B8 এবং B9-এ এটা প্রুফ করতে বলা হয়েছে। বিশেষত B9 বিশেষভাবে লক্ষ্য করার মতো। এখানে খুব গুরুত্বপূর্ণ একটা জিনিসের ব্যবহার করা হয়েছে- একই সংখ্যক জিনিস পৃথক দুইভাবে গোনা আর এভাবে কোন আইডেন্টিটি প্রমাণ করা।
B7-ও গুরুত্বপূর্ণ। আর আমি A6*-এর সাথে আরেকটা প্রবলেম করতে দিয়েছিলাম না? সেটাই হচ্ছে B10*. এটা অবশ্যই করতে হবে। বাইনোমিয়াল এক্সপ্যানশন বোঝা অনেকটাই নির্ভর করছে এর উপর।
বাইনমিয়াল এক্সপ্যানশন: আমরা এটা স্টেপ বাই স্টেপ বোঝার চেষ্টা করবো।
প্রথমে আমরা $(A+B)(A+B)$ সমান কত সেটা বের করি। (ক্লাস সেভেনে শেখা সূত্র ভুলে যাও)
প্রথম (A+B)-র A-র সাথে দ্বিতীয় (A+B)-র B যদি গুণ করি তবে আমরা পাব AB. এটা অবশ্যই গুণফলের একটা পদ হবে। আবার প্রথম (A+B)-র B-র সাথে দ্বিতীয় (A+B)-র B গুণ করলে পাওয়া যাবে BB. এটাও গুণফলে থাকবে। প্রকৃতপক্ষে A এবং B ব্যবহার করে ২ লেংথের যে $২^২=৪$ টি স্ট্রিং তৈরি করা যায় তার প্রতিটিই গুণফলে থাকবে। সুতরাং
\[(A+B)(A+B)=AA+AB+BA+BB\]
এখন $(A+B)^3$-কে বিস্তৃত বের করো। (মানে গুণফল বের করো)
এবারও আগের মতো A এবং B ব্যবহার করে ৩ লেংথের যে $২^৩=৮$ টি স্ট্রিং তৈরি করা যায় সেগুলো নিয়েই গুণফল তৈরি হবে।
\[(A+B)^3=AAA+ABA+BAA+BBA+AAB+ABB+BAB+BBB\]
সাধারণভাবে, A,B দিয়ে n লেংথের যে $2^n$-টি স্ট্রিং পাওয়া যায় তাদের যোগফলই হচ্ছে $(A+B)^n$.
তাহলে $(A+B)^n$-এর বিস্তৃতিতে পদগুলো কি কি হবে?
কিছু পদ হতে পারে যাতে n-টি প্লেসেই A। আরেকরকম পদ থাকবে যাতে B থাকবে ১টা আর n-1টা থাকবে A. আবার কিছু পদ থাকবে যাতে B থাকবে ২টা, আর A থাকবে n-2টা... এভাবে চলবে। অর্থাৎ
\[(A+B)^n=k_1A^n+k_2A^{n-1}B+k_3A^{n-2}B^2+...k_nAB^{n-1}+k_{n+1}B^n\]
$k_1,k_2,...$ হচ্ছে প্রতিটা পদের সহগ যার মান নির্ণয় করতে হবে।
ধর যদি বলা হয় $(A+B)^3$-এর বিস্তৃতে $AB^2$ এর সহগ কত হবে?
১টা A আর ২টা B দিয়ে স্ট্রিং বানানো যায় মোট $\binom 3 1$-ভাবে। (B10* দেখ) সুতরাং সহগের মান হবে $\binom 3 1=3$. এখন $(A+B)^n$-এর বিস্তৃতিতে $A^kB^{n-k}$-র সহগ কত হবে? kটি A আর n-kটি B দিয়ে স্ট্রিং তৈরি করা যায় $\binom{n}{n-k}$-টি। তাহলে $A^kB^{n-k}$-র সহগও হবে এটাই।
সুতরাং,
\[(A+B)^n=\binom n 0A^n+\binom n 1A^{n-1}B+\binom n 2A^{n-2}B^2+...+\binom n nB^n\]
#Expand $(A+B)^4$ and $(A+B)^5$. বিস্তৃত করে আমার সাথে মিলাও।