Combination - Wikipedia

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Combination - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"b02e078a-de57-4771-aa29-89f776bb5cca","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Combination","wgTitle":"Combination","wgCurRevisionId":1259007196,"wgRevisionId":1259007196,"wgArticleId":5308,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 Chinese-language sources (zh)","Articles with short description","Short description is different from Wikidata","Use dmy dates from April 2022","Combinatorics"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Combination","wgRelevantArticleId":5308,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false ,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q202805","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader", "ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Combination - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Combination"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Combination&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Combination"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Combination rootpage-Combination skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Combination" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Combination" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Combination" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Combination" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Number_of_k-combinations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Number_of_k-combinations"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Number of <i>k</i>-combinations</span> </div> </a> <button aria-controls="toc-Number_of_k-combinations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Number of <i>k</i>-combinations subsection</span> </button> <ul id="toc-Number_of_k-combinations-sublist" class="vector-toc-list"> <li id="toc-Example_of_counting_combinations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example_of_counting_combinations"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Example of counting combinations</span> </div> </a> <ul id="toc-Example_of_counting_combinations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Enumerating_k-combinations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Enumerating_k-combinations"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Enumerating <i>k</i>-combinations</span> </div> </a> <ul id="toc-Enumerating_k-combinations-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Number_of_combinations_with_repetition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Number_of_combinations_with_repetition"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Number of combinations with repetition</span> </div> </a> <button aria-controls="toc-Number_of_combinations_with_repetition-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Number of combinations with repetition subsection</span> </button> <ul id="toc-Number_of_combinations_with_repetition-sublist" class="vector-toc-list"> <li id="toc-Example_of_counting_multisubsets" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example_of_counting_multisubsets"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Example of counting multisubsets</span> </div> </a> <ul id="toc-Example_of_counting_multisubsets-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Number_of_k-combinations_for_all_k" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Number_of_k-combinations_for_all_k"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Number of <i>k</i>-combinations for all <i>k</i></span> </div> </a> <ul id="toc-Number_of_k-combinations_for_all_k-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Probability:_sampling_a_random_combination" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Probability:_sampling_a_random_combination"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Probability: sampling a random combination</span> </div> </a> <ul id="toc-Probability:_sampling_a_random_combination-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Number_of_ways_to_put_objects_into_bins" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Number_of_ways_to_put_objects_into_bins"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Number of ways to put objects into bins</span> </div> </a> <ul id="toc-Number_of_ways_to_put_objects_into_bins-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Combination</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 55 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-55" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">55 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-af mw-list-item"><a href="https://af.wikipedia.org/wiki/Kombinasie" title="Kombinasie – Afrikaans" lang="af" hreflang="af" data-title="Kombinasie" data-language-autonym="Afrikaans" data-language-local-name="Afrikaans" class="interlanguage-link-target"><span>Afrikaans</span></a></li><li class="interlanguage-link interwiki-am mw-list-item"><a href="https://am.wikipedia.org/wiki/%E1%88%B5%E1%89%A5%E1%88%B0%E1%89%A3" title="ስብሰባ – Amharic" lang="am" hreflang="am" data-title="ስብሰባ" data-language-autonym="አማርኛ" data-language-local-name="Amharic" class="interlanguage-link-target"><span>አማርኛ</span></a></li><li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AA%D9%88%D9%81%D9%8A%D9%82_(%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A7%D8%AA)" title="توفيق (رياضيات) – Arabic" lang="ar" hreflang="ar" data-title="توفيق (رياضيات)" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Kombinezon" title="Kombinezon – Azerbaijani" lang="az" hreflang="az" data-title="Kombinezon" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%B8%E0%A6%AE%E0%A6%BE%E0%A6%AC%E0%A7%87%E0%A6%B6_(%E0%A6%97%E0%A6%A3%E0%A6%BF%E0%A6%A4)" title="সমাবেশ (গণিত) – Bangla" lang="bn" hreflang="bn" data-title="সমাবেশ (গণিত)" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-be mw-list-item"><a href="https://be.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B0%D0%BB%D1%83%D1%87%D1%8D%D0%BD%D0%BD%D0%B5_(%D0%BA%D0%B0%D0%BC%D0%B1%D1%96%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D1%8B%D0%BA%D0%B0)" title="Спалучэнне (камбінаторыка) – Belarusian" lang="be" hreflang="be" data-title="Спалучэнне (камбінаторыка)" data-language-autonym="Беларуская" data-language-local-name="Belarusian" class="interlanguage-link-target"><span>Беларуская</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" title="Комбинация (математика) – Bulgarian" lang="bg" hreflang="bg" data-title="Комбинация (математика)" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-cv mw-list-item"><a href="https://cv.wikipedia.org/wiki/%D0%9F%D0%B0%D0%B9%D0%BB%D0%B0%D1%88%D1%83" title="Пайлашу – Chuvash" lang="cv" hreflang="cv" data-title="Пайлашу" data-language-autonym="Чӑвашла" data-language-local-name="Chuvash" class="interlanguage-link-target"><span>Чӑвашла</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Kombinace" title="Kombinace – Czech" lang="cs" hreflang="cs" data-title="Kombinace" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Kombination_(Kombinatorik)" title="Kombination (Kombinatorik) – German" lang="de" hreflang="de" data-title="Kombination (Kombinatorik)" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Kombinatsioon" title="Kombinatsioon – Estonian" lang="et" hreflang="et" data-title="Kombinatsioon" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A3%CF%85%CE%BD%CE%B4%CF%85%CE%B1%CF%83%CE%BC%CF%8C%CF%82_(%CE%BC%CE%B1%CE%B8%CE%B7%CE%BC%CE%B1%CF%84%CE%B9%CE%BA%CE%AC)" title="Συνδυασμός (μαθηματικά) – Greek" lang="el" hreflang="el" data-title="Συνδυασμός (μαθηματικά)" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Combinaci%C3%B3n_(matem%C3%A1ticas)" title="Combinación (matemáticas) – Spanish" lang="es" hreflang="es" data-title="Combinación (matemáticas)" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Kombina%C4%B5o_(kombinatoriko)" title="Kombinaĵo (kombinatoriko) – Esperanto" lang="eo" hreflang="eo" data-title="Kombinaĵo (kombinatoriko)" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Konbinazio_(konbinatoria)" title="Konbinazio (konbinatoria) – Basque" lang="eu" hreflang="eu" data-title="Konbinazio (konbinatoria)" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%B1%DA%A9%DB%8C%D8%A8_(%D8%B1%DB%8C%D8%A7%D8%B6%DB%8C)" title="ترکیب (ریاضی) – Persian" lang="fa" hreflang="fa" data-title="ترکیب (ریاضی)" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Combinaison_sans_r%C3%A9p%C3%A9tition" title="Combinaison sans répétition – French" lang="fr" hreflang="fr" data-title="Combinaison sans répétition" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Combinaci%C3%B3ns" title="Combinacións – Galician" lang="gl" hreflang="gl" data-title="Combinacións" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9" title="조합 – Korean" lang="ko" hreflang="ko" data-title="조합" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B6%D5%B8%D6%82%D5%A3%D5%B8%D6%80%D5%A4%D5%B8%D6%82%D5%A9%D5%B5%D5%B8%D6%82%D5%B6_(%D5%AF%D5%B8%D5%B4%D5%A2%D5%AB%D5%B6%D5%A1%D5%BF%D5%B8%D6%80%D5%AB%D5%AF%D5%A1)" title="Զուգորդություն (կոմբինատորիկա) – Armenian" lang="hy" hreflang="hy" data-title="Զուգորդություն (կոմբինատորիկա)" data-language-autonym="Հայերեն" data-language-local-name="Armenian" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%B8%E0%A4%82%E0%A4%9A%E0%A4%AF_(%E0%A4%97%E0%A4%A3%E0%A4%BF%E0%A4%A4)" title="संचय (गणित) – Hindi" lang="hi" hreflang="hi" data-title="संचय (गणित)" data-language-autonym="हिन्दी" data-language-local-name="Hindi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Kombinasi" title="Kombinasi – Indonesian" lang="id" hreflang="id" data-title="Kombinasi" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-is mw-list-item"><a href="https://is.wikipedia.org/wiki/Samantekt" title="Samantekt – Icelandic" lang="is" hreflang="is" data-title="Samantekt" data-language-autonym="Íslenska" data-language-local-name="Icelandic" class="interlanguage-link-target"><span>Íslenska</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Combinazione" title="Combinazione – Italian" lang="it" hreflang="it" data-title="Combinazione" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A6%D7%99%D7%A8%D7%95%D7%A3_(%D7%A7%D7%95%D7%9E%D7%91%D7%99%D7%A0%D7%98%D7%95%D7%A8%D7%99%D7%A7%D7%94)" title="צירוף (קומבינטוריקה) – Hebrew" lang="he" hreflang="he" data-title="צירוף (קומבינטוריקה)" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%B8%E0%B2%82%E0%B2%AF%E0%B3%8B%E0%B2%9C%E0%B2%A8%E0%B3%86%E0%B2%97%E0%B2%B3%E0%B3%81" title="ಸಂಯೋಜನೆಗಳು – Kannada" lang="kn" hreflang="kn" data-title="ಸಂಯೋಜನೆಗಳು" data-language-autonym="ಕನ್ನಡ" data-language-local-name="Kannada" class="interlanguage-link-target"><span>ಕನ್ನಡ</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Kombin%C4%81cija" title="Kombinācija – Latvian" lang="lv" hreflang="lv" data-title="Kombinācija" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Deriniai" title="Deriniai – Lithuanian" lang="lt" hreflang="lt" data-title="Deriniai" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Kombin%C3%A1ci%C3%B3" title="Kombináció – Hungarian" lang="hu" hreflang="hu" data-title="Kombináció" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%86%D0%B8%D1%98%D0%B0" title="Комбинација – Macedonian" lang="mk" hreflang="mk" data-title="Комбинација" data-language-autonym="Македонски" data-language-local-name="Macedonian" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Combinatie_(wiskunde)" title="Combinatie (wiskunde) – Dutch" lang="nl" hreflang="nl" data-title="Combinatie (wiskunde)" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B_(%E6%95%B0%E5%AD%A6)" title="組合せ (数学) – Japanese" lang="ja" hreflang="ja" data-title="組合せ (数学)" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/Kombinasjon_i_matematikk" title="Kombinasjon i matematikk – Norwegian Nynorsk" lang="nn" hreflang="nn" data-title="Kombinasjon i matematikk" data-language-autonym="Norsk nynorsk" data-language-local-name="Norwegian Nynorsk" class="interlanguage-link-target"><span>Norsk nynorsk</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Kombinacja_bez_powt%C3%B3rze%C5%84" title="Kombinacja bez powtórzeń – Polish" lang="pl" hreflang="pl" data-title="Kombinacja bez powtórzeń" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Combina%C3%A7%C3%A3o" title="Combinação – Portuguese" lang="pt" hreflang="pt" data-title="Combinação" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Combinare" title="Combinare – Romanian" lang="ro" hreflang="ro" data-title="Combinare" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5" title="Сочетание – Russian" lang="ru" hreflang="ru" data-title="Сочетание" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sah mw-list-item"><a href="https://sah.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5" title="Сочетание – Yakut" lang="sah" hreflang="sah" data-title="Сочетание" data-language-autonym="Саха тыла" data-language-local-name="Yakut" class="interlanguage-link-target"><span>Саха тыла</span></a></li><li class="interlanguage-link interwiki-sq mw-list-item"><a href="https://sq.wikipedia.org/wiki/Kombinacioni" title="Kombinacioni – Albanian" lang="sq" hreflang="sq" data-title="Kombinacioni" data-language-autonym="Shqip" data-language-local-name="Albanian" class="interlanguage-link-target"><span>Shqip</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Combination_(mathematics)" title="Combination (mathematics) – Simple English" lang="en-simple" hreflang="en-simple" data-title="Combination (mathematics)" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Kombin%C3%A1cia_(kombinatorika)" title="Kombinácia (kombinatorika) – Slovak" lang="sk" hreflang="sk" data-title="Kombinácia (kombinatorika)" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Kombinacija_(matematika)" title="Kombinacija (matematika) – Slovenian" lang="sl" hreflang="sl" data-title="Kombinacija (matematika)" data-language-autonym="Slovenščina" data-language-local-name="Slovenian" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-ckb mw-list-item"><a href="https://ckb.wikipedia.org/wiki/%DA%AF%D9%88%D9%86%D8%AC%DB%8E%D9%86" title="گونجێن – Central Kurdish" lang="ckb" hreflang="ckb" data-title="گونجێن" data-language-autonym="کوردی" data-language-local-name="Central Kurdish" class="interlanguage-link-target"><span>کوردی</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%86%D0%B8%D1%98%D0%B0" title="Комбинација – Serbian" lang="sr" hreflang="sr" data-title="Комбинација" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Kombinacija" title="Kombinacija – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Kombinacija" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Kombinaatio" title="Kombinaatio – Finnish" lang="fi" hreflang="fi" data-title="Kombinaatio" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Kombination_(matematik)" title="Kombination (matematik) – Swedish" lang="sv" hreflang="sv" data-title="Kombination (matematik)" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%9A%E0%AF%87%E0%AE%B0%E0%AF%8D%E0%AE%B5%E0%AF%81_(%E0%AE%95%E0%AE%A3%E0%AE%BF%E0%AE%A4%E0%AE%AE%E0%AF%8D)" title="சேர்வு (கணிதம்) – Tamil" lang="ta" hreflang="ta" data-title="சேர்வு (கணிதம்)" data-language-autonym="தமிழ்" data-language-local-name="Tamil" class="interlanguage-link-target"><span>தமிழ்</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%88%E0%B8%B1%E0%B8%94%E0%B8%AB%E0%B8%A1%E0%B8%B9%E0%B9%88" title="การจัดหมู่ – Thai" lang="th" hreflang="th" data-title="การจัดหมู่" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Kombinasyon" title="Kombinasyon – Turkish" lang="tr" hreflang="tr" data-title="Kombinasyon" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D1%96%D0%BD%D0%B0%D1%86%D1%96%D1%8F_(%D0%BA%D0%BE%D0%BC%D0%B1%D1%96%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0)" title="Комбінація (комбінаторика) – Ukrainian" lang="uk" hreflang="uk" data-title="Комбінація (комбінаторика)" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-ur mw-list-item"><a href="https://ur.wikipedia.org/wiki/%D8%AA%D9%88%D9%84%DB%8C%D9%81" title="تولیف – Urdu" lang="ur" hreflang="ur" data-title="تولیف" data-language-autonym="اردو" data-language-local-name="Urdu" class="interlanguage-link-target"><span>اردو</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/T%E1%BB%95_h%E1%BB%A3p_(to%C3%A1n_h%E1%BB%8Dc)" title="Tổ hợp (toán học) – Vietnamese" lang="vi" hreflang="vi" data-title="Tổ hợp (toán học)" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-classical mw-list-item"><a href="https://zh-classical.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E5%AD%B8" title="組合學 – Literary Chinese" lang="lzh" hreflang="lzh" data-title="組合學" data-language-autonym="文言" data-language-local-name="Literary Chinese" class="interlanguage-link-target"><span>文言</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E7%B5%84%E5%90%88" title="組合 – Chinese" lang="zh" hreflang="zh" data-title="組合" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q202805#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Combination" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Combination" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Combination"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Combination&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Combination&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Combination"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Combination&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Combination&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Combination" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Combination" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Combination&oldid=1259007196" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Combination&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Combination&id=1259007196&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCombination"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCombination"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Combination&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Combination&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Combinations_(combinatorics)" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q202805" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about the mathematics of selecting part of a collection. For other uses, see <a href="/wiki/Combination_(disambiguation)" class="mw-disambig" title="Combination (disambiguation)">Combination (disambiguation)</a>.</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">"COMBIN" redirects here. For other uses, see <a href="/wiki/Combin_(disambiguation)" class="mw-redirect mw-disambig" title="Combin (disambiguation)">Combin (disambiguation)</a>.</div> <div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Selection of items from a set</div> <p> In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, a <b>combination</b> is a selection of items from a <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">set</a> that has distinct members, such that the order of selection does not matter (unlike <a href="/wiki/Permutation" title="Permutation">permutations</a>). For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a <i>k</i>-combination of a set <i>S</i> is a subset of <i>k</i> distinct elements of <i>S</i>. So, two combinations are identical <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> each combination has the same members. (The arrangement of the members in each set does not matter.) If the set has <i>n</i> elements, the number of <i>k</i>-combinations, denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(n,k)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C(n,k)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0156b716afda8988cc95572986f147917c3b8fe5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.216ex; height:2.843ex;" alt="{\displaystyle C(n,k)}"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{k}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fee549e664007a80759a5ce8e696d54f4fd996d1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.016ex; height:2.843ex;" alt="{\displaystyle C_{k}^{n}}"></span>, is equal to the <a href="/wiki/Binomial_coefficient" title="Binomial coefficient">binomial coefficient</a> </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>⋯</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>k</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>⋯</mo> <mn>1</mn> </mrow> </mfrac> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/08bdf0fff474c26293414f9eb01ab4bc73ef941f" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:32.755ex; height:6.509ex;" alt="{\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}"></span> </p><p>which can be written using <a href="/wiki/Factorial" title="Factorial">factorials</a> as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mi>k</mi> <mo>!</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/813f7124a61dac205542db3f8491b36cb306453a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.008ex; height:4.343ex;" alt="{\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}}"></span> whenever <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\leq n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>≤</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\leq n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/621f658bb51d7caac329d29e9bf435361813777f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.704ex; height:2.343ex;" alt="{\displaystyle k\leq n}"></span>, and which is zero when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k>n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>></mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k>n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66e81682bf174c978e9008ffb557ba4da2cf7478" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.704ex; height:2.176ex;" alt="{\displaystyle k>n}"></span>. This formula can be derived from the fact that each <i>k</i>-combination of a set <i>S</i> of <i>n</i> members has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/949e312c9bf9a9a5e641c1db1b1d7c6f0425b536" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.858ex; height:2.176ex;" alt="{\displaystyle k!}"></span> permutations so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>=</mo> <msubsup> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>×</mo> <mi>k</mi> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc9443cccae5758c6dfd2b47a27a4a5f6be83f30" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.853ex; height:2.843ex;" alt="{\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}^{n}=P_{k}^{n}/k!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>=</mo> <msubsup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>k</mi> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{k}^{n}=P_{k}^{n}/k!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e9422de6ab522ab8adbfb853bb60afb6245df2f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.175ex; height:3.009ex;" alt="{\displaystyle C_{k}^{n}=P_{k}^{n}/k!}"></span>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The set of all <i>k</i>-combinations of a set <i>S</i> is often denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\binom {S}{k}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>S</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \textstyle {\binom {S}{k}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe7e42ea65abdc7f06cd4d253cd9948f244d6545" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.19ex; height:3.509ex;" alt="{\displaystyle \textstyle {\binom {S}{k}}}"></span>. </p><p>A combination is a combination of <i>n</i> things taken <i>k</i> at a time <i>without repetition</i>. To refer to combinations in which repetition is allowed, the terms <i>k</i>-combination with repetition, <i>k</i>-<a href="/wiki/Multiset" title="Multiset">multiset</a>,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> or <i>k</i>-selection,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> are often used.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> If, in the above example, it were possible to have two of any one kind of fruit there would be 3 more 2-selections: one with two apples, one with two oranges, and one with two pears. </p><p>Although the set of three fruits was small enough to write a complete list of combinations, this becomes impractical as the size of the set increases. For example, a <a href="/wiki/Hand_(poker)" class="mw-redirect" title="Hand (poker)">poker hand</a> can be described as a 5-combination (<i>k</i> = 5) of cards from a 52 card deck (<i>n</i> = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Number_of_k-combinations">Number of <i>k</i>-combinations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=1" title="Edit section: Number of k-combinations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Binomial_coefficient" title="Binomial coefficient">Binomial coefficient</a></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">"COMBIN" redirects here. For other uses, see <a href="/wiki/Combin_(disambiguation)" class="mw-redirect mw-disambig" title="Combin (disambiguation)">Combin (disambiguation)</a>.</div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Combinations_without_repetition;_5_choose_3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Combinations_without_repetition%3B_5_choose_3.svg/220px-Combinations_without_repetition%3B_5_choose_3.svg.png" decoding="async" width="220" height="213" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Combinations_without_repetition%3B_5_choose_3.svg/330px-Combinations_without_repetition%3B_5_choose_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/65/Combinations_without_repetition%3B_5_choose_3.svg/440px-Combinations_without_repetition%3B_5_choose_3.svg.png 2x" data-file-width="250" data-file-height="242" /></a><figcaption>3-element subsets of a 5-element set</figcaption></figure> <p>The number of <i>k</i>-combinations from a given set <i>S</i> of <i>n</i> elements is often denoted in elementary combinatorics texts by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(n,k)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C(n,k)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0156b716afda8988cc95572986f147917c3b8fe5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.216ex; height:2.843ex;" alt="{\displaystyle C(n,k)}"></span>, or by a variation such as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{k}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fee549e664007a80759a5ce8e696d54f4fd996d1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.016ex; height:2.843ex;" alt="{\displaystyle C_{k}^{n}}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {}_{n}C_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {}_{n}C_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/846dc3e79abc1db020c2588140a418703f524e9d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.969ex; height:2.509ex;" alt="{\displaystyle {}_{n}C_{k}}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {}^{n}C_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {}^{n}C_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10255ea6f6be016a6ab4d8910c53209a4b9ee1bd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.969ex; height:2.676ex;" alt="{\displaystyle {}^{n}C_{k}}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n,k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{n,k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bdb416527a2744b763f4052853d934d6777dfd11" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.194ex; height:2.843ex;" alt="{\displaystyle C_{n,k}}"></span> or even <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{n}^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b088b67f00e4739e57c658ac7dd5913898013ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.887ex; height:2.843ex;" alt="{\displaystyle C_{n}^{k}}"></span><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> (the last form is standard in French, Romanian, Russian, and Chinese texts).<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> The same number however occurs in many other mathematical contexts, where it is denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{k}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{k}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/206415d3742167e319b2e52c2ca7563b799abad7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.116ex; height:3.176ex;" alt="{\displaystyle {\tbinom {n}{k}}}"></span> (often read as "<i>n</i> choose <i>k</i>"); notably it occurs as a coefficient in the <a href="/wiki/Binomial_formula" class="mw-redirect" title="Binomial formula">binomial formula</a>, hence its name binomial coefficient. One can define <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{k}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{k}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/206415d3742167e319b2e52c2ca7563b799abad7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.116ex; height:3.176ex;" alt="{\displaystyle {\tbinom {n}{k}}}"></span> for all natural numbers <i>k</i> at once by the relation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>X</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>≥</mo> <mn>0</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d151361d61b9297641517b2031ad50a636c9a46" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:24.399ex; height:7.009ex;" alt="{\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}"></span> </p><p>from which it is clear that </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mn>0</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>n</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mn>1</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60a924fc85da7e28152c97bafee42deb8064de58" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.638ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}"></span> </p><p>and further </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4f2bc3e21cb9f37945844d08f67b177b20cabda3" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.077ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{k}}=0}"></span> </p><p>for <i>k</i> > <i>n</i>. </p><p>To see that these coefficients count <i>k</i>-combinations from <i>S</i>, one can first consider a collection of <i>n</i> distinct variables <i>X</i><sub><i>s</i></sub> labeled by the elements <i>s</i> of <i>S</i>, and expand the <a href="/wiki/Multiplication" title="Multiplication">product</a> over all elements of <i>S</i>: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \prod _{s\in S}(1+X_{s});}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munder> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> <mo>∈</mo> <mi>S</mi> </mrow> </munder> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>;</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \prod _{s\in S}(1+X_{s});}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec0e4e9ec6ebfdb9966d04ec9fc3a9ea4b214c8e" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:12.356ex; height:5.676ex;" alt="{\displaystyle \prod _{s\in S}(1+X_{s});}"></span> </p><p>it has 2<sup><i>n</i></sup> distinct terms corresponding to all the subsets of <i>S</i>, each subset giving the product of the corresponding variables <i>X</i><sub><i>s</i></sub>. Now setting all of the <i>X</i><sub><i>s</i></sub> equal to the unlabeled variable <i>X</i>, so that the product becomes <span class="nowrap">(1 + <i>X</i>)<sup><i>n</i></sup></span>, the term for each <i>k</i>-combination from <i>S</i> becomes <i>X</i><sup><i>k</i></sup>, so that the coefficient of that power in the result equals the number of such <i>k</i>-combinations. </p><p>Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up to <span class="nowrap">(1 + <i>X</i>)<sup><i>n</i></sup></span>, one can use (in addition to the basic cases already given) the recursion relation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ad549fc68ce9889ccb2b4cd29f105c9436926f7" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:29.039ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}"></span> </p><p>for 0 < <i>k</i> < <i>n</i>, which follows from <span class="nowrap">(1 + <i>X</i>)<sup><i>n</i></sup> </span>=<span class="nowrap"> (1 + <i>X</i>)<sup><i>n</i> − 1</sup>(1 + <i>X</i>)</span>; this leads to the construction of <a href="/wiki/Pascal%27s_triangle" title="Pascal's triangle">Pascal's triangle</a>. </p><p>For determining an individual binomial coefficient, it is more practical to use the formula </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>⋯</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>k</mi> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1a558ebcf6018fcd6e7c5702dbacf1eb388b3d61" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:39.962ex; height:6.343ex;" alt="{\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}"></span> </p><p>The <a href="/wiki/Numerator" class="mw-redirect" title="Numerator">numerator</a> gives the number of <a href="/wiki/Permutation#k-permutations_of_n" title="Permutation"><i>k</i>-permutations</a> of <i>n</i>, i.e., of sequences of <i>k</i> distinct elements of <i>S</i>, while the <a href="/wiki/Denominator" class="mw-redirect" title="Denominator">denominator</a> gives the number of such <i>k</i>-permutations that give the same <i>k</i>-combination when the order is ignored. </p><p>When <i>k</i> exceeds <i>n</i>/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mrow> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ab2a3c255ba72d0904e56626a13e882dda50112" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.429ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}"></span> </p><p>for 0 ≤ <i>k</i> ≤ <i>n</i>. This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms of <i>k</i>-combinations by taking the <a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">complement</a> of such a combination, which is an <span class="nowrap">(<i>n</i> − <i>k</i>)</span>-combination. </p><p>Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mi>k</mi> <mo>!</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f4e3f6d2dc3075f5569c82118fad11c32dff393" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:19.158ex; height:6.343ex;" alt="{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}"></span> </p><p>where <i>n</i>! denotes the <a href="/wiki/Factorial" title="Factorial">factorial</a> of <i>n</i>. It is obtained from the previous formula by multiplying denominator and numerator by <span class="nowrap">(<i>n</i> − <i>k</i>)</span>!, so it is certainly computationally less efficient than that formula. </p><p>The last formula can be understood directly, by considering the <i>n</i>! permutations of all the elements of <i>S</i>. Each such permutation gives a <i>k</i>-combination by selecting its first <i>k</i> elements. There are many duplicate selections: any combined permutation of the first <i>k</i> elements among each other, and of the final (<i>n</i> − <i>k</i>) elements among each other produces the same combination; this explains the division in the formula. </p><p>From the above formulas follow relations between adjacent numbers in Pascal's triangle in all three directions: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>{</mo> <mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false"> <mtr> <mtd> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> <mi>k</mi> </mfrac> </mrow> </mstyle> </mtd> <mtd> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>if </mtext> </mrow> <mi>k</mi> <mo>></mo> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <mrow> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mrow> </mfrac> </mrow> </mstyle> </mtd> <mtd> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>if </mtext> </mrow> <mi>k</mi> <mo><</mo> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <mi>k</mi> </mfrac> </mrow> </mstyle> </mtd> <mtd> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>if </mtext> </mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>></mo> <mn>0</mn> </mtd> </mtr> </mtable> <mo fence="true" stretchy="true" symmetric="true"></mo> </mrow> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f3a23aa6b8933af0e9f4f996fb4c739d8d0b57f3" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.505ex; width:44.785ex; height:18.176ex;" alt="{\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.}"></span> </p><p>Together with the basic cases <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mn>0</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> <mo>=</mo> <mn>1</mn> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>n</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/02a799c900e4739328c05e6772c14e48001dcd8b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:13.591ex; height:3.343ex;" alt="{\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}"></span>, these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), of <i>k</i>-combinations of sets of growing sizes, and of combinations with a complement of fixed size <span class="nowrap"><i>n</i> − <i>k</i></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Example_of_counting_combinations">Example of counting combinations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=2" title="Edit section: Example of counting combinations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>As a specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mn>52</mn> <mn>5</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>52</mn> <mo>×</mo> <mn>51</mn> <mo>×</mo> <mn>50</mn> <mo>×</mo> <mn>49</mn> <mo>×</mo> <mn>48</mn> </mrow> <mrow> <mn>5</mn> <mo>×</mo> <mn>4</mn> <mo>×</mo> <mn>3</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>1</mn> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>311,875,200</mn> <mn>120</mn> </mfrac> </mrow> <mo>=</mo> <mn>2,598,960.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc23290c935c895f42918bf2486ec5e8b70045bd" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:61.533ex; height:6.176ex;" alt="{\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}"></span> </p><p>Alternatively one may use the formula in terms of factorials and cancel the factors in the numerator against parts of the factors in the denominator, after which only multiplication of the remaining factors is required: <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left" rowspacing="0.8em 0.8em 0.8em 0.8em 0.8em 0.3em" columnspacing="0em 0em 0em 0em" displaystyle="true"> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mn>52</mn> <mn>5</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>52</mn> <mo>!</mo> </mrow> <mrow> <mn>5</mn> <mo>!</mo> <mn>47</mn> <mo>!</mo> </mrow> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>52</mn> <mo>×</mo> <mn>51</mn> <mo>×</mo> <mn>50</mn> <mo>×</mo> <mn>49</mn> <mo>×</mo> <mn>48</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>47</mn> <mo>!</mo> </menclose> </mrow> </mrow> <mrow> <mn>5</mn> <mo>×</mo> <mn>4</mn> <mo>×</mo> <mn>3</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>1</mn> </menclose> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>47</mn> <mo>!</mo> </menclose> </mrow> </mrow> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>52</mn> <mo>×</mo> <mn>51</mn> <mo>×</mo> <mn>50</mn> <mo>×</mo> <mn>49</mn> <mo>×</mo> <mn>48</mn> </mrow> <mrow> <mn>5</mn> <mo>×</mo> <mn>4</mn> <mo>×</mo> <mn>3</mn> <mo>×</mo> <mn>2</mn> </mrow> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <mn>26</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>2</mn> </menclose> </mrow> <mo stretchy="false">)</mo> <mo>×</mo> <mo stretchy="false">(</mo> <mn>17</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>3</mn> </menclose> </mrow> <mo stretchy="false">)</mo> <mo>×</mo> <mo stretchy="false">(</mo> <mn>10</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>5</mn> </menclose> </mrow> <mo stretchy="false">)</mo> <mo>×</mo> <mn>49</mn> <mo>×</mo> <mo stretchy="false">(</mo> <mn>12</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>4</mn> </menclose> </mrow> <mo stretchy="false">)</mo> </mrow> <mrow> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>5</mn> </menclose> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>4</mn> </menclose> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>3</mn> </menclose> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <menclose notation="updiagonalstrike"> <mn>2</mn> </menclose> </mrow> </mrow> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>26</mn> <mo>×</mo> <mn>17</mn> <mo>×</mo> <mn>10</mn> <mo>×</mo> <mn>49</mn> <mo>×</mo> <mn>12</mn> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mn>2,598,960.</mn> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5541f14cc4ca51756ec76a67071c816f69070dfa" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -19.005ex; width:61.777ex; height:39.176ex;" alt="{\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}"></span> </p><p>Another alternative computation, equivalent to the first, is based on writing </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>0</mn> <mo stretchy="false">)</mo> </mrow> <mn>1</mn> </mfrac> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </mfrac> </mrow> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> <mi>k</mi> </mfrac> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/804a276361ac74dff4c556839a829cac04825fff" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:60.679ex; height:6.343ex;" alt="{\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}"></span> </p><p>which gives </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mn>52</mn> <mn>5</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>52</mn> <mn>1</mn> </mfrac> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>51</mn> <mn>2</mn> </mfrac> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>50</mn> <mn>3</mn> </mfrac> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>49</mn> <mn>4</mn> </mfrac> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>48</mn> <mn>5</mn> </mfrac> </mrow> <mo>=</mo> <mn>2,598,960.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f3f5d87031068b75bfec60a8f948f402f4cd6f0a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:49.188ex; height:6.176ex;" alt="{\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.}"></span> </p><p>When evaluated in the following order, <span class="texhtml">52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5</span>, this can be computed using only integer arithmetic. The reason is that when each division occurs, the intermediate result that is produced is itself a binomial coefficient, so no remainders ever occur. </p><p>Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="0.9em 0.9em 0.3em" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mn>52</mn> <mn>5</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mi>k</mi> <mo>!</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>52</mn> <mo>!</mo> </mrow> <mrow> <mn>5</mn> <mo>!</mo> <mo stretchy="false">(</mo> <mn>52</mn> <mo>−</mo> <mn>5</mn> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>52</mn> <mo>!</mo> </mrow> <mrow> <mn>5</mn> <mo>!</mo> <mn>47</mn> <mo>!</mo> </mrow> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mrow> <mn>80</mn> <mo>,</mo> <mn>658</mn> <mo>,</mo> <mn>175</mn> <mo>,</mo> <mn>170</mn> <mo>,</mo> <mn>943</mn> <mo>,</mo> <mn>878</mn> <mo>,</mo> <mn>571</mn> <mo>,</mo> <mn>660</mn> <mo>,</mo> <mn>636</mn> <mo>,</mo> <mn>856</mn> <mo>,</mo> <mn>403</mn> <mo>,</mo> <mn>766</mn> <mo>,</mo> <mn>975</mn> <mo>,</mo> <mn>289</mn> <mo>,</mo> <mn>505</mn> <mo>,</mo> <mn>440</mn> <mo>,</mo> <mn>883</mn> <mo>,</mo> <mn>277</mn> <mo>,</mo> <mn>824</mn> <mo>,</mo> <mn>000</mn> <mo>,</mo> <mn>000</mn> <mo>,</mo> <mn>000</mn> <mo>,</mo> <mn>000</mn> </mrow> <mrow> <mn>120</mn> <mo>×</mo> <mn>258</mn> <mo>,</mo> <mn>623</mn> <mo>,</mo> <mn>241</mn> <mo>,</mo> <mn>511</mn> <mo>,</mo> <mn>168</mn> <mo>,</mo> <mn>180</mn> <mo>,</mo> <mn>642</mn> <mo>,</mo> <mn>964</mn> <mo>,</mo> <mn>355</mn> <mo>,</mo> <mn>153</mn> <mo>,</mo> <mn>611</mn> <mo>,</mo> <mn>979</mn> <mo>,</mo> <mn>969</mn> <mo>,</mo> <mn>197</mn> <mo>,</mo> <mn>632</mn> <mo>,</mo> <mn>389</mn> <mo>,</mo> <mn>120</mn> <mo>,</mo> <mn>000</mn> <mo>,</mo> <mn>000</mn> <mo>,</mo> <mn>000</mn> </mrow> </mfrac> </mstyle> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mn>2,598,960.</mn> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/71b6bc44a40b770f570cabbf47c9476b54bb1d56" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.671ex; width:76.389ex; height:16.509ex;" alt="{\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}}"></span> </p> <div class="mw-heading mw-heading3"><h3 id="Enumerating_k-combinations">Enumerating <i>k</i>-combinations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=3" title="Edit section: Enumerating k-combinations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>One can <a href="/wiki/Enumeration" title="Enumeration">enumerate</a> all <i>k</i>-combinations of a given set <i>S</i> of <i>n</i> elements in some fixed order, which establishes a <a href="/wiki/Bijection" title="Bijection">bijection</a> from an interval of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{k}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{k}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/206415d3742167e319b2e52c2ca7563b799abad7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.116ex; height:3.176ex;" alt="{\displaystyle {\tbinom {n}{k}}}"></span> integers with the set of those <i>k</i>-combinations. Assuming <i>S</i> is itself ordered, for instance <i>S</i> = { 1, 2, ..., <i>n</i> }, there are two natural possibilities for ordering its <i>k</i>-combinations: by comparing their smallest elements first (as in the illustrations above) or by comparing their largest elements first. The latter option has the advantage that adding a new largest element to <i>S</i> will not change the initial part of the enumeration, but just add the new <i>k</i>-combinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely with <i>k</i>-combinations of ever larger sets. If moreover the intervals of the integers are taken to start at 0, then the <i>k</i>-combination at a given place <i>i</i> in the enumeration can be computed easily from <i>i</i>, and the bijection so obtained is known as the <a href="/wiki/Combinatorial_number_system" title="Combinatorial number system">combinatorial number system</a>. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p><p>There are many ways to enumerate <i>k</i> combinations. One way is to track <i>k</i> index numbers of the elements selected, starting with {0 .. <i>k</i>−1} (zero-based) or {1 .. <i>k</i>} (one-based) as the first allowed <i>k</i>-combination. Then, repeatedly move to the next allowed <i>k</i>-combination by incrementing the smallest index number for which this would not create two equal index numbers, at the same time resetting all smaller index numbers to their initial values. </p> <div class="mw-heading mw-heading2"><h2 id="Number_of_combinations_with_repetition">Number of combinations with repetition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=4" title="Edit section: Number of combinations with repetition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Multiset_coefficient" class="mw-redirect" title="Multiset coefficient">Multiset coefficient</a></div> <p>A <i>k</i>-<b>combination with repetitions</b>, or <i>k</i>-<b>multicombination</b>, or <b><a href="/wiki/Multiset" title="Multiset">multisubset</a></b> of size <i>k</i> from a set <i>S</i> of size <i>n</i> is given by a set of <i>k</i> not necessarily distinct elements of <i>S</i>, where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms. In other words, it is a sample of <i>k</i> elements from a set of <i>n</i> elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index to each element of <i>S</i> and think of the elements of <i>S</i> as <i>types</i> of objects, then we can let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e87000dd6142b81d041896a30fe58f0c3acb2158" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}"></span> denote the number of elements of type <i>i</i> in a multisubset. The number of multisubsets of size <i>k</i> is then the number of nonnegative integer (so allowing zero) solutions of the <a href="/wiki/Diophantine_equation" title="Diophantine equation">Diophantine equation</a>:<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <mo>…</mo> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>k</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1ba6b0fac89320983b5b374fc750e3f9bff2de" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:23.517ex; height:2.509ex;" alt="{\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}"></span> </p><p>If <i>S</i> has <i>n</i> elements, the number of such <i>k</i>-multisubsets is denoted by </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> </mrow> <mo>)</mo> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a1036e7fd2784e9fbea9e4c6f45ceec53ac34d9d" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.723ex; height:6.176ex;" alt="{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}"></span> </p><p>a notation that is analogous to the <a href="/wiki/Binomial_coefficient" title="Binomial coefficient">binomial coefficient</a> which counts <i>k</i>-subsets. This expression, <i>n</i> multichoose <i>k</i>,<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> can also be given in terms of binomial coefficients: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mi>n</mi> <mo>+</mo> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de5f3a99048a07d41c50dee05a71a239a78f64f2" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:23.304ex; height:6.176ex;" alt="{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}"></span> </p><p>This relationship can be easily proved using a representation known as <a href="/wiki/Stars_and_bars_(combinatorics)" title="Stars and bars (combinatorics)">stars and bars</a>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <style data-mw-deduplicate="TemplateStyles:r1214851843">.mw-parser-output .hidden-begin{box-sizing:border-box;width:100%;padding:5px;border:none;font-size:95%}.mw-parser-output .hidden-title{font-weight:bold;line-height:1.6;text-align:left}.mw-parser-output .hidden-content{text-align:left}@media all and (max-width:500px){.mw-parser-output .hidden-begin{width:auto!important;clear:none!important;float:none!important}}</style><div class="hidden-begin mw-collapsible mw-collapsible-leftside-toggle mw-collapsed" style=""><div class="hidden-title skin-nightmode-reset-color" style="background:lightgray;">Proof</div><div class="hidden-content mw-collapsible-content" style=""> <p>A solution of the above Diophantine equation can be represented by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a8788bf85d532fa88d1fb25eff6ae382a601c308" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}"></span> <i>stars</i>, a separator (a <i>bar</i>), then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7af1b928f06e4c7e3e8ebfd60704656719bd766" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{2}}"></span> more stars, another separator, and so on. The total number of stars in this representation is <i>k</i> and the number of bars is <i>n</i> - 1 (since a separation into n parts needs n-1 separators). Thus, a string of <i>k</i> + <i>n</i> - 1 (or <i>n</i> + <i>k</i> - 1) symbols (stars and bars) corresponds to a solution if there are <i>k</i> stars in the string. Any solution can be represented by choosing <i>k</i> out of <span class="nowrap"><i>k</i> + <i>n</i> − 1</span> positions to place stars and filling the remaining positions with bars. For example, the solution <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>3</mn> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mn>2</mn> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <mn>0</mn> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>=</mo> <mn>5</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af4708d8e8a3412e99473ab0df330dcf156bbd94" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:29.681ex; height:2.509ex;" alt="{\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}"></span> of the equation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>=</mo> <mn>10</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4364d3e579bb272263b34d1dc513e8c1ff00e3a9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:23.48ex; height:2.509ex;" alt="{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}"></span> (<i>n</i> = 4 and <i>k</i> = 10) can be represented by<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10f99b6113cf67ca14b8de9dec01b5e005bf6110" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.524ex; height:2.843ex;" alt="{\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}"></span> </p><p>The number of such strings is the number of ways to place 10 stars in 13 positions, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mn>13</mn> <mn>10</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mn>13</mn> <mn>3</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mn>286</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9136c79e0122b072a1b5b3a684d6482ca0d6028a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:17.879ex; height:3.509ex;" alt="{\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}"></span> which is the number of 10-multisubsets of a set with 4 elements. </p> </div></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Combinations_with_repetition;_5_multichoose_3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/62/Combinations_with_repetition%3B_5_multichoose_3.svg/370px-Combinations_with_repetition%3B_5_multichoose_3.svg.png" decoding="async" width="370" height="405" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/62/Combinations_with_repetition%3B_5_multichoose_3.svg/555px-Combinations_with_repetition%3B_5_multichoose_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/62/Combinations_with_repetition%3B_5_multichoose_3.svg/740px-Combinations_with_repetition%3B_5_multichoose_3.svg.png 2x" data-file-width="626" data-file-height="685" /></a><figcaption><a href="/wiki/Bijection" title="Bijection">Bijection</a> between 3-subsets of a 7-set (left) and 3-multisets with elements from a 5-set (right).<br />This illustrates that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mn>7</mn> <mn>3</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mn>5</mn> <mn>3</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ba6eaf8db7f16c2e906c65923bd5811b5886c1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:9.583ex; height:3.509ex;" alt="{\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}"></span>.</figcaption></figure> <p>As with binomial coefficients, there are several relationships between these multichoose expressions. For example, for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 1,k\geq 0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>≥</mo> <mn>1</mn> <mo>,</mo> <mi>k</mi> <mo>≥</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\geq 1,k\geq 0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a1c7d5e26380b520cb97d622f6716aa75d1b47ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.162ex; height:2.509ex;" alt="{\displaystyle n\geq 1,k\geq 0}"></span>, </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> </mrow> <mo>)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6c73b231f2fbfa42d5e10c310d8c3f5022d9ceb0" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.513ex; height:6.176ex;" alt="{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}"></span> This identity follows from interchanging the stars and bars in the above representation.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Example_of_counting_multisubsets">Example of counting multisubsets</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=5" title="Edit section: Example of counting multisubsets"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For example, if you have four types of donuts (<i>n</i> = 4) on a menu to choose from and you want three donuts (<i>k</i> = 3), the number of ways to choose the donuts with repetition can be calculated as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mn>4</mn> <mn>3</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mspace width="negativethinmathspace" /> <mspace width="negativethinmathspace" /> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mrow> <mn>4</mn> <mo>+</mo> <mn>3</mn> <mo>−</mo> <mn>1</mn> </mrow> <mn>3</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mn>6</mn> <mn>3</mn> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>6</mn> <mo>×</mo> <mn>5</mn> <mo>×</mo> <mn>4</mn> </mrow> <mrow> <mn>3</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>1</mn> </mrow> </mfrac> </mrow> <mo>=</mo> <mn>20.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/99e27a6af2a02f384c452ea8de8dfc016bd9dfb9" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:48.999ex; height:6.176ex;" alt="{\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}"></span> </p><p>This result can be verified by listing all the 3-multisubsets of the set <i>S</i> = {1,2,3,4}. This is displayed in the following table.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> The second column lists the donuts you actually chose, the third column shows the nonnegative integer solutions <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [x_{1},x_{2},x_{3},x_{4}]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [x_{1},x_{2},x_{3},x_{4}]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cbec11b6cf47c5e117f30ff33ecc05c54e84e9ec" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.931ex; height:2.843ex;" alt="{\displaystyle [x_{1},x_{2},x_{3},x_{4}]}"></span> of the equation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>=</mo> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc08f22c9429eee438027893fd12e10598281f5e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.318ex; height:2.509ex;" alt="{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}"></span> and the last column gives the stars and bars representation of the solutions.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p> <table class="wikitable" style="margin-left: auto; margin-right: auto; border; none"> <tbody><tr> <th>No.</th> <th>3-multiset</th> <th>Eq. solution</th> <th>Stars and bars </th></tr> <tr> <td>1</td> <td>{1,1,1}</td> <td>[3,0,0,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar \bigstar \bigstar |||}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar \bigstar \bigstar |||}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/547e4c2fe9b9ad2d3615e7ecabd04e5f299c1be8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar \bigstar \bigstar |||}"></span> </td></tr> <tr> <td>2</td> <td>{1,1,2}</td> <td>[2,1,0,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar \bigstar |\bigstar ||}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar \bigstar |\bigstar ||}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9f5876e32bcecf1bae8d1e67aa38d0f2d84786c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar \bigstar |\bigstar ||}"></span> </td></tr> <tr> <td>3</td> <td>{1,1,3}</td> <td>[2,0,1,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar \bigstar ||\bigstar |}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar \bigstar ||\bigstar |}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/13a762093e98a37460944de1fa8bddbac788b26b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar \bigstar ||\bigstar |}"></span> </td></tr> <tr> <td>4</td> <td>{1,1,4}</td> <td>[2,0,0,1]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar \bigstar |||\bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar \bigstar |||\bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/91fb18cd66c09a69ad5ace0bfbf924ac75c1d3ec" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar \bigstar |||\bigstar }"></span> </td></tr> <tr> <td>5</td> <td>{1,2,2}</td> <td>[1,2,0,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar |\bigstar \bigstar ||}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar |\bigstar \bigstar ||}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dbb8f7f5c80e0d9e327259b0be8c89e3c5cae04a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar |\bigstar \bigstar ||}"></span> </td></tr> <tr> <td>6</td> <td>{1,2,3}</td> <td>[1,1,1,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar |\bigstar |\bigstar |}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar |\bigstar |\bigstar |}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ef56bd946c762f7895d9a3ea564068233e33b59e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar |\bigstar |\bigstar |}"></span> </td></tr> <tr> <td>7</td> <td>{1,2,4}</td> <td>[1,1,0,1]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar |\bigstar ||\bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar |\bigstar ||\bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2cb150ba29ac9f6668262d5adc33e499158b7a15" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar |\bigstar ||\bigstar }"></span> </td></tr> <tr> <td>8</td> <td>{1,3,3}</td> <td>[1,0,2,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar ||\bigstar \bigstar |}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar ||\bigstar \bigstar |}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0b9553204acb9742dcf97b2bd460fd948e2a6b3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar ||\bigstar \bigstar |}"></span> </td></tr> <tr> <td>9</td> <td>{1,3,4}</td> <td>[1,0,1,1]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar ||\bigstar |\bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar ||\bigstar |\bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5fabbe781b9da6828999c488a5a025d6b6efc594" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar ||\bigstar |\bigstar }"></span> </td></tr> <tr> <td>10</td> <td>{1,4,4}</td> <td>[1,0,0,2]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bigstar |||\bigstar \bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigstar |||\bigstar \bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1cb05d2c8b85ad5947a7f6177aeb135676ab8bdf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle \bigstar |||\bigstar \bigstar }"></span> </td></tr> <tr> <td>11</td> <td>{2,2,2}</td> <td>[0,3,0,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\bigstar \bigstar \bigstar ||}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\bigstar \bigstar \bigstar ||}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4937f8e153e1a62edeee6c2b84e43fe7ead267e9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |\bigstar \bigstar \bigstar ||}"></span> </td></tr> <tr> <td>12</td> <td>{2,2,3}</td> <td>[0,2,1,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\bigstar \bigstar |\bigstar |}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\bigstar \bigstar |\bigstar |}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b18ec6a971bcd47371dceac912e0aceda53ee742" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |\bigstar \bigstar |\bigstar |}"></span> </td></tr> <tr> <td>13</td> <td>{2,2,4}</td> <td>[0,2,0,1]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\bigstar \bigstar ||\bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\bigstar \bigstar ||\bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b0e3b8b39bff8b8794c9e2e3b24da3d284d08e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |\bigstar \bigstar ||\bigstar }"></span> </td></tr> <tr> <td>14</td> <td>{2,3,3}</td> <td>[0,1,2,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\bigstar |\bigstar \bigstar |}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\bigstar |\bigstar \bigstar |}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a02286e57a98b67e963f9d22da6b72c6536cc52" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |\bigstar |\bigstar \bigstar |}"></span> </td></tr> <tr> <td>15</td> <td>{2,3,4}</td> <td>[0,1,1,1]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\bigstar |\bigstar |\bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\bigstar |\bigstar |\bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf9ce771f505fe889210766e12ba0b3091fb399b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |\bigstar |\bigstar |\bigstar }"></span> </td></tr> <tr> <td>16</td> <td>{2,4,4}</td> <td>[0,1,0,2]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\bigstar ||\bigstar \bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\bigstar ||\bigstar \bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f01979879effaf5472a25c8ea5471844139a20d0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |\bigstar ||\bigstar \bigstar }"></span> </td></tr> <tr> <td>17</td> <td>{3,3,3}</td> <td>[0,0,3,0]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ||\bigstar \bigstar \bigstar |}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ||\bigstar \bigstar \bigstar |}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf065d8c5166e0b0a849204de826e9aa9b2212e7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle ||\bigstar \bigstar \bigstar |}"></span> </td></tr> <tr> <td>18</td> <td>{3,3,4}</td> <td>[0,0,2,1]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ||\bigstar \bigstar |\bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ||\bigstar \bigstar |\bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af86c2f563c97fa148bd34ec5ae23d6508ed9d5a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle ||\bigstar \bigstar |\bigstar }"></span> </td></tr> <tr> <td>19</td> <td>{3,4,4}</td> <td>[0,0,1,2]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ||\bigstar |\bigstar \bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ||\bigstar |\bigstar \bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2f88df1743c8073753f019dafb42fa351aca22a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle ||\bigstar |\bigstar \bigstar }"></span> </td></tr> <tr> <td>20</td> <td>{4,4,4}</td> <td>[0,0,0,3]</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |||\bigstar \bigstar \bigstar }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>★</mi> <mi>★</mi> <mi>★</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |||\bigstar \bigstar \bigstar }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2aaaaf9bed186965cb19723f51ae7ffadd66bfc6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.522ex; height:2.843ex;" alt="{\displaystyle |||\bigstar \bigstar \bigstar }"></span> </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Number_of_k-combinations_for_all_k">Number of <i>k</i>-combinations for all <i>k</i></h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=6" title="Edit section: Number of k-combinations for all k"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Binomial_coefficient#Sum_of_coefficients_row" title="Binomial coefficient">Binomial coefficient § Sum of coefficients row</a></div> <p>The number of <i>k</i>-combinations for all <i>k</i> is the number of subsets of a set of <i>n</i> elements. There are several ways to see that this number is 2<sup><i>n</i></sup>. In terms of combinations, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b90228aa739736ddf00837c52923bcca6fdc55ec" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.89ex; height:3.343ex;" alt="{\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}"></span>, which is the sum of the <i>n</i>th row (counting from 0) of the <a href="/wiki/Binomial_coefficient#Sum_of_coefficients_row" title="Binomial coefficient">binomial coefficients</a> in <a href="/wiki/Pascal%27s_triangle" title="Pascal's triangle">Pascal's triangle</a>. These combinations (subsets) are enumerated by the 1 digits of the set of <a href="/wiki/Base_2" class="mw-redirect" title="Base 2">base 2</a> numbers counting from 0 to 2<sup><i>n</i></sup> − 1, where each digit position is an item from the set of <i>n</i>. </p><p>Given 3 cards numbered 1 to 3, there are 8 distinct combinations (<a href="/wiki/Subsets" class="mw-redirect" title="Subsets">subsets</a>), including the <a href="/wiki/Empty_set" title="Empty set">empty set</a>: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>2</mn> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>3</mn> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo fence="false" stretchy="false">}</mo> <mo>;</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo fence="false" stretchy="false">}</mo> <mo fence="false" stretchy="false">}</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo>=</mo> <mn>8</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1ba1750093ea7d108e76fb15c21742d65b4a98fd" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:58.151ex; height:3.176ex;" alt="{\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}"></span> </p><p>Representing these subsets (in the same order) as base 2 numerals: </p> <ul><li>0 – 000</li> <li>1 – 001</li> <li>2 – 010</li> <li>3 – 011</li> <li>4 – 100</li> <li>5 – 101</li> <li>6 – 110</li> <li>7 – 111</li></ul> <div class="mw-heading mw-heading2"><h2 id="Probability:_sampling_a_random_combination">Probability: sampling a random combination</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=7" title="Edit section: Probability: sampling a random combination"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are various <a href="/wiki/Algorithms" class="mw-redirect" title="Algorithms">algorithms</a> to pick out a random combination from a given set or list. <a href="/wiki/Rejection_sampling" title="Rejection sampling">Rejection sampling</a> is extremely slow for large sample sizes. One way to select a <i>k</i>-combination efficiently from a population of size <i>n</i> is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>k</mi> <mo>−</mo> <mi mathvariant="normal">#</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>samples chosen</mtext> </mrow> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mi mathvariant="normal">#</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>samples visited</mtext> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdb06ba31e208b0bfc80a314aae642ad95ce64da" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:15.353ex; height:4.343ex;" alt="{\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}"></span> (see <a href="/wiki/Reservoir_sampling" title="Reservoir sampling">Reservoir sampling</a>). Another is to pick a random non-negative integer less than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\binom {n}{k}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \textstyle {\binom {n}{k}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/20897631d805059d3e86b791c9d6b96c0f20abf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.116ex; height:3.176ex;" alt="{\displaystyle \textstyle {\binom {n}{k}}}"></span> and convert it into a combination using the <a href="/wiki/Combinatorial_number_system" title="Combinatorial number system">combinatorial number system</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Number_of_ways_to_put_objects_into_bins">Number of ways to put objects into bins</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=8" title="Edit section: Number of ways to put objects into bins"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A combination can also be thought of as a selection of <i>two</i> sets of items: those that go into the chosen bin and those that go into the unchosen bin. This can be generalized to any number of bins with the constraint that every item must go to exactly one bin. The number of ways to put objects into bins is given by the <a href="/wiki/Multinomial_theorem#Ways_to_put_objects_into_bins" title="Multinomial theorem">multinomial coefficient</a> </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mrow> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>!</mo> <mspace width="thinmathspace" /> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>!</mo> <mo>⋯</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/71d0fd5e097a16fd6ca3e51317c0525aba473d1a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:34.874ex; height:6.176ex;" alt="{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}"></span> </p><p>where <i>n</i> is the number of items, <i>m</i> is the number of bins, and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> is the number of items that go into bin <i>i</i>. </p><p>One way to see why this equation holds is to first number the objects arbitrarily from <i>1</i> to <i>n</i> and put the objects with numbers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,\ldots ,k_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1,2,\ldots ,k_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0efd5f35b4631e6e268904b531646a8dd32614a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.803ex; height:2.509ex;" alt="{\displaystyle 1,2,\ldots ,k_{1}}"></span> into the first bin in order, the objects with numbers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mn>1</mn> <mo>,</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/abad90061f9c686a82db49e5a68a6dfb7b951585" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.014ex; height:2.509ex;" alt="{\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}}"></span> into the second bin in order, and so on. There are <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bae971720be3cc9b8d82f4cdac89cb89877514a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}"></span> distinct numberings, but many of them are equivalent, because only the set of items in a bin matters, not their order in it. Every combined permutation of each bins' contents produces an equivalent way of putting items into bins. As a result, every equivalence class consists of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>!</mo> <mspace width="thinmathspace" /> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>!</mo> <mo>⋯</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e775f8b4b5d3bb93ac1e8fda18d175188f195630" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.242ex; height:2.509ex;" alt="{\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}"></span> distinct numberings, and the number of equivalence classes is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>!</mo> <mspace width="thinmathspace" /> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>!</mo> <mo>⋯</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>!</mo> </mrow> </mfrac> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5fafef67f81a1deb0d22b50e7ce281bb251ec39" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:10.089ex; height:4.176ex;" alt="{\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}"></span>. </p><p>The binomial coefficient is the special case where <i>k</i> items go into the chosen bin and the remaining <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n-k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b98e1d6a69bccd09a4b9b69bdf03a08c1706c8c1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.446ex; height:2.343ex;" alt="{\displaystyle n-k}"></span> items go into the unchosen bin: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mi>k</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="2.047em" minsize="2.047em">(</mo> </mrow> <mfrac linethickness="0"> <mi>n</mi> <mrow> <mi>k</mi> <mo>,</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mrow> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="2.047em" minsize="2.047em">)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mi>k</mi> <mo>!</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d34aa3431c50f1816c2718d22ce246657bcbb3e9" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:33.369ex; height:6.343ex;" alt="{\displaystyle {\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.}"></span> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=9" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239009302">.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{clear:left;float:left;margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}</style><ul role="navigation" aria-label="Portals" class="noprint portalbox portalborder portalright"> <li class="portalbox-entry"><span class="portalbox-image"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics_blue-p.svg" class="mw-file-description"><img alt="icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/28px-Nuvola_apps_edu_mathematics_blue-p.svg.png" decoding="async" width="28" height="28" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/42px-Nuvola_apps_edu_mathematics_blue-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/56px-Nuvola_apps_edu_mathematics_blue-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span></span><span class="portalbox-link"><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></span></li></ul> <style data-mw-deduplicate="TemplateStyles:r1184024115">.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}</style><div class="div-col" style="column-width: 30em;"> <ul><li><a href="/wiki/Binomial_coefficient" title="Binomial coefficient">Binomial coefficient</a></li> <li><a href="/wiki/Combinatorics" title="Combinatorics">Combinatorics</a></li> <li><a href="/wiki/Block_design" title="Block design">Block design</a></li> <li><a href="/wiki/Kneser_graph" title="Kneser graph">Kneser graph</a></li> <li><a href="/wiki/List_of_permutation_topics" title="List of permutation topics">List of permutation topics</a></li> <li><a href="/wiki/Multiset" title="Multiset">Multiset</a></li> <li><a href="/wiki/Probability" title="Probability">Probability</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=10" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFReichl2016" class="citation book cs1">Reichl, Linda E. (2016). "2.2. Counting Microscopic States". <i>A Modern Course in Statistical Physics</i>. WILEY-VCH. p. 30. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-527-69048-0" title="Special:BookSources/978-3-527-69048-0"><bdi>978-3-527-69048-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=2.2.+Counting+Microscopic+States&rft.btitle=A+Modern+Course+in+Statistical+Physics&rft.pages=30&rft.pub=WILEY-VCH&rft.date=2016&rft.isbn=978-3-527-69048-0&rft.aulast=Reichl&rft.aufirst=Linda+E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a href="#CITEREFMazur2010">Mazur 2010</a>, p. 10</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a href="#CITEREFRyser1963">Ryser 1963</a>, p. 7 also referred to as an <i>unordered selection</i>.</span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">When the term <i>combination</i> is used to refer to either situation (as in (<a href="#CITEREFBrualdi2010">Brualdi 2010</a>)) care must be taken to clarify whether sets or multisets are being discussed.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><a href="#CITEREFUspensky1937">Uspensky 1937</a>, p. 18</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation book cs1 cs1-prop-foreign-lang-source"><i>High School Textbook for full-time student (Required) Mathematics Book II B</i> (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-7-107-19616-4" title="Special:BookSources/978-7-107-19616-4"><bdi>978-7-107-19616-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=High+School+Textbook+for+full-time+student+%28Required%29+Mathematics+Book+II+B&rft.place=China&rft.pages=107-116&rft.edition=2nd&rft.pub=People%27s+Education+Press&rft.date=2006-06&rft.isbn=978-7-107-19616-4&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation book cs1"><a rel="nofollow" class="external text" href="http://www.shuxue9.com/pep/gzxuanxiu23/ebook/31.html"><i>人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press)</i></a>. People's Education Press. p. 21.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=%E4%BA%BA%E6%95%99%E7%89%88%E9%AB%98%E4%B8%AD%E6%95%B0%E5%AD%A6%E9%80%89%E4%BF%AE2-3+%28Mathematics+textbook%2C+volume+2-3%2C+for+senior+high+school%2C+People%27s+Education+Press%29&rft.pages=21&rft.pub=People%27s+Education+Press&rft_id=http%3A%2F%2Fwww.shuxue9.com%2Fpep%2Fgzxuanxiu23%2Febook%2F31.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><a href="#CITEREFMazur2010">Mazur 2010</a>, p. 21</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLucia_Moura" class="citation web cs1">Lucia Moura. <a rel="nofollow" class="external text" href="http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf">"Generating Elementary Combinatorial Objects"</a> <span class="cs1-format">(PDF)</span>. <i>Site.uottawa.ca</i>. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 9 October 2022<span class="reference-accessdate">. Retrieved <span class="nowrap">10 April</span> 2017</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Site.uottawa.ca&rft.atitle=Generating+Elementary+Combinatorial+Objects&rft.au=Lucia+Moura&rft_id=http%3A%2F%2Fwww.site.uottawa.ca%2F~lucia%2Fcourses%2F5165-09%2FGenCombObj.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.sagemath.org/doc/reference/sage/combinat/subset.html">"SAGE : Subsets"</a> <span class="cs1-format">(PDF)</span>. <i>Sagemath.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">10 April</span> 2017</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Sagemath.org&rft.atitle=SAGE+%3A+Subsets&rft_id=http%3A%2F%2Fwww.sagemath.org%2Fdoc%2Freference%2Fsage%2Fcombinat%2Fsubset.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><a href="#CITEREFBrualdi2010">Brualdi 2010</a>, p. 52</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><a href="#CITEREFBenjaminQuinn2003">Benjamin & Quinn 2003</a>, p. 70</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text">In the article <a href="/wiki/Stars_and_bars_(combinatorics)" title="Stars and bars (combinatorics)">Stars and bars (combinatorics)</a> the roles of <span class="texhtml mvar" style="font-style:italic;">n</span> and <span class="texhtml mvar" style="font-style:italic;">k</span> are reversed.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><a href="#CITEREFBenjaminQuinn2003">Benjamin & Quinn 2003</a>, pp. 71 –72</span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><a href="#CITEREFBenjaminQuinn2003">Benjamin & Quinn 2003</a>, p. 72 (identity 145)</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><a href="#CITEREFBenjaminQuinn2003">Benjamin & Quinn 2003</a>, p. 71</span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><a href="#CITEREFMazur2010">Mazur 2010</a>, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=11" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBenjaminQuinn2003" class="citation cs2"><a href="/wiki/Arthur_T._Benjamin" title="Arthur T. Benjamin">Benjamin, Arthur T.</a>; <a href="/wiki/Jennifer_Quinn" title="Jennifer Quinn">Quinn, Jennifer J.</a> (2003), <a href="/wiki/Proofs_That_Really_Count" title="Proofs That Really Count"><i>Proofs that Really Count: The Art of Combinatorial Proof</i></a>, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-88385-333-7" title="Special:BookSources/978-0-88385-333-7"><bdi>978-0-88385-333-7</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Proofs+that+Really+Count%3A+The+Art+of+Combinatorial+Proof&rft.series=The+Dolciani+Mathematical+Expositions+27&rft.pub=The+Mathematical+Association+of+America&rft.date=2003&rft.isbn=978-0-88385-333-7&rft.aulast=Benjamin&rft.aufirst=Arthur+T.&rft.au=Quinn%2C+Jennifer+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrualdi2010" class="citation cs2"><a href="/wiki/Richard_A._Brualdi" title="Richard A. Brualdi">Brualdi, Richard A.</a> (2010), <i>Introductory Combinatorics</i> (5th ed.), Pearson Prentice Hall, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-13-602040-0" title="Special:BookSources/978-0-13-602040-0"><bdi>978-0-13-602040-0</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introductory+Combinatorics&rft.edition=5th&rft.pub=Pearson+Prentice+Hall&rft.date=2010&rft.isbn=978-0-13-602040-0&rft.aulast=Brualdi&rft.aufirst=Richard+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></li> <li><a href="/wiki/Erwin_Kreyszig" title="Erwin Kreyszig">Erwin Kreyszig</a>, <i>Advanced Engineering Mathematics</i>, John Wiley & Sons, INC, 1999.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMazur2010" class="citation cs2">Mazur, David R. (2010), <i>Combinatorics: A Guided Tour</i>, Mathematical Association of America, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-88385-762-5" title="Special:BookSources/978-0-88385-762-5"><bdi>978-0-88385-762-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Combinatorics%3A+A+Guided+Tour&rft.pub=Mathematical+Association+of+America&rft.date=2010&rft.isbn=978-0-88385-762-5&rft.aulast=Mazur&rft.aufirst=David+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRyser1963" class="citation cs2"><a href="/wiki/H._J._Ryser" title="H. J. Ryser">Ryser, Herbert John</a> (1963), <i>Combinatorial Mathematics</i>, The Carus Mathematical Monographs 14, Mathematical Association of America</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Combinatorial+Mathematics&rft.series=The+Carus+Mathematical+Monographs+14&rft.pub=Mathematical+Association+of+America&rft.date=1963&rft.aulast=Ryser&rft.aufirst=Herbert+John&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFUspensky1937" class="citation cs2"><a href="/wiki/J._V._Uspensky" title="J. V. Uspensky">Uspensky, James</a> (1937), <a rel="nofollow" class="external text" href="https://archive.org/details/in.ernet.dli.2015.263184/page/n25/mode/2up"><i>Introduction to Mathematical Probability</i></a>, McGraw-Hill</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Mathematical+Probability&rft.pub=McGraw-Hill&rft.date=1937&rft.aulast=Uspensky&rft.aufirst=James&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fin.ernet.dli.2015.263184%2Fpage%2Fn25%2Fmode%2F2up&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACombination" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Combination&action=edit&section=12" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://www.topcoder.com/community/data-science/data-science-tutorials/basics-of-combinatorics/">Topcoder tutorial on combinatorics </a></li> <li><a rel="nofollow" class="external text" href="http://mathforum.org/library/drmath/sets/high_perms_combs.html">Many Common types of permutation and combination math problems, with detailed solutions</a></li> <li><a rel="nofollow" class="external text" href="http://www.murderousmaths.co.uk/books/unknownform.htm">The Unknown Formula</a> For combinations when choices can be repeated and order does <i>not</i> matter</li> <li><a rel="nofollow" class="external text" href="http://www.lucamoroni.it/the-dice-roll-sum-problem/">The dice roll with a given sum problem</a> An application of the combinations with repetition to rolling multiple dice</li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Combination&oldid=1259007196">https://en.wikipedia.org/w/index.php?title=Combination&oldid=1259007196</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Category</a>: <ul><li><a href="/wiki/Category:Combinatorics" title="Category:Combinatorics">Combinatorics</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_Chinese-language_sources_(zh)" title="Category:CS1 Chinese-language sources (zh)">CS1 Chinese-language sources (zh)</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_April_2022" title="Category:Use dmy dates from April 2022">Use dmy dates from April 2022</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 22 November 2024, at 21:46<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Combination&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-9m94g","wgBackendResponseTime":162,"wgPageParseReport":{"limitreport":{"cputime":"0.409","walltime":"0.617","ppvisitednodes":{"value":1756,"limit":1000000},"postexpandincludesize":{"value":22484,"limit":2097152},"templateargumentsize":{"value":1098,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":8,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":40650,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 405.525 1 -total"," 43.11% 174.811 1 Template:Reflist"," 26.04% 105.601 3 Template:Cite_book"," 17.03% 69.067 1 Template:About"," 11.58% 46.963 1 Template:Short_description"," 8.77% 35.566 10 Template:Harvnb"," 6.12% 24.806 5 Template:Citation"," 4.34% 17.602 2 Template:Pagetype"," 4.20% 17.048 6 Template:Main_other"," 4.06% 16.465 1 Template:Portal"]},"scribunto":{"limitreport-timeusage":{"value":"0.203","limit":"10.000"},"limitreport-memusage":{"value":7384285,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFBenjaminQuinn2003\"] = 1,\n [\"CITEREFBrualdi2010\"] = 1,\n [\"CITEREFLucia_Moura\"] = 1,\n [\"CITEREFMazur2010\"] = 1,\n [\"CITEREFReichl2016\"] = 1,\n [\"CITEREFRyser1963\"] = 1,\n [\"CITEREFUspensky1937\"] = 1,\n}\ntemplate_list = table#1 {\n [\"About\"] = 1,\n [\"Citation\"] = 5,\n [\"Cite book\"] = 3,\n [\"Cite web\"] = 2,\n [\"Div col\"] = 1,\n [\"Div col end\"] = 1,\n [\"Harv\"] = 1,\n [\"Harvnb\"] = 10,\n [\"Hidden begin\"] = 1,\n [\"Hidden end\"] = 1,\n [\"Main\"] = 1,\n [\"Math\"] = 1,\n [\"Mvar\"] = 2,\n [\"Nobreak\"] = 1,\n [\"Nowrap\"] = 7,\n [\"Portal\"] = 1,\n [\"Redirect\"] = 2,\n [\"Reflist\"] = 1,\n [\"See also\"] = 2,\n [\"Short description\"] = 1,\n [\"Use dmy dates\"] = 1,\n}\narticle_whitelist = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-98vmp","timestamp":"20241124053314","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Combination","url":"https:\/\/en.wikipedia.org\/wiki\/Combination","sameAs":"http:\/\/www.wikidata.org\/entity\/Q202805","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q202805","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-07-26T16:24:13Z","dateModified":"2024-11-22T21:46:47Z","headline":"way of selecting things out of a group where order does not matter"}</script> </body> </html>

CINXE.COM

Combination - Wikipedia