গণিতশাস্ত্রেদ্বিপদী সহগ (ইংরেজিঃ Binomial coefficient) বলতে সেসব ধনাত্মক পূর্ণসংখ্যা নির্দেশ করে যেসব সংখ্যা দ্বিপদী উপপাদ্যে সহগ হিসেবে বিদ্যমান। সাধারণভাবে দ্বিপদী সহগকে এক জোড়া পূর্ণসংখ্যা দ্বারা সূচিত করা হয়, যেখানে এবং প্রকাশ করা হয় দ্বারা । এটি হলো দ্বিপদী ঘাত এর বিস্তৃতিতে এর সহগ, এবং এটি নিম্নোক্ত সূত্র দ্বারা সংজ্ঞায়িতঃ
উদাহরণস্বরূপ, এর পঞ্চম ঘাতের বিস্তৃতিঃ
,
এবং পদটির দ্বিপদী সহগ ।
কে মানসমূহের জন্য পর পর সারি অনুযায়ী সাজানো হলে একটি ত্রিভুজ সদৃশ পুনরাবৃত্তিমূলক সম্পর্ক পাওয়া যায় যাকে প্যাসকেলের ত্রিভুজ বলা হয়। এই সম্পর্কটি হলোঃ
দ্বিপদী সহগসমূহ গণিতশাস্ত্রের অনেক শাখায় আবির্ভূত হয়, বিশেষত গুচ্ছ-বিন্যাসতত্ত্বে (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 দ্বারা পূরণের মাধ্যমে। এরপর ভিতরের প্রতিটি অবস্থান পূরণ করা হয়েছে তার ঠিক উপরের দুটি পদের সমষ্টি দ্বারা। এই পদ্ধতির মাধ্যমে গুণ-ভাগ ব্যতীতই দ্রুততার সাথে দ্বিপদী সহগ গণনা করা যায়। উদাহরণস্বরূপ, ৫ম সারি হতে বলা যায়
গুচ্ছ-বিন্যাসতত্ত্ব ও পরিসংখ্যান
দ্বিপদী সহগ গুচ্ছ-বিন্যাসতত্ত্বে ব্যাপকভাবে ব্যবহার হয়। কেননা, প্রচলিত বিভিন্ন গণনা সংক্রান্ত সমস্যার জন্য সরাসরি সূত্র ব্যবহার করা যায়। যেমনঃ
সংখ্যক উপাদানের কোনো সেট হতে সংখ্যক উপাদান বাছাই করা যায় মোট উপায়ে (পুনরাবৃত্তি ব্যতীত)
সংখ্যক উপাদানের কোনো সেট হতে সংখ্যক উপাদান বাছাই করা যায় মোট উপায়ে (পুনরাবৃত্তি অনুমিত)
যেমন, এই প্রাথমিক শর্ত দ্বারা যেকোনো বাস্তব বা জটিল সংখ্যা এর জন্য দ্বিপদী সহগ ব্যাখ্যা করা যায়। এসব "সর্বজনীন দ্বিপদী সহগ" নিউটনের সর্বজনীন দ্বিপদী সহগেও আবির্ভূত হয়।
প্রতিটি এর জন্য বহুপদী কে বৈশিষ্টায়িত করা যায় অনন্য ঘাতের বহুপদী হিসেবে, যেখানে, এবং ।
এর সহগসমূহকে প্রথম ক্রমের স্টার্লিং সংখ্যা হিসেবে প্রকাশ করা যায়ঃ
এর অন্তরজ গণনা করা যায় লগারিদমিক অন্তরীকরণ দ্বারাঃ
পূর্ণসাংখ্যিক বহুপদী
প্রতিটি বহুপদী পূর্ণসাংখ্যিকঃ এর সকল পূর্ণসাংখ্যিক মানের জন্য এর মান একটি পূর্ণসংখ্যা। অতএব, যেকোনো পূর্ণসাংখ্যিক রৈখিক সমাবেশের জন্য দ্বিপদী সহগসমূহও পূর্ণসাংখ্যিক।
উদাহরণ
এই পূর্ণসাংখ্যিক বহুপদীকে এভাবেও প্রকাশ করা যায়ঃ
দ্বিপদী সহগযুক্ত কিছু অভেদ
যদি একটি ধণাত্মক পূর্ণসংখ্যা এবং ইচ্ছামূলক সংখ্যা হয়, তবে
এবং,
এছাড়া এটিও কার্যকরী হতে পারেঃ
কোনো একটি নির্দিষ্ট এর জন্য নিম্নোক্ত পুনরাবৃত্ততা পাওয়া যায়ঃ
কিছু ত্রিকোণমিতিক যোগজের মানকে দ্বিপদী সহগ দ্বারা প্রকাশ করা যায়ঃ
এর জন্য,
এগুলো প্রমাণ করা যায় অয়লারের সূত্র দ্বারা। এজন্য ত্রিকোণমিতিক ফাংশনকে সূচকীয় জটিল সংখ্যা হিসেবে প্রকাশ করে, দ্বিপদী সহগ অনুযায়ী বিস্তৃত করে, প্রতিটি পদকে আলাদা আলাদাভাবে যোগজীকরণ করতে হয়।
উদ্ভূত ফাংশন
সাধারণ উদ্ভূত ফাংশন
এর কোনো একটি নির্দিষ্ট মানের জন্য ধারাটির সাধারণ উদ্ভূত ফাংশন হলো,
এর কোনো একটি নির্দিষ্ট মানের জন্য ধারাটির সাধারণ উদ্ভূত ফাংশন হলো,
আর উভয়ই পরিবির্তনশীল হলে দ্বিপদী সহগ হবে,
দ্বিপদী সহগের অপর একটি প্রতিসম সাধারণ উদ্ভূত ফাংশন হলো,
সূচকীয় উদ্ভূত ফাংশন
দ্বিপদী সহগের একটি প্রতিসম দ্বিপরিবির্তনশীল উদ্ভূত ফাংশন হলোঃ
বিভাজ্যতার বৈশিষ্ট্যসমূহ
১৮৫২ খ্রিস্টাব্দে আরনেস্ট কামার প্রমাণ করেন যে, যদি ও অঋণাত্মক পূর্ণসংখ্যা হয় এবং একটি মৌলিক সংখ্যা হয়, তবে এর সর্বোচ্চ যে ঘাত দ্বারা বিভাজ্য তা হলো ; যেখানে হলো ও কে ভিত্তিতে যোগ করার ফলে প্রাপ্ত ক্যারি এর সংখ্যা। একইভাবে এ কোনো একটি মৌলিক সংখ্যা এর সূচকের মান অঋণাত্মক পূর্ণসংখ্যা এর সমান যাতে এর ফ্যাক্টরিয়াল অংশ এর ফ্যাক্টরিয়াল অংশ অপেক্ষা বড় হয়। এটি হতে সিদ্ধান্তে আসা যায় যে, , দ্বারা বিভাজ্য। এর থেকে পরবর্তীতে পাওয়া যায় সকল ধণাত্মক পূর্ণসংখ্যা এর জন্য যাতে ; , দ্বারা বিভাজ্য। তবে এটি এর উচ্চ ঘাতের জন্য প্রযোজ্য নয়।
ডেভিড সিংমাস্টার এর ফলাফল হতে দেখা যায়, যেকোনো পূর্ণসংখ্যা প্রায় সকল দ্বিপদী সহগ দ্বারা বিভাজ্য। আরো সুনির্দিষ্টভাবে বলা যায়, কোনো একটি পূর্ণসংখ্যা নির্দিষ্ট করে যদি এমনভাবে সংজ্ঞায়িত করা হয় যা এর দ্বিপদী সহগসমূহ নির্দেশ করে এবং হয়, আর , দ্বারা বিভাজ্য হয়। তাহলে
যেহেতু শর্ত পূরণকারী দ্বিপদী সহগের সংখ্যা , তাই এটি নির্দেশ করে দ্বারা বিভাজ্য দ্বিপদী সহগ প্রাপ্তির পরিমাণ তথা দ্বিপদী সহগ ঘনত্ব যার মান দাঁড়ায় ১।
দ্বিপদী সহগসমূহের বিভাজ্যতার সাথে ধারাবাহিক পূর্ণসংখ্যার লসাগুর সাথে সম্পর্ক রয়েছে। উদাহরণস্বরূপঃ[৬]
, দ্বারা বিভাজ্য।
, এর গুণিতক।
এছাড়াও কোনো একটি পূর্ণসংখ্যা একটি মৌলিক সংখ্যা হবে যদি ও কেবল যদি সকল মধ্যবর্তী দ্বিপদী সহগ
দ্বারা বিভাজ্য হয়।
সীমাস্থ এবং অসীমতট সূত্র
এর জন্য নিম্নোক্ত সীমা শর্ত পূরণকারী সকল এর মানের ক্ষেত্রে প্রযোজ্যঃ
প্রথম অসমতাটি আসে নিচের সম্পর্ক্টি হতে,
কেননা এক্ষেত্রে গুণফলের প্রতিটি যুক্ত পদ । একই যুক্তি দিয়ে দেখানো যায়,
আর সর্বশেষ অসমতাটি পাওয়া যায় কে এর জন্য টেইলর সিরিজ দ্বারা গুণ করার মাধ্যমে বিভাজ্যতার বৈশিষ্ট্য থেকে বলা যায়,
যেহেতু স্টার্লিং এর সূত্রের অসমতা ফ্যাক্টরিয়ালকেও সীমাস্থ করে থাকে, তাই উপরের অসীমতটের অনুমিত মানকে সামান্য পরিবর্তন করলে যথাযথ সীমাস্থ মান পাওয়া যায়।
নির্দিষ্টভাবে, যখন যথেচ্ছভাবে বড় হয়ঃ
এবং
এবং সাধারণভাবে, এবং এর জন্য,
, অপেক্ষা যথেষ্ট বড়
যখন যথেষ্ট বড় এবং যথেষ্ট ছোট, তখন,
যা হতে পাওয়া যায় স্টার্লিং এর সূত্রের সদৃশ রূপঃ
আরো যথাযথ মান পাওয়ার জন্য কে যোগজ দ্বারা অনুমিতভাবে প্রকাশ করা যায়,
যদি বড় এবং , এর সাথে সরলরৈখিকভাবে সম্পর্কিত হয়, তবে দ্বিপদী সহগ এর বিভিন্ন যথাযথ অসীমতট মান পাওয়া যায়। উদাহরণস্বরূপ, যদি , তাহলে[৭]
যেখানে,
দ্বিপদী সহগসমূহের সমষ্টি
দ্বিপদী উপপাদ্য ব্যবহার করে দ্বিপদী সহগসমূহের সমষ্টির সাধারণ ও আসন্ন ঊর্ধ্ব সীমা পাওয়া যায়ঃ
এবং উভয়ই ১ অপেক্ষা যথেষ্ট বড় হলে স্টার্লিং এর আসন্নমান হতে নিম্নের অনুমিত আসীমতট পাওয়া যায়ঃ
যেখানে, হলো এর দ্বৈত এন্ট্রপি। আরো যথাযথভাবে, সকল পূর্ণসংখ্যা এর জন্য ও হলে, প্রথম টি দ্বিপদী সহগের সমষ্টি নিম্নরূপে মোটামুটিভাবে গণনা করা যায়ঃ[৮]
প্রথম ক্রমের স্টার্লিং সংখ্যা ব্যবহার করে যেকোনো ইচ্ছামূলক বিন্দু এ ধারার বিস্তৃতিতে পাওয়া যায়,
এর জন্য দ্বিপদী সহগ
বাস্তব সংখ্যা ও পূর্ণসংখ্যার জন্য দ্বিপদী সহগের সংজ্ঞা সম্প্রসারিত করা যায়।
বিশেষ করে নিম্নের অভেদটি যেকোনো অঋণাত্মক পূর্ণসংখ্যার জন্য প্রযোজ্যঃ
এটি পাওয়া যায় নিউটনের দ্বিপদী ধারা অনুসারে কে সম্প্রসারণ করার মাধ্যমেঃ
দ্বিপদী সহগের গুণনের জন্য অভেদক
দ্বিপদী সহগসমূহের গুণফলকে দ্বিপদী সহগের রৈখিক সমাবেশ হিসেবে প্রকাশ করা যায়ঃ
যেখানে সংযোগ সহগগুলো হলো যৈগিক পদের সহগসমূহ।
আংশিক ভগ্নাংশে ভাঙন
দ্বিপদী সহগের পূরকের আংশিক ভগ্নাংশে ভাঙন নিচের রাশি দ্বারা প্রকাশিত,
নিউটনের দ্বিপদী ধারা
নিউটনের দ্বিপদী ধারা হলো অসীম পদ পর্যন্ত দ্বিপদী উপপাদ্যের সরলীকরণঃ
।
এই অভেদটি পাওয়া যায় উভয় পাশ অন্তরক সমীকরণ কে সিদ্ধ করে তা দেখানোর মাধ্যমে।
এই ধারার অভিসৃতির ব্যাসার্ধ ১। এর একটি বিকল্প রূপ হলোঃ
যেখানে নিচের অভেদটি প্রয়োগ করা হয়েছে,
যৌগিক সেটের দ্বিপদী সহগ
দ্বিপদী সহগ দ্বারা কোনো একটি সেটের নির্ধারিত সংখ্যক উপাদান নিয়ে উপসেট গণনা করা যায়। এর সাথে সংশ্লিষ্ট গুচ্ছ-বিন্যাসতাত্ত্বিক সমস্যা হলো যেকোনো সেট হতে নির্ধারিত সংখ্যক উপাদান নিয়ে যৌগিক সেট গণনা তথা কোনো সেট হতে নির্দিষ্ট সংখ্যক উপাদান বাছাই করার উপায় এই শর্তে যে একই উপাদান একাধিকবার বাছাই করা যাবে। এর মাধ্যমে প্রাপ্ত সংখ্যাগুলোকে বলা হয় যৌগিক সেটের সহগ;[৯] সংখ্যক উপাদানের একটি সেট হতে সংখ্যক উপাদান নিয়ে "যৌগিক বাছাই" এর উপায়কে প্রকাশ করা হয় দ্বারা।
যৌগিক সেটের সহগসমূহকে দ্বিপদী সহগ দ্বারাও প্রকাশ করা যেতে পারে নিম্নোক্ত নিয়ম ব্যবহার করে
।
এই অভেদের একটি সম্ভাব্য বিকল্প বৈশিষ্ট্য দেয়া যেতে পারে এভাবেঃ নিম্নগামী ফ্যাক্টরিয়াল প্রকাশ করা যায় এভাবে,
,
এবং সংশ্লিষ্ট ঊর্ধ্বগামী ফ্যাক্টরিয়াল প্রকাশ করা যায় এভাবে,
উদাহরণস্বরূপ,
তবে দ্বিপদী সহগকে এভাবে উল্লেখ করা যেতে পারে,
,
যখন সংশ্লিষ্ট যৌগিক সহগ সংজ্ঞায়িত নিম্নগামী ফ্যাক্টরিয়াল ঊর্ধ্বগামী ফ্যাক্টরিয়াল দ্বারা প্রতিস্থাপনের মাধ্যমেঃ
ঋণাত্মক পূর্ণসংখ্যার জন্য সাধারণীকরণ
এর যেকোনো মানের জন্য,
বিশেষত, ঋণাত্মক পূর্ণসংখ্যার জন্য গণনাকৃত দ্বিপদী সহগ চিহ্নযুক্ত যৌগিক সেটের সহগ দ্বারা গণনা করা হয়। বিশেষ ক্ষেত্র এর জন্য এটি দাঁড়ায়,
।
দুটি বাস্তব বা জটিল মানের আর্গুমেন্ট
গ্যামা ফাংশন বা বেটা ফাংশন দ্বারা দ্বিপদী সহগ দুটি বাস্তব বা জটিল মানের আর্গুমেন্টের জন্য সাধারণভাবে প্রকাশ করা যায়,
এই সংজ্ঞা হতে থেকে নিম্নের বৈশিষ্ট্যসমূহ পাওয়া যায়ঃ
অধিকন্তু,
q ধারায় সাধারণীকরণ
দ্বিপদী সহগের q-analog সাধারণীকরণ বিদ্যমান যা গাউসিয়ান দ্বিপদী সহগ নামে পরিচিত।
অসীম কার্ডিনালের জন্য সাধারণীকরণ
দ্বিপদী সহগের সংজ্ঞা অসীম কার্ডিনালের জন্য সাধারণীকরণ করা যায় এভাবেঃ
চিহ্নটি হাতে লিখার জন্য সুবিধাজনক হলেও টাইপরাইটার এবং কম্পিউটার প্রান্তের জন্য তা সমস্যাদায়ক। অনেক প্রোগ্রামিং ভাষাই দ্বিপদী সহগ গণনার জন্য কোনো প্রমাণ সাবরুটিন প্রদান করে না। তবে 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.।