ترکیب یک انتخاب نامرتب از عناصر یک مجموعه محدود با تعداد ثابت و بدون تکرار عناصر است. ترکیب های مختلف باید حداقل در یک عنصر متفاوت باشند و ترتیب عناصر مهم نیست. به عنوان مثال، از مجموعه تمام حروف صدادار حروف لاتین (AEIOU)، می توانید 10 ترکیب مختلف از 3 حرف ایجاد کنید که سه گانه های نامرتب زیر را تشکیل می دهند:

AEI، AEO، AEU، AIO، AIU، AOU، EIO، EIU، EOU، IOU.

جالب است بدانید که از همان پنج حرف می توانید 10 ترکیب مختلف را نیز بدست آورید اگر آنها را 2 حرف در یک زمان ترکیب کنید و جفت های نامرتب زیر را ایجاد کنید:

AE، AI، AO، AU، EI، EO، اتحادیه اروپا، IO، IU، OU.

با این حال، اگر همان حروف صدادار لاتین را با 4 ترکیب کنید، فقط 5 ترکیب مختلف زیر را دریافت خواهید کرد:

AEIO، AEIU، AIOU، EIOU، AEOU.

به طور کلی، برای نشان دادن تعداد ترکیبات n عنصر مختلف از عناصر m، از نمادهای تابعی، شاخص یا برداری (Appel) زیر استفاده می شود:

صرف نظر از شکل نمادگذاری، تعداد ترکیبات n عنصر توسط m عنصر را می توان با استفاده از فرمول های ضربی و فاکتوریل زیر تعیین کرد:

به راحتی می توان بررسی کرد که نتیجه محاسبات با استفاده از این فرمول ها با نتایج مثال مورد بحث در بالا با ترکیبی از حروف صدادار با حروف لاتین مطابقت دارد. به طور خاص، با n=5 و m=3، محاسبات با استفاده از این فرمول ها نتیجه زیر را به دست خواهند داد:

در حالت کلی، فرمول های تعداد ترکیب ها معنای ترکیبی دارند و برای هر مقدار صحیح n و m معتبر هستند، به طوری که n > m > 0. اگر m > n و m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

علاوه بر این، به خاطر سپردن اعداد محدود کننده زیر مفید است که به راحتی با جایگزینی مستقیم در فرمول های ضربی و فاکتوریل قابل بررسی است:

همچنین باید توجه داشت که فرمول ضرب حتی زمانی که n یک عدد واقعی باشد، تا زمانی که m هنوز یک مقدار صحیح باشد، معتبر باقی می‌ماند. با این حال، سپس نتیجه محاسبه با استفاده از آن، با حفظ اعتبار صوری، معنای ترکیبی خود را از دست می دهد.

هویت ترکیبات

استفاده عملی از فرمول های ضربی و فاکتوریل برای تعیین تعداد ترکیب ها برای مقادیر دلخواه n و m به دلیل رشد نمایی محصولات فاکتوریل صورت و مخرج آنها بهره وری کمی دارد. حتی برای مقادیر نسبتاً کوچک n و m، این محصولات اغلب از قابلیت های نمایش اعداد صحیح در سیستم های محاسباتی و نرم افزاری مدرن فراتر می روند. علاوه بر این، مقادیر آنها به طور قابل توجهی بیشتر از مقدار حاصل از تعداد ترکیبات است که می تواند نسبتاً کوچک باشد. به عنوان مثال، تعداد ترکیبات n=10 در m=8 عنصر تنها 45 است. اما برای یافتن این مقدار با استفاده از فرمول فاکتوریل، ابتدا باید مقادیر بسیار بزرگتر 10 را محاسبه کنید! در صورت شمار و 8! در مخرج:

برای حذف عملیات وقت گیر برای پردازش مقادیر زیاد، برای تعیین تعداد ترکیبات، می توانید از روابط تکراری مختلفی استفاده کنید که مستقیماً از فرمول های ضربی و فاکتوریل پیروی می کنند. به طور خاص، رابطه عود زیر از فرمول ضربی ناشی می شود، که به ما امکان می دهد نسبت شاخص های آن را فراتر از علامت تعداد ترکیب ها برداریم:

در نهایت، ثابت نگه داشتن زیرنویس رابطه عود زیر را فراهم می کند که به راحتی از فرمول فاکتوریل برای تعداد ترکیب ها بدست می آید:

پس از تبدیل های ابتدایی، سه رابطه عود حاصله را می توان به شکل های زیر نشان داد:

اگر اکنون سمت چپ و راست 2 فرمول اول را جمع کنیم و نتیجه را n کاهش دهیم، یک رابطه عود مهم به دست می آید که به آن هویت جمع اعداد ترکیبی می گویند:

هویت جمع یک قانون عود اساسی برای تعیین موثر تعداد ترکیب ها برای مقادیر بزرگ n و m فراهم می کند، زیرا اجازه می دهد تا عملیات ضرب در محصولات فاکتوریل با عملیات جمع ساده تر و برای تعداد کمتری از ترکیب ها جایگزین شود. به طور خاص، با استفاده از هویت جمع، اکنون به راحتی می توان تعداد ترکیبات n=10 در m=8 عنصر را که در بالا مورد بحث قرار گرفت، با انجام دنباله تبدیل های مکرر زیر تعیین کرد:

علاوه بر این، چندین رابطه مفید برای محاسبه مجموع متناهی را می توان از هویت جمع استخراج کرد، به ویژه فرمول جمع بندی توسط زیرنویس که به شکل زیر است:

این رابطه زمانی به دست می‌آید که در هویت جمع، عود را در طول عبارت با بزرگ‌ترین بالانویس بسط دهیم در حالی که زیرنویس آن بزرگ‌تر از 0 باشد. مثال عددی زیر این فرآیند تبدیل‌های مکرر را نشان می‌دهد:

فرمول جمع زیرنویس اغلب برای محاسبه مجموع توان اعداد طبیعی استفاده می شود. به طور خاص، با فرض m=1، با استفاده از این فرمول به راحتی می توان مجموع n عدد اول سری طبیعی را پیدا کرد:

نسخه مفید دیگری از فرمول جمع را می توان با گسترش تکرار هویت جمع در طول عبارت با کوچکترین بالانویس به دست آورد. مثال عددی زیر این نسخه از تبدیل‌های مکرر را نشان می‌دهد:

در حالت کلی، در نتیجه چنین تبدیل هایی، مجموع اعداد ترکیب ها به دست می آید که هر دو شاخص آن ها با عبارت های همسایه یک تفاوت دارند و تفاوت شاخص ها ثابت می ماند (در مثال در نظر گرفته شده، نیز برابر با یک). بنابراین، فرمول جمع زیر را برای هر دو شاخص اعداد ترکیبی به دست می آوریم:

علاوه بر روابط عود و فرمول های جمع مورد بحث در بالا، بسیاری از هویت های مفید دیگر برای اعداد ترکیبی در تجزیه و تحلیل ترکیبی به دست آمده اند. مهمترین آنها در این میان است هویت تقارن، که به شکل زیر است:

اعتبار هویت تقارن را می توان در مثال زیر با مقایسه تعداد ترکیبات 5 عنصر با 2 و با (5 2) = 3 تأیید کرد:

هویت تقارن معنای ترکیبی آشکاری دارد، زیرا با تعیین تعداد گزینه‌ها برای انتخاب m عنصر از n عنصر، به طور همزمان تعداد ترکیب‌ها را از عناصر انتخاب نشده باقی‌مانده (nm) تعیین می‌کند. تقارن نشان داده شده بلافاصله با جایگزینی m با (nm) در فرمول فاکتوریل برای تعداد ترکیبات به دست می آید:

اعداد و هویت های ترکیبی به طور گسترده در حوزه های مختلف ریاضیات محاسباتی مدرن استفاده می شوند. با این حال، محبوب ترین کاربردهای آنها مربوط به دو جمله ای نیوتن و مثلث پاسکال است.

قضیه دوجمله ای

برای انجام تبدیل‌ها و محاسبات مختلف ریاضی، مهم است که بتوانیم هر توان طبیعی یک دوجمله‌ای جبری (دوجمله‌ای) را در قالب یک چند جمله‌ای نشان دهیم. برای توان های کوچک، چند جمله ای مورد نظر را می توان به راحتی با ضرب مستقیم دو جمله ای ها به دست آورد. به طور خاص، فرمول های زیر برای مربع و مکعب مجموع دو جمله از درس ریاضیات ابتدایی به خوبی شناخته شده است:

در حالت کلی، برای یک درجه دلخواه n از یک دو جمله ای، نمایش مورد نیاز به شکل چند جمله ای توسط قضیه دو جمله ای نیوتن ارائه می شود که برابری زیر را درست اعلام می کند:

این برابری را معمولاً دوجمله ای نیوتن می نامند. چند جمله ای سمت راست آن از مجموع حاصلضرب های n جمله X و Y دو جمله ای سمت چپ تشکیل می شود و ضرایب جلوی آنها دو جمله ای نامیده می شود و برابر است با تعداد ترکیبات با شاخص ها که از توان آنها حاصل می شود. با توجه به محبوبیت خاص فرمول دوجمله ای نیوتن در تجزیه و تحلیل ترکیبی، اصطلاحات ضریب دو جمله ای و تعداد ترکیب ها به طور کلی مترادف در نظر گرفته می شوند.

بدیهی است که فرمول مجموع مجذور و مکعب به ترتیب موارد خاصی از قضیه دو جمله ای برای n=2 و n=3 هستند. برای رسیدگی به درجات بالاتر (n>3)، باید از فرمول دو جمله ای نیوتن استفاده شود. کاربرد آن برای یک دوجمله ای درجه چهارم (n=4) با مثال زیر نشان داده شده است:

لازم به ذکر است که فرمول دوجمله ای حتی قبل از نیوتن برای ریاضیدانان قرون وسطایی شرق عرب و اروپای غربی شناخته شده بود. بنابراین نام پذیرفته شده آن از نظر تاریخی صحیح نیست. شایستگی نیوتن این است که او این فرمول را در مورد یک توان واقعی دلخواه r تعمیم داد که می تواند هر مقدار مثبت یا منفی عقلانی و غیرمنطقی را بگیرد. در حالت کلی، چنین فرمول دوجمله ای نیوتن دارای مجموع بی نهایت در سمت راست است و معمولاً به صورت زیر نوشته می شود:

به عنوان مثال، با مقدار کسری مثبت توان r=1/2، با در نظر گرفتن مقادیر ضرایب دو جمله ای، بسط زیر به دست می آید:

در حالت کلی، فرمول دوجمله ای نیوتن برای هر توان، نسخه خاصی از فرمول مکلارین است که بسط یک تابع دلخواه را به یک سری توانی می دهد. نیوتن نشان داد که برای |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. اگر اکنون Z=X/Y را تنظیم کنیم و ضلع چپ و راست را در Yn ضرب کنیم، نسخه‌ای از فرمول دوجمله‌ای نیوتن که در بالا بحث شد به دست می‌آید.

علیرغم کلیت آن، قضیه دوجمله ای معنای ترکیبی خود را فقط برای توان های اعداد صحیح غیر منفی دو جمله ای حفظ می کند. در این حالت می توان از آن برای اثبات چندین هویت مفید برای ضرایب دو جمله ای استفاده کرد. به طور خاص، فرمول‌هایی برای جمع‌آوری تعداد ترکیب‌ها بر اساس زیرنویس و هر دو شاخص در بالا مورد بحث قرار گرفت. با قرار دادن X = Y = 1 یا Z = 1 در فرمول دوجمله ای نیوتن می توان هویت جمع بالانویس گم شده را به راحتی بدست آورد:

هویت مفید دیگر برابری مجموع ضرایب دوجمله ای با اعداد زوج و فرد را ایجاد می کند. فوراً از فرمول دوجمله ای نیوتن به دست می آید اگر X = 1 و Y = 1 یا Z = 1:

در نهایت، از هر دو هویت در نظر گرفته شده، هویت مجموع ضرایب دوجمله ای را فقط با اعداد زوج یا تنها به دست می آوریم:

بر اساس هویت های در نظر گرفته شده و قاعده مکرر حذف شاخص ها از زیر علامت تعداد ترکیب ها، تعدادی رابطه جالب می توان به دست آورد. به عنوان مثال، اگر در فرمول جمع بالای n در همه جا با (n1) جایگزین کنیم و شاخص های هر جمله را حذف کنیم، رابطه زیر را به دست می آوریم:

با استفاده از تکنیک مشابه در فرمول مجموع ضرایب دوجمله ای با اعداد زوج و فرد، می توان صحت رابطه زیر را اثبات کرد:

هویت مفید دیگر به شما امکان می دهد تا با استفاده از فرمول کوشی زیر، مجموع حاصل از ضرایب دوجمله ای متقارن دو جمله ای با درجه دلخواه n و k را به راحتی محاسبه کنید:

اعتبار این فرمول از برابری لازم ضرایب برای هر درجه m از متغیر Z در سمت چپ و راست رابطه یکسان زیر ناشی می شود:

در حالت خاصی که n=k=m، با در نظر گرفتن هویت تقارن، فرمول محبوب تری برای مجموع مجذورهای ضرایب دوجمله ای به دست می آید:

بسیاری از هویت های مفید دیگر برای ضرایب دوجمله ای را می توان در ادبیات گسترده در مورد تجزیه و تحلیل ترکیبی یافت. با این حال، معروف ترین کاربرد عملی آنها مربوط به مثلث پاسکال است.

مثلث پاسکال

مثلث حسابی پاسکال یک جدول عددی نامتناهی را تشکیل می دهد که از ضرایب دو جمله ای تشکیل شده است. خطوط آن بر اساس توان های دوجمله ای از بالا به پایین مرتب شده اند. در هر خط، ضرایب دو جمله ای به ترتیب صعودی اعداد ترکیبی مربوطه از چپ به راست مرتب شده اند. مثلث پاسکال معمولاً به صورت متساوی الساقین یا مستطیل نوشته می شود.

بصری تر و رایج تر، فرمت متساوی الساقین است، که در آن ضرایب دوجمله ای، به صورت پلکانی، یک مثلث متساوی الساقین بی نهایت را تشکیل می دهند. قطعه اولیه آن برای دوجمله ای تا درجه 4 (n=4) به شکل زیر است:

به طور کلی، مثلث متساوی الساقین پاسکال یک قانون هندسی مناسب برای تعیین ضرایب دو جمله ای ارائه می دهد که بر اساس هویت جمع و تقارن ترکیبات اعداد است. به طور خاص، با توجه به هویت جمع، هر ضریب دوجمله ای مجموع دو ضریب ردیف قبلی نزدیکترین به آن است. با توجه به هویت تقارن، مثلث متساوی الساقین پاسکال نسبت به نیمساز آن متقارن است. بنابراین، هر یک از خطوط آن یک پالیندروم عددی از ضرایب دو جمله ای است. ویژگی های جبری و هندسی نشان داده شده این امکان را فراهم می کند که به راحتی مثلث متساوی الساقین پاسکال را گسترش داده و مقادیر ضرایب دو جمله ای توان های دلخواه را به طور مداوم پیدا کنید.

با این حال، برای مطالعه ویژگی های مختلف مثلث پاسکال، استفاده از قالب مستطیلی که به طور رسمی سخت تر است، راحت تر است. در این قالب، با یک ماتریس مثلثی پایین تر از ضرایب دو جمله ای مشخص می شود، جایی که آنها یک مثلث قائم الزاویه بی نهایت را تشکیل می دهند. قطعه اولیه مثلث قائم الزاویه پاسکال برای دوجمله ای تا درجه 9 (n=9) به شکل زیر است:

از نظر هندسی، چنین جدول مستطیلی با تغییر شکل افقی مثلث متساوی الساقین پاسکال به دست می آید. در نتیجه، سری اعداد موازی با اضلاع جانبی مثلث متساوی الساقین پاسکال به عمودها و مورب های مثلث قائم الزاویه پاسکال تبدیل می شوند و خطوط افقی هر دو مثلث بر هم منطبق می شوند. در عین حال، قوانین جمع و تقارن ضرایب دوجمله ای همچنان معتبر هستند، اگرچه مثلث قائم الزاویه پاسکال مشخصه تقارن بصری همتای متساوی الساقین خود را از دست می دهد. برای جبران این، تحلیل رسمی خصوصیات عددی مختلف ضرایب دو جمله ای برای افقی، عمودی و مورب مثلث قائم الزاویه پاسکال راحت تر می شود.

با شروع تجزیه و تحلیل افقی مثلث قائم الزاویه پاسکال، به راحتی می توان متوجه شد که مجموع عناصر هر سطر با عدد n مطابق با فرمول جمع دوجمله ای ها با بالانویس برابر با 2n است. از این نتیجه می شود که مجموع عناصر بالای هر یک از خطوط افقی با عدد n برابر است با (2 n 1). اگر مقدار مجموع عناصر هر افقی در سیستم اعداد باینری نوشته شود، این نتیجه کاملاً آشکار می شود. به عنوان مثال، برای n=4 این جمع را می توان به صورت زیر نوشت:

در اینجا چند ویژگی جالب دیگر از افقی ها وجود دارد که به توان های دو نیز مربوط می شوند. معلوم می شود که اگر عدد افقی توان دو باشد (n=2 k)، آنگاه تمام عناصر داخلی آن (به جز عناصر خارجی) اعداد زوج هستند. برعکس، تمام اعداد یک خط افقی فرد خواهند بود اگر عدد آن یک کمتر از توان دو باشد (n=2 k 1). اعتبار این ویژگی ها را می توان با بررسی برابری ضرایب دوجمله ای داخلی به عنوان مثال در افقی های n=4 و n=3 یا n=8 و n=7 تایید کرد.

حالا بگذارید شماره ردیف مثلث قائم الزاویه پاسکال یک عدد اول p باشد. سپس تمام ضرایب دوجمله ای داخلی آن بر p بخش پذیر است. بررسی این ویژگی برای مقادیر کوچک اعداد خطوط اصلی آسان است. به عنوان مثال، تمام ضرایب دوجمله ای داخلی پنجمین افقی (5، 10 و 5) به وضوح بر 5 بخش پذیر هستند. برای اثبات این نتیجه برای هر عدد افقی اول p، باید فرمول ضربی ضرایب دو جمله ای آن را به صورت زیر بنویسید:

از آنجایی که p یک عدد اول است و بنابراین بر m بخش پذیر نیست، حاصل ضرب ضرایب باقیمانده صورت‌گر این فرمول باید بر m بخش‌پذیر باشد تا مقدار صحیح ضریب دوجمله‌ای تضمین شود. نتیجه این است که نسبت در پرانتز یک عدد طبیعی N است و نتیجه مطلوب آشکار می شود:

با استفاده از این نتیجه، می توانیم ثابت کنیم که اعداد تمام خطوط افقی مثلث پاسکال، که عناصر داخلی آن بر یک عدد اول معین p قابل تقسیم هستند، توان های p هستند، یعنی به شکل n=p k هستند. به طور خاص، اگر p=3 باشد، عدد اول p نه تنها تمام عناصر داخلی ردیف 3 را که در بالا مشخص شد، بلکه، برای مثال، افقی 9 (9، 36، 84 و 126) را تقسیم می‌کند. از طرف دیگر، در مثلث پاسکال نمی توان خط افقی را یافت که همه عناصر داخلی آن بر یک عدد مرکب بخش پذیر باشند. در غیر این صورت، تعداد چنین خط افقی باید به طور همزمان توانی از مقسوم‌کننده‌های اول عدد مرکب باشد که تمام عناصر داخلی آن تقسیم می‌شوند، اما این به دلایل واضح غیرممکن است.

ملاحظات در نظر گرفته شده به ما اجازه می دهد تا معیار کلی زیر را برای تقسیم پذیری عناصر افقی مثلث پاسکال فرمول بندی کنیم. بزرگترین مقسوم علیه مشترک (GCD) تمام عناصر داخلی هر خط افقی مثلث پاسکال با عدد n برابر است با عدد اول p اگر n=pk یا 1 در سایر موارد:

GCD(Cmn) = ( ) برای هر 0< m < n .

در پایان تجزیه و تحلیل افقی ها، لازم است یک ویژگی جالب دیگر را در نظر بگیریم که سری ضرایب دوجمله ای تشکیل دهنده آنها را دارند. اگر ضرایب دوجمله ای هر خط افقی با عدد n در توان های متوالی عدد 10 ضرب شود و سپس تمام این حاصلضرب ها جمع شوند، نتیجه 11 n می شود. توجیه رسمی برای این نتیجه، جایگزینی مقادیر X=10 و Y=1 (یا Z=1) به فرمول دو جمله ای نیوتن است. مثال عددی زیر تحقق این ویژگی را برای n=5 نشان می‌دهد:

تجزیه و تحلیل ویژگی های عمودهای مثلث قائم الزاویه پاسکال می تواند با مطالعه ویژگی های فردی عناصر تشکیل دهنده آنها آغاز شود. به طور رسمی، هر m عمودی توسط دنباله نامتناهی از ضرایب دوجمله ای با یک رونوشت ثابت (m) و افزایشی از زیرنویس تشکیل می شود:

بدیهی است که وقتی m=0 دنباله ای از یک ها به دست می آید و وقتی m=1 یک سری اعداد طبیعی تشکیل می شود. وقتی m=2 عمودی از اعداد مثلثی تشکیل شده است. هر عدد مثلثی را می توان روی یک صفحه به شکل یک مثلث متساوی الاضلاع ترسیم کرد که با اشیاء دلخواه (هسته) که در یک الگوی شطرنجی مرتب شده اند پر شده است. در این حالت، مقدار هر عدد مثلثی T k، تعداد هسته‌های نشان‌دهنده را تعیین می‌کند و ایندکس نشان می‌دهد که چند ردیف از هسته برای نشان دادن آن نیاز است. برای مثال، 4 عدد مثلثی اولیه، پیکربندی‌های زیر را از تعداد متناظر نمادهای هسته‌ای «@» نشان می‌دهند:

لازم به ذکر است که به روشی مشابه می توان اعداد مربعی S k را در نظر گرفت که از مربع کردن اعداد طبیعی و به طور کلی اعداد چند ضلعی شکل که از پر کردن منظم چند ضلعی های منتظم به دست می آیند، به دست می آیند. به طور خاص، 4 عدد مربع اولیه را می توان به صورت زیر نشان داد:

با بازگشت به تجزیه و تحلیل عمودهای مثلث پاسکال، می‌توان به این نکته اشاره کرد که عمود بعدی در m=3 با اعداد چهاروجهی (هرمی) پر شده است. هر عدد Pk تعداد هسته‌هایی را که می‌توان به شکل چهار وجهی مرتب کرد مشخص می‌کند و این شاخص تعیین می‌کند که چند لایه مثلثی افقی از ردیف‌های هسته‌ها برای نمایش آن در فضای سه‌بعدی لازم است. در این حالت، تمام لایه های افقی باید به صورت اعداد مثلثی متوالی نشان داده شوند. عناصر عمودهای زیر مثلث پاسکال برای m>3 مجموعه ای از اعداد هیپرتترادال را تشکیل می دهند که تفسیر هندسی بصری در صفحه یا فضای سه بعدی ندارند، اما به طور رسمی با آنالوگ های چند بعدی اعداد مثلثی و چهار وجهی مطابقت دارند.

اگرچه سری های اعداد عمودی مثلث پاسکال دارای ویژگی های شکلی منفرد در نظر گرفته شده است، برای آنها می توان مجموع جزئی مقادیر عناصر اولیه را با استفاده از فرمول جمع کردن اعداد ترکیب ها بر اساس زیرنویس محاسبه کرد. . در مثلث پاسکال این فرمول تفسیر هندسی زیر را دارد. مجموع مقادیر n ضریب دوجمله ای بالایی هر عمودی برابر با مقدار عنصر عمود بعدی است که در یک خط زیر قرار دارد. این نتیجه همچنین با ساختار هندسی اعداد مثلثی، چهار وجهی و ابر چهار وجهی سازگار است، زیرا نمایش هر یک از این اعداد شامل لایه‌های هسته‌ای است که اعداد مرتبه پایین‌تری را نشان می‌دهند. به طور خاص، nامین عدد مثلثی T n را می توان با جمع تمام اعداد طبیعی که لایه های خطی آن را نشان می دهند به دست آورد:

به طور مشابه، یافتن عدد چهار وجهی Pn با محاسبه مجموع زیر از n عدد مثلثی اول که لایه های هسته افقی آن را تشکیل می دهند، دشوار نیست:

علاوه بر افقی و عمودی در مثلث قائم الزاویه پاسکال، می توان ردیف های مورب عناصر را ردیابی کرد که مطالعه ویژگی های آنها نیز مورد توجه است. در این حالت معمولاً بین قطرهای نزولی و صعودی تمایز قائل می شود. قطرهای رو به پایین موازی با هیپوتنوز مثلث قائم الزاویه پاسکال هستند. آنها توسط مجموعه ای از ضرایب دو جمله ای با افزایش هر دو شاخص تشکیل می شوند. به دلیل هویت تقارن، قطرهای نزولی در مقادیر عناصر خود با ردیف های عمودی متناظر مثلث پاسکال منطبق می شوند و بنابراین همه ویژگی های آنها را که در بالا مورد بحث قرار گرفت تکرار می کنند. مطابقت نشان داده شده را می توان با همزمانی مقادیر عناصر مورب نزولی و عمودی با هر عدد n دنبال کرد، اگر صفرهای عمودی در نظر گرفته نشود:

قطرهای صعودی سری اعدادی را به صورت هندسی عمود بر هیپوتنوز مثلث قائم الزاویه پاسکال تشکیل می دهند. آنها با ضرایب دو جمله ای با کاهش پایین تر و افزایش بالانویس پر شده اند. به طور خاص، 7 قطر صعودی بالا بدون در نظر گرفتن صفرهای دنباله‌ای، دنباله عددی زیر را تشکیل می‌دهند:

به طور کلی عدد مورب صعودی n دارای ضرایب دو جمله ای زیر است که مجموع شاخص های هر کدام برابر با (n1) است:

با توجه به هویت جمع برای اعداد ترکیبی، هر عنصر مورب برابر است با مجموع دو عنصر متناظر در شاخص های دو قطر صعودی قبلی. این اجازه می دهد تا هر مورب صعودی بعدی با جمع زوجی عناصر افقی مجاور از دو قطر قبلی ساخته شود و مثلث پاسکال را بی نهایت در طول قطر گسترش دهد. قطعه زیر از مثلث پاسکال ساخت یک قطر صعودی شماره 8 را در امتداد قطرهای شماره 6 و 7 نشان می دهد:

با این روش ساخت، مجموع عناصر هر مورب صعودی، با شروع از 3، برابر با مجموع عناصر دو قطر صعودی قبلی خواهد بود و 2 قطر اول فقط از یک عنصر تشکیل شده است، مقدار که 1 است. نتایج محاسبات مربوطه سری عددی زیر را تشکیل می دهد که بر اساس آن می توانید اعتبار خاصیت در نظر گرفته شده قطرهای صعودی مثلث قائم الزاویه پاسکال را بررسی کنید:

با تجزیه و تحلیل این اعداد، می بینید که طبق قانون مشابه، دنباله معروف اعداد فیبوناچی تشکیل می شود که هر عدد بعدی برابر با مجموع دو عدد قبلی و دو عدد اول برابر با 1 است:

بنابراین، می‌توانیم نتیجه مهم زیر را بگیریم: مجموع مورب عناصر مثلث پاسکال، دنباله فیبوناچی را تشکیل می‌دهند. این ویژگی به ما اجازه می دهد تا یکی دیگر از ویژگی های جالب مثلث پاسکال را ایجاد کنیم. با گسترش فرمول فیبوناچی به صورت بازگشتی، به راحتی می توان ثابت کرد که مجموع n عدد اول فیبوناچی برابر است با (F n+2 1).

بنابراین مجموع ضرایب دو جمله ای که n قطر بالایی را پر می کند نیز برابر است با (F n+2 1). نتیجه این است که مجموع n قطر اول مثلث پاسکال 1 کمتر از مجموع ضرایب دوجمله ای است که روی قطر آن با عدد (n+2) قرار دارد.

در پایان، لازم به ذکر است که ویژگی های در نظر گرفته شده از افقی، عمودی و مورب مثلث پاسکال، تنوع عظیمی از احتمالات را که جنبه های مختلف ریاضی را که در نگاه اول هیچ وجه اشتراکی با هم ندارند، به هم متصل نمی کند. چنین ویژگی‌های غیرمعمولی به ما اجازه می‌دهد مثلث پاسکال را یکی از کامل‌ترین سیستم‌های عددی در نظر بگیریم، که همه قابلیت‌های آن را نمی‌توان فهرست کرد و برآورد بیش از حد دشوار است.

الگوریتم محاسبه تعداد ترکیب ها با استفاده از مثلث پاسکال در زیر ارائه شده است:

تابع خصوصی SochTT (ByVal n به عنوان عدد صحیح، ByVal k به عنوان عدد صحیح) به عنوان Double Dim i به عنوان عدد صحیح Dim j به عنوان عدد صحیح Dim TT () به عنوان Double ReDim TT (n, k) برای i = 0 تا n TT (0, i) = 1 TT (i، i) = 1 بعدی برای i = 2 به n برای j = 1 به i - 1 TT (i، j) = TT (i - 1، j - 1) + TT (i - 1، j) بعدی بعدی SochTT = TT (n، k) تابع پایان

اگر لازم است تعداد ترکیب ها را بارها محاسبه کنید، ممکن است راحت تر باشد که مثلث پاسکال را یک بار بسازید و سپس داده ها را از آرایه دریافت کنید.

Dim TT () به عنوان Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n به عنوان عدد صحیح، ByVal k به عنوان عدد صحیح) به عنوان Double If n > Ubound (TT) سپس BuildTT Ubound (TT) + 1، n SochTT = TT (n، k) Function End Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (شروع ByVal به عنوان عدد صحیح، ByVal پایان به عنوان عدد صحیح) Dim i به عنوان عدد صحیح Dim j به عنوان عدد صحیح ReDim حفظ TT (پایان، پایان) برای i = شروع تا پایان TT (0، i) = 1 TT (i، i) = 1 بعد اگر پایان< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub

ابتدا باید روال CreateTT را فراخوانی کنید. سپس می توانید تعداد ترکیب ها را با استفاده از تابع SochTT بدست آورید. هنگامی که دیگر به مثلث نیاز ندارید، رویه TerminateTT را فراخوانی کنید. در کد بالا، هنگام فراخوانی تابع SochTT، اگر مثلث هنوز به سطح مورد نیاز تکمیل نشده باشد، با روش BuildTT تکمیل می شود. سپس تابع عنصر مورد نظر آرایه TT را دریافت کرده و آن را برمی گرداند.

Dim X () به عنوان عدد صحیح Dim شمارنده () به عنوان عدد صحیح Dim K به عنوان عدد صحیح Dim N به عنوان عدد صحیح عمومی Sub Soch() Dim i به عنوان عدد صحیح N = CInt(InputBox("Enter N")) K = CINT(InputBox("K را وارد کنید ")) K = K + 1 ReDim X(N) برای i = 1 به N X(i) = i بعدی txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c به عنوان عدد صحیح) Dim i به عنوان عدد صحیح Dim j به عنوان عدد صحیح Dim n1 به عنوان عدد صحیح Dim Out() به عنوان عدد صحیح Dim X1() به عنوان عدد صحیح اگر c = K سپس ReDim Out(K) X1 = X برای i = 1 به K - 1 n1 = 0 برای j = 1 به N اگر X1(j)<>0 سپس n1 = n1 + 1 اگر n1 = شمارنده(i) سپس Out(i) = X1(j) X1(j) = 0 خروج برای پایان اگر بعدی txtOut.Text = txtOut.Text & CStr(Out(i)) بعدی txtOut.Text = txtOut.Text و vbCrLf دیگر برای شمارنده (c) = شمارنده (c - 1) به N - c + 1 SochGenerate c + 1 پایان بعدی If End Sub

فهرست کردن ترکیبات اعداد طبیعی

برای حل بسیاری از مسائل عملی، لازم است تمام ترکیبات کاردینالیته ثابت را که می توان از عناصر یک مجموعه محدود به دست آورد، فهرست کرد و فقط تعداد آنها را تعیین نکرد. با در نظر گرفتن امکان همیشه موجود برای شماره گذاری اعداد صحیح عناصر هر مجموعه محدود، در بیشتر موارد مجاز است خود را به استفاده از الگوریتم هایی برای شمارش ترکیبی از اعداد طبیعی محدود کنیم. طبیعی ترین و ساده ترین آنها، الگوریتم فهرست کردن ترکیبات اعداد طبیعی است نظم لغوی.

برای توصیف رسمی این الگوریتم، راحت است فرض کنیم که مجموعه اصلی، که تمام ترکیبات m عناصر آن باید فهرست شوند، اعداد طبیعی متوالی از 1 تا n را تشکیل می دهند. سپس هر ترکیبی از m

در نتیجه ترتیب، مقدار در هر موقعیت از چنین بردار ترکیبی به طور طبیعی مشخص می شود که از نظر مقدار از بالا و پایین به شرح زیر محدود می شود:

الگوریتم واژگانی به طور متوالی چنین بردارهای ترکیبی را تولید می کند، که با کوچکترین بردار از نظر لغوی شروع می شود، که در آن همه موقعیت ها حاوی حداقل مقادیر ممکن زیر از عناصر برابر با شاخص های آنها هستند:

هر بردار ترکیبی متوالی پس از اسکن عناصر آن از چپ به راست به منظور یافتن سمت راست ترین عنصری که هنوز به مقدار حد خود نرسیده است، از بردار فعلی تشکیل می شود:

مقدار چنین عنصری باید 1 افزایش یابد. به هر عنصر در سمت راست آن باید کوچکترین مقدار ممکن نسبت داده شود که 1 بزرگتر از همسایه سمت چپ آن است. پس از این تغییرات، بردار بعدی ترکیبات ترکیب عنصری زیر را خواهد داشت:

بنابراین، بردار ترکیبی بعدی از نظر لغوی بزرگتر از بردار قبلی خواهد بود، زیرا مقادیر عناصر اولیه (j1) آنها از نظر مقدار برابر هستند و مقدار عنصر در موقعیت j 1 بزرگتر از مقدار قبلی است. . رابطه مشخص شده افزایش نظم واژگانی تضمین شده است که در تمام تکرارهای الگوریتم برآورده شود. نتیجه یک دنباله واژگانی رو به افزایش است که با بزرگترین بردار ترکیبی از نظر لغوی تکمیل می شود، که در آن عناصر در همه موقعیت ها دارای حداکثر مقادیر زیر هستند:

الگوریتم واژگانی در نظر گرفته شده با مثال زیر نشان داده شده است، جایی که لازم است به ترتیب واژگانی فزاینده تمام 15 ترکیب از n=6 عدد طبیعی اول را با m=4 عدد، یعنی تمام زیرمجموعه های 4 عنصری ممکن از مولد اصلی فهرست کنیم. مجموعه (1، 2، 3، 4، 5، 6) از 6 عنصر. نتایج محاسبات در جدول زیر ارائه شده است:

در این مثال، بزرگترین مقادیر مجاز اعداد در موقعیت های بردارهای ترکیبی به ترتیب 3، 4، 5 و 6 است. برای سهولت در تفسیر نتایج، در هر بردار ترکیبی، سمت راست ترین عنصر که دارای هنوز به حداکثر مقدار خود نرسیده است، زیر خط کشیده شده است. شاخص های عددی بردارهای ترکیبی اعداد آنها را به ترتیب لغوی تعیین می کنند. در حالت کلی، عدد لغوی N هر ترکیبی از n عنصر با m را می توان با استفاده از فرمول زیر محاسبه کرد، که در آن، به دلایل زیبایی، نمادگرایی Appel برای نشان دادن تعداد ترکیب ها استفاده می شود:

به طور خاص، محاسبات زیر با استفاده از این فرمول برای عدد ترکیبی (1، 3، 4، 6) از n=6 عنصر m=4 به ترتیب لغوی، نتیجه N=8 را به دست می‌دهد که با مثال مورد بحث در بالا مطابقت دارد:

در حالت کلی، با استفاده از هویت برای مجموع اعداد ترکیبات برای هر دو شاخص، می توان نشان داد که تعداد کوچکترین ترکیب از نظر لغوی (1، ... i، ... m) هنگام محاسبه با استفاده از این فرمول همیشه برابر با 1 خواهد بود:

همچنین بدیهی است که تعداد بزرگترین ترکیب واژگانی (m, … nm+i, … n) هنگام محاسبه با استفاده از این فرمول برابر با تعداد ترکیبات n عنصر در m خواهد بود:

از فرمول محاسبه اعداد ترکیبی واژگانی می توان برای حل مسئله معکوس استفاده کرد، جایی که باید بردار ترکیب را با تعداد آن به ترتیب لغوی تعیین کنید. برای حل چنین مشکل معکوس، باید به شکل یک معادله نوشته شود، جایی که تمام مقادیر مجهول عناصر بردار ترکیب مورد نظر (C 1، ... C i، ... C m ) در تعداد ترکیبات سمت راست آن متمرکز می شوند و تفاوت شناخته شده L از تعداد ترکیبات در سمت چپ n عنصر هر m و تعداد ترکیب مورد نیاز N نوشته می شود:

راه حل این معادله توسط الگوریتم "طمع" زیر ارائه می شود که در طی تکرارهای آن مقادیر عناصر بردار ترکیب مورد نظر به ترتیب انتخاب می شوند. در تکرار اولیه، حداقل مقدار ممکن (با محدودیت های آن) C 1 انتخاب می شود که در آن عبارت اول در سمت راست دارای حداکثر مقداری است که از L تجاوز نمی کند:

اکنون سمت چپ L باید به تعداد ترکیبات اول در سمت راست با مقدار انتخاب شده C 1 کاهش یابد و به طور مشابه مقدار C 2 را در تکرار دوم تعیین کنید:

به طور مشابه، تمام تکرارهای بعدی باید برای انتخاب مقادیر سایر عناصر C i از ترکیب مورد نظر، تا آخرین عنصر C m انجام شود:

به دلایل واضح، مقدار آخرین عنصر C m را می توان بر اساس برابری تعداد ترکیبات آن با مقدار باقیمانده سمت چپ L تعیین کرد:

لازم به ذکر است که مقدار آخرین عنصر ترکیب C m را می توان حتی ساده تر، بدون برشمردن مقادیر احتمالی آن پیدا کرد:

اجرای تکرارهای الگوریتم در نظر گرفته شده با مثال زیر نشان داده شده است، جایی که لازم است ترکیباتی با عدد N=8 به ترتیب لغوی تعیین شود، اگر n=6 و m=4 باشد:

توانایی الگوریتمی برای تعیین ترکیب با یک عدد معین به ترتیب لغوی می تواند در جهات مختلف مورد استفاده قرار گیرد. به ویژه، هنگام فهرست کردن ترکیب ها به ترتیب لغوی، لازم است از بازگشت به هر ترکیبی که قبلاً به دست آمده است اطمینان حاصل شود، کافی است فقط تعداد آن را بدانید. علاوه بر این، تولید ترکیب‌ها به هر ترتیبی امکان‌پذیر می‌شود، که با دنباله‌ای دلخواه از اعداد واژگانی آنها تنظیم می‌شود.

اکنون الگوریتمی برای تولید ترکیب ها به ترتیب واژگانی ارائه می کنیم:

2 برای i:= 1 تا k A[i] := i;

5 شروع نوشتن (A, …, A[k]);

6 اگر A[k] = n پس p:= p 1 else p:= k;

8 برای i:= k پایین به p انجام A[i] := A[p] + i p + 1

ترکیبات با عناصر تکرار شونده

بر خلاف ترکیب کلاسیک، که در آن همه عناصر متفاوت هستند، ترکیبی با تکرار، انتخاب نامرتبی از عناصر یک مجموعه محدود را تشکیل می‌دهد، جایی که هر عنصری می‌تواند به طور نامحدود به طور مکرر ظاهر شود و لزوماً در یک نسخه وجود ندارد. در این حالت معمولاً تعداد تکرار عناصر فقط با طول ترکیب محدود می شود و ترکیباتی که حداقل در یک عنصر با هم تفاوت دارند متفاوت در نظر گرفته می شوند. به عنوان مثال، با انتخاب 4 عدد به صورت اختیاری متفاوت از مجموعه 1، 2 و 3، می توانید 15 ترکیب زیر را با تکرار ایجاد کنید:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

به طور کلی، ترکیب با تکرار را می توان با انتخاب n عنصر از انواع دلخواه تشکیل داد. با این حال، آنها همیشه می توانند با اعداد طبیعی متوالی از 1 تا n مرتبط شوند. سپس هر ترکیبی از m اختیاری اعداد مختلف در این محدوده را می توان به صورت برداری نوشت و آنها را به ترتیب غیر کاهشی از چپ به راست مرتب کرد:

طبیعتاً با این شکل علامت گذاری، به دلیل امکان تکرار نامحدود، هر عنصر همسایه می تواند برابر باشد. با این حال، هر بردار ترکیبی با تکرار n عنصر توسط m را می توان با یک بردار ترکیبی از (n+m-1) عنصر با m مرتبط کرد که به صورت زیر ساخته می شود:

واضح است که برای هر مقدار از عناصر بردار f، عناصر بردار C تضمین می شود که متفاوت باشند و به طور دقیق به ترتیب افزایش مقادیر آنها از محدوده 1 تا (n+m1) مرتب شوند. :

وجود یک تناظر یک به یک بین عناصر بردارهای ترکیبی f و C به ما اجازه می‌دهد تا روش ساده زیر را برای فهرست‌بندی سیستماتیک ترکیب‌ها با تکرار n عنصر با m پیشنهاد کنیم. فقط لازم است، به عنوان مثال، به ترتیب واژگانی، تمام ترکیبات C از (n+m1) عناصر m فهرست شوند، و به ترتیب عناصر هر یک از آنها را با استفاده از فرمول زیر به عناصر مربوط به ترکیبات با تکرار f تبدیل کنید:

در نتیجه، دنباله ای از بردارهای ترکیبات با تکرار عناصر تشکیل می شود که به ترتیب ایجاد شده با فهرست کردن ترکیبات مربوطه بدون تکرار عناصر مرتب می شوند. به طور خاص، برای به دست آوردن دنباله بالا از ترکیبات 3 رقمی 1، 2 و 3 با تکرارهای 4 رقمی، لازم است تمام ترکیبات بدون تکرار 6 رقمی 1،2،3،4، 5 به ترتیب لغوی فهرست شوند. و 6 هر کدام 4 رقمی هستند و آنها را همانطور که نشان داده شده تبدیل می کنند. مثال زیر چنین تبدیل ترکیب (1،3،4،6) را با عدد واژگانی 8 نشان می دهد:

مطابقت یک به یک در نظر گرفته شده بین ترکیبات با و بدون تکرار عناصر به این معنی است که مجموعه آنها به همان اندازه قدرتمند هستند. بنابراین، در حالت کلی، تعداد ترکیبات با تکرار n عنصر در m برابر است با تعداد ترکیبات بدون تکرار (n+m1) عنصر در m. با استفاده از نمادهای مشابه برای نشان دادن اعداد ترکیبات با تکرار f و بدون تکرار C، این برابری را می توان به صورت زیر نوشت:

به راحتی می توان بررسی کرد که برای مثال در نظر گرفته شده در بالا، که در آن n=3 و m=4، تعداد ترکیب های تکراری برابر با 15 خواهد بود، که با نتیجه فهرست مستقیم آنها مطابقت دارد:

لازم به ذکر است که برخلاف نسخه کلاسیک، مقادیر پارامترهای ترکیبی با تکرار n و m مستقیماً به یکدیگر مرتبط نیستند، بنابراین برای هر ترکیبی از مقادیر مثبت آنها f(n,m)>0. شرایط مرزی مربوطه از برابری بین مقادیر (n+m1) و (n1) یا (n+m1) و m تعیین می شود:

همچنین باید کاملاً واضح باشد که اگر m برابر با 1 باشد، هیچ تکراری از عناصر ممکن نیست و بنابراین، برای هر مقدار مثبت n>0 برابری زیر صادق خواهد بود:

علاوه بر این، برای تعداد ترکیبات با تکرار برای هر مقدار مثبت n و m، رابطه عود زیر معتبر است، که مشابه هویت جمع برای تعداد ترکیبات بدون تکرار عناصر است:

در واقع، با جایگزینی رسمی تعداد متناظر از ترکیبات بدون تکرار در سمت چپ و راست، به هویت اضافه نشان داده شده تبدیل می‌شود:

رابطه عود در نظر گرفته شده را می توان برای تعیین موثر تعداد ترکیب ها با تکرار استفاده کرد، زمانی که حذف عملیات فشرده محاسبات فاکتوریل و جایگزینی آنها با عملیات جمع ساده تر مهم است. در این مورد، برای محاسبه مقدار f(n,m)، فقط باید این رابطه بازگشتی را اعمال کنید تا زمانی که مجموع عبارت‌های فرم f(1,m) و f(i,1) را بدست آورید، جایی که i مقادیری را در محدوده n تا 1 می گیرد. طبق تعریف کمیت، این عبارات به ترتیب برابر با 1 و i هستند. مثال زیر استفاده از این تکنیک تبدیل را برای حالت n=3 و m=4 نشان می دهد:

فهرست کردن ترکیبات باینری

هنگام پیاده سازی ترکیبات در سخت افزار یا برنامه نویسی به زبان اسمبلی، مهم است که بتوان رکوردهای ترکیبی را در فرمت باینری پردازش کرد. در این مورد، هر ترکیبی از n عنصر m باید به شکل یک عدد دودویی n بیتی (B n،...B j،...B 1) مشخص شود، که در آن رقم واحد m عناصر را نشان می دهد. ترکیب، و ارقام باقیمانده (nm) مقادیر صفر دارند. بدیهی است که با این شکل نمادگذاری، ترکیب‌های مختلف باید در ترتیب ارقام 1 متفاوت باشند، و تنها راه‌های C(n,m) برای ترتیب m یک یا (nm) صفر در یک مجموعه باینری n بیتی وجود دارد. به عنوان مثال، جدول زیر تمام 6 ترکیب باینری را فهرست می کند که اعداد باینری 4 بیتی را برای همه ترکیبات 4 عنصر یک مجموعه دلخواه (E 1 , E 2 , E 3 , E 4 ) در 2 ارائه می دهد:

در حالت کلی، وظیفه برشمردن چنین ترکیب‌های باینری به جستجوی سیستماتیک همه مجموعه‌های دودویی n بیتی با ترتیب‌های مختلف m یک و (nm) بیت صفر می‌رسد. در ساده‌ترین شکل، چنین جستجویی با روش‌های مختلف جابجایی بیت‌های مجاور با یک شیفت (الگوریتم‌های جابجایی انتقالی) اجرا می‌شود. اینها الگوریتم های تکراری هستند و نام آنها منعکس کننده ماهیت عملیات انجام شده در هر مرحله است. رویه‌های تکراری الگوریتم‌های انتقال مثبت، دنباله‌ای از ترکیب‌های باینری را تشکیل می‌دهند که با یک مجموعه دودویی شروع می‌شوند، جایی که همه آن‌ها در ارقام مرتبه پایین (در سمت راست) متمرکز می‌شوند و زمانی پایان می‌یابند که همه 1ها در ارقام مرتبه بالا باشند. سمت چپ):

در حالی که در ترکیب های اولیه و نهایی مطابقت دارند، این توالی ها در ترتیب فهرست بندی مجموعه های باینری میانی متفاوت هستند. با این حال، در همه موارد، هر ترکیب باینری بعدی در نتیجه انجام عملیات جابجایی و جابجایی مربوطه، از ترکیب قبلی تشکیل می‌شود. در عین حال، الگوریتم‌های مختلف انتقال مثبت در نحوه انتخاب یک جفت بیت برای جابجایی و گروهی از بیت‌ها برای جابجایی متفاوت هستند. این ویژگی در زیر برای الگوریتم‌های جابجایی با جابجایی چپ و راست مورد بحث قرار می‌گیرد.

در الگوریتم جابجایی با جابجایی به چپ، در هر مرحله، ترکیب دودویی بعدی از ترکیب فعلی با جایگزینی 10 (جایگزینی) و جابجایی گروه ارقام واحد پیشرو، در صورت وجود، نزدیک به عدد فعلی، به دست می‌آید. جفت 10 پس از جابجایی (تغییر) به دست آمد. اگر در این حالت هیچ واحدی در ارقام پیشرو در ترکیب باینری فعلی وجود نداشته باشد، تغییر انجام نمی‌شود، حتی زمانی که واحد پیشرو پس از جابه‌جایی در این مرحله به دست می‌آید. جابجایی همچنین زمانی انجام نمی شود که در مهم ترین بیت ها قبل از جفت 10 که پس از جابجایی به دست می آید، صفر وجود نداشته باشد. اقدامات در نظر گرفته شده با مثال زیر از انجام دو تکرار متوالی از این الگوریتم نشان داده شده است، جایی که در یک تکرار (15) فقط جابجایی (T") انجام می شود، و در تکرار دیگر (16) جابجایی با یک تغییر تکمیل می شود. T"+S"):

در الگوریتم جابجایی به سمت راست، مراحل مفهومی مشابهی در هر مرحله انجام می شود. فقط جابه‌جایی تضمین می‌کند که سمت راست‌ترین بیت‌های 01 با 10 جایگزین شوند (به جای سمت چپ)، و سپس همه بیت‌های سمت راست آن به کمترین بیت‌های مهم منتقل شوند. مانند قبل، شیفت تنها در صورتی انجام می شود که واحدهایی وجود داشته باشند که بتوان آنها را به راست جابجا کرد. اقدامات در نظر گرفته شده با مثال زیر از انجام دو تکرار متوالی از این الگوریتم نشان داده شده است، که در یک تکرار (3) فقط جابجایی (T") انجام می شود و در تکرار دیگر (4) جابجایی با یک تغییر تکمیل می شود. T"+S"):

لازم به ذکر است که اگر ترکیبات دودویی در سیستم اعداد پایه 2 به صورت اعداد صحیح تفسیر شوند، تکرارهای هر دو الگوریتم را می توان به صورت افزایشی نوشت. به ویژه، برای الگوریتم جابجایی با یک شیفت به راست، هر ترکیب دودویی بعدی (B" n ,…B” j , …B” 1) را همیشه می توان از ترکیب فعلی (B n,…B j,…B 1) با انجام عملیات جمع اعداد صحیح با استفاده از فرمول افزودنی زیر بدست آورد:

در این فرمول افزایشی، توان های دوگانه f و t به ترتیب تعداد ارقام صفر مرتبه پایین ترکیب دودویی فعلی و تعداد یک های ردیف در سمت چپ آنها را نشان می دهند. برای مثال، برای چهارمین ترکیب باینری (001110) از n=6 رقم f=1 و t=3. بنابراین، محاسبه ترکیب باینری بعدی با استفاده از فرمول افزودنی در تکرار 5، نتیجه زیر را به دست می‌دهد که معادل انجام عملیات جابجایی و تغییر است:

برای تجزیه و تحلیل مقایسه ای از الگوریتم های جابجایی در نظر گرفته شده با جابجایی های چپ و راست، توصیه می شود دنباله های ترکیب های دودویی را که در تکرار خود ایجاد می کنند، مقایسه کنید. جدول زیر دو دنباله از این ترکیبات باینری از 4 عنصر 2 را نشان می دهد که به ترتیب توسط الگوریتم های تغییر چپ (TSL) و راست (TSR) به دست می آیند:

با مقایسه این 2 دنباله، می بینید که آینه معکوس هستند. این بدان معنی است که هر دو ترکیب دودویی که در آنها در فاصله یکسان از انتهای متقابل دنباله های آنها قرار دارند، تصویر آینه ای از یکدیگر هستند، یعنی زمانی که نمایه سازی بیت ها در هر یک از آنها معکوس می شود، منطبق می شوند. به عنوان مثال، دومین الگوی باینری از ابتدای دنباله TSL (0101) یک تصویر آینه ای از الگوی باینری (1010) است که از انتهای دنباله TSR دوم است. به طور کلی، هر ترکیب دودویی با عدد i از یک دنباله، تصویر آینه ای از یک ترکیب دودویی با عدد (ni+1) یک دنباله دیگر است. این رابطه بین این دنباله ها نتیجه ماهیت متقارن عملیات جابجایی و جابجایی در دو الگوریتم در نظر گرفته شده برای شمارش ترکیب های باینری است.

لازم به ذکر است که از فرمت باینری می توان برای ضبط ترکیبات با تکرار عناصر نیز استفاده کرد. برای این کار لازم است بین ترکیبات با تکرار و ترکیبات باینری که به صورت زیر ساخته می شوند، مطابقت یک به یک برقرار شود. اجازه دهید یک ترکیب دلخواه با تکرارها وجود داشته باشد که با انتخاب m عناصر متفاوت از n عنصر مجموعه تولید کننده به دست می آید. برای ایجاد تطابق مورد نظر، ابتدا باید تمام عناصر تشکیل دهنده مجموعه (گربه) را به ترکیب اضافه کنید و سپس الحاق (مرتب سازی) حاصل را طوری مرتب کنید که همه عناصر یکسان در کنار هم قرار گیرند. نتیجه یک دنباله از عناصر (n+m) است که در آن n گروه از عناصر یکسان وجود دارد. مجموعاً (n+m1) شکاف بین عناصر وجود خواهد داشت که در میان آنها (n1) شکاف بین گروه‌های عناصر یکسان و m شکاف بین عناصر درون گروه‌ها وجود خواهد داشت. برای وضوح، می توانید نمادهای "|" را در فاصله های مشخص شده قرار دهید. و به همین ترتیب. اگر اکنون 1 را با فاصله بین گروه ها (|) و 0 را با سایر فضاهای () مطابقت دهیم، یک ترکیب باینری به دست می آوریم. این توسط یک مجموعه دودویی از (n+m1) بیت تشکیل شده است، که در آن (n1) یک و m صفر بیت است، که مکان آن به طور منحصر به فرد با ترکیب اصلی با تکرار عناصر n تا m مطابقت دارد. تکنیک تبدیل در نظر گرفته شده با مثال زیر از ساخت یک ترکیب دودویی (1001101) با استفاده از ترکیبی با تکرارها (BBD)، که عناصر آن از مجموعه تولید کننده پنج حرف اول لاتین انتخاب شده اند نشان داده شده است:

به طور کلی، تعداد چنین مجموعه‌های باینری، تعداد روش‌های ترتیب دادن (n1) یک‌ها (یا m صفر) در ارقام دودویی (n+m1) را تعیین می‌کند. این مقدار آشکارا برابر است با تعداد ترکیبات (n+m1) توسط (n1) یا با m، یعنی C(n+m1,n1) یا C(n+m1,m) که برابر است با تعداد ترکیبات با تکرار f(n,m) از n عنصر، m هر کدام. بنابراین، داشتن یک تناظر یک به یک بین ترکیب‌های تکراری و ترکیب‌های باینری، مشروع است که شمارش ترکیب‌ها با تکرار را به شمارش ترکیب‌های باینری تقلیل دهیم، به عنوان مثال، با استفاده از الگوریتم‌های جابه‌جایی با تغییر چپ یا راست. پس از این، فقط باید با استفاده از ترکیبات باینری حاصل، ترکیبات مورد نیاز را با تکرارها بازیابی کنید. همیشه می توان با استفاده از تکنیک بازیابی زیر این کار را انجام داد.

اجازه دهید مجموعه اصلی که از عناصر آن ترکیبات با تکرارهای m نه لزوماً عناصر متفاوت تشکیل شود، به صورت دلخواه مرتب شود تا هر یک از عناصر آن دارای شماره سریال معینی از 1 تا n باشد. اجازه دهید شمارش ترکیبات باینری (n+m1) ارقام دودویی را نیز پیاده سازی کنیم، که در آن (n1) یک ها و m رقم صفر است. هر ترکیب دودویی حاصل را می توان در سمت چپ با یک رقم واحد ساختگی تکمیل کرد و همه ارقام واحد را می توان از چپ به راست با اعداد صحیح از 1 تا n شماره گذاری کرد. سپس تعداد صفرهای پشت سر هم بعد از هر واحد i ترکیب باینری برابر با تعداد نمونه‌های عنصر i مجموعه اصلی در ترکیب مربوطه با تکرار خواهد بود. تکنیک در نظر گرفته شده با مثال زیر نشان داده شده است، جایی که با استفاده از یک ترکیب دودویی (1001101)، ترکیبی با تکرارهای BBD بازیابی می شود، که عناصر آن از مجموعه تولید پنج حرف اول لاتین انتخاب شده اند، که به ترتیب حروف الفبا نوشته شده است. ، و خط روی عناصری را نشان می دهد که در این ترکیب وجود ندارند:

با انجام اقدامات مشابه در شرایط این مثال، می توانید تمام 35 ترکیب باینری را که مجموعه های باینری 7 بیتی را تشکیل می دهند، که در آن 4 یک و 3 صفر وجود دارد، فهرست کنید و ترکیب های مربوطه را با تکرار 5 عنصر از 3 بازیابی کنید.

زمستان نزدیک بود و خوما و سوسلیک تصمیم گرفتند نخود ذخیره کنند. تمام روز به انبار دویدند و چند غلاف حمل کردند: خما، چهار، و سوسلیک، دو. تا غروب، آنها تمام غلاف هایی را که برداشت کرده بودند شمردند و به این فکر کردند که حالا چگونه این نخودها را تقسیم کنند. خوما استدلال کرد که اگر او دو برابر سوسلیک در یک زمان بکشد، پس باید دو برابر نخود بگیرد. سوسلیک معقولانه به این موضوع اعتراض کرد که اولاً سرعت خوما به طور محسوسی از سوسلیک کمتر است و ثانیاً چه کسی می داند شاید خوما فقط یکی دو بار فرار کرده بود و بقیه اوقات بیکار بود ...

به دوستان خود کمک کنید حداقل کمی این وضعیت دشوار را درک کنند. همه گزینه‌های ممکن را برای اینکه Suslik چند غلاف و چند Khoma آورده است، تعیین کنید.

داده های ورودی

در خط اول یک عدد زوج طبیعی M وجود دارد - تعداد غلاف های سرقت شده، 2 ≤ M ≤ 1000.

خروجی

تمام ترکیبات ممکن از مقادیر غلاف آورده شده توسط Suslik و Khoma، یک ترکیب در هر خط. هر ترکیب دو عدد صحیح غیر منفی را نشان می‌دهد که با یک فاصله از هم جدا شده‌اند: عدد اول تعداد غلاف‌هایی است که Suslik آورده است، دومی که توسط Khoma آورده شده است. ترکیب ها را به ترتیب نزولی شماره اول مرتب کنید.

تست ها

داده های ورودی	خروجی
6	\\ 6 \; 0 \\ 2 \; 4
11	\\ 11\;0 \\ 7\;4 \\ 3\;8
18	\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16

کد برنامه

#عبارتند از با استفاده از namespace std ; int main()( int a، b = 0; cin >> a ; در حالی که (a >= 0 ) ( کوت<< a << " " << b << "\n" ; a -= 4 ; b += 4 ; بازگشت 0 ;

راه حل مشکل

بگذارید a تعداد غلاف هایی باشد که هما آورده و b تعداد غلاف هایی باشد که سوسلیک آورده است. از آنجایی که خوما با توجه به شرایط مسئله فقط چهار غلاف را حمل می کرد، a = a-4 و b = b + 4 را در نظر می گیریم تا بدین ترتیب تمام ترکیب های ممکن از تعداد غلاف های آورده شده توسط Suslik و Khoma را برشماریم. بیایید از یک حلقه نیز استفاده کنیم در حالی که، که عمل توضیح داده شده در بالا را تا 0 \geq تکرار می کند. در پاسخ ما تمام ترکیب های ممکن از تعداد پادهای آورده شده توسط دوستان را چاپ می کنیم، یکی در هر خط، به ترتیب نزولی از شماره اول.

الگوریتم های ترکیبی اغلب استفاده می شوند. شما می توانید اطلاعات زیادی در مورد الگوریتم های ترکیبی در اینترنت پیدا کنید. با این حال، اینترنت روسی زبان عمدتاً ساده‌ترین مسائل شمارش پیوسته (تولید) اشیاء ترکیبی را در یک حلقه ایجاد می‌کند. مثلا:

مثال

// ترکیب 3 از 52 برای (int i1 = 0; i1< 50; ++i1) for (int i2 = i1+1; i2 < 51; ++i2) for (int i3 = i2+1; i3 < 52; ++i3) // ...

شاخص ترکیبی

هر ترکیب، جایگشت، ترتیب و سایر اشیاء ترکیبی را می توان با یک شاخص مرتبط کرد - این عددی است که هنگام تکرار از طریق این الگوریتم در آن ظاهر می شود.

در اینجا ما به یک مشکل پیچیده تر نگاه خواهیم کرد، که راه حل آن را در RuNet پیدا نکردم (با این حال، یک پیوند می دهم، اما آن فرمول به وضوح نادرست است) - بر اساس خود ترکیب (در این مورد، مجموعه ای از سه عدد) شاخص آن را پیدا کنید.

گزینه ای برای جستجوی "هدر رو" وجود دارد. شمارنده ترکیبی را روشن می کنیم، الگوریتم بالا را انتخاب می کنیم و همه چیز را امتحان می کنیم تا به گزینه مورد نظر برسیم. این گزینه پیچیدگی زمانی بسیار بالایی دارد، بنابراین ما این گزینه را کنار می گذاریم.
فرض کنید ورودی شامل اعداد i1، i2، i3 است. اول از همه، ما باید آنها را به ترتیب صعودی مرتب کنیم (توجه داشته باشید که خود الگوریتم تولید، که در بالا ارائه شد، همیشه آنها را به صورت مرتب تولید می کند، اگرچه خود مفهوم "ترکیب" مستلزم نظم دلخواه است).

برای قطعیت، پس از ترتیب i1 = 3، i2 = 7، i3 = 12، فرض کنیم.
این بدان معنی است که ما از تمام ترکیباتی که i1 برابر با 0، 1 و 2 بود، "گذر کردیم".
برای i1 = 0، از ترکیبات C(2، 51) عبور کرده‌ایم، زیرا شاخص‌های i1، i2 از تمام ترکیب‌های 2 از 51 عدد عبور می‌کنند.
برای i1 = 1 از ترکیبات C(2، 50) گذشتیم.
برای i1 = 2 از ترکیبات C(2، 49) گذشتیم.
در مجموع، ما از طریق SUM (از n = 0 به n = i1-1) C(2، 51-n) رفتیم.
برای i1 = 3، بیایید آن دسته از ترکیباتی را که در حین اجرای نمایه i2 از آنها عبور کردیم، در نظر بگیریم (و برای ما با i2 = i1+1 = 4 شروع می شود).
هنگامی که i2 = 4، C(1، 47) ترکیب گذشت، زمانی که i2 = 5، C(1، 46) ترکیب گذشت، زمانی که i2 = 6، C(1، 45) ترکیب گذشت.
بر اساس قیاس کامل، برای i2 ​​= 7 ترکیب هایی را که شاخص i3 از طریق آنها اجرا می کند در نظر می گیریم.
فرمول کلی را دریافت می کنیم:
شاخص ترکیبی مورد نیاز = SUM (از n = 0 تا i1-1) C(2، 51-n) + SUM (از n = i1+1 تا i2-1) C(1، 51-n) + SUM (از n = i2+1 تا i3-1) C (0، 51-n).

شاخص زیر مجموعه

در ترکیب شناسی یک شی پیچیده تر وجود دارد - تقسیم به زیر مجموعه ها. به عنوان مثال، تقسیم یک مجموعه 52 عنصری به سه زیر مجموعه، به عنوان مثال، 2، 3، و 47 عنصر، که در آن ترتیب عناصر در هر زیر مجموعه بی اهمیت است. (به هر حال، ترکیب 2 از 52 به سادگی یک مورد خاص از تقسیم به دو زیر مجموعه 2 و 50 عنصر است).

یک الگوریتم تولید معمولی این است که ما ترکیبات 2 از 52 را تولید می کنیم، و برای هر ترکیبی از این قبیل در یک حلقه تو در تو، ترکیبات 3 از 50 را تولید می کنیم و بررسی می کنیم که شاخص های (i3، i4، i5) در ترکیب تودرتو انجام می دهند. با شاخص های (i1, i2) در ترکیب خارجی منطبق نیست:

کد ++C

// ترکیب خارجی برای (int i1 = 0; i1< 51; ++i1) for (int i2 = i1+1; i2 < 52; ++i2) // ВНУТРЕННЕЕ СОЧЕТАНИЕ for (int i3 = 0; i3 < 50; ++i3) if (i3 != i1 && i3 != i2) for (int i4 = i3+1; i4 < 51; ++i4) if (i4 != i1 && i4 != i2) for (int i5 = i4+1; i5 < 52; ++i5) if (i5 != i1 && i5 != i2) // ...

باز هم، هر یک از این پارتیشن ها شاخص خاص خود را دارد.
به نظر می رسد که الگوریتم ما برای یافتن شاخص ترکیبی را می توان برای یافتن شاخص پارتیشن تغییر داد.
لازم به ذکر است که باید شاخص ها را در "ترکیب خارجی" i1, i2 در بین خود و شاخص های i3, i4, i5 در بین خود اما مستقل از دو مورد اول مرتب کنیم.
همچنین باید در نظر گرفت که در یک "ترکیب تودرتو" ما اساساً با یک مجموعه 50 عنصری کار می کنیم، اما شاخص های i3، i4، i5 باید به روش خاصی "تغییر" شوند تا از 0 تغییر نکنند. به 51، اما از 0 تا 49:

کد ++C

if (i3 >= i1) --i3; if (i3 >= i2) --i2; // مشابه برای i4، i5

(به عنوان مثال، ما شاخص های i1، i2 را از مجموعه 52 عنصری خود حذف می کنیم و سپس مجموعه باقیمانده را برای بستن سوراخ ها تغییر می دهیم، در حالی که شاخص های i3-i5 جابجا می شوند).
باید در نظر گرفت که در داخل هر ترکیب "خارجی" دقیقاً C(3، 50) ترکیبات "تودرتو" داریم.
سپس الگوریتم به موارد زیر کاهش می یابد:
COMBINATION_INDEX (i1، i2 از 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3، i4، i5 از 50 بعد از تغییر فهرست).

رساندن الگوریتم ها به پیچیدگی ثابت

فوراً باید توجه داشته باشم که اگر برای مثال i1 = 0 (مجموع n = از 0 تا -1 را بشماریم) یا i2 = 1 (مجموع را از 1 تا 0 می شماریم) "خطا" در فرمول رخ می دهد. در واقع در چنین مواردی باید مجموع مربوطه را برابر با صفر گرفت و نتیجه صحیح خواهد بود.
من باید به پیچیدگی زمانی الگوریتم‌هایمان هم توجه کنم: آنها پیچیدگی خطی دارند، به شرطی که C را زمان ثابت در نظر بگیرید. این در حال حاضر بسیار بهتر از زور وحشیانه است.
اما در واقع (در مورد ما 52) هیچ چیز مانع از کاهش الگوریتم به پیچیدگی ثابت نمی شود. برای انجام این کار، دانش ریاضیات را به کار می گیریم و تمام مقادیر را به صورت تحلیلی محاسبه می کنیم.
به عنوان مثال، تعداد ترکیبات C(2، K)، اگر آن را به شکل فرمول K "بسط" کنید! / ((K-2)! * 2!)، به چند جمله ای درجه 2 کاهش می یابد. و از آنجایی که ما آن را زیر علامت مجموع داریم، می‌توانیم فرمول‌های حاصل از مجموع توان N ام اعداد را در سری‌های طبیعی اعمال کنیم (به ویکی‌پدیا مراجعه کنید) و یک چند جمله‌ای منفرد از درجه 3 بدست آوریم. که بدیهی است پیچیدگی زمانی ثابتی دارد. (علاوه بر این، "خطایی" که در ابتدای زیرنویس ذکر کردم به هیچ وجه خود را نشان نمی دهد؛ فرمول صحیح باقی می ماند).
تکرار می کنم، این برای ابعاد ثابت مجموعه پایه. با این حال، من مطمئن هستم که با کمک فرابرنامه نویسی می توانید کامپایلر را "آموزش" دهید تا این کار را برای شما انجام دهد.

کد مثال برای تقسیم ایندکس بر 2، 3، 47

int get_split_2_3_47_index(int ​​· i1, int i2, int i3, int i4, int i5) ( // شاخص ترکیب 2 از 52 ضربدر C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600؛ // "Re-index" گروه داخلی به طوری که شماره گذاری 0...49 باشد اگر (i3 > = i1) --i3؛ اگر (i3 >= i2) --i3؛ اگر (i4 >= i1) --i4؛ اگر (i4 >= i2) --i4؛ اگر (i5 >= i1) --i5 ؛ اگر (i5 >= i2) --i5؛ // اکنون شاخص ترکیب را با 3 // 0 اضافه کنید: // SUM برای n = 0 توسط i3-1 COMBINATIONS (2, 49-n) // = SUM برای m = 50-i3 در 49 (m * (m-1) / 2) افست += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3)) / 2) / 2؛ // 1: // SUM برای n = i3+1 تا i4-1 ترکیبات (1، 49-n) افست += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2؛ // 2: // SUM برای n = i4+1 تا i5-1 (1) افست + = (i5 - i4 - 1)؛ برگشت افست ؛ )

پس گفتار

در شبیه ساز پوکر خود (تگزاس هولدم)، می خواستم احتمال برنده شدن را از قبل برای همه ترکیب های ممکن از کارت های دستم (2 قطعه) و همه کارت های فلاپ (3 کارت روی میز) محاسبه و ذخیره کنم. این مربوط به تقسیم است. مجموعه 52 با 2، 3، 47 زیر مجموعه.
محاسبه و ذخیره شد.
اما وقتی زمان خواندن داده‌ها از یک فایل برای یک ترکیب خاص فرا رسید، واقعاً نمی‌خواستم چیزی را برای مدت طولانی محاسبه کنم یا در یک فایل گیگابایت جستجو کنم. حالا من فقط افست را در فایل تعیین می کنم و مستقیماً آنچه را که نیاز دارم می خوانم.

به طور کلی، من الگوریتم های ترکیبی را به کلاس های زیر تقسیم می کنم:

• تولید اشیاء ترکیبی در یک چرخه واحد (همه چیز در اینجا ساده است، من مثال زدم).
• حرکت به شیء ترکیبی بعدی (یا قبلی)، دانستن مورد قبلی (نوعی تکرار کننده رو به جلو/عقب، بیان شده در C++) - در اینجا می توانید کتاب درسی T. I. Fedoryaeva را یادداشت کنید که یک الگوریتم پیچیدگی زمانی ثابت برای جایگشت ها ارائه می دهد. و نمونه های دیگر را می توان در RuNet یافت، اما فقط برای جایگشت - اما دیدن الگوریتم های مشابه برای سایر اشیاء ترکیبی جالب خواهد بود.
• پیدا کردن شاخص یک شی هیچ نمونه ای وجود ندارد، به استثنای کتابچه راهنمای فدوریوا، علاوه بر این، پیچیدگی خطی و فقط برای جایگشت.
• یافتن یک شی با شاخص

داشتن یک کتاب مرجع در مورد الگوریتم های ترکیبی برای همه اشیاء ترکیبی، از جمله جایگشت، ترکیب، قرارگیری، زیرمجموعه، ترکیب با تکرار، قرار دادن با تکرار، جالب خواهد بود.

تعداد ترکیبات

ترکیبیاز جانب nتوسط کمجموعه ای نامیده می شود کعناصر انتخاب شده از داده ها nعناصر. مجموعه‌هایی که فقط در ترتیب عناصر متفاوت هستند (اما نه در ترکیب) یکسان در نظر گرفته می‌شوند؛ به همین دلیل است که ترکیب‌ها با قرارگیری متفاوت هستند.

فرمول های صریح

تعداد ترکیبات از nتوسط ک برابر با ضریب دوجمله ای

برای یک مقدار ثابت nتابع تولید اعداد ترکیب با تکرار از nتوسط کاست:

تابع تولید دوبعدی اعداد ترکیب با تکرار به صورت زیر است:

پیوندها

• آر. استنلیترکیبات شمارشی. - م.: میر، 1990.
• تعداد ترکیب ها را به صورت آنلاین محاسبه کنید

بنیاد ویکی مدیا 2010.

ببینید «تعداد ترکیبات» در فرهنگ‌های دیگر چیست:

70 هفتاد 67 68 69 70 71 72 73 40 50 60 70 80 90 100 فاکتورسازی: 2×5×7 نت رومی: LXX باینری: 100 0110 ... ویکی پدیا

عدد نور، یک عدد شرطی که به طور منحصر به فرد خارجی را بیان می کند شرایط در حین عکاسی (معمولاً روشنایی سوژه و حساسیت به نور مواد عکاسی مورد استفاده). هر مقدار E.h را می توان چندین بار انتخاب کرد. عدد دیافراگم ترکیبی... ... فرهنگ لغت بزرگ دایره المعارفی پلی تکنیک

شکلی از عدد که دو شی را هم در رابطه با یک شیء واحد و هم در رابطه با بسیاری از اشیاء متمایز می کند. این شکل در روسی مدرن وجود ندارد، اما بقایای تأثیر آن باقی مانده است. بنابراین، ترکیب دو جدول (ر.ک. جمع... ... فرهنگ اصطلاحات زبانشناسی

ریاضیات ترکیبی، ترکیبیات، شاخه ای از ریاضیات که به حل مسائل مربوط به انتخاب و ترتیب عناصر یک مجموعه معین، معمولا متناهی، مطابق با قوانین داده شده اختصاص دارد. هر یک از این قوانین روش ساخت را تعیین می کند... ... دایره المعارف ریاضی

در ترکیبات، ترکیب by مجموعه ای از عناصر است که از یک مجموعه معین حاوی عناصر مختلف انتخاب شده اند. مجموعه هایی که فقط در ترتیب عناصر متفاوت هستند (اما نه در ترکیب) یکسان در نظر گرفته می شوند، این ترکیبات ... ... ویکی پدیا

مشغول مطالعه حوادثی است که وقوع آنها با قطعیت مشخص نیست. این به ما امکان می‌دهد منطقی بودن انتظار وقوع برخی رویدادها را در مقایسه با سایر رویدادها قضاوت کنیم، اگرچه تخصیص مقادیر عددی به احتمالات رویدادها اغلب غیر ضروری است. دایره المعارف کولیر

1) همان تجزیه و تحلیل ترکیبی ریاضی. 2) بخشی از ریاضیات ابتدایی مرتبط با مطالعه تعداد ترکیبات، مشروط به شرایط خاص، که می تواند از یک مجموعه متناهی معین از اشیاء تشکیل شود... ... دایره المعارف بزرگ شوروی

- (پارادوکسوهای یونانی غیرمنتظره، عجیب) به معنای وسیع: عبارتی که به شدت از عقاید ثابت و پذیرفته شده عمومی متفاوت است، انکار آنچه "بی قید و شرط صحیح" به نظر می رسد. به معنای محدودتر، دو عبارت متضاد، برای... ... دایره المعارف فلسفی

- (یا اصل شامل و حذف) یک فرمول ترکیبی که به شما امکان می دهد کاردینالیته اتحاد تعداد محدودی از مجموعه های محدود را تعیین کنید که در حالت کلی می توانند با یکدیگر تلاقی ... ویکی پدیا

یک نظریه ریاضی مربوط به تعیین تعداد روش های مختلف توزیع اشیاء داده شده به ترتیب مشخص. به ویژه در نظریه معادلات و نظریه احتمال اهمیت دارد. ساده ترین کارها از این دست عبارتند از... ... فرهنگ لغت دایره المعارف F.A. بروکهاوس و I.A. افرون

کتاب ها

• کتاب درسی انگلیسی. در دو قسمت. قسمت 2، N. A. Bonk، G. A. Kotiy، N. A. Lukyanova. این کتاب قسمت دوم کتاب درسی زبان انگلیسی است. شامل 20 درس، کتاب گرامر درس به درس و جداول گرامر مرجع. حجم واژگانی جدید...