Question 1197427
.
How many ways are there to distribute 15 {{{highlight(cross(district))}}} <U>distinct</U> items into 5 distinct boxes with:
i) At least two empty box.
ii) No empty box.
~~~~~~~~~~~~~~~~~~~~~



&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;In this my post, &nbsp;I consider case &nbsp;(ii), &nbsp;ONLY.



&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The &nbsp;" stars and bars " &nbsp;method works for undistinguishable balls and distinguishable boxes, &nbsp;ONLY.


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;It is clear from the logic of this method.  &nbsp;Many &nbsp;(if not all) &nbsp;autoritative sources point it directly. 


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;See, for example, this Wikipedia article 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Therefore, it is inadequate and hopeless to apply the &nbsp;" stars and bars " &nbsp;method for the given problem, 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;where the balls are considered as &nbsp;DISTINGUISHABLE.


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;For it, &nbsp;another technique should be used.  &nbsp;See my solution below.



<pre>
The formula for the number of distributions of n distinguishable items in m distinguishable boxes 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 spreadshhets 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.



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

        k	(-1)^k	combin(2,k)	(2-k)^15   Separate addends
                                                   of formula (1)
        0	  1	   1	        32768	     32768
        1	 -1	   2	           1	        -2
				                     32766    <<<---=== Final sum F(15,2)


    It is not so easy to check it manually that F(15,2) = 32766 is the correct number of different distributions
    of 15 distinguishable balls in 2 distinguishable boxes, but at least it seems likelihood.



    And finally, below are calculations for n= 15, m= 5  (fifteen balls in five boxes, the requested case).

        k	(-1)^k	combin(5,k)	(5-k)^15   Separate addends
                                                   of formula (1)
	0	  1	   1	    30517578125	   30517578125
	1	 -1	   5	    1073741824	   -5368709120
	2	  1	  10	       14348907	     143489070
	3	 -1	  10	          32768	       -327680
	4	  1	   5	              1	             5
					           25292030400    <<<---=== Final sum F(15,5)


<U>ANSWER</U>.  The number of all different distributions of 15 distinguishable balls in 5 distinguishable boxes is 25292030400.
</pre>

Solved.



//////////////////



Although the formula is given in the cited references, I think, there are not so many people who know
how to approach to the problem, who know about existing of this formula, who know on how to solve this problem in a right way.


This problem is of much higher level than average high school and even of much higher level than
an ordinary Math circle at a school or at a local University level.


Only professional mathematicians working in Combinatorial Math know about  existing this formula.


Another circle of persons who can be competent in the area, are those who are professionally trained
to participate in International Math Olympiads, as well as their trainers and their teachers.


Third circle of such people are those who know well the relevant popular Math literature.
I myself do belong to this last category.



////////////////



Here one more tutor came (@rippletable) and brought an incorrect solution.


Ignore it, since it is incorrect.