ضرایب دوجملهای و شمارش پایه
ضرایب دوجملهای تعداد روشهای انتخاب زیرمجموعهای با اندازه ثابت از یک مجموعه متناهی را شمارش میکنند و به عنوان بلوک سازنده اصلی شمارش ترکیبیاتی عمل میکنند.
Definition
ضریب دوجملهای C(n,k) تعداد زیرمجموعههای k-عضوی از یک مجموعه n-عضوی است که برابر با n!/(k!(n-k)!) میباشد؛ شمارش پایه، کاربرد سیستماتیک قواعد جمع و ضرب در پیکربندیهای متناهی است.
Scope
این مبحث به اصول بنیادی شمارش – قواعد جمع و ضرب – و نقش محوری ضریب دوجملهای C(n,k)، اتحادهای آن (قاعده پاسکال، قضیه دوجملهای، اتحاد وندرموند) و ظهور آن در مثلث پاسکال میپردازد. این مبحث ابزار اولیه را که تمام ترکیبیات شمارشی بر آن بنا شده است، پایهگذاری میکند.
Core questions
- به چند روش میتوان k شیء را از n شیء متمایز انتخاب کرد؟
- قواعد جمع و ضرب چگونه یک مسئله شمارش را تجزیه میکنند؟
- چه اتحادهایی ضرایب دوجملهای را به یکدیگر و به قضیه دوجملهای مرتبط میکنند؟
- مثلث پاسکال چگونه این ضرایب را به صورت بازگشتی کدگذاری میکند؟
Key concepts
- قاعده جمع و قاعده ضرب
- جایگشتها در مقابل ترکیبها
- فاکتوریلها
- مثلث پاسکال
- اتحاد وندرموند
- ضرایب چندجملهای
Key theories
- قضیه دوجملهای
- بسط (x+y)^n = مجموع C(n,k) x^k y^(n-k) بر روی k، ضرایب دوجملهای را به عنوان ضرایب جبری در یک توان از یک دوجملهای بیان میکند و شمارش را به جبر چندجملهای پیوند میدهد.
- قاعده پاسکال
- رابطه بازگشتی C(n,k) = C(n-1,k-1) + C(n-1,k) هر ضریب دوجملهای را از دو ضریب بالای آن میسازد، مثلث پاسکال را تولید میکند و نشان میدهد که آیا یک زیرمجموعه انتخاب شده شامل یک عنصر متمایز است یا خیر.
Clinical relevance
ضرایب دوجملهای زیربنای توزیع احتمال دوجملهای، تحلیل الگوریتمهای ترکیبیاتی، و هر زمینهای هستند که نیاز به شمارش انتخابهای نامرتب دارد، که این امر آنها را در احتمال، آمار و علوم کامپیوتر فراگیر میسازد.
History
آرایههای مثلثی ضرایب دوجملهای قرنها پیش از رساله پاسکال در سال 1654 که این ساختار را در غرب نامی ماندگار بخشید، در ریاضیات چینی، فارسی و هندی ظاهر شدهاند.
Key figures
- Blaise Pascal
- Isaac Newton
Related topics
Seminal works
- stanley2011
Frequently asked questions
- تفاوت بین جایگشت و ترکیب چیست؟
- جایگشت آرایشهایی را شمارش میکند که ترتیب در آنها اهمیت دارد؛ ترکیب، که توسط ضریب دوجملهای شمارش میشود، انتخابهایی را شمارش میکند که ترتیب در آنها بیاهمیت است.
- چرا C(n,0) برابر با 1 است؟
- دقیقاً یک روش برای انتخاب هیچ چیز از یک مجموعه وجود دارد – زیرمجموعه تهی – بنابراین تعداد زیرمجموعههای صفر-عضوی یک است.