# Permutations with restrictions

I have a problem that can be modeled as:

there are 8 boxes in total, and 60 different items. I want to put all items into boxes (all of them can be put into a single box).

Now I want to find:

1) the number of total posssible situations

2) the number of posssible situations when certain number of items are put into certain box (such are 6 different items are put into box #2).

Edit:

I found a somehow similar problem, but I think my data would be too large to enumerate. http://stackoverflow.com/questions/20721161/combinations-between-two-lists

-
Is this a Mathematica related question, or did you mean to post this on MATH.stackexchange.com? – ciao Mar 5 '14 at 9:34
I want to use mathematica to solve this problem, but I have no clue about where to start with. – capsensitive Mar 5 '14 at 9:37
I think if you only want to know the number (instead of figuring out explicit elements), it's indeed a math problem. – Yi Wang Mar 5 '14 at 10:09
6 in box 2: 60!/54! 54^7.. mathematica will crunch the numbers but you need to work out the math on your own. (this problem is far to large for direct simulation) – george2079 Mar 5 '14 at 13:25
bzzt, guilty of commenting before coffee again. I'll post an answer with the correct result – george2079 Mar 5 '14 at 15:04

I find it useful to work through the sort of problem with a smaller example:

 nbox = 4;
nball = 5;


generate all ball-to-box binnings:

 boxassign = Tuples[Range[nbox], {nball}];
boxassign[[;; 10]] // MatrixForm


the formula for the total count is pretty obvious i think:

 (boxassign // Length ) == nbox^nball


True

Now transpose that to a list of the balls in each box: (I'm sure there are more efficient ways to do this, but this is clearly readable)

 ballinbox =
Function[box, Sort@Flatten@Position[#, box]] /@ Range[nbox] & /@ boxassign;
ballinbox[[1 ;; 10]] // MatrixForm


Now select the cases where there are three balls in box two for example:

  nintwo = 3;
( byintwo = Select[ ballinbox , Length[#[[2]]] == nintwo & ] ) // MatrixForm


you can inspect the unique sets in box two and observe that it is all the possible subsets:

 Union@(byintwo[[ ;; , 2]])
Length[%]   ==  nball! / nintwo! / (nball - nintwo)!


True

Now the total count is just that number multiplied be all the ways we can distribute the remaining balls:

Length[byintwo] ==
( nball! / nintwo! / (nball - nintwo)! ) (nbox - 1)^(nball - nintwo)


True

so that for the example:

 Clear[nball,nintwo,nbox]; (* oops!! *)
( nball! / nintwo! / (nball - nintwo)! ) (nbox - 1)^(nball - nintwo) /.
{nball -> 60, nintwo -> 6, nbox -> 8}


216181483166095764640743948702606019893283529061497140

-
Unfortunately: $\frac{60!}{6!54!} 7^{54}=216181483166095764640743948702606019893283529061497140\neq 262440$ – ubpdqn Mar 6 '14 at 3:34
DOH! @ubpdqn i will fix that, good catch – george2079 Mar 6 '14 at 12:34

@capsensitive;

Hi;

1)

I am viewing this as a labeled balls into labeled urns because all 60 in the last urn is different then all 60 in the first urn.

I have a little function for computing these:

m[distballs_,disturns_,occupiedurns_]:=
Binomial[disturns,occupiedurns]Sum[(-1)^j
Binomial[occupiedurns,j](occupiedurns-j)^distballs,
{j,0,occupiedurns}]


where distballs = 60, disturns = 8, occupied urns = 1 to 8 because there can be 0 urns empty or 7 urns empty.

Sum[m[60,8,k],{k,1,8}]


yields:

1532495540865888858358347027150309183618739122183602176

A fair amount of assumptions were made but that is how I would do it. I do agree that the question belongs on Mathematics.SE.

-
For the first item you have 8 possibilities, for the second item you have 8 possibilities, for the third item you have 8 possibilities... err... etc. 8^60 – Dr. belisarius Mar 5 '14 at 12:33