# Combination or Permutation?

I read this puzzle as below.

You have 40 boxes, all placed in a row at exact intervals of 1 meter. You also have 9 balls(all same type). You wish to place all the balls in the boxes, no more than one ball in each box, so that there are no three boxes A, B, and C such that the distance between A and B is equal to the distance between B and C. How many ways can you arrange the balls in the boxes?

e.g. (For clearer understanding) For 5 boxes and 4 balls Then only possible arrangement is as below

Boxes: 1 2 3 4 5

Balls: B B - B B

I want to come up with a formula in terms of nPr (permutation) or nCr(combination) of r objects out of n objects and other some terms in the formula for this particular case(40 boxes,9 balls) and generic formula for n boxes and r balls.

I am trying to solve this first on paper by manually listing down arrangements for different values of boxes and balls. I tried for combinations (5,4) , (6,4) , (7,4), ... but haven't seen a pattern to construct a generic formula. I have below questions regarding this-

1.Should we consider permutations(where order of balls is not important) or combinations(where order of balls is important).

2.What would be the generic relation for solving this problem.

Any pointers useful.

-
The order of the balls is irrelevant (since they are all the same type). You are trying to select boxes (combinations) subject to specific restrictions. –  Arturo Magidin Jun 5 '11 at 21:46
I thought so. But the original puzzle does not mention anything about this and left it open. –  goldenmean Jun 5 '11 at 21:51
This problem doesn't really have anything to do with the difference between permutations and combinations. Which one you use will depend upon which method you come up with of counting the possibilities. I would suggest counting the combinations using inclusion-exclusion. –  Jim Belk Jun 5 '11 at 22:09
As others have noted the problem is definitely about combinations, but that doesn't mean that the solution will necessarily be in terms of only the combination functions. –  Thomas Andrews Jun 6 '11 at 0:01
Simulation suggests the answer is about 2.8% of the ${40 \choose 9}$ possibilities, so between 7.5 and 8 million in total. A brute force enumeration and check may turn out to be the easiest way to find an exact solution. –  Henry Jun 6 '11 at 6:11

## 1 Answer

An answer because the comments will not take what follows:

A simulation in R (poorly written and slow, but it works)

ss <- 10000
balls <- 9
boxes <- 40

diff <- function(x,y) {abs(x-y)}
dupe <- function(x) {sum(duplicated(x))}

counter <- 0
for (i in 1:ss)
{
a <- sample(1:boxes, balls)
b <- as.data.frame(outer(a,a,FUN="diff"))
if (sum(sapply(b, FUN="dupe")) == 0) {counter = counter+1}
}

counter/ss
choose(boxes,balls) * counter/ss


giving the answer

> counter/ss
[1] 0.0283
> choose(boxes,balls) * counter/ss
[1] 7738320


(I actually took a larger slower sample, but the result was similar.)

So the answer is about 2.8% of the ${40 \choose 9}$ possibilities, so between 7.5 and 8 million in total.

A brute force enumeration and check may turn out to be the easiest way to find an exact solution.

-