Lesson In how many ways N distinguishable objects can be distributed among n different boxes ?

Source code of 'In how many ways N distinguishable objects can be distributed among n different boxes ?'

This Lesson (In how many ways N distinguishable objects can be distributed among n different boxes ?) was created by by ikleyn(52906)

: View Source, Show
About ikleyn:

<H2>In how many ways N distinguishable objects  can be distributed among n different boxes ?</H2>

This lesson is advanced.

<H3>Problem 1</H3>In how many ways &nbsp;8 &nbsp;distinguishable objects  can be distributed among &nbsp;4 &nbsp;different boxes so that no one box is empty ?

<B>Solution</B>

<pre>
The formula for the number of distributions of n distinguishable items in m distinguishable boxes so that no one box is empty is

F(n,m) = {{{sum((-1)^k*C[m]^k*(m-k)^n, k=0,m)}}}.    (1)

The sources for this formula are these references

Feller - An Introduction to Probability Theory and its Applications, Vol I, 3ed, 1968,

Chen Chuan-Chong, Koh Khee-Meng - Principles and Techniques in Combinatorics, 1992,

Anderson - A first course in combinatorial Mathematics, 2001.

To make calculations using this formula, I prepared Excel spreadsheets for some different values n and m.

Below are calculations for n= 3, m= 2  (three balls in two boxes).

k	(-1)^k	combin(2,k)	(2-k)^3	   Separate addends
                                                   of formula (1)
	0	  1	   1	           8	      8
	1	 -1	   2	           1	     -2
					              6    <<<---=== Final sum F(3,2)

You can check it manually that F(3,2) = 6 is the correct number of different distributions
    of 3 distinguishable balls in 2 distinguishable boxes.

Below are calculations for n= 4, m= 2  (four balls in two boxes).

k	(-1)^k	combin(2,k)	(2-k)^4	   Separate addends
                                                   of formula (1)
        0	  1	   1	          16	     16
        1	 -1	   2	           1	     -2
				                     14    <<<---=== Final sum F(4,2)

You can check it manually that F(4,2) = 14 is the correct number of different distributions
    of 4 distinguishable balls in 2 distinguishable boxes.

And finally, below are calculations for n= 8, m= 4  (8 balls in 4 boxes, the requested case).

k	(-1)^k	combin(4,k)	(4-k)^8	   Separate addends
                                                   of formula (1)
        0	  1	   1	         65536	     65536
        1	 -1	   4	          6561	    -26244
        2	  1	   6	           256	      1536
        3	 -1	   4	             1	        -4
				                     40824    <<<---=== Final sum F(8,4)

<U>ANSWER</U>.  The number of all different distributions of 8 distinguishable objects in 4 different boxes is 40824.
</pre>

My other lessons on Permutations and Combinations in this site are

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Permutations.lesson>Introduction to Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-permutations.lesson>PROOF of the formula on the number of Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Permutations.lesson>Simple and simplest problems on permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Special-type-permutations-problems.lesson>Special type permutations problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/How-many-different-permutations-may-exist-ubder-given-restrictions.lesson>Problems on Permutations with restrictions</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Permutations.lesson>Math circle level problem on Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Combinations-.lesson>Introduction to Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-combinations.lesson>PROOF of the formula on the number of Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Combinations.lesson>Problems on Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinations-problems-with-restrictions.lesson>Problems on Combinations with restrictions</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Combinations.lesson>Math circle level problem on Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Arranging-elements-of-sets-containing-undistinguishable-elements.lesson>Arranging elements of sets containing indistinguishable elements</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Persons-sitting-around-a-circular-table.lesson>Persons sitting around a cicular table</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinatoric-problems-for-entities-other-than-permutations-and-combinations.lesson>Combinatoric problems for entities other than permutations and combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Fundamental-counting-principle-problems.lesson>Fundamental counting principle problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Miscellaneous-problems-on-permutations-combinations-and-other-combinatoric-entities.lesson>Miscellaneous problems on permutations, combinations and other combinatoric entities</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Some-twisted-combinatorics-problem.lesson>Some twisted combinatorics problem</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Inclusion-Exclusion-principle.lesson>Inclusion-Exclusion principle problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/DERANGEMENT-problems.lesson>Derangement problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Stars-and-bars-method-for-Combinatorics-problems-2.lesson>Stars and bars method for Combinatorics problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Men-and-women-standing-in-line-.lesson>Men and women standing in line</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/One-combinatorial-Geometry-problem-solved-using-the-Euler-formula.lesson>One combinatorial Geometry problem solved using the Euler formula</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Nice-recreational-problems-on-permutations.lesson>Nice recreational problems on permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-the-lessons-on-Permutations-and-Combinations.lesson>OVERVIEW of lessons on Permutations and Combinations</A>

Use this file/link &nbsp;<A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A>&nbsp; to navigate over all topics and lessons of the online textbook &nbsp;ALGEBRA-II.