## A divisibility problem

Posted by Chris on April 23, 2013 – 11:20 pm

Under what circumstances is/isn’t C(n,r) divisible by n?

Assume that n and are r integers (include 0 and negatives).

—

C(n,r) = n! / ((n-r)! r!)

You might find it convenient to use e.g. a|b for “a divides b”

and a¦b for “a doesn’t divide b”

On my British keyboard, the | is next to the Z and

the ¦ is next to the top left 1 and is accessed with the Alt Gr key

April 23rd, 2013 at 11:30 pm

I’ve posted this because I don’t understand why in the blockbuster problem, we had the number C(12,4) = 495 and it isn’t divisible by 12. i.e. 12 ¦ C(12,4).

It’s doing me in. Of course, solving the above problem won’t help me

LATER: I’ve understood why 495 doesn’t have to be divisible by 12.

April 24th, 2013 at 12:29 am

If n is prime then there can be no divisors of n within r or n-r, so this would be one case where n|C(n,r).

With a number like 12 with lots of small divisore there will always be divisors of 12 within (n-r)! and r!

Hope this helps!

April 24th, 2013 at 3:58 am

Actually my post 2 is not quite right . . .

C(12,4) isn’t divisible by 12, but C(12,5) and C(12,6) both are.

So, n being prime is one condition, but obviously there are others.

April 24th, 2013 at 7:38 am

Hi Wiz, that’s a good start. However, C(n,r) being divisible by n if n is a prime isn’t quite true.

You haven’t thoroughly checked for special cases special cases e.g. r = 0 and r = n.

In consequence, I’ve modified the question. Just to be really rotten, I’m allowing n and r to be negative. At the moment, I don’t know what happens then.

I actually thought of the problem for several related reasons. All are essentially spin-offs from the Blockbuster problem.

I found my self floundering when trying to pose a three-colour version of Blockbuster. I wanted to pose it as it would allow me to become sure of or amend my notes on how to handle ring type combinatorics.

I started Googling on rings. Almost immediately I became confused. I’m sorted now though. I was going to write about what had been confusing me here, but I’ve decided to put it on the Blockbuster page instead.

April 24th, 2013 at 10:25 am

I rather suspect that it may not be possible to give a straightforward answer to the problem.

I think Wiz has pretty much identified the sort of consideration needed.

May 1st, 2013 at 11:35 pm

I had deliberately extended the problem to include the negative integers because I had a vague recollection that it wasn’t entirely daft to contemplate the factorials of negative integers. This is surprising in several ways. By using the definition of factorials or by considering the gamma function, you’d be forced to conclude that such a number wasn’t definable. You get ±∞.

If n > 0, then (-n)! = (-n)(-n-1)(-n-2)…(-∞+1)(-∞)(-∞-1)… = ±Ω

This is obviously mega-dodgy maths. But ignoring that quibble for now, we have that Ω is ∞ multiplied by ∞ an infinite number of times. So Ω is pretty big. I’d guess that Ω is an uncountable infinity and that 1/Ω is indistinguishable from 0. (i.e. it is not infinitesimal. That’s important, because infinitesimals are not numbers (now I’m being fussy!!!). See Hyperreal numbers. I’m going to assume that it is valid to say that the reciprocal of a negative factorial is 0.

If n > 0, (-n!) = (-n)(-n-1)(-n-2)…

= (-1)(-2)…(-n+1) (-n)! / ((-1)(-2)…(-n+1))

= (-1)

^{n}(-1)! / (n-1)!As (-1)

^{n}is a pain to type, I’ll use ± to imply it.If m,n > 0, then (-m)!/(-n)! = ± ((-1)!/(m-1)!) / ((-1)!/(n-1)!) = ± (n-1)!/(m-1)!

So, if n > m > 0, then (-m)!/(-n!) = ± (n-1)!/(m-1)! is an integer, and (-n)!/(-m)! is the reciprocal of an integer. In either case, if we divide by another negative factorial, we’d get 0.

C(n,r) = n!/((n-r)! r!). There is no way for this to be infinite with finite n,r.

If r > n > 0, then C(n,r) = 0. That makes a lot of sense. e.g. you can’t pick 5 objects from 3 objects.

Case r = 0: C(n,0) = n!/n! = 1. As no integer divide 1, C(n,0) isn’t divisible by n.

Now I’ll get back to the posted problem with sensible values for n and r.

We have: n! = C(n,r) (n-r)! r!. As Wiz noted, if n > r > 0, then n > n-r and so if n is prime, neither (n-r)! nor r! can be divisible by any. But n! is divisible by n. So by Euclid’s lemma, C(n,r) must be divisible by n.

– I’m bored with this now. I might improve it later.

May 3rd, 2013 at 4:00 pm

A bit off topic, here’s an identity (that I kept on working out when doing the Blockbuster problems).

C(n,r) = C(n-1,r-1) n/r