Subscribe via feed.

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

This post is under “MathsChallenge” and has 7 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

7 Responds so far- Add one»

  1. 1. Chris Said:

    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.

  2. 2. Wizard of Oz Said:

    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!

  3. 3. Wizard of Oz Said:

    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.

  4. 4. Chris Said:

    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.

  5. 5. Chris Said:

    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.

  6. 6. Chris Said:

    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.

  7. 7. Chris Said:

    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

Post a reply

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0