Combinatorial design

Combinatorial design theory (কম্বিনেটোরিয়াল ডিজাইন থিওরি) হলো কম্বিনেটোরিয়াল গণিতের একটি শাখা যা সসীম সেটের সিস্টেমের অস্তিত্ব, গঠন এবং বৈশিষ্ট্য নিয়ে কাজ করে, যার বিন্যাসগুলো 'ভারসাম্য' (balance) এবং/অথবা 'প্রতিসাম্য' (symmetry)-এর সাধারণ ধারণাগুলোকে সন্তুষ্ট করে। এই ধারণাগুলোকে সুনির্দিষ্ট করা হয়নি, যাতে বিভিন্ন ধরনের বস্তুকে একই ছাতার নিচে বিবেচনা করা যায়। কখনও কখনও এতে ব্লক ডিজাইন-এর মতো সেটের ছেদবিন্দুর সংখ্যাগত আকার অন্তর্ভুক্ত থাকতে পারে, আবার কখনও এটি সুডোকু গ্রিড-এর মতো অ্যারেতে ভুক্তিগুলোর স্থানিক বিন্যাসকেও বোঝাতে পারে।

কম্বিনেটোরিয়াল ডিজাইন থিওরি ডিজাইন অফ এক্সপেরিমেন্টস-এর ক্ষেত্রে প্রয়োগ করা যেতে পারে। কম্বিনেটোরিয়াল ডিজাইনের কিছু মৌলিক তত্ত্ব পরিসংখ্যানবিদ রোনাল্ড ফিশার-এর জৈবিক পরীক্ষার নকশা সংক্রান্ত কাজের মাধ্যমে উদ্ভূত হয়েছিল। আধুনিক প্রয়োগগুলো সসীম জ্যামিতি, টুর্নামেন্ট শিডিউলিং, লটারি, গাণিতিক রসায়ন, গাণিতিক জীববিজ্ঞান, অ্যালগরিদম ডিজাইন এবং বিশ্লেষণ, নেটওয়ার্কিং, গ্রুপ টেস্টিং এবং ক্রিপ্টোগ্রাফি সহ বিভিন্ন ক্ষেত্রে পাওয়া যায়।

উদাহরণ

ফ্যানো প্লেন

ধরা যাক, n সংখ্যক মানুষ আছে, তাদের কি এমন সেটে ভাগ করা সম্ভব যাতে প্রতিটি মানুষ অন্তত একটি সেটে থাকে, প্রতি জোড়া মানুষ ঠিক একটি সেটে একসাথে থাকে, প্রতি দুটি সেটে ঠিক একজন মানুষ সাধারণ থাকে এবং কোনো সেটেই সবাই, একজনকে ছাড়া সবাই, বা ঠিক একজন মানুষ না থাকে? উত্তরটি n-এর ওপর নির্ভর করে।

এর সমাধান কেবল তখনই সম্ভব যদি n-এর আকার q² + q + 1 হয়। যদি q একটি প্রাইম পাওয়ার হয়, তবে সমাধান বিদ্যমান তা প্রমাণ করা কিছুটা জটিল। এটি অনুমান করা হয় যে এগুলোই একমাত্র সমাধান। আরও দেখানো হয়েছে যে, যদি q-এর মান ১ বা ২ মড ৪ হয়, তবে q দুটি বর্গ সংখ্যা-এর যোগফল। এই শেষ ফলাফলটি, ব্রুক-রাইজার উপপাদ্য, সসীম ফিল্ড-এর ওপর ভিত্তি করে গঠনমূলক পদ্ধতি এবং কোয়াড্রাটিক ফর্ম-এর প্রয়োগের সমন্বয়ে প্রমাণিত হয়।

যখন এমন একটি কাঠামো বিদ্যমান থাকে, তখন একে সসীম প্রজেক্টিভ প্লেন বলা হয়; যা দেখায় যে কীভাবে সসীম জ্যামিতি এবং কম্বিনেটোরিক্স একে অপরের সাথে ছেদ করে। যখন q = 2 হয়, তখন প্রজেক্টিভ প্লেনটিকে ফ্যানো প্লেন বলা হয়।

ইতিহাস

কম্বিনেটোরিয়াল ডিজাইনের ইতিহাস প্রাচীনকাল থেকে চলে আসছে, যার মধ্যে লো শু স্কয়ার একটি প্রাথমিক ম্যাজিক স্কয়ার। কম্বিনেটোরিয়াল ডিজাইনের অন্যতম প্রাচীন তারিখযুক্ত প্রয়োগ পাওয়া যায় ভারতে বরাহমিহিরের লেখা বৃহৎ সংহিতা বইটিতে, যা প্রায় ৫৮৭ খ্রিস্টাব্দে লেখা হয়েছিল। এটি ১৬টি ভিন্ন পদার্থ থেকে ৪টি পদার্থ নির্বাচন করে ম্যাজিক স্কয়ার ব্যবহার করে সুগন্ধি তৈরির উদ্দেশ্যে ব্যবহৃত হতো।

১৮শ শতাব্দীতে ল্যাটিন স্কয়ার এবং ১৯শ শতাব্দীতে স্টেইনার সিস্টেম-এর মতো উদাহরণসহ কম্বিনেটোরিক্স-এর সাধারণ বিকাশের সাথে সাথে কম্বিনেটোরিয়াল ডিজাইনও বিকশিত হয়েছে। ডিজাইনগুলো বিনোদনমূলক গণিত-এও জনপ্রিয় ছিল, যেমন কার্কম্যানের স্কুলগার্ল সমস্যা (১৮৫০), এবং ব্যবহারিক সমস্যাগুলোতে, যেমন রাউন্ড-রবিন টুর্নামেন্ট-এর সময়সূচী নির্ধারণ (সমাধান ১৮৮০-এর দশকে প্রকাশিত)। বিংশ শতাব্দীতে ডিজাইনগুলো পরীক্ষার নকশা-তে প্রয়োগ করা হয়েছিল, বিশেষ করে ল্যাটিন স্কয়ার, সসীম জ্যামিতি এবং অ্যাসোসিয়েশন স্কিম, যা বীজগণিতীয় পরিসংখ্যান-এর ক্ষেত্র তৈরি করেছে।

মৌলিক কম্বিনেটোরিয়াল ডিজাইন

কম্বিনেটোরিয়াল ডিজাইনের শাস্ত্রীয় মূল ভিত্তি হলো ব্যালেন্সড ইনকমপ্লিট ব্লক ডিজাইন (BIBDs), হ্যাডামার্ড ম্যাট্রিক্স এবং হ্যাডামার্ড ডিজাইন, প্রতিসম BIBDs, ল্যাটিন স্কয়ার, রিসলভ্যাবল BIBDs, ডিফারেন্স সেট এবং পেয়ারওয়াইজ ব্যালেন্সড ডিজাইন (PBDs)। অন্যান্য কম্বিনেটোরিয়াল ডিজাইনগুলো এই মৌলিক ডিজাইনগুলোর সাথে সম্পর্কিত বা এগুলো থেকে বিকশিত হয়েছে।

• একটি ব্যালেন্সড ইনকমপ্লিট ব্লক ডিজাইন বা BIBD (সাধারণত সংক্ষেপে ব্লক ডিজাইন বলা হয়) হলো একটি সসীম সেট X-এর v উপাদানের b উপসেটের (যাকে 'ব্লক' বলা হয়) একটি সংগ্রহ B', যাতে X-এর প্রতিটি উপাদান ব্লকের সমান সংখ্যা r-এ থাকে, প্রতিটি ব্লকে উপাদানের সংখ্যা k সমান হয় এবং প্রতিটি ভিন্ন উপাদানের জোড়া ব্লকের সমান সংখ্যা λ-তে একসাথে উপস্থিত থাকে। BIBD-গুলোকে 2-ডিজাইন হিসেবেও পরিচিত এবং প্রায়শই 2-(v,k,λ) ডিজাইন হিসেবে চিহ্নিত করা হয়। উদাহরণস্বরূপ, যখন λ = 1 এবং b = v হয়, তখন আমরা একটি প্রজেক্টিভ প্লেন পাই: X হলো প্লেনের বিন্দুর সেট এবং ব্লকগুলো হলো রেখা।
• একটি প্রতিসম ব্যালেন্সড ইনকমপ্লিট ব্লক ডিজাইন বা SBIBD হলো এমন একটি BIBD যেখানে v  =  b (বিন্দুর সংখ্যা ব্লকের সংখ্যার সমান)। এগুলো BIBD-এর সবচেয়ে গুরুত্বপূর্ণ এবং সুপরিচিত উপশ্রেণী। প্রজেক্টিভ প্লেন, বাইপ্লেন এবং হ্যাডামার্ড 2-ডিজাইন সবই SBIBD। এগুলো বিশেষ আগ্রহের কারণ, কারণ এগুলো ফিশারের অসমতা (b ≥ v)-এর চরম উদাহরণ।
• একটি রিসলভ্যাবল BIBD হলো এমন একটি BIBD যার ব্লকগুলোকে সেটে (যাকে 'প্যারালাল ক্লাস' বলা হয়) বিভক্ত করা যায়, যার প্রতিটি BIBD-এর বিন্দুর সেটের একটি পার্টিশন গঠন করে। প্যারালাল ক্লাসের সেটকে ডিজাইনের একটি 'রেজোলিউশন' বলা হয়। বিখ্যাত ১৫ স্কুলগার্ল সমস্যা-এর সমাধান হলো v  = 15, k  = 3 এবং λ = 1 বিশিষ্ট একটি BIBD-এর রেজোলিউশন।
• একটি ল্যাটিন রেকট্যাঙ্গেল হলো একটি r × n ম্যাট্রিক্স যাতে ১, ২, ৩, ..., n সংখ্যাগুলো (বা অন্য কোনো nটি ভিন্ন প্রতীক) ভুক্তি হিসেবে থাকে, যেখানে কোনো সংখ্যাই কোনো সারি বা কলামে একাধিকবার থাকে না এবং r ≤ n। একটি n × n ল্যাটিন রেকট্যাঙ্গেলকে ল্যাটিন স্কয়ার বলা হয়। যদি r < n হয়, তবে হলের ম্যারেজ উপপাদ্য ব্যবহার করে একটি r × n ল্যাটিন রেকট্যাঙ্গেলের সাথে n − r সারি যোগ করে একটি ল্যাটিন স্কয়ার তৈরি করা সম্ভব।

দুটি n অর্ডারের ল্যাটিন স্কয়ারকে 'অর্থোগোনাল' বলা হয় যদি দুটি স্কয়ারের সংশ্লিষ্ট ভুক্তিগুলোর সমস্ত ক্রমজোড়ের সেটে n²টি ভিন্ন সদস্য থাকে (সমস্ত সম্ভাব্য ক্রমজোড় উপস্থিত থাকে)। একই অর্ডারের ল্যাটিন স্কয়ারের একটি সেটকে মিউচুয়ালি অর্থোগোনাল ল্যাটিন স্কয়ার (MOLS) বলা হয় যদি সেটের প্রতিটি জোড়া ল্যাটিন স্কয়ার অর্থোগোনাল হয়। n অর্ডারের MOLS-এর একটি সেটে সর্বোচ্চ n − 1টি স্কয়ার থাকতে পারে। n অর্ডারের n − 1টি MOLS-এর একটি সেট ব্যবহার করে n অর্ডারের একটি প্রজেক্টিভ প্লেন তৈরি করা যায় (এবং বিপরীতক্রমেও)।

• একটি (v, k, λ) ডিফারেন্স সেট হলো একটি গ্রুপ G-এর একটি উপসেট D, যাতে G-এর অর্ডার v, D-এর আকার k হয় এবং G-এর প্রতিটি নন-আইডেন্টিটি উপাদানকে D-এর উপাদানগুলোর গুণফল d₁d₂⁻¹ হিসেবে ঠিক λ উপায়ে প্রকাশ করা যায় (যখন G গুণন প্রক্রিয়ায় লেখা হয়)।

যদি D একটি ডিফারেন্স সেট হয় এবং g গ্রুপ G-এর সদস্য হয়, তবে g D = {gd: d in D} ও একটি ডিফারেন্স সেট, যাকে D-এর একটি 'ট্রান্সলেট' বলা হয়। একটি ডিফারেন্স সেট D-এর সমস্ত ট্রান্সলেটের সেট একটি প্রতিসম BIBD গঠন করে। এই ডিজাইনে vটি উপাদান এবং vটি ব্লক থাকে। ডিজাইনের প্রতিটি ব্লক kটি বিন্দু নিয়ে গঠিত, প্রতিটি বিন্দু kটি ব্লকে থাকে। যেকোনো দুটি ব্লকের মধ্যে ঠিক λটি উপাদান সাধারণ থাকে এবং যেকোনো দুটি বিন্দু λটি ব্লকে একসাথে উপস্থিত থাকে। এই SBIBD-কে D-এর 'ডেভেলপমেন্ট' বলা হয়।

বিশেষ করে, যদি λ = 1 হয়, তবে ডিফারেন্স সেটটি একটি প্রজেক্টিভ প্লেন তৈরি করে। $\mathbb{\mathbb{Z}}/7\mathbb{\mathbb{Z}}$ গ্রুপে (যোগের মাধ্যমে লেখা একটি অ্যাবেলিয়ান গ্রুপ) একটি (7,3,1) ডিফারেন্স সেটের উদাহরণ হলো উপসেট {1,2,4}। এই ডিফারেন্স সেটের ডেভেলপমেন্ট ফ্যানো প্লেন প্রদান করে।

যেহেতু প্রতিটি ডিফারেন্স সেট একটি SBIBD প্রদান করে, তাই প্যারামিটার সেটটিকে অবশ্যই ব্রুক-রাইজার-চাওলা উপপাদ্য সন্তুষ্ট করতে হবে, কিন্তু প্রতিটি SBIBD একটি ডিফারেন্স সেট প্রদান করে না।

• m অর্ডারের একটি হ্যাডামার্ড ম্যাট্রিক্স হলো একটি m × m ম্যাট্রিক্স H, যার ভুক্তিগুলো ±1 এবং যা HH^⊤  = mI_m শর্ত পূরণ করে, যেখানে H^⊤ হলো H-এর ট্রান্সপোজ এবং I_m হলো m × m আইডেন্টিটি ম্যাট্রিক্স। একটি হ্যাডামার্ড ম্যাট্রিক্সকে 'স্ট্যান্ডার্ডাইজড ফর্মে' (অর্থাৎ, সমতুল্য হ্যাডামার্ড ম্যাট্রিক্সে রূপান্তরিত) আনা যায় যেখানে প্রথম সারি এবং প্রথম কলামের ভুক্তিগুলো সবই +1। যদি অর্ডার m > 2 হয়, তবে m অবশ্যই 4-এর গুণিতক হতে হবে।

স্ট্যান্ডার্ডাইজড ফর্মে 4a অর্ডারের একটি হ্যাডামার্ড ম্যাট্রিক্স দেওয়া থাকলে, প্রথম সারি এবং প্রথম কলাম সরিয়ে ফেলুন এবং প্রতিটি −1-কে 0-তে রূপান্তর করুন। প্রাপ্ত 0–1 ম্যাট্রিক্স M হলো একটি প্রতিসম 2-(4a − 1, 2a − 1, a − 1) ডিজাইনের ইনসিডেন্স ম্যাট্রিক্স, যাকে হ্যাডামার্ড 2-ডিজাইন বলা হয়। এই গঠনটি বিপরীতমুখী এবং এই প্যারামিটারগুলো বিশিষ্ট একটি প্রতিসম 2-ডিজাইনের ইনসিডেন্স ম্যাট্রিক্স ব্যবহার করে 4a অর্ডারের একটি হ্যাডামার্ড ম্যাট্রিক্স তৈরি করা যায়। যখন a = 2 হয়, তখন আমরা পরিচিত ফ্যানো প্লেন-কে হ্যাডামার্ড 2-ডিজাইন হিসেবে পাই।

• pairwise balanced design একটি পেয়ারওয়াইজ ব্যালেন্সড ডিজাইন (বা PBD) হলো একটি সেট X এবং X-এর উপসেটগুলোর একটি পরিবার (যার আকার সমান হতে হবে এমন নয় এবং পুনরাবৃত্তি থাকতে পারে) যাতে X-এর প্রতিটি ভিন্ন উপাদানের জোড়া ঠিক λ (একটি ধনাত্মক পূর্ণসংখ্যা) উপসেটে থাকে। সেট X-কে উপসেটগুলোর একটি হিসেবে থাকার অনুমতি দেওয়া হয় এবং যদি সমস্ত উপসেট X-এর অনুলিপি হয়, তবে PBD-কে 'ট্রিভিয়াল' বলা হয়। X-এর আকার v এবং পরিবারে উপসেটের সংখ্যা (বহুগুণিতা সহ গণনা করা) হলো b।

ফিশারের অসমতা PBD-এর জন্য প্রযোজ্য: যেকোনো নন-ট্রিভিয়াল PBD-এর জন্য, v ≤ b।

এই ফলাফলটি বিখ্যাত এরডোস-ডি ব্রুইন উপপাদ্য-কেও সাধারণীকরণ করে: λ = 1 বিশিষ্ট একটি PBD-এর জন্য যার ১ বা v আকারের কোনো ব্লক নেই, v ≤ b, যেখানে সমতা তখনই ঘটে যদি PBD একটি প্রজেক্টিভ প্লেন বা একটি নিয়ার-পেন্সিল হয়।

তথ্যসূত্র

60em

• (1992). "Designs and Their Codes". Cambridge University Press. ISBN 0-521-41361-3.
• (1986). "Design Theory". Cambridge University Press.. ২য় সংস্করণ (১৯৯৯) 978-0-521-44432-3।
• (1949). "A Note on Fisher's Inequality for Balanced Incomplete Block Designs". Annals of Mathematical Statistics. 20 (4) 619–620. doi:10.1214/aoms/1177729958.
• (2003). Block designs: A Randomization approach, Volume II: Design. 170. Springer. ISBN 0-387-95470-8.
• (2007). Handbook of Combinatorial Designs. Chapman & Hall/ CRC. ISBN 978-1-58488-506-1.
• (1940). "An examination of the different possible solutions of a problem in incomplete blocks". Annals of Eugenics. 10 52–75. doi:10.1111/j.1469-1809.1940.tb02237.x.
• Hall, Jr., Marshall. (1986). "Combinatorial Theory". Wiley-Interscience. ISBN 0-471-09138-3.
• (1985). Design theory. Cambridge University Press. ISBN 0-521-25754-9.
• Lander, E. S.. (1983). "Symmetric Designs: An Algebraic Approach". Cambridge University Press.
• (1997). "Design Theory". CRC Press. ISBN 0-8493-3986-3.
• (1988). Constructions and Combinatorial Problems in Design of Experiments. Dover. ISBN 978-0-486-65685-4.
• (2005). "Block Designs: Analysis, Combinatorics and Applications". World Scientific. ISBN 978-981-4480-23-9.
• Ryser, Herbert John. (1963). Combinatorial Mathematics. 14. Mathematical Association of America. ISBN 978-0-88385-000-8.
• (1970). "Non-isomorphic solutions of some balanced incomplete block designs I". Journal of Combinatorial Theory. 9 (2) 174–191. doi:10.1016/S0021-9800(70)80024-2.
• Stinson, Douglas R.. (2003). "Combinatorial Designs: Constructions and Analysis". Springer. ISBN 0-387-95487-2.
• (1987). "Combinatorics of Experimental Design". Oxford U. P. [Clarendon]. ISBN 0-19-853256-3.
• (1992). A Course in Combinatorics. Cambridge University Press. ISBN 978-0-521-41057-1.

---

উৎস: ইংরেজি উইকিপিডিয়ার “Combinatorial design” নিবন্ধের অনুবাদ। মূল নিবন্ধ: https://en.wikipedia.org/wiki/Combinatorial_design এই অনুবাদটি স্বয়ংক্রিয়ভাবে প্রস্তুত করা হয়েছে।