গণিতশাস্ত্রে দ্বিপদী সহগ (ইংরেজিঃ Binomial coefficient) বলতে সেসব ধনাত্মক পূর্ণসংখ্যা নির্দেশ করে যেসব সংখ্যা দ্বিপদী উপপাদ্যে সহগ হিসেবে বিদ্যমান। সাধারণভাবে দ্বিপদী সহগকে এক জোড়া পূর্ণসংখ্যা দ্বারা সূচিত করা হয়, যেখানে
n
≥
k
≥
0
{\displaystyle n\geq k\geq 0}
এবং প্রকাশ করা হয়
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
দ্বারা । এটি হলো দ্বিপদী ঘাত
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
এর বিস্তৃতিতে
x
k
{\displaystyle x^{k}}
এর সহগ, এবং এটি নিম্নোক্ত সূত্র দ্বারা সংজ্ঞায়িতঃ
দ্বিপদী সহগসমূহকে প্যাসকেলের ত্রিভুজ অনুযায়ী সাজানো যায় যেখানে প্রতিটি ভুক্তি তার ঠিক উপরস্থ দুটি পদের যোগফল
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}}
উদাহরণস্বরূপ,
(
1
+
x
)
{\displaystyle (1+x)}
এর পঞ্চম ঘাতের বিস্তৃতিঃ
(
1
+
x
)
5
=
(
5
0
)
x
0
+
(
5
1
)
x
1
+
(
5
2
)
x
2
+
(
5
3
)
x
3
+
(
5
4
)
x
4
+
(
5
5
)
x
5
{\displaystyle (1+x)^{5}={\binom {5}{0}}x^{0}+{\binom {5}{1}}x^{1}+{\binom {5}{2}}x^{2}+{\binom {5}{3}}x^{3}+{\binom {5}{4}}x^{4}+{\binom {5}{5}}x^{5}}
=
1
+
5
x
+
10
x
2
+
10
x
3
+
5
x
4
+
x
5
{\displaystyle =1+5x+10x^{2}+10x^{3}+5x^{4}+x^{5}}
,
৪র্থ ঘাত পর্যন্ত দ্বিপদী বিস্তৃতির visualization।
এবং
x
2
{\displaystyle x^{2}}
পদটির দ্বিপদী সহগ
(
5
2
)
=
5
!
2
!
3
!
=
10
{\displaystyle {\binom {5}{2}}={\frac {5!}{2!3!}}=10}
।
(
n
0
)
,
(
n
1
)
,
(
n
2
)
,
.
.
.
,
(
n
n
)
{\displaystyle {\binom {n}{0}},{\binom {n}{1}},{\binom {n}{2}},...,{\binom {n}{n}}}
কে
n
=
0
,
1
,
2
,
.
.
.
{\displaystyle n=0,1,2,...}
মানসমূহের জন্য পর পর সারি অনুযায়ী সাজানো হলে একটি ত্রিভুজ সদৃশ পুনরাবৃত্তিমূলক সম্পর্ক পাওয়া যায় যাকে প্যাসকেলের ত্রিভুজ বলা হয়। এই সম্পর্কটি হলোঃ
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
{\displaystyle {\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}}
দ্বিপদী সহগসমূহ গণিতশাস্ত্রের অনেক শাখায় আবির্ভূত হয়, বিশেষত গুচ্ছ-বিন্যাসতত্ত্বে (combinatorics )।
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
প্রতীকটিকে মূলত পড়া হয় "
n
{\displaystyle n}
choose
k
{\displaystyle k}
" কেননা,
n
{\displaystyle n}
সংখ্যক উপাদান বিশিষ্ট কোনো একটি নির্দিষ্ট সেট থেকে
k
{\displaystyle k}
সংখ্যক অনন্য উপাদান নিয়ে মোট উপসেট তৈরী করার উপায় সংখ্যা হলো
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
টি। উদাহরণস্বরূপ,
S
=
{
1
,
2
,
3
,
4
,
5
}
{\displaystyle S=\{1,2,3,4,5\}}
সেটটি হতে
2
{\displaystyle 2}
টি অনন্য উপাদান নিয়ে মোট উপসেট তৈরী করা যায়
(
5
2
)
=
10
{\displaystyle {\tbinom {5}{2}}=10}
টি, যেগুলো হলোঃ
{
1
,
2
}
,
{
1
,
3
}
,
{
1
,
4
}
,
{
1
,
5
}
,
{
2
,
3
}
,
{
2
,
4
}
,
{
2
,
5
}
,
{
3
,
4
}
,
{
3
,
5
}
,
{
4
,
5
}
{\displaystyle \{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}}
।
যেকোনো জটিল সংখ্যা
z
{\displaystyle z}
এবং পূর্ণসংখ্যা
k
≥
0
{\displaystyle k\geq 0}
এর জন্য দ্বিপদী সহগকে সাধারণভাবে
(
z
k
)
{\displaystyle {\tbinom {z}{k}}}
আকারে প্রকাশ করা যায় এবং জটিল সংখ্যার অনেক বৈশিষ্ট্যই এভাবে আরো সাধারণ রূপে প্রকাশিত হয়।
ইতিহাস এবং চিহ্নলিপি
সম্পাদনা
১৮২৬ খ্রিস্টাব্দে আন্দ্রিয়াস ভন এটিইংসহাউসেন সর্বপ্রথম
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
চিহ্নলিপিটি ব্যবহার করেন[১] , যদিও এই সংখ্যাসমূহের বিষয়ে কয়েক শতাব্দী আগ হতেই জানা ছিলো। দ্বিপদী সহগের বিষয়ে সর্বপ্রথম বিস্তারিত আলোচনার প্রমাণ মেলে প্রাচীন সংস্কৃত ভাষায় রচিত পিঙ্গলার চন্দ্রসাস্ত্র(Chandaḥśāstra) গ্রন্থে হালায়ুধার(Halayudha) নোট হতে। ১১৫০ খ্রিস্টাব্দের দিকে ভারতীয় গণিতবিদ দ্বিতীয় ভাস্কর তার লীলাবতী নামক গ্রন্থে দ্বিপদী সহগের বিষয়ে ব্যাখ্যা প্রদান করেন[২] ।
এছাড়াও ব্যবহৃত বিকল্প চিহ্নলিপিগুলো হলো
C
(
n
,
k
)
,
n
C
k
,
n
C
k
,
C
n
k
,
{\displaystyle C(n,k),{}_{n}\!\mathbb {C} _{k},nC_{k},{}\!\mathbb {C} _{n}^{k},}
এবং
C
n
,
k
{\displaystyle C_{n,k}}
যেগুলোর প্রতিটিতেই
C
{\displaystyle C}
নির্দেশ করে সমাবেশ বা বাছাই। অনেক ক্যাল্কুলেটরে
C
{\displaystyle C}
চিহ্নলিপিটি ব্যবহার করা হয় কিছুটা ভিন্নভাবে যাতে তা একটি একক-লাইন বিশিষ্ট পর্দায় প্রকাশযোগ্য হয়।
সংজ্ঞা এবং ব্যাখ্যা
সম্পাদনা
দ্বিপদী সহগের মান গণনা
সম্পাদনা
দ্বিপদী সহগ
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
এর মান দ্বিপদী ঘাতের বিস্তৃতি বা
k
{\displaystyle k}
সংখ্যক সমাবেশ গণনা ব্যতীতও অনেক উপায়ে বের করা যায়।
পুনরাবৃত্তি সূত্র
সম্পাদনা
দ্বিপদী সহগের মান গণনার একটি পদ্ধতি হলো পুনরাবৃত্তি সূত্র যা সম্পূর্ণ যোগাত্মক
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
f
o
r
a
l
l
i
n
t
e
g
e
r
s
n
,
k
:
1
≤
k
≤
n
−
1
,
{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}\ for\ all\ integers\ n,k:1\leq k\leq n-1,}
যেখানে সীমাস্থ মান,
(
n
0
)
=
(
n
n
)
=
1
f
o
r
a
l
l
i
n
e
t
g
e
r
s
n
≥
0
,
{\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1\ for\ all\ inetgers\ n\geq 0,}
সূত্রটির ব্যাখ্যা দেয়া যায় এইভাবেঃ ধরা যাক একটি সেট
{
1
,
2
,
3
,
.
.
.
,
n
}
{\displaystyle \{1,2,3,...,n\}}
। এ সেট হতে আলদা আলদাভাবে (ক)
k
{\displaystyle k}
সংখ্যক উপাদান নিয়ে গ্রূপ করা হলো যার প্রতিটিতে একটি সাধারণ উপাদান, ধরা যাক,
i
{\displaystyle i}
বিদ্যমান (যেহেতু,
i
{\displaystyle i}
ইতিমধ্যে ঐ গ্রূপের একটি স্থান দখল করেছে, তাই অবশিষ্ট
n
−
1
{\displaystyle n-1}
সংখ্যক উপাদান হতে
k
−
1
{\displaystyle k-1}
সংখ্যক উপাদান বাছাই করতে হবে) এবং (খ)
k
{\displaystyle k}
সংখ্যক উপাদান নিয়ে সম্ভাব্য সকল গ্রূপ যাতে ঐ
i
{\displaystyle i}
অন্তর্ভুক্ত না থাকে, (অর্থাৎ
n
−
1
{\displaystyle n-1}
সংখ্যক উপাদান হতে
k
{\displaystyle k}
সংখ্যক উপাদান বাছাই করতে হবে) গণনা করলে তার সমষ্টি হলো নির্ণেয় মান।
কোনো একটি নির্দিষ্ট দ্বিপদী সহগের মান গণনার ক্ষেত্রে আরো কার্যকরী নিম্নের সূত্রটি,
(
n
k
)
=
n
k
_
k
!
=
n
(
n
−
1
)
(
n
−
2
)
.
.
.
(
n
−
(
k
−
1
)
)
k
(
k
−
1
)
(
k
−
2
)
.
.
.1
=
∏
i
=
1
k
n
+
1
−
i
i
{\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}}}
এখানে, প্রথম ভগ্নাংশের লব
n
k
_
{\displaystyle n^{\underline {k}}}
কে বলা হয় ক্রমহ্রাসমান ফ্যাক্টরিয়াল । এখানে সূত্রের লব হলো
n
{\displaystyle n}
সংখ্যক উপাদানের একটি সেট হতে
k
{\displaystyle k}
সংখ্যক উপাদান বাছাই এর মোট উপায় সংখ্যা যখন ক্রম বিবেচনাধীন এবং হর হলো অনন্য উপায় সংখ্যা ঐ একই
k
{\displaystyle k}
সংখ্যক সমাবেশের জন্য যখন ক্রম অবিবেচনাধীন।
দ্বিপদী সহগের
n
{\displaystyle n}
ও
n
−
k
{\displaystyle n-k}
এর সাপেক্ষে প্রতিসমতা ধর্মের কারণে এসব গণনা আরো সহজে সম্পন্ন করা যায়।
ফ্যাক্টোরিয়াল সূত্র
সম্পাদনা
যদিও গণনার দিক দিয়ে এটি সময়সাপেক্ষ, এই সূত্রটি প্রমাণ ও প্রতিপাদনের ক্ষেত্রে বহূল ব্যবহ্রত,
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
f
o
r
0
≤
k
≤
n
,
{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}\ for\ 0\leq k\leq n,}
এখানে
n
!
{\displaystyle n!}
নির্দেশ করে
n
{\displaystyle n}
এর ফ্যাক্টোরিয়াল। এই সুত্রটি পাওয়া যায় গুণক সূত্রের লব ও হর উভয়কে
(
n
−
k
)
!
{\displaystyle (n-k)!}
দ্বারা গুণ করার মাধ্যমে যার ফলে লব ও হরে অনেকগুলো সাধারণ উৎপাদক তৈরী হয়। এই সূত্র হতে প্রতিসমতার ধর্ম খুব সহজেই বোধগম্য গুণক সুত্রের তুলনায়,
(
n
k
)
=
(
n
n
−
k
)
f
o
r
0
≤
k
≤
n
,
{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}\ for\ 0\leq k\leq n,}
এর থেকে ক্রমহ্রাসমান ফ্যাক্টরিয়াল এর ধারণা ব্যবহার করে আরো কার্যকরীভাবে দ্বিপদী সহগের মান গণনা করা যায়,
(
n
k
)
=
{
n
k
_
/
k
!
,
if
k
≤
n
2
n
n
−
k
_
/
(
n
−
k
)
!
,
if
k
>
n
2
{\displaystyle {\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!,&{\text{if }}k\leq {\tfrac {n}{2}}\\n^{\underline {n-k}}/(n-k)!,&{\text{if }}k>{\tfrac {n}{2}}\end{cases}}}
প্যাস্কেলের ত্রিভূজ
সম্পাদনা
প্যাস্কেলের সূত্র হলো একটি গুরুত্বপূর্ণ পুনরাবৃত্তিক সম্পর্ক
(
n
k
)
+
(
n
k
+
1
)
=
(
n
+
1
k
+
1
)
{\displaystyle {\binom {n}{k}}+{\binom {n}{k+1}}={\binom {n+1}{k+1}}}
প্যাস্কেলের ত্রিভূজের ০-১৬ পর্যন্ত সারি
যা গাণিতিক আরোহ বিধি ব্যবহারের মাধ্যমে প্রমাণ করা যায়।
প্যাস্কেলের সূত্র হতে পাওয়া যায় প্যাস্কেলের ত্রিভূজঃ
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
সারি নম্বর
n
{\displaystyle n}
এ বিদ্যমান সংখ্যাগুলো হলো
k
=
0
,
1
,
2
,
.
.
.
,
n
{\displaystyle k=0,1,2,...,n}
এর জন্য
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
এর মান। এটি তৈরী করা হয়েছে প্রথমে সর্ববহিঃস্থ অবস্থানগুলো 1 দ্বারা পূরণের মাধ্যমে। এরপর ভিতরের প্রতিটি অবস্থান পূরণ করা হয়েছে তার ঠিক উপরের দুটি পদের সমষ্টি দ্বারা। এই পদ্ধতির মাধ্যমে গুণ-ভাগ ব্যতীতই দ্রুততার সাথে দ্বিপদী সহগ গণনা করা যায়। উদাহরণস্বরূপ, ৫ম সারি হতে বলা যায়
(
x
+
y
)
5
=
1
_
x
5
+
5
_
x
4
y
+
10
_
x
3
y
2
+
10
_
x
2
y
3
+
5
_
x
y
4
+
1
_
y
5
.
{\displaystyle (x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.}
গুচ্ছ-বিন্যাসতত্ত্ব ও পরিসংখ্যান
সম্পাদনা
বহুপদী হিসেবে দ্বিপদী সহগ
সম্পাদনা
দ্বিপদী সহগযুক্ত কিছু অভেদ
সম্পাদনা
যদি
k
{\displaystyle k}
একটি ধণাত্মক পূর্ণসংখ্যা এবং
n
{\displaystyle n}
ইচ্ছামূলক সংখ্যা হয়, তবে
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
{\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}
এবং,
(
n
−
1
k
)
−
(
n
−
1
k
−
1
)
=
n
−
2
k
n
(
n
k
)
{\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}}
এছাড়া এটিও কার্যকরী হতে পারেঃ
(
n
h
)
(
n
−
h
k
)
=
(
n
k
)
(
n
−
k
h
)
{\displaystyle {\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}}
কোনো একটি নির্দিষ্ট
n
{\displaystyle n}
এর জন্য নিম্নোক্ত পুনরাবৃত্ততা পাওয়া যায়ঃ
(
n
k
)
=
n
+
1
−
k
k
(
n
k
−
1
)
{\displaystyle {\binom {n}{k}}={\frac {n+1-k}{k}}{\binom {n}{k-1}}}
দ্বিপদী সহগসমূহের সমষ্টি
সম্পাদনা
∑
k
=
0
n
(
n
k
)
=
2
n
{\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}}
এই সূত্র প্রকাশ করে যে প্যাসকেলের ত্রিভুজের
n
{\displaystyle n}
তম সারির পদসমূহের যোগফল সর্বদা
2
n
{\displaystyle 2^{n}}
। দ্বিপদী উপপাদ্যে
x
=
y
=
1
{\displaystyle x=y=1}
ধরা হলে এটি পাওয়া যায়।
একইভাবে, পূর্ববর্তী রাশিকে
x
{\displaystyle x}
এর সাপেক্ষে অন্তরীকরণ করলে পাওয়া যায় নিম্নের সূত্রঃ
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
{\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}}
এবং একে পুনরায় অন্তরীকরণ করে পাওয়া যায়ঃ
∑
k
=
0
n
k
2
(
n
k
)
=
(
n
+
n
2
)
2
n
−
2
{\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}
জটিল সংখ্যা
m
,
n
{\displaystyle m,n}
এবং অঋণাত্মক পূর্ণসংখ্যা
k
{\displaystyle k}
এর জন্য প্রযোজ্য চিউ-ভ্যানডারমন্ড অভেদ থেকে পাওয়া যায়,
∑
j
=
0
k
(
m
j
)
(
n
−
m
k
−
j
)
=
(
n
k
)
{\displaystyle \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}}
বিশেষ ক্ষেত্র,
n
=
2
m
,
k
=
m
{\displaystyle n=2m,k=m}
এর জন্য এটি দাঁড়ায়,
∑
j
=
0
m
(
m
j
)
2
=
(
2
m
m
)
{\displaystyle \sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}}}
এখানে, ডানপাশের পদটি হলো কেন্দ্রীয় দ্বিপদী সহগ ।
চিউ-ভ্যানডারমন্ড অভেদের অপর একটি রূপ হলো,
∑
m
=
0
n
(
m
j
)
=
(
n
−
m
k
−
j
)
=
(
n
+
1
k
+
1
)
{\displaystyle \sum _{m=0}^{n}{\binom {m}{j}}={\binom {n-m}{k-j}}={\binom {n+1}{k+1}}}
যেখানে,
0
≤
j
≤
k
≤
n
{\displaystyle 0\leq j\leq k\leq n\ }
এবং
j
,
k
,
n
∈
N
{\displaystyle j,k,n\in N}
।
এক্ষত্রে,
j
=
m
{\displaystyle j=m}
হলে পাওয়া যায় হকি-স্টিক অভেদ ,
(
n
m
=
k
)
=
(
n
+
1
k
+
1
)
{\displaystyle {\binom {n}{m=k}}={\binom {n+1}{k+1}}}
এবং এর অনুরূপ,
∑
r
=
0
m
(
n
+
r
r
)
=
(
n
+
m
−
1
m
)
{\displaystyle \sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m-1}{m}}}
F
(
n
)
{\displaystyle F(n)}
যদি
n
{\displaystyle n}
তম ফিবোনাচি সংখ্যা হয়, তবে,
∑
k
=
0
⌊
n
/
2
⌋
(
n
−
k
k
)
=
F
(
n
+
1
)
{\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1)}
বহুখন্ডের সমষ্টি
সম্পাদনা
পূর্ণসংখ্যা
s
,
t
{\displaystyle s,t}
যেখানে
0
≤
t
≤
s
{\displaystyle 0\leq t\leq s}
এর জন্য, বহুখন্ডীয় ধারা হতে দ্বিপদী সহগের সমষ্টির নিম্নোক্ত অভেদটি পাওয়া যায়,
(
n
t
)
+
(
n
t
+
s
)
+
(
n
t
+
2
s
)
+
.
.
.
=
1
s
∑
j
=
0
s
−
1
(
2
cos
π
j
s
)
n
cos
π
(
n
−
2
t
)
j
s
{\displaystyle {\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+...={\frac {1}{s}}\sum _{j=0}^{s-1}{\biggl (}2\cos {\frac {\pi j}{s}}{\biggr )}^{n}\cos {\frac {\pi (n-2t)j}{s}}}
s
{\displaystyle s}
এর ছোট মানের জন্য এসব ধারার চমৎকার রুপ দেখা যায়; উদাহরণস্বরূপ[৩]
(
n
0
)
+
(
n
3
)
+
(
n
6
)
+
.
.
.
=
1
3
(
2
n
+
2
cos
n
π
3
)
{\displaystyle {\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+...={\frac {1}{3}}{\biggl (}2^{n}+2\cos {\frac {n\pi }{3}}{\biggr )}}
(
n
1
)
+
(
n
4
)
+
(
n
7
)
+
.
.
.
=
1
3
(
2
n
+
2
cos
(
n
−
2
)
π
3
)
{\displaystyle {\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+...={\frac {1}{3}}{\biggl (}2^{n}+2\cos {\frac {(n-2)\pi }{3}}{\biggr )}}
(
n
2
)
+
(
n
5
)
+
(
n
8
)
+
.
.
.
=
1
3
(
2
n
+
2
cos
(
n
−
2
)
π
3
)
{\displaystyle {\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+...={\frac {1}{3}}{\biggl (}2^{n}+2\cos {\frac {(n-2)\pi }{3}}{\biggr )}}
(
n
0
)
+
(
n
4
)
+
(
n
8
)
+
.
.
.
=
1
2
(
2
n
−
1
+
2
n
2
cos
n
π
4
)
{\displaystyle {\binom {n}{0}}+{\binom {n}{4}}+{\binom {n}{8}}+...={\frac {1}{2}}{\biggl (}2^{n-1}+2^{\tfrac {n}{2}}\cos {\frac {n\pi }{4}}{\biggr )}}
(
n
1
)
+
(
n
5
)
+
(
n
9
)
+
.
.
.
=
1
2
(
2
n
−
1
+
2
n
2
sin
n
π
4
)
{\displaystyle {\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+...={\frac {1}{2}}{\biggl (}2^{n-1}+2^{\tfrac {n}{2}}\sin {\frac {n\pi }{4}}{\biggr )}}
(
n
2
)
+
(
n
6
)
+
(
n
10
)
+
.
.
.
=
1
2
(
2
n
−
1
−
2
n
2
cos
n
π
4
)
{\displaystyle {\binom {n}{2}}+{\binom {n}{6}}+{\binom {n}{10}}+...={\frac {1}{2}}{\biggl (}2^{n-1}-2^{\tfrac {n}{2}}\cos {\frac {n\pi }{4}}{\biggr )}}
(
n
3
)
+
(
n
7
)
+
(
n
11
)
+
.
.
.
=
1
2
(
2
n
−
1
−
2
n
2
sin
n
π
4
)
{\displaystyle {\binom {n}{3}}+{\binom {n}{7}}+{\binom {n}{11}}+...={\frac {1}{2}}{\biggl (}2^{n-1}-2^{\tfrac {n}{2}}\sin {\frac {n\pi }{4}}{\biggr )}}
যদিও দ্বিপদী সহগের আংশিক সমষ্টির কোনো নির্দিষ্ট সূত্র নেই,[৪] প্যাস্কেলের অভেদক এবং গাণিতিক আরোহ পদ্ধতি ব্যবহার করে দেখানো যায় যে,
k
=
0
,
1
,
2
,
.
.
.
n
−
1
,
{\displaystyle k=0,1,2,...n-1,}
এর জন্য
∑
j
=
0
k
(
−
1
)
j
(
n
j
)
=
(
−
1
)
k
(
n
−
1
k
)
,
{\displaystyle \sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},}
এবং বিশেষ ক্ষেত্রে,[৫]
∑
j
=
0
n
(
−
1
)
j
(
n
j
)
=
0
{\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0}
যখন
n
>
0
{\displaystyle n>0}
।
ডিক্সনের অভেদকটি হলো,
∑
k
=
−
a
a
(
−
1
)
k
(
2
a
k
+
a
)
3
=
(
3
a
)
!
(
a
!
)
3
{\displaystyle \sum _{k=-a}^{a}(-1)^{k}{\binom {2a}{k+a}}^{3}={\frac {(3a)!}{{(a!)}^{3}}}}
অথবা, আরো সাধারণরূপে,
∑
k
=
−
a
a
(
−
1
)
k
(
a
+
b
a
+
k
)
(
b
+
c
b
+
k
)
(
c
+
a
c
+
k
)
=
(
a
+
b
+
c
)
!
a
!
b
!
c
!
,
{\displaystyle \sum _{k=-a}^{a}(-1)^{k}{\binom {a+b}{a+k}}{\binom {b+c}{b+k}}{\binom {c+a}{c+k}}={\frac {(a+b+c)!}{a!b!c!}},}
যেখানে
a
,
b
,
c
∈
N
{\displaystyle a,b,c\in N}
।
অবিচ্ছিন্ন অভেদক
সম্পাদনা
কিছু ত্রিকোণমিতিক যোগজের মানকে দ্বিপদী সহগ দ্বারা প্রকাশ করা যায়ঃ
m
,
n
∈
N
{\displaystyle m,n\in N}
এর জন্য,
∫
−
π
π
cos
(
(
2
m
−
n
)
x
)
cos
n
x
d
x
=
π
2
n
−
1
(
n
m
)
{\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}x\operatorname {d} \!x={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}}
∫
−
π
π
sin
(
(
2
m
−
n
)
x
)
sin
n
x
d
x
=
{
(
−
1
)
m
+
(
n
+
1
)
/
2
π
2
n
−
1
(
n
m
)
n
odd
0
otherwise
{\displaystyle \int _{-\pi }^{\pi }\sin((2m-n)x)\sin ^{n}x\operatorname {d} \!x={\begin{cases}(-1)^{m+(n+1)/2}{\tfrac {\pi }{2^{n-1}}}{\tbinom {n}{m}}&n{\text{ odd}}\\0&{\text{ otherwise}}\end{cases}}}
∫
−
π
π
cos
(
(
2
m
−
n
)
x
)
sin
n
x
d
x
=
{
(
−
1
)
m
+
(
n
/
2
)
π
2
n
−
1
(
n
m
)
n
even
0
otherwise
{\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}x\operatorname {d} \!x={\begin{cases}(-1)^{m+(n/2)}{\tfrac {\pi }{2^{n-1}}}{\tbinom {n}{m}}&n{\text{ even}}\\0&{\text{ otherwise}}\end{cases}}}
এগুলো প্রমাণ করা যায় অয়লারের সূত্র দ্বারা। এজন্য ত্রিকোণমিতিক ফাংশনকে সূচকীয় জটিল সংখ্যা হিসেবে প্রকাশ করে, দ্বিপদী সহগ অনুযায়ী বিস্তৃত করে, প্রতিটি পদকে আলাদা আলাদাভাবে যোগজীকরণ করতে হয়।
সাধারণ উদ্ভূত ফাংশন
সম্পাদনা
n
{\displaystyle n}
এর কোনো একটি নির্দিষ্ট মানের জন্য
(
n
0
)
,
(
n
1
)
,
(
n
2
)
,
.
.
.
,
{\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},...,}
ধারাটির সাধারণ উদ্ভূত ফাংশন হলো,
∑
k
=
0
∞
(
n
k
)
x
k
=
(
1
+
x
)
n
{\displaystyle \sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}}
k
{\displaystyle k}
এর কোনো একটি নির্দিষ্ট মানের জন্য
(
0
k
)
,
(
1
k
)
,
(
2
k
)
,
.
.
.
,
{\displaystyle {\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},...,}
ধারাটির সাধারণ উদ্ভূত ফাংশন হলো,
∑
n
=
k
∞
(
n
k
)
y
n
=
y
k
(
1
−
y
)
k
+
1
{\displaystyle \sum _{n=k}^{\infty }{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}}
আর
n
,
k
{\displaystyle n,k}
উভয়ই পরিবির্তনশীল হলে দ্বিপদী সহগ হবে,
∑
n
=
0
∞
∑
k
=
0
n
(
n
k
)
x
k
y
n
=
1
1
−
y
−
x
y
{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}}
দ্বিপদী সহগের অপর একটি প্রতিসম সাধারণ উদ্ভূত ফাংশন হলো,
∑
n
=
0
∞
∑
k
=
0
∞
(
n
+
k
k
)
x
k
y
n
=
1
1
−
x
−
y
{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\binom {n+k}{k}}x^{k}y^{n}={\frac {1}{1-x-y}}}
সূচকীয় উদ্ভূত ফাংশন
সম্পাদনা
দ্বিপদী সহগের একটি প্রতিসম দ্বিপরিবির্তনশীল উদ্ভূত ফাংশন হলোঃ
∑
n
=
0
∞
∑
k
=
0
∞
(
n
+
k
k
)
x
k
y
n
(
n
+
k
)
!
=
e
x
+
y
{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\binom {n+k}{k}}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}}
বিভাজ্যতার বৈশিষ্ট্যসমূহ
সম্পাদনা
১৮৫২ খ্রিস্টাব্দে আরনেস্ট কামার প্রমাণ করেন যে, যদি
m
{\displaystyle m}
ও
n
{\displaystyle n}
অঋণাত্মক পূর্ণসংখ্যা হয় এবং
p
{\displaystyle p}
একটি মৌলিক সংখ্যা হয়, তবে
p
{\displaystyle p}
এর সর্বোচ্চ যে ঘাত দ্বারা
(
m
+
n
n
)
{\displaystyle {\tbinom {m+n}{n}}}
বিভাজ্য তা হলো
p
c
{\displaystyle p^{c}}
; যেখানে
c
{\displaystyle c}
হলো
m
{\displaystyle m}
ও
n
{\displaystyle n}
কে
p
{\displaystyle p}
ভিত্তিতে যোগ করার ফলে প্রাপ্ত ক্যারি এর সংখ্যা। একইভাবে
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
এ কোনো একটি মৌলিক সংখ্যা
p
{\displaystyle p}
এর সূচকের মান অঋণাত্মক পূর্ণসংখ্যা
j
{\displaystyle j}
এর সমান যাতে
k
/
p
j
{\displaystyle k/p^{j}}
এর ফ্যাক্টরিয়াল অংশ
n
/
p
j
{\displaystyle n/p^{j}}
এর ফ্যাক্টরিয়াল অংশ অপেক্ষা বড় হয়। এটি হতে সিদ্ধান্তে আসা যায় যে,
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
,
n
/
gcd
(
n
,
k
)
{\displaystyle n/\gcd(n,k)}
দ্বারা বিভাজ্য। এর থেকে পরবর্তীতে পাওয়া যায় সকল ধণাত্মক পূর্ণসংখ্যা
r
,
s
{\displaystyle r,s}
এর জন্য যাতে
s
<
p
r
{\displaystyle s<p^{r}}
;
(
p
r
s
)
{\displaystyle {\tbinom {p^{r}}{s}}}
,
p
{\displaystyle p}
দ্বারা বিভাজ্য। তবে এটি
p
{\displaystyle p}
এর উচ্চ ঘাতের জন্য প্রযোজ্য নয়।
ডেভিড সিংমাস্টার এর ফলাফল হতে দেখা যায়, যেকোনো পূর্ণসংখ্যা প্রায় সকল দ্বিপদী সহগ দ্বারা বিভাজ্য। আরো সুনির্দিষ্টভাবে বলা যায়, কোনো একটি পূর্ণসংখ্যা
d
{\displaystyle d}
নির্দিষ্ট করে
f
(
N
)
{\displaystyle f(N)}
যদি এমনভাবে সংজ্ঞায়িত করা হয় যা
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
এর দ্বিপদী সহগসমূহ নির্দেশ করে এবং
n
<
N
{\displaystyle n<N}
হয়, আর
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
,
d
{\displaystyle d}
দ্বারা বিভাজ্য হয়। তাহলে
lim
n
→
∞
f
(
N
)
N
(
N
+
1
)
/
2
=
1.
{\displaystyle \lim _{n\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.}
যেহেতু
n
<
N
{\displaystyle n<N}
শর্ত পূরণকারী দ্বিপদী সহগের সংখ্যা
N
(
N
+
1
)
/
2
{\displaystyle N(N+1)/2}
, তাই এটি নির্দেশ করে
d
{\displaystyle d}
দ্বারা বিভাজ্য দ্বিপদী সহগ প্রাপ্তির পরিমাণ তথা দ্বিপদী সহগ ঘনত্ব যার মান দাঁড়ায় ১।
দ্বিপদী সহগসমূহের বিভাজ্যতার সাথে ধারাবাহিক পূর্ণসংখ্যার লসাগুর সাথে সম্পর্ক রয়েছে। উদাহরণস্বরূপঃ[৬]
(
n
+
k
k
)
{\displaystyle {\binom {n+k}{k}}}
,
lcm
(
n
,
n
+
1
,
.
.
.
,
n
+
k
)
n
{\displaystyle {\frac {\operatorname {lcm} (n,n+1,...,n+k)}{n}}}
দ্বারা বিভাজ্য।
(
n
+
k
k
)
{\displaystyle {\binom {n+k}{k}}}
,
lcm
(
n
,
n
+
1
,
.
.
.
,
k
)
n
.
lcm
(
(
k
0
)
,
(
k
k
1
)
,
.
.
.
,
(
k
k
)
)
{\displaystyle {\frac {\operatorname {lcm} (n,n+1,...,k)}{n.\operatorname {lcm} ({\tbinom {k}{0}},{\tbinom {k}{k1}},...,{\tbinom {k}{k}})}}}
এর গুণিতক।
এছাড়াও কোনো একটি পূর্ণসংখ্যা
n
≥
2
{\displaystyle n\geq 2}
একটি মৌলিক সংখ্যা হবে যদি ও কেবল যদি সকল মধ্যবর্তী দ্বিপদী সহগ
(
n
1
)
,
(
n
2
)
,
.
.
.
,
(
n
n
−
1
)
{\displaystyle {\binom {n}{1}},{\binom {n}{2}},...,{\binom {n}{n-1}}}
n
{\displaystyle n}
দ্বারা বিভাজ্য হয়।
সীমাস্থ এবং অসীমতট সূত্র
সম্পাদনা
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
এর জন্য নিম্নোক্ত সীমা
1
≤
k
≤
n
{\displaystyle 1\leq k\leq n}
শর্ত পূরণকারী সকল
n
,
k
{\displaystyle n,k}
এর মানের ক্ষেত্রে প্রযোজ্যঃ
n
k
k
k
≤
(
n
k
)
≤
n
k
k
!
<
(
n
.
e
k
)
k
.
{\displaystyle {\frac {n^{k}}{k^{k}}}\leq {\binom {n}{k}}\leq {\frac {n^{k}}{k!}}<{\biggl (}{\frac {n.e}{k}}{\biggr )}^{k}.}
প্রথম অসমতাটি আসে নিচের সম্পর্ক্টি হতে,
(
n
k
)
=
n
k
n
−
1
k
−
1
.
.
.
n
−
(
k
−
1
)
1
{\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\frac {n-1}{k-1}}...{\frac {n-(k-1)}{1}}}
কেননা এক্ষেত্রে গুণফলের প্রতিটি
k
{\displaystyle k}
যুক্ত পদ
≥
n
k
{\displaystyle \geq {\frac {n}{k}}}
। একই যুক্তি দিয়ে দেখানো যায়,
(
n
k
)
≤
n
k
k
!
{\displaystyle {\binom {n}{k}}\leq {\frac {n^{k}}{k!}}}
আর সর্বশেষ অসমতাটি পাওয়া যায়
(
n
k
)
k
{\displaystyle {\biggl (}{\frac {n}{k}}{\biggr )}^{k}}
কে
e
k
{\displaystyle e^{k}}
এর জন্য টেইলর সিরিজ দ্বারা গুণ করার মাধ্যমে বিভাজ্যতার বৈশিষ্ট্য থেকে বলা যায়,
lcm
(
n
−
k
,
.
.
.
,
n
)
(
n
−
k
)
.
lcm
(
(
k
0
)
,
(
k
1
)
.
.
.
,
(
k
k
)
)
≤
(
n
k
)
≤
lcm
(
n
−
k
,
.
.
.
,
n
)
n
−
k
{\displaystyle {\frac {\operatorname {lcm} (n-k,...,n)}{(n-k).\operatorname {lcm} ({\tbinom {k}{0}},{\tbinom {k}{1}}...,{\tbinom {k}{k}})}}\leq {\binom {n}{k}}\leq {\frac {\operatorname {lcm} (n-k,...,n)}{n-k}}}
যা হতে দুটি অসমতাই পাওয়া যায়।[৬]
n
{\displaystyle n}
এবং
k
{\displaystyle k}
উভয়ই বড়
সম্পাদনা
n
,
i
{\displaystyle n,i}
যথেষ্ট বড় হলে স্টার্লিং এর সূত্র হতে নিচের আসন্ন মান পাওয়া যায়,
(
n
i
)
∼
n
2
π
i
(
n
−
i
)
.
n
n
i
3
(
n
−
i
)
n
−
i
{\displaystyle {\binom {n}{i}}\sim {\sqrt {\frac {n}{2\pi i(n-i)}}}.{\frac {n^{n}}{i^{3}(n-i)^{n-i}}}}
যেহেতু স্টার্লিং এর সূত্রের অসমতা ফ্যাক্টরিয়ালকেও সীমাস্থ করে থাকে, তাই উপরের অসীমতটের অনুমিত মানকে সামান্য পরিবর্তন করলে যথাযথ সীমাস্থ মান পাওয়া যায়।
নির্দিষ্টভাবে, যখন
n
{\displaystyle n}
যথেচ্ছভাবে বড় হয়ঃ
(
2
n
n
)
∼
2
2
n
π
n
{\displaystyle {\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}}
এবং
n
(
2
n
n
)
≥
2
2
n
−
1
{\displaystyle {\sqrt {n}}{\binom {2n}{n}}\geq 2^{2n-1}}
এবং সাধারণভাবে,
m
≥
2
{\displaystyle m\geq 2}
এবং
n
≥
1
{\displaystyle n\geq 1}
এর জন্য,
n
(
m
n
n
)
≥
m
m
(
n
−
1
)
+
1
(
m
−
1
)
(
m
−
1
)
(
n
−
1
)
{\displaystyle {\sqrt {n}}{\binom {mn}{n}}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}}
n
{\displaystyle n}
,
k
{\displaystyle k}
অপেক্ষা যথেষ্ট বড়
সম্পাদনা
যখন
n
{\displaystyle n}
যথেষ্ট বড় এবং
k
{\displaystyle k}
যথেষ্ট ছোট, তখন,
(
n
k
)
=
n
(
n
−
1
)
.
.
.
(
n
−
k
+
1
)
k
!
≈
(
n
−
k
/
2
)
k
k
k
e
−
k
2
π
k
=
(
n
/
k
−
0.5
)
k
e
k
)
2
π
k
,
{\displaystyle {\binom {n}{k}}={\frac {n(n-1)...(n-k+1)}{k!}}\approx {\frac {(n-k/2)^{k}}{k^{k}e^{-k}{\sqrt {2\pi k}}}}={\frac {(n/k-0.5)^{k}e^{k})}{\sqrt {2\pi k}}},}
যা হতে পাওয়া যায় স্টার্লিং এর সূত্রের সদৃশ রূপঃ
ln
(
n
k
)
≈
k
ln
(
n
/
k
−
0.5
)
+
k
−
0.5
ln
(
2
π
k
)
.
{\displaystyle \ln {\binom {n}{k}}\approx k\ln(n/k-0.5)+k-0.5\ln(2\pi k).}
আরো যথাযথ মান পাওয়ার জন্য
ln
(
n
(
n
−
1
)
.
.
.
(
n
−
k
+
1
)
)
{\displaystyle \ln(n(n-1)...(n-k+1))}
কে যোগজ দ্বারা অনুমিতভাবে প্রকাশ করা যায়,
ln
(
n
k
)
≈
(
n
+
0.5
)
ln
n
+
0.5
n
−
k
+
0.5
+
k
ln
n
−
k
+
0.5
k
−
0.5
ln
(
2
π
k
)
{\displaystyle \ln {\binom {n}{k}}\approx (n+0.5)\ln {\frac {n+0.5}{n-k+0.5}}+k\ln {\frac {n-k+0.5}{k}}-0.5\ln(2\pi k)}
যদি
n
{\displaystyle n}
বড় এবং
k
{\displaystyle k}
,
n
{\displaystyle n}
এর সাথে সরলরৈখিকভাবে সম্পর্কিত হয়, তবে দ্বিপদী সহগ
(
n
k
)
{\displaystyle {\binom {n}{k}}}
এর বিভিন্ন যথাযথ অসীমতট মান পাওয়া যায়। উদাহরণস্বরূপ, যদি
|
n
/
2
−
k
|
=
o
(
n
2
/
3
)
{\displaystyle \left\vert n/2-k\right\vert =o(n^{2/3})}
, তাহলে[৭]
(
n
k
)
∼
(
n
n
2
)
e
−
d
2
/
(
2
n
)
∼
2
n
1
2
n
π
e
−
d
2
/
(
2
n
)
{\displaystyle {\binom {n}{k}}\sim {\binom {n}{\tfrac {n}{2}}}e^{-d^{2}/(2n)}\sim {\frac {2^{n}}{\sqrt {{\frac {1}{2}}n\pi }}}e^{-d^{2}/(2n)}}
যেখানে,
d
=
n
−
2
k
{\displaystyle d=n-2k}
দ্বিপদী সহগসমূহের সমষ্টি
সম্পাদনা
দ্বিপদী উপপাদ্য ব্যবহার করে দ্বিপদী সহগসমূহের সমষ্টির সাধারণ ও আসন্ন ঊর্ধ্ব সীমা পাওয়া যায়ঃ
∑
i
=
0
k
(
n
i
)
≤
∑
i
=
0
k
n
i
.1
k
−
i
≤
(
1
+
n
)
k
{\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}\leq \sum _{i=0}^{k}n^{i}.1^{k-i}\leq (1+n)^{k}}
k
{\displaystyle k}
এবং
n
−
k
{\displaystyle n-k}
উভয়ই ১ অপেক্ষা যথেষ্ট বড় হলে স্টার্লিং এর আসন্নমান হতে নিম্নের অনুমিত আসীমতট পাওয়া যায়ঃ
log
2
(
n
k
)
∼
n
H
(
k
n
)
=
k
log
2
(
n
k
)
+
(
n
−
k
)
log
2
(
n
n
−
k
)
{\displaystyle \log _{2}{\binom {n}{k}}\sim nH{\biggl (}{\frac {k}{n}}{\biggr )}=k\log _{2}{\biggl (}{\frac {n}{k}}{\biggr )}+(n-k)\log _{2}{\biggl (}{\frac {n}{n-k}}{\biggr )}}
যেখানে,
H
(
ϵ
)
=
−
ϵ
log
2
(
ϵ
)
−
(
1
−
ϵ
)
log
2
(
1
−
ϵ
)
{\displaystyle H(\epsilon )=-\epsilon \log _{2}(\epsilon )-(1-\epsilon )\log _{2}(1-\epsilon )}
হলো
ϵ
{\displaystyle \epsilon }
এর দ্বৈত এন্ট্রপি । আরো যথাযথভাবে, সকল পূর্ণসংখ্যা
n
≥
k
≥
1
{\displaystyle n\geq k\geq 1}
এর জন্য ও
ϵ
≐
k
/
n
≤
1
/
2
{\displaystyle \epsilon \doteq k/n\leq 1/2}
হলে, প্রথম
k
+
1
{\displaystyle k+1}
টি দ্বিপদী সহগের সমষ্টি নিম্নরূপে মোটামুটিভাবে গণনা করা যায়ঃ[৮]
1
8
n
ϵ
(
1
−
ϵ
)
.2
H
(
ϵ
)
.
n
≤
∑
i
=
0
k
(
n
i
)
≤
2
H
(
ϵ
)
.
n
.
{\displaystyle {\frac {1}{\sqrt {8n\epsilon (1-\epsilon )}}}.2^{H(\epsilon ).n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon ).n}.}
সাধারণ দ্বিপদী সহগ
সম্পাদনা
গ্যামা ফাংশনের অসীম গুণনের সূত্র থেকেও দ্বিপদী সহগের রাশিমালা পাওয়া যায়,
(
−
1
)
k
(
z
k
)
=
(
z
−
k
−
1
k
)
=
1
Γ
(
−
z
)
1
(
k
+
1
)
z
+
1
∏
j
=
k
+
1
(
1
+
1
j
)
−
z
−
1
1
−
z
+
1
j
{\displaystyle (-1)^{k}{\binom {z}{k}}={\binom {z-k-1}{k}}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {(1+{\tfrac {1}{j}})^{-z-1}}{1-{\tfrac {z+1}{j}}}}}
যা প্রদান করে অসীমতটের সূত্রসমূহ,
(
z
k
)
≈
(
−
1
)
k
)
Γ
(
−
z
)
k
z
+
1
{\displaystyle {\binom {z}{k}}\approx {\frac {(-1)^{k})}{\Gamma (-z)k^{z+1}}}}
এবং
(
z
+
k
k
)
=
k
z
Γ
(
z
+
1
)
(
1
+
z
(
z
+
1
)
2
k
+
ϑ
(
k
−
2
)
)
{\displaystyle {\binom {z+k}{k}}={\frac {k^{z}}{\Gamma (z+1)}}{\biggl (}1+{\frac {z(z+1)}{2k}}+\vartheta (k^{-2}){\biggr )}}
যখন
k
⟶
∞
{\displaystyle k\longrightarrow \infty }
।
এই অসীমতটের ধর্ম অনুমানের মধ্যেও অন্তর্ভুক্ত
(
z
+
k
k
)
≈
e
z
(
H
k
−
γ
)
Γ
(
z
+
1
)
{\displaystyle {\binom {z+k}{k}}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}
এখানে,
H
k
{\displaystyle H_{k}}
হলো
k
{\displaystyle k}
তম হারমোনিক সংখ্যা এবং
γ
{\displaystyle \gamma }
হলো অয়লার-মাস্কেরোনি ধ্রুবক ।
এছাড়াও কিছু জটিল সংখ্যা
x
{\displaystyle x}
এর জন্য যখন
k
⟶
∞
{\displaystyle k\longrightarrow \infty }
ও
j
/
k
⟶
x
{\displaystyle j/k\longrightarrow x}
হয়, সেক্ষেত্রে অসীমতটের সূত্রটি সত্য হয়,
(
z
+
k
j
)
(
k
j
)
→
(
1
−
j
k
)
−
z
{\displaystyle {\frac {\binom {z+k}{j}}{\binom {k}{j}}}\rightarrow {\biggl (}1-{\frac {j}{k}}{\biggr )}^{-z}}
এবং
(
j
j
−
k
)
(
j
−
z
j
−
k
)
→
(
j
k
)
z
{\displaystyle {\frac {\binom {j}{j-k}}{\binom {j-z}{j-k}}}\rightarrow {\biggl (}{\frac {j}{k}}{\biggr )}^{z}}
।
যৌগিক পদের সাধারণীকরণ
সম্পাদনা
দ্বিপদী সহগকে যৌগিক পদের সহগ হিসেবে সাধারণীকরণ করা যায়, যেখানে যৌগিক পদের সহগ সংজ্ঞায়িত নিম্নোক্ত রূপেঃ
(
n
k
1
,
k
2
,
k
3
,
.
.
.
,
k
r
)
=
n
!
k
1
!
k
2
!
k
3
!
.
.
.
k
r
!
{\displaystyle {\binom {n}{k_{1},k_{2},k_{3},...,k_{r}}}={\frac {n!}{k_{1}!k_{2}!k_{3}!...k_{r}!}}}
যেখানে
∑
i
=
1
r
k
i
=
n
.
{\displaystyle \sum _{i=1}^{r}k_{i}=n.}
উল্লেখ্য, দ্বিপদী সহগসমূহ প্রকাশ করে
(
x
+
y
)
n
{\displaystyle (x+y)^{n}}
এর সহগসমূহ; আর যৌগিক পদের সহগসমূহ প্রকাশ করে
(
x
1
+
x
2
+
x
3
+
.
.
.
+
x
r
)
n
{\displaystyle (x_{1}+x_{2}+x_{3}+...+x_{r})^{n}}
বহুপদীর সহগসমূহ।
এক্ষেত্রে
r
=
2
{\displaystyle r=2}
হলে পাওয়া যায় দ্বিপদী সহগঃ
(
n
k
1
,
k
2
)
=
(
n
k
1
,
n
−
k
1
)
=
(
n
k
1
)
=
(
n
k
2
)
{\displaystyle {\binom {n}{k_{1},k_{2}}}={\binom {n}{k_{1},n-k_{1}}}={\binom {n}{k_{1}}}={\binom {n}{k_{2}}}}
যৌগিক পদের সহগের অনেক ধর্ম দ্বিপদী সহগের ধর্মের মতোই। উদাহরণস্বরূপ, পুনরাবৃত্তি ধর্মঃ
(
n
k
1
,
k
2
,
.
.
.
,
k
r
)
=
(
n
−
1
k
1
−
1
,
k
2
,
.
.
.
,
k
r
)
+
(
n
−
1
k
1
,
k
2
−
1
,
.
.
.
,
k
r
)
+
.
.
.
+
(
n
−
1
k
1
,
k
2
,
.
.
.
,
k
r
−
1
)
{\displaystyle {\binom {n}{k_{1},k_{2},...,k_{r}}}={\binom {n-1}{k_{1}-1,k_{2},...,k_{r}}}+{\binom {n-1}{k_{1},k_{2}-1,...,k_{r}}}+...+{\binom {n-1}{k_{1},k_{2},...,k_{r}-1}}}
এবং প্রতিসমতাঃ
(
n
k
1
−
1
,
k
2
,
.
.
.
,
k
r
)
=
(
n
k
σ
1
,
k
σ
2
,
.
.
.
,
k
σ
r
)
{\displaystyle {\binom {n}{k_{1}-1,k_{2},...,k_{r}}}={\binom {n}{k_{\sigma 1},k_{\sigma 2},...,k_{\sigma r}}}}
যেখানে,
(
σ
i
)
{\displaystyle ({\sigma i})}
হলো
1
,
2
,
3
,
.
.
.
,
r
{\displaystyle 1,2,3,...,r}
এর একটি বিন্যাস ।
প্রথম ক্রমের স্টার্লিং সংখ্যা ব্যবহার করে যেকোনো ইচ্ছামূলক বিন্দু
z
o
{\displaystyle z_{o}}
এ ধারার বিস্তৃতিতে পাওয়া যায়,
(
z
k
)
=
1
k
!
∑
i
=
0
k
z
i
s
k
,
i
=
∑
i
=
0
k
(
z
−
z
0
)
i
∑
i
=
j
k
(
z
0
j
−
i
)
s
k
+
i
−
j
,
i
(
k
+
i
−
j
)
!
{\displaystyle {\binom {z}{k}}={\frac {1}{k!}}\sum _{i=0}^{k}z^{i}s_{k,i}=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{i=j}^{k}{\binom {z_{0}}{j-i}}{\frac {s_{k+i-j,i}}{(k+i-j)!}}}
=
∑
i
=
0
k
(
z
−
z
0
)
i
∑
j
=
i
k
z
0
j
−
i
(
j
i
)
s
k
,
j
k
!
{\displaystyle =\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}{z_{0}}^{j-i}{\binom {j}{i}}{\frac {s_{k,j}}{k!}}}
n
=
1
/
2
{\displaystyle n=1/2}
এর জন্য দ্বিপদী সহগ
সম্পাদনা
n
{\displaystyle n}
বাস্তব সংখ্যা ও
k
{\displaystyle k}
পূর্ণসংখ্যার জন্য দ্বিপদী সহগের সংজ্ঞা সম্প্রসারিত করা যায়।
বিশেষ করে নিম্নের অভেদটি যেকোনো অঋণাত্মক পূর্ণসংখ্যার জন্য প্রযোজ্যঃ
(
1
/
2
k
)
=
(
2
k
k
)
(
−
1
)
k
+
1
2
2
k
(
2
k
−
1
)
.
{\displaystyle {\binom {1/2}{k}}={\binom {2k}{k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.}
এটি পাওয়া যায় নিউটনের দ্বিপদী ধারা অনুসারে
1
+
x
{\displaystyle {\sqrt {1+x}}}
কে সম্প্রসারণ করার মাধ্যমেঃ
1
+
x
=
∑
k
≥
0
(
1
/
2
k
)
x
k
{\displaystyle {\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}}
দ্বিপদী সহগের গুণনের জন্য অভেদক
সম্পাদনা
দ্বিপদী সহগসমূহের গুণফলকে দ্বিপদী সহগের রৈখিক সমাবেশ হিসেবে প্রকাশ করা যায়ঃ
(
z
m
)
(
z
n
)
=
∑
k
=
0
m
(
m
+
n
−
k
k
,
m
−
k
,
n
−
k
)
(
z
m
+
n
−
k
)
{\displaystyle {\binom {z}{m}}{\binom {z}{n}}=\sum _{k=0}^{m}{\binom {m+n-k}{k,m-k,n-k}}{\binom {z}{m+n-k}}}
যেখানে সংযোগ সহগগুলো হলো যৈগিক পদের সহগসমূহ।
আংশিক ভগ্নাংশে ভাঙন
সম্পাদনা
দ্বিপদী সহগের পূরকের আংশিক ভগ্নাংশে ভাঙন নিচের রাশি দ্বারা প্রকাশিত,
1
(
z
n
)
=
∑
i
=
o
n
−
1
(
−
1
)
n
−
1
−
i
(
n
i
)
n
−
i
z
−
i
,
{\displaystyle {\frac {1}{\binom {z}{n}}}=\sum _{i=o}^{n-1}(-1)^{n-1-i}{\binom {n}{i}}{\frac {n-i}{z-i}},}
1
(
z
+
n
n
)
=
∑
i
=
1
n
(
−
1
)
i
−
1
(
n
i
)
i
z
+
i
{\displaystyle {\frac {1}{\binom {z+n}{n}}}=\sum _{i=1}^{n}(-1)^{i-1}{\binom {n}{i}}{\frac {i}{z+i}}}
নিউটনের দ্বিপদী ধারা
সম্পাদনা
নিউটনের দ্বিপদী ধারা হলো অসীম পদ পর্যন্ত দ্বিপদী উপপাদ্যের সরলীকরণঃ
(
1
+
z
)
α
=
∑
n
=
0
∞
(
α
n
)
z
n
=
1
+
(
α
1
)
z
+
(
α
2
)
z
2
+
.
.
.
{\displaystyle (1+z)^{\alpha }=\sum _{n=0}^{\infty }{\binom {\alpha }{n}}z^{n}=1+{\binom {\alpha }{1}}z+{\binom {\alpha }{2}}z^{2}+...}
।
এই অভেদটি পাওয়া যায় উভয় পাশ অন্তরক সমীকরণ
(
1
+
z
)
f
′
(
z
)
=
α
f
(
z
)
{\displaystyle (1+z)f'(z)=\alpha f(z)}
কে সিদ্ধ করে তা দেখানোর মাধ্যমে।
এই ধারার অভিসৃতির ব্যাসার্ধ ১। এর একটি বিকল্প রূপ হলোঃ
1
(
1
−
z
)
α
+
1
=
∑
n
=
0
∞
(
n
+
α
n
)
z
n
{\displaystyle {\frac {1}{(1-z)^{\alpha }+1}}=\sum _{n=0}^{\infty }{\binom {n+\alpha }{n}}z^{n}}
যেখানে নিচের অভেদটি প্রয়োগ করা হয়েছে,
(
n
k
)
=
(
−
1
)
k
(
k
−
n
−
1
k
)
{\displaystyle {\binom {n}{k}}=(-1)^{k}{\binom {k-n-1}{k}}}
যৌগিক সেটের দ্বিপদী সহগ
সম্পাদনা
দ্বিপদী সহগ দ্বারা কোনো একটি সেটের নির্ধারিত সংখ্যক উপাদান নিয়ে উপসেট গণনা করা যায়। এর সাথে সংশ্লিষ্ট গুচ্ছ-বিন্যাসতাত্ত্বিক সমস্যা হলো যেকোনো সেট হতে নির্ধারিত সংখ্যক উপাদান নিয়ে যৌগিক সেট গণনা তথা কোনো সেট হতে নির্দিষ্ট সংখ্যক উপাদান বাছাই করার উপায় এই শর্তে যে একই উপাদান একাধিকবার বাছাই করা যাবে। এর মাধ্যমে প্রাপ্ত সংখ্যাগুলোকে বলা হয় যৌগিক সেটের সহগ;[৯]
n
{\displaystyle n}
সংখ্যক উপাদানের একটি সেট হতে
k
{\displaystyle k}
সংখ্যক উপাদান নিয়ে "যৌগিক বাছাই" এর উপায়কে প্রকাশ করা হয়
(
(
n
k
)
)
{\displaystyle {\biggl (}{\binom {n}{k}}{\biggr )}}
দ্বারা।
যৌগিক সেটের সহগসমূহকে দ্বিপদী সহগ দ্বারাও প্রকাশ করা যেতে পারে নিম্নোক্ত নিয়ম ব্যবহার করে
(
f
k
)
=
(
(
r
k
)
)
=
(
r
+
k
−
1
k
)
{\displaystyle {\binom {f}{k}}={\biggl (}{\binom {r}{k}}{\biggr )}={\binom {r+k-1}{k}}}
।
এই অভেদের একটি সম্ভাব্য বিকল্প বৈশিষ্ট্য দেয়া যেতে পারে এভাবেঃ নিম্নগামী ফ্যাক্টরিয়াল প্রকাশ করা যায় এভাবে,
(
f
)
k
=
f
k
_
=
(
f
−
k
+
1
)
.
.
.
(
f
−
3
)
.
(
f
−
2
)
.
(
f
−
1
)
.
f
{\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)...(f-3).(f-2).(f-1).f}
,
এবং সংশ্লিষ্ট ঊর্ধ্বগামী ফ্যাক্টরিয়াল প্রকাশ করা যায় এভাবে,
r
(
k
)
=
r
k
¯
=
r
.
(
r
+
1
)
.
(
r
+
2
)
.
(
r
+
3
)
.
.
.
(
r
+
k
−
1
)
{\displaystyle r^{(k)}=r^{\overline {k}}=r.(r+1).(r+2).(r+3)...(r+k-1)}
উদাহরণস্বরূপ,
17.18.19.20.21
=
(
21
)
5
=
21
5
_
=
17
5
¯
=
17
(
5
)
.
{\displaystyle 17.18.19.20.21=(21)_{5}=21^{\underline {5}}=17{\overline {5}}=17^{(5)}.}
তবে দ্বিপদী সহগকে এভাবে উল্লেখ করা যেতে পারে,
(
f
k
)
=
(
f
)
k
k
!
=
(
f
−
k
+
1
)
.
.
.
(
f
−
2
)
.
(
f
−
1
)
.
f
1.2.3.4.5...
k
{\displaystyle {\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)...(f-2).(f-1).f}{1.2.3.4.5...k}}}
,
যখন সংশ্লিষ্ট যৌগিক সহগ সংজ্ঞায়িত নিম্নগামী ফ্যাক্টরিয়াল ঊর্ধ্বগামী ফ্যাক্টরিয়াল দ্বারা প্রতিস্থাপনের মাধ্যমেঃ
(
(
r
k
)
)
=
r
(
k
)
k
!
=
r
.
(
r
+
1
)
.
(
r
+
2
)
.
.
.
(
r
+
k
−
1
)
1.2.3.4.5...
k
{\displaystyle {\biggl (}{\binom {r}{k}}{\biggr )}={\frac {r^{(k)}}{k!}}={\frac {r.(r+1).(r+2)...(r+k-1)}{1.2.3.4.5...k}}}
ঋণাত্মক পূর্ণসংখ্যার জন্য সাধারণীকরণ
সম্পাদনা
n
{\displaystyle n}
এর যেকোনো মানের জন্য,
(
−
n
k
)
=
−
n
.
−
(
n
+
1
)
.
−
(
n
+
2
)
.
.
.
−
(
n
+
k
−
2
)
.
−
(
n
+
k
−
1
)
k
!
{\displaystyle {\binom {-n}{k}}={\frac {-n.-(n+1).-(n+2)...-(n+k-2).-(n+k-1)}{k!}}}
=
(
−
1
)
k
n
(
n
+
1
)
(
n
+
2
)
.
.
.
(
n
+
k
−
1
)
k
!
{\displaystyle =(-1)^{k}{\frac {n(n+1)(n+2)...(n+k-1)}{k!}}}
=
(
−
1
)
k
(
n
+
k
−
1
k
)
{\displaystyle =(-1)^{k}{\binom {n+k-1}{k}}}
=
(
−
1
)
k
(
(
n
k
)
)
.
{\displaystyle =(-1)^{k}{\biggl (}{\binom {n}{k}}{\biggr )}.}
বিশেষত, ঋণাত্মক পূর্ণসংখ্যার জন্য গণনাকৃত দ্বিপদী সহগ চিহ্নযুক্ত যৌগিক সেটের সহগ দ্বারা গণনা করা হয়। বিশেষ ক্ষেত্র
n
=
−
1
{\displaystyle n=-1}
এর জন্য এটি দাঁড়ায়,
(
−
1
)
k
=
(
−
1
k
)
=
(
(
−
k
k
)
)
{\displaystyle (-1)^{k}={\binom {-1}{k}}={\biggl (}{\binom {-k}{k}}{\biggr )}}
।
দুটি বাস্তব বা জটিল মানের আর্গুমেন্ট
সম্পাদনা
গ্যামা ফাংশন বা বেটা ফাংশন দ্বারা দ্বিপদী সহগ দুটি বাস্তব বা জটিল মানের আর্গুমেন্টের জন্য সাধারণভাবে প্রকাশ করা যায়,
(
x
y
)
=
Γ
(
x
+
1
)
Γ
(
y
+
1
)
Γ
(
x
−
y
+
1
)
=
1
(
x
+
1
)
B
(
x
−
y
+
1
,
y
+
1
)
.
{\displaystyle {\binom {x}{y}}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (x-y+1,y+1)}}.}
এই সংজ্ঞা হতে
Γ
{\displaystyle \Gamma }
থেকে নিম্নের বৈশিষ্ট্যসমূহ পাওয়া যায়ঃ
(
x
y
)
=
sin
(
y
π
)
sin
(
x
π
)
(
−
y
−
1
−
x
−
1
)
=
sin
(
(
x
−
y
)
π
)
sin
(
x
π
)
(
y
−
x
−
1
y
)
;
{\displaystyle {\binom {x}{y}}={\frac {\sin(y\pi )}{\sin(x\pi )}}{\binom {-y-1}{-x-1}}={\frac {\sin((x-y)\pi )}{\sin(x\pi )}}{\binom {y-x-1}{y}};}
অধিকন্তু,
(
x
y
)
(
y
x
)
=
sin
(
(
x
−
y
)
π
)
(
x
−
y
)
π
.
{\displaystyle {\binom {x}{y}}{\binom {y}{x}}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}.}
q ধারায় সাধারণীকরণ
সম্পাদনা
দ্বিপদী সহগের q-analog সাধারণীকরণ বিদ্যমান যা গাউসিয়ান দ্বিপদী সহগ নামে পরিচিত।
অসীম কার্ডিনালের জন্য সাধারণীকরণ
সম্পাদনা
দ্বিপদী সহগের সংজ্ঞা অসীম কার্ডিনালের জন্য সাধারণীকরণ করা যায় এভাবেঃ
(
α
β
)
=
|
B
⊆
A
:
|
B
|
=
β
|
{\displaystyle {\binom {\alpha }{\beta }}=\left\vert {B\subseteq A:\left\vert B\right\vert }=\beta \right\vert }
যেখানে
A
{\displaystyle A}
হলো একটি সেট যার কার্ডিনালিটি
α
{\displaystyle \alpha }
।
প্রোগ্রামিং ভাষায় দ্বিপদী সহগ
সম্পাদনা
(
n
k
)
{\displaystyle {\binom {n}{k}}}
চিহ্নটি হাতে লিখার জন্য সুবিধাজনক হলেও টাইপরাইটার এবং কম্পিউটার প্রান্তের জন্য তা সমস্যাদায়ক। অনেক প্রোগ্রামিং ভাষাই দ্বিপদী সহগ গণনার জন্য কোনো প্রমাণ সাবরুটিন প্রদান করে না। তবে APL প্রোগ্রামিং ভাষা এবং J প্রোগ্রামিং ভাষা এটি প্রকাশের জন্য বিস্ময় চিহ্ন ব্যবহার করেঃ
k
!
n
{\displaystyle k!n}
।
ফ্যাক্টরিয়াল সূত্রের সরল রূপায়ন দেখা যায়, যেমন নিচের পাইথনের snippet,
from math import factorial
def binomialCoefficient ( n , k ):
return factorial ( n ) // ( factorial ( k ) * factorial ( n - k ))
অনেক ধীরগতিসম্পন্ন এবং বেশ বড় কোনো সংখ্যার ফ্যাক্টরিয়াল গণনার ক্ষেত্রে তা প্রায় অকার্যকর। গুণক সূত্রের সরাসরি প্রয়োগ এক্ষেত্রে ভালো ফলাফল দেয়ঃ
def binomialCoefficient ( n , k ):
if k < 0 or k > n :
return 0
if k == 0 or k == n :
return 1
k = min ( k , n - k ) # take advantage of symmetry
c = 1
for i in range ( k ):
c = c * ( n - i ) / ( i + 1 )
return c
(পাইথনে , range(k)
0
{\displaystyle 0}
হতে
k
−
1
{\displaystyle k-1}
পর্যন্ত তালিকা তৈরী করে)
প্যাস্কেলের সূত্র হতে পুনরাবৃত্তির একটি সংজ্ঞা দেয় যা পাইথনে ব্যবহার করা গেলেও এর কার্যকরিতা কমঃ
def binomialCoefficient ( n , k ):
if k < 0 or k > n :
return 0
if k > n - k : # take advantage of symmetry
k = n - k
if k == 0 or n <= 1 :
return 1
return binomialCoefficient ( n - 1 , k ) + binomialCoefficient ( n - 1 , k - 1 )
উপরে উল্লিখিত উদাহরণ ফাংশন আকারেও লিখা যায়। নিচে স্কিম প্রোগ্রামিং ভাষায় রচিত প্রোগ্রামটি পুনরাবৃত্ত সংজ্ঞা ব্যবহার করে,
(
n
k
+
1
)
=
n
−
1
k
+
1
(
n
k
)
{\displaystyle {\binom {n}{k+1}}={\frac {n-1}{k+1}}{\binom {n}{k}}}
নিচের কোডটিতে এ ধারণা ব্যবহার করা হয়েছে,
( define ( binomial n k )
;; Helper function to compute C(n,k) via forward recursion
( define ( binomial-iter n k i prev )
( if ( >= i k )
prev
( binomial-iter n k ( + i 1 ) ( / ( * ( - n i ) prev ) ( + i 1 )))))
;; Use symmetry property C(n,k)=C(n, n-k)
( if ( < k ( - n k ))
( binomial-iter n k 0 1 )
( binomial-iter n ( - n k ) 0 1 )))
কোনো নির্দিষ্ট দৈর্ঘ্যের পূর্ণসংখ্যা বিশিষ্ট প্রোগ্রামিং ভাষায়
(
n
k
+
1
)
=
[
(
n
−
k
)
(
n
k
)
]
÷
(
k
+
1
)
{\displaystyle {\binom {n}{k+1}}=[(n-k){\tbinom {n}{k}}]\div (k+1)}
গণনার সময়
(
n
−
k
)
{\displaystyle (n-k)}
দ্বারা গুণন যখন ফলাফল পাওয়া সম্ভন সেক্ষেত্রেও ওভারফ্লো হতে পারে। এটি এড়ানো যায় প্রথমে ভাগ প্রক্রিয়ার প্রয়োগ এবং ভাগশেষ ব্যবহার করার মাধ্যমেঃ
(
n
k
+
1
)
=
[
(
n
k
)
÷
(
k
+
1
)
]
(
n
−
k
)
+
[
(
n
k
)
mod
(
k
+
1
)
]
(
n
−
k
)
(
k
+
1
)
{\displaystyle {\binom {n}{k+1}}=[{\tbinom {n}{k}}\div (k+1)](n-k)+{\frac {[{\binom {n}{k}}{\bmod {(}}k+1)](n-k)}{(k+1)}}}
C ভাষায় এর প্রয়োগঃ
#include <limits.h>
unsigned long binomial ( unsigned long n , unsigned long k ) {
unsigned long c = 1 , i ;
if ( k > n - k ) // take advantage of symmetry
k = n - k ;
for ( i = 1 ; i <= k ; i ++ , n -- ) {
if ( c / i > UINT_MAX / n ) // return 0 on overflow
return 0 ;
c = c / i * n + c % i * n / i ; // split c * n / i into (c / i * i + c % i) * n / i
}
return c ;
}
↑ Higham, Nicholas J., 1961- (১৯৯৮)। Handbook of writing for the mathematical sciences (2nd ed সংস্করণ)। Philadelphia: Society for Industrial and Applied Mathematics। আইএসবিএন 0898714206 । ওসিএলসি 38992868 ।
↑ Knuth, Georgia M. (1997-01)। "Informatics Report Problems: What You See is Not What You Wanted" । AAOHN Journal । 45 (1): 48–50। আইএসএসএন 0891-0162 । ডিওআই :10.1177/216507999704500109 ।
↑ Moll, Victor H. (২০১৪-১১-১২)। Special Integrals of Gradshteyn and Ryzhik । Chapman and Hall/CRC। আইএসবিএন 9780429075889 ।
↑ [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. ।
↑ ক খ Farhi, Bakir (2007-8)। "Nontrivial lower bounds for the least common multiple of some finite sequences of integers" । Journal of Number Theory (ইংরেজি ভাষায়)। 125 (2): 393–411। ডিওআই :10.1016/j.jnt.2006.10.017 ।
↑ Spencer, Joel H.,। Asymptopia । Florescu, Laura.। Providence, Rhode Island। আইএসবিএন 9781470409043 । ওসিএলসি 865574788 ।
↑ Flum, Jörg; Grohe, Martin (২০০২)। STACS 2002 । Berlin, Heidelberg: Springer Berlin Heidelberg। পৃষ্ঠা 359–371। আইএসবিএন 9783540432838 ।
↑ Munarini, Emanuele (2011), "Riordan matrices and sums of harmonic numbers", Applicable Analysis and Discrete Mathematics, 5 (2): 176–200, doi:10.2298/AADM110609014M, MR 2867317. ।