গণিতশাস্ত্রেদ্বিপদী সহগ (ইংরেজিঃ Binomial coefficient) বলতে সেসব ধনাত্মক পূর্ণসংখ্যা নির্দেশ করে যেসব সংখ্যা দ্বিপদী উপপাদ্যে সহগ হিসেবে বিদ্যমান। সাধারণভাবে দ্বিপদী সহগকে এক জোড়া পূর্ণসংখ্যা দ্বারা সূচিত করা হয়, যেখানে এবং প্রকাশ করা হয় দ্বারা । এটি হলো দ্বিপদী ঘাত এর বিস্তৃতিতে এর সহগ, এবং এটি নিম্নোক্ত সূত্র দ্বারা সংজ্ঞায়িতঃ
দ্বিপদী সহগসমূহকে প্যাসকেলের ত্রিভুজ অনুযায়ী সাজানো যায় যেখানে প্রতিটি ভুক্তি তার ঠিক উপরস্থ দুটি পদের যোগফল
উদাহরণস্বরূপ, এর পঞ্চম ঘাতের বিস্তৃতিঃ
,
৪র্থ ঘাত পর্যন্ত দ্বিপদী বিস্তৃতির visualization।
এবং পদটির দ্বিপদী সহগ ।
কে মানসমূহের জন্য পর পর সারি অনুযায়ী সাজানো হলে একটি ত্রিভুজ সদৃশ পুনরাবৃত্তিমূলক সম্পর্ক পাওয়া যায় যাকে প্যাসকেলের ত্রিভুজ বলা হয়। এই সম্পর্কটি হলোঃ
দ্বিপদী সহগসমূহ গণিতশাস্ত্রের অনেক শাখায় আবির্ভূত হয়, বিশেষত গুচ্ছ-বিন্যাসতত্ত্বে (combinatorics)। প্রতীকটিকে মূলত পড়া হয় " choose " কেননা, সংখ্যক উপাদান বিশিষ্ট কোনো একটি নির্দিষ্ট সেট থেকে সংখ্যক অনন্য উপাদান নিয়ে মোট উপসেট তৈরী করার উপায় সংখ্যা হলো টি। উদাহরণস্বরূপ, সেটটি হতে টি অনন্য উপাদান নিয়ে মোট উপসেট তৈরী করা যায় টি, যেগুলো হলোঃ ।
যেকোনো জটিল সংখ্যাএবং পূর্ণসংখ্যাএর জন্য দ্বিপদী সহগকে সাধারণভাবে আকারে প্রকাশ করা যায় এবং জটিল সংখ্যার অনেক বৈশিষ্ট্যই এভাবে আরো সাধারণ রূপে প্রকাশিত হয়।
১৮২৬ খ্রিস্টাব্দে আন্দ্রিয়াস ভন এটিইংসহাউসেন সর্বপ্রথম চিহ্নলিপিটি ব্যবহার করেন[১], যদিও এই সংখ্যাসমূহের বিষয়ে কয়েক শতাব্দী আগ হতেই জানা ছিলো। দ্বিপদী সহগের বিষয়ে সর্বপ্রথম বিস্তারিত আলোচনার প্রমাণ মেলে প্রাচীন সংস্কৃত ভাষায় রচিত পিঙ্গলার চন্দ্রসাস্ত্র(Chandaḥśāstra) গ্রন্থে হালায়ুধার(Halayudha) নোট হতে। ১১৫০ খ্রিস্টাব্দের দিকে ভারতীয় গণিতবিদ দ্বিতীয় ভাস্কর তার লীলাবতী নামক গ্রন্থে দ্বিপদী সহগের বিষয়ে ব্যাখ্যা প্রদান করেন[২]।
এছাড়াও ব্যবহৃত বিকল্প চিহ্নলিপিগুলো হলো এবং যেগুলোর প্রতিটিতেই নির্দেশ করে সমাবেশ বা বাছাই। অনেক ক্যাল্কুলেটরেচিহ্নলিপিটি ব্যবহার করা হয় কিছুটা ভিন্নভাবে যাতে তা একটি একক-লাইন বিশিষ্ট পর্দায় প্রকাশযোগ্য হয়।
স্বাভাবিক সংখ্যা ও এর জন্য দ্বিপদী সহগ কে সংজ্ঞায়িত করা যায় এর বিস্তৃতিতে এর সহগ হিসেবে। এই একই সহগ আরো পাওয়া যায় নিম্নোক্ত দ্বিপদী সূত্রে()
দ্বিপদী সহগ আরো পরিলক্ষিত হয় গুচ্ছ-বিন্যাসতত্ত্বে, যেখানে এর দ্বারা সংখ্যক উপাদান হতে সংখ্যক ভিন্ন উপাদান বাছাই এর উপায় সংখ্যা নির্দেশ করে; অথবা আরো রীত্যনুসারে বলা যায় সংখ্যক উপাদানের সেট হতে সংখ্যক উপাদান নিয়ে গঠিত উপসেট (অথবা টি সমাবেশ সংখ্যা)।
দ্বিপদী সহগের মান গণনার একটি পদ্ধতি হলো পুনরাবৃত্তি সূত্র যা সম্পূর্ণ যোগাত্মক
যেখানে সীমাস্থ মান,
সূত্রটির ব্যাখ্যা দেয়া যায় এইভাবেঃ ধরা যাক একটি সেট । এ সেট হতে আলদা আলদাভাবে (ক) সংখ্যক উপাদান নিয়ে গ্রূপ করা হলো যার প্রতিটিতে একটি সাধারণ উপাদান, ধরা যাক, বিদ্যমান (যেহেতু, ইতিমধ্যে ঐ গ্রূপের একটি স্থান দখল করেছে, তাই অবশিষ্ট সংখ্যক উপাদান হতে সংখ্যক উপাদান বাছাই করতে হবে) এবং (খ) সংখ্যক উপাদান নিয়ে সম্ভাব্য সকল গ্রূপ যাতে ঐ অন্তর্ভুক্ত না থাকে, (অর্থাৎ সংখ্যক উপাদান হতে সংখ্যক উপাদান বাছাই করতে হবে) গণনা করলে তার সমষ্টি হলো নির্ণেয় মান।
কোনো একটি নির্দিষ্ট দ্বিপদী সহগের মান গণনার ক্ষেত্রে আরো কার্যকরী নিম্নের সূত্রটি,
এখানে, প্রথম ভগ্নাংশের লব কে বলা হয় ক্রমহ্রাসমান ফ্যাক্টরিয়াল। এখানে সূত্রের লব হলো সংখ্যক উপাদানের একটি সেট হতে সংখ্যক উপাদান বাছাই এর মোট উপায় সংখ্যা যখন ক্রম বিবেচনাধীন এবং হর হলো অনন্য উপায় সংখ্যা ঐ একই সংখ্যক সমাবেশের জন্য যখন ক্রম অবিবেচনাধীন।
দ্বিপদী সহগের ও এর সাপেক্ষে প্রতিসমতা ধর্মের কারণে এসব গণনা আরো সহজে সম্পন্ন করা যায়।
যদিও গণনার দিক দিয়ে এটি সময়সাপেক্ষ, এই সূত্রটি প্রমাণ ও প্রতিপাদনের ক্ষেত্রে বহূল ব্যবহ্রত,
এখানে নির্দেশ করে এর ফ্যাক্টোরিয়াল। এই সুত্রটি পাওয়া যায় গুণক সূত্রের লব ও হর উভয়কে দ্বারা গুণ করার মাধ্যমে যার ফলে লব ও হরে অনেকগুলো সাধারণ উৎপাদক তৈরী হয়। এই সূত্র হতে প্রতিসমতার ধর্ম খুব সহজেই বোধগম্য গুণক সুত্রের তুলনায়,
এর থেকে ক্রমহ্রাসমান ফ্যাক্টরিয়াল এর ধারণা ব্যবহার করে আরো কার্যকরীভাবে দ্বিপদী সহগের মান গণনা করা যায়,
যা গাণিতিক আরোহ বিধি ব্যবহারের মাধ্যমে প্রমাণ করা যায়।
প্যাস্কেলের সূত্র হতে পাওয়া যায় প্যাস্কেলের ত্রিভূজঃ
0:
1
1:
1
1
2:
1
2
1
3:
1
3
3
1
4:
1
4
6
4
1
5:
1
5
10
10
5
1
6:
1
6
15
20
15
6
1
7:
1
7
21
35
35
21
7
1
8:
1
8
28
56
70
56
28
8
1
সারি নম্বর এ বিদ্যমান সংখ্যাগুলো হলো এর জন্য এর মান। এটি তৈরী করা হয়েছে প্রথমে সর্ববহিঃস্থ অবস্থানগুলো 1 দ্বারা পূরণের মাধ্যমে। এরপর ভিতরের প্রতিটি অবস্থান পূরণ করা হয়েছে তার ঠিক উপরের দুটি পদের সমষ্টি দ্বারা। এই পদ্ধতির মাধ্যমে গুণ-ভাগ ব্যতীতই দ্রুততার সাথে দ্বিপদী সহগ গণনা করা যায়। উদাহরণস্বরূপ, ৫ম সারি হতে বলা যায়
যেমন, এই প্রাথমিক শর্ত দ্বারা যেকোনো বাস্তব বা জটিল সংখ্যা এর জন্য দ্বিপদী সহগ ব্যাখ্যা করা যায়। এসব "সর্বজনীন দ্বিপদী সহগ" নিউটনের সর্বজনীন দ্বিপদী সহগেও আবির্ভূত হয়।
প্রতিটি এর জন্য বহুপদী কে বৈশিষ্টায়িত করা যায় অনন্য ঘাতের বহুপদী হিসেবে, যেখানে, এবং ।
প্রতিটি বহুপদী পূর্ণসাংখ্যিকঃ এর সকল পূর্ণসাংখ্যিক মানের জন্য এর মান একটি পূর্ণসংখ্যা। অতএব, যেকোনো পূর্ণসাংখ্যিক রৈখিক সমাবেশের জন্য দ্বিপদী সহগসমূহও পূর্ণসাংখ্যিক।
কিছু ত্রিকোণমিতিক যোগজের মানকে দ্বিপদী সহগ দ্বারা প্রকাশ করা যায়ঃ
এর জন্য,
এগুলো প্রমাণ করা যায় অয়লারের সূত্র দ্বারা। এজন্য ত্রিকোণমিতিক ফাংশনকে সূচকীয় জটিল সংখ্যা হিসেবে প্রকাশ করে, দ্বিপদী সহগ অনুযায়ী বিস্তৃত করে, প্রতিটি পদকে আলাদা আলাদাভাবে যোগজীকরণ করতে হয়।
১৮৫২ খ্রিস্টাব্দে আরনেস্ট কামার প্রমাণ করেন যে, যদি ও অঋণাত্মক পূর্ণসংখ্যা হয় এবং একটি মৌলিক সংখ্যা হয়, তবে এর সর্বোচ্চ যে ঘাত দ্বারা বিভাজ্য তা হলো ; যেখানে হলো ও কে ভিত্তিতে যোগ করার ফলে প্রাপ্ত ক্যারি এর সংখ্যা। একইভাবে এ কোনো একটি মৌলিক সংখ্যা এর সূচকের মান অঋণাত্মক পূর্ণসংখ্যা এর সমান যাতে এর ফ্যাক্টরিয়াল অংশ এর ফ্যাক্টরিয়াল অংশ অপেক্ষা বড় হয়। এটি হতে সিদ্ধান্তে আসা যায় যে, , দ্বারা বিভাজ্য। এর থেকে পরবর্তীতে পাওয়া যায় সকল ধণাত্মক পূর্ণসংখ্যা এর জন্য যাতে ; , দ্বারা বিভাজ্য। তবে এটি এর উচ্চ ঘাতের জন্য প্রযোজ্য নয়।
ডেভিড সিংমাস্টার এর ফলাফল হতে দেখা যায়, যেকোনো পূর্ণসংখ্যা প্রায় সকল দ্বিপদী সহগ দ্বারা বিভাজ্য। আরো সুনির্দিষ্টভাবে বলা যায়, কোনো একটি পূর্ণসংখ্যা নির্দিষ্ট করে যদি এমনভাবে সংজ্ঞায়িত করা হয় যা এর দ্বিপদী সহগসমূহ নির্দেশ করে এবং হয়, আর , দ্বারা বিভাজ্য হয়। তাহলে
যেহেতু শর্ত পূরণকারী দ্বিপদী সহগের সংখ্যা , তাই এটি নির্দেশ করে দ্বারা বিভাজ্য দ্বিপদী সহগ প্রাপ্তির পরিমাণ তথা দ্বিপদী সহগ ঘনত্ব যার মান দাঁড়ায় ১।
দ্বিপদী সহগসমূহের বিভাজ্যতার সাথে ধারাবাহিক পূর্ণসংখ্যার লসাগুর সাথে সম্পর্ক রয়েছে। উদাহরণস্বরূপঃ[৬]
, দ্বারা বিভাজ্য।
, এর গুণিতক।
এছাড়াও কোনো একটি পূর্ণসংখ্যা একটি মৌলিক সংখ্যা হবে যদি ও কেবল যদি সকল মধ্যবর্তী দ্বিপদী সহগ
যেহেতু স্টার্লিং এর সূত্রের অসমতা ফ্যাক্টরিয়ালকেও সীমাস্থ করে থাকে, তাই উপরের অসীমতটের অনুমিত মানকে সামান্য পরিবর্তন করলে যথাযথ সীমাস্থ মান পাওয়া যায়।
দ্বিপদী সহগ দ্বারা কোনো একটি সেটের নির্ধারিত সংখ্যক উপাদান নিয়ে উপসেট গণনা করা যায়। এর সাথে সংশ্লিষ্ট গুচ্ছ-বিন্যাসতাত্ত্বিক সমস্যা হলো যেকোনো সেট হতে নির্ধারিত সংখ্যক উপাদান নিয়ে যৌগিক সেট গণনা তথা কোনো সেট হতে নির্দিষ্ট সংখ্যক উপাদান বাছাই করার উপায় এই শর্তে যে একই উপাদান একাধিকবার বাছাই করা যাবে। এর মাধ্যমে প্রাপ্ত সংখ্যাগুলোকে বলা হয় যৌগিক সেটের সহগ;[৯] সংখ্যক উপাদানের একটি সেট হতে সংখ্যক উপাদান নিয়ে "যৌগিক বাছাই" এর উপায়কে প্রকাশ করা হয় দ্বারা।
যৌগিক সেটের সহগসমূহকে দ্বিপদী সহগ দ্বারাও প্রকাশ করা যেতে পারে নিম্নোক্ত নিয়ম ব্যবহার করে
।
এই অভেদের একটি সম্ভাব্য বিকল্প বৈশিষ্ট্য দেয়া যেতে পারে এভাবেঃ নিম্নগামী ফ্যাক্টরিয়াল প্রকাশ করা যায় এভাবে,
,
এবং সংশ্লিষ্ট ঊর্ধ্বগামী ফ্যাক্টরিয়াল প্রকাশ করা যায় এভাবে,
উদাহরণস্বরূপ,
তবে দ্বিপদী সহগকে এভাবে উল্লেখ করা যেতে পারে,
,
যখন সংশ্লিষ্ট যৌগিক সহগ সংজ্ঞায়িত নিম্নগামী ফ্যাক্টরিয়াল ঊর্ধ্বগামী ফ্যাক্টরিয়াল দ্বারা প্রতিস্থাপনের মাধ্যমেঃ
চিহ্নটি হাতে লিখার জন্য সুবিধাজনক হলেও টাইপরাইটার এবং কম্পিউটার প্রান্তের জন্য তা সমস্যাদায়ক। অনেক প্রোগ্রামিং ভাষাই দ্বিপদী সহগ গণনার জন্য কোনো প্রমাণ সাবরুটিন প্রদান করে না। তবে APL প্রোগ্রামিং ভাষা এবং J প্রোগ্রামিং ভাষা এটি প্রকাশের জন্য বিস্ময় চিহ্ন ব্যবহার করেঃ ।
ফ্যাক্টরিয়াল সূত্রের সরল রূপায়ন দেখা যায়, যেমন নিচের পাইথনেরsnippet,
অনেক ধীরগতিসম্পন্ন এবং বেশ বড় কোনো সংখ্যার ফ্যাক্টরিয়াল গণনার ক্ষেত্রে তা প্রায় অকার্যকর। গুণক সূত্রের সরাসরি প্রয়োগ এক্ষেত্রে ভালো ফলাফল দেয়ঃ
defbinomialCoefficient(n,k):ifk<0ork>n:return0ifk==0ork==n:return1k=min(k,n-k)# take advantage of symmetryc=1foriinrange(k):c=c*(n-i)/(i+1)returnc
(পাইথনে, range(k) হতে পর্যন্ত তালিকা তৈরী করে)
প্যাস্কেলের সূত্র হতে পুনরাবৃত্তির একটি সংজ্ঞা দেয় যা পাইথনে ব্যবহার করা গেলেও এর কার্যকরিতা কমঃ
defbinomialCoefficient(n,k):ifk<0ork>n:return0ifk>n-k:# take advantage of symmetryk=n-kifk==0orn<=1:return1returnbinomialCoefficient(n-1,k)+binomialCoefficient(n-1,k-1)
উপরে উল্লিখিত উদাহরণ ফাংশন আকারেও লিখা যায়। নিচে স্কিম প্রোগ্রামিং ভাষায় রচিত প্রোগ্রামটি পুনরাবৃত্ত সংজ্ঞা ব্যবহার করে,
নিচের কোডটিতে এ ধারণা ব্যবহার করা হয়েছে,
(define(binomialnk);; Helper function to compute C(n,k) via forward recursion(define(binomial-iternkiprev)(if(>=ik)prev(binomial-iternk(+i1)(/(*(-ni)prev)(+i1)))));; Use symmetry property C(n,k)=C(n, n-k)(if(<k(-nk))(binomial-iternk01)(binomial-itern(-nk)01)))
কোনো নির্দিষ্ট দৈর্ঘ্যের পূর্ণসংখ্যা বিশিষ্ট প্রোগ্রামিং ভাষায় গণনার সময় দ্বারা গুণন যখন ফলাফল পাওয়া সম্ভন সেক্ষেত্রেও ওভারফ্লো হতে পারে। এটি এড়ানো যায় প্রথমে ভাগ প্রক্রিয়ার প্রয়োগ এবং ভাগশেষ ব্যবহার করার মাধ্যমেঃ
C ভাষায় এর প্রয়োগঃ
#include<limits.h>unsignedlongbinomial(unsignedlongn,unsignedlongk){unsignedlongc=1,i;if(k>n-k)// take advantage of symmetryk=n-k;for(i=1;i<=k;i++,n--){if(c/i>UINT_MAX/n)// return 0 on overflowreturn0;c=c/i*n+c%i*n/i;// split c * n / i into (c / i * i + c % i) * n / i}returnc;}
↑[Boardman, Michael (2004), "The Egg-Drop Numbers", Mathematics Magazine, 77 (5): 368–372, doi:10.2307/3219201, JSTOR 3219201, MR 1573776, it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients. "The Egg-Drop Numbers"]|ইউআরএল= এর মান পরীক্ষা করুন (সাহায্য)। Mathematics Magazine।
↑see induction developed in eq (7) p. 1389 in Aupetit, Michael (2009), "Nearly homogeneous multi-partitioning with a deterministic generator", Neurocomputing, 72 (7–9): 1379–1389, doi:10.1016/j.neucom.2008.12.024, ISSN 0925-2312.।