Stars and bars (combinatorics): Difference between revisions

Revision as of 19:01, 30 March 2025

Revision as of 19:30, 30 March 2025

Line 26:

===Theorem one===

For any pair of [[positive integer]]s {{mvar|n}} and {{mvar|k}}, the number of {{mvar|k}}-[[tuple]]s of '''positive''' integers whose sum is {{mvar|n}}, is equal to the number of {{math|(''k'' − 1)}}-element subsets of a set with {{math|''n'' − 1}} elements.

For example, if {{math|1=''n'' = 10}} and {{math|1=''k'' = 4}}, the theorem gives the number of solutions to {{math|1=''x''{{sub|1}} + ''x''{{sub|2}} + ''x''{{sub|3}} + ''x''{{sub|4}} = 10}} (with {{math|''x''{{sub|1}}, ''x''{{sub|2}}, ''x''{{sub|3}}, ''x''{{sub|4}} > 0}}) as the [[binomial coefficient]]