Combinatorics Workshop: Day 1 (04.12.13)

Latest News, Announcements, and Forum Rules
User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Combinatorics Workshop: Day 1 (04.12.13)

Unread post by Phlembac Adib Hasan » Tue Dec 03, 2013 7:05 pm

বছর দুয়েক আগে এই ওয়ার্কশপটা চালিয়েছিলাম। এখানে মূলত বেসিক কাউন্টিং শেখানো হবে। তবে যেকোন ম্যাথের শাখার মতই, আমি তোমাকে ম্যাথ গিলিয়ে দিতে পারব না। নিজে থেকে তোমাকে খাটতে হবে।
Book: Combinatorics: A Problem Oriented Approach
Download link (বইয়ের প্রচ্ছদে ক্লিক করলেই ডাউনলোড শুরু হবে)

সূচীপত্র:
Day 1
Day 2
Day 3
Day 4
Day 5
Day 6
Exam 1
Day 7
Day 8
Day 9
Day 10
Day 11
Day 12
Day 13



আজকের পড়া: A-Strings.
এই চ্যাপ্টারের বেশিরভাগ জিনিস ক্লাসেই বহুবার আলোচনা করা হয়েছে। তাই গাণিতিক অংশ বুঝতে সমস্যা হওয়ার কথা না। তবে ইংরেজি বুঝতে যাদের সমস্যা তাদের জন্য কিছু জিনিস সংক্ষেপে আবার বলছি:

স্ট্রিং: পাশাপাশি কয়েকটা উপাদানের একটা সারি। word বা শব্দ যেরকম। যেমন: "অআকখ", "bat", "aabc123" ইত্যাদি। সেটের সাথে স্ট্রিংয়ের পার্থক্য হচ্ছে সেটের উপাদানগুলোর অবস্থানের কোন ভ্যালু নাই, কিন্তু স্ট্রিং-এ আছে। যেমন- {a,b,c}, {b,a,c}, {a,b,a,c} ইত্যাদি দ্বারা একই সেটকে বুঝায়। কিন্তু "abc", "bac", "abac" প্রত্যেকে আলাদা আলাদা স্ট্রিং। এই উদাহরণে আরেকটা বিষয় খেয়াল করো। স্ট্রিঙে একই উপাদান বার বার ব্যবহৃত হতে পারে। (শব্দে এক বর্ণ যেমন বার বার ব্যবহার করা যায়)

স্ট্যান্ডার্ড প্রবলেম ১,২, A1-A5 করতে কোন সমস্যা হওয়া উচিত না। পারমুটেশনও সবার জানা।

A6* প্রবলেমটা খেয়াল করো। এটা করো এবং সাথে আরেকটা প্রবলেম করো।
# "AAABB"-এই স্ট্রিংটিকে কতভাবে সাজানো যায়? এবার জেনারেলাইজ কর: n-টি A আর m-টি B দিয়ে তৈরি স্ট্রিংকে কতভাবে সাজানো যায়?

প্রোডাক্ট রুল দুটি উদাহরণ দিয়ে বুঝাচ্ছি।

# দুই অঙ্কের এমন কয়টি সংখ্যা আছে যাদের ডান অঙ্কটি পাঁচ থেকে বড়?
# তিন অঙ্কের এমন কয়টি সংখ্যা আছে যাদের প্রতিটি অঙ্ক ভিন্ন এবং অঙ্কগুলো বাঁ থেকে ডানে মানের উর্ধক্রমে সাজানো? (এরকম একটা সংখ্যা ১২৩)

প্রথম উদাহরণে সরাসরি প্রোডাক্ট রুল খাটবে, দ্বিতীয়টাতে না। প্রথমটাতে কেন খাটবে আর দ্বিতীয়টাতে কেন খাটবে না চিন্তা করে বের করো। যদি সফল হও, তবে প্রোডাক্ট রুল তুমি বুঝে গেছো। আর না পারলে নিচের হিডেন টেক্সট দেখো।
প্রথম উদাহরণে দ্বিতীয় ডিজিটে কি বসানো যাবে সেটা প্রথম ডিজিটের উপর নির্ভর করে না। 1st digit বেছে নেওয়ার জন্য অপশন আছে ৯ টা: ১ থেকে ৯ পর্যন্ত ৯টি ডিজিট। দ্বিতীয় ডিজিটে বসানো যায় এমন অঙ্ক আছে ৪টা: ৬,৭,৮,৯। প্রথম স্থানে ১ বসালে দ্বিতীয় স্থানে ৬-৯ পর্যন্ত যেকোনো অঙ্ক বসানো যায়। এভাবে আমরা চারটা সংখ্যা পাই। যথা: ১৬,১৭,১৮,১৯. আবার প্রথম স্থানে ২ বসালে আমরা পাই আরও চারটা সংখ্যা- ২৬, ২৭, ২৮, ২৯. এরকম ৩,৪...৯ পর্যন্ত প্রতিটা অঙ্কের জন্য ৪টা করে সংখ্যা পাওয়া যাবে। তাই ৯টি অঙ্কের জন্য মোট $৯\times ৪$ টি সংখ্যা পাওয়া যাবে। লক্ষ্য করো যে এখানে যে দ্বিতীয় ডিজিটে সবসময়ই ৬-৯ অর্থাৎ ৪টি অঙ্ক বসানো যাচ্ছে।

আর দ্বিতীয় উদাহরণ দেখো: এখানে প্রথম ডিজিট বেছে নেওয়ার অপশন ৯ টা। কিন্তু দ্বিতীয় ডিজিট বেছে নেওয়ার অপশন নির্দিষ্ট না। প্রথম ডিজিটে ১ বসালে দ্বিতীয় ডিজিটে ২-৯ পর্যন্ত বসানো যাবে। প্রথম ডিজিটে ৪ বসালে দ্বিতীয় ডিজিটে তুমি ৫-৯ বসাতে পারবে। আগের উদাহরণের সাথে পার্থক্যটা বুঝতে পারছ? এখানে দ্বিতীয় বা তৃতীয় ডিজিটে অঙ্ক বসানোর অপশন সংখ্যা ইন্ডিপেন্ডেন্ট বা স্বাধীন না এবং স্থির কোন সংখ্যাও না। বরঞ্চ আগের ডিজিটের উপর নির্ভর করে অপশন সংখ্যা চেঞ্জ হচ্ছে। i-তম স্থানে প্রোডাক্ট রুল তখনই খাটে যখন i-তম স্থানে অবজেক্ট বা অঙ্ক বসানোর অপশন সংখ্যা আগের স্থানগুলোতে বসানো অবজেক্ট না অঙ্কগুলোর ওপর নির্ভর করে চেঞ্জ হয় না । যেমন- প্রথম উদাহরণে ১ম আর ২য় দুই স্থানেই অপশনের সংখ্যা ফিক্সড। তাই এই দুই অপশনের সংখ্যা গুণ করলেই মোট পারমুটেশনের সংখ্যা বের হবে। এটাই প্রোডাক্ট রুল।
A7 থেকে A14 পর্যন্ত প্রব্লেমগুলো আশা করি পারবে। আর আটকে গেলে বইলো। আমরা তো আছিই, হিন্ট দিবনে। (A14-এ ৩ ডিজিটের জায়গায় ১০০ ডিজিট দিয়ে গতবারের সেকেন্ডারির ডিভিশনালে আসছিলো।)

প্রোবাবিলিটি সম্পর্কে আশা করি কিছু বলতে হবে না। বইয়ের লেখা যথেষ্ট পরিষ্কার। তবে যদি দরকার হয় পরে ব্যাখ্যা করব নে। রিঅ্যারেঞ্জমেন্ট, ডিরেঞ্জমেন্ট সম্পর্কেও একই কথা। A22*, A23* ইন্টারেস্টিং। বাকি প্রব্লেমগুলার মাঝে যেগুলা পারা যায় করে ফেলো। বিশেষত: A26, A27, A30-A33, A35, A37-A39, A41, A44-A47.

যদি কিছু বুঝতে সমস্যা হয় তবে এখানে জিজ্ঞেস কর। আর সংকোচ বোধ হলে আমাকে বা সিনিয়র ভাইয়াদের মেসেজ পাঠাও। আর এক্সারসাইজগুলো করে এখানে সমাধান পোস্ট দাও বা ইন্টারেস্টিং হলে নতুন টপিক খুলে সেখানে ডিসকাশন করো।
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by asif e elahi » Wed Dec 04, 2013 4:29 pm

I didn't understand dominated sequences.What is dominated sequence??

User avatar
nishat protyasha
Posts: 33
Joined: Tue Sep 17, 2013 12:02 am
Location: Sylhet, Bangladesh.

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by nishat protyasha » Wed Dec 04, 2013 6:38 pm

আচ্ছা ভাইয়া, প্রোডাক্ট রুলের দ্বিতীয় উদাহরনের ক্ষেত্রে প্রথম ডিজিট বেছে নেওয়ার অপশন ১০ টি কেন হবে ? '0' নিলে তো তা দুই ডিজিটের হয়ে যায়।

Prosenjit Basak
Posts: 53
Joined: Wed Nov 28, 2012 12:48 pm

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by Prosenjit Basak » Wed Dec 04, 2013 8:40 pm

nishat protyasha wrote:আচ্ছা ভাইয়া, প্রোডাক্ট রুলের দ্বিতীয় উদাহরনের ক্ষেত্রে প্রথম ডিজিট বেছে নেওয়ার অপশন ১০ টি কেন হবে ? '0' নিলে তো তা দুই ডিজিটের হয়ে যায়।
হ্যা, ভাইয়া এই প্রশ্ন টা আমারও । বলা হয়েছে তিন ডিজিটের সংখ্যা তো আমি যদি প্রথম স্থানে $0$ বসাই তো এইটা দুই ডিজিটের একটা সংখ্যা হয়ে যাবে। যেমনঃ একটা $012$ এইটাকে কি আমি তিন ডিজিটের সংখ্যা বলব নাকি দুই ডিজিটের? :?:
Yesterday is past, tomorrow is a mystery but today is a gift.

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by Phlembac Adib Hasan » Wed Dec 04, 2013 8:54 pm

asif e elahi wrote:I didn't understand dominated sequences.What is dominated sequence??
I guess you meant consistently dominated sequence. ধর একটা স্ট্রিং-এ A উপাদানটা সবচেয়ে বেশিবার আছে। (যেমন: "ABBAA") এখন স্ট্রিংটা যদি এমন হয় যে সকল i-এর জন্য প্রথম i-টা প্লেসের মাঝে অন্তত i/2-টা প্লেসেই আছে A, তখন তাকে বলা হবে consistently dominated sequence. যেমন: "AABAACB"
প্রথম ১ টা প্লেসে আছে অন্তত ১টা A
প্রথম ২ টা প্লেসে আছে অন্তত ১টা A
প্রথম ৩ টা প্লেসে আছে অন্তত ২টা A
প্রথম ৪ টা প্লেসে আছে অন্তত ২টা A
এইভাবে যাবে।
nishat protyasha wrote:আচ্ছা ভাইয়া, প্রোডাক্ট রুলের দ্বিতীয় উদাহরনের ক্ষেত্রে প্রথম ডিজিট বেছে নেওয়ার অপশন ১০ টি কেন হবে ? '0' নিলে তো তা দুই ডিজিটের হয়ে যায়।
Oh, didn't notice. প্রথম ডিজিটে ০ নেওয়া ভুল। পোস্ট লেখার সময় ১০০০-এর ছোট সব স্বাভাবিক সংখ্যা নিয়ে ডাকটা সাজিয়েছিলাম। পরে এডিট করে যখন তিন অঙ্ক লেখি তখন সলু.-তে চেঞ্জ করা হয়নি। যাই হোক, ভুল ধরিয়ে দেওয়ার জন্য ধন্যবাদ।
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by Phlembac Adib Hasan » Wed Dec 04, 2013 8:57 pm

@পিএমএসের পোলাপান, তোমরা কি এক্সারসাইজগুলা করস? করে সলু পোস্ট দিতে বলছিলাম। একটাও পাইলাম না। :/
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Ridwan Abrar
Posts: 13
Joined: Mon Aug 05, 2013 8:01 pm

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by Ridwan Abrar » Thu Oct 23, 2014 12:22 pm

:?: I couldn't understand the example of product rule. Can anyone explain me in detail?

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Combinatorics Workshop: Day 1 (04.12.13)

Unread post by *Mahi* » Thu Oct 23, 2014 6:11 pm

Which one, and which part was the problem? They are discussed quite comprehensively here. I don't think we can do any better if you do not point to a specific part of the examples.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Post Reply