4
$\begingroup$

(Disclaimer: I'm a high school student, and my highest knowledge of mathematics is some elementary calculus. This may not be the correct terminology.)

A while ago, I saw the following problem: prove, for natural numbers $a$, $b$, $c$, $d$ with $a \geq b + c + d$ that $\frac{a!}{b!c!d!}$ is a natural number.

I had a neat idea about this when I realized that the expression $\frac{a!}{b!c!d!}$ actually gives the answer to a combinatorial problem. Namely, it is the number of unique permutations of $a$ objects when $b$ are of one type (indistinguishable from each other), $c$ are of another type, and $d$ are of another type. Obviously, one cannot have a non-natural number of permutations, so this must always be a natural number.

Is this a valid method of proof? Can one establish that an expression is always a natural number by assigning to it a combinatorial meaning?

$\endgroup$
  • 2
    $\begingroup$ Yes, it is a very nice proof method. You might enjoy the book "Proofs that really count," (Benjamin and Quinn) which has a large number of combinatorial arguments. $\endgroup$ – André Nicolas Jun 25 '13 at 7:13
  • $\begingroup$ I just want to remark that in order to get the right number, one must assume that all remaining $a-(b+c+d)$ objects are individually distinguishable (each one has a different colour form all the others, say). $\endgroup$ – Marc van Leeuwen Jun 25 '13 at 7:31
3
$\begingroup$

Yes: you’ve discovered one form of combinatorial proof, an elegant and often very informative kind of proof that is very frequently used in combinatorics. However, your argument needs a little bit of repair. Let $e=a-(b+c+d)$; then the multinomial coefficient

$$\binom{a}{b,c,d,e}=\frac{a!}{b!\,c!\,d!\,e!}$$

is the number of distinguishable permutations of $a$ objects consisting of $b$ indistinguishable objects of one type, $c$ indistinguishable objects of another type, $d$ indistinguishable objects of a third type, and $e$ indistinguishable objects of a fourth type. This is clearly a non-negative integer, since it counts a discrete collection of entities, and

$$\frac{a!}{b!\,c!\,d!}=\binom{a}{b,c,d,e}\cdot e!$$

is therefore also a non-negative integer.

Alternatively, you could take the $e$ remaining elements to be distinguishable from one another and from the other three types, in which case $\frac{a!}{b!\,c!\,d!}$ is indeed the number of distinguishable permutations of the $a$ objects, and you don’t need the intermediate step. If this is what you had in mind, the only repair needed is to make this a bit clearer!

$\endgroup$
  • 1
    $\begingroup$ @David: Yes, if it’s understood that the remaining objects are all distinguishable from one another and from the first three types. It wasn’t clear to me that this is what you had in mind, though I did realize at the last minute that it might have been — hence the last paragraph. By the way, congratulations: that’s a very nice realization to have come to. $\endgroup$ – Brian M. Scott Jun 25 '13 at 7:20
  • $\begingroup$ Ah, I see. Yeah, I had in mind that the rest of the elements would be distinguishable. I see that I should have made that explicit, though. Thanks! $\endgroup$ – David Zhang Jun 25 '13 at 7:21
  • $\begingroup$ @David: You’re welcome! $\endgroup$ – Brian M. Scott Jun 25 '13 at 7:22
2
$\begingroup$

Yes, this is a perfectly valid way of showing that the value of an expression is always a natural number. By the way, this is an argument for having $0\in\Bbb N$ (a point that unfortunately still raises controversy), because showing that a number counts the elements of a finite set does not involve showing the set is non-empty. I would even consider this the most natural approach to showing an expression takes natural number values, although it does not of course work in all cases.

The most down to earth approach is showing separately that an expression always takes integer values (in the case at hand you could do this by counting prime factors in numerator and denominator) and that it cannot take negative values. Depending on the situation this can be straightforward, tedious, or virtually impossible. There are famous results and conjectures about certain types of expression always taking natural number values where neither of these methods seem to work. Cases are known where a proof of this property was found by performing a (highly abstract) construction and showing that it defines a vector space whose dimension is given by the expression without having constructed a set with that number of elements!

$\endgroup$
1
$\begingroup$

You can notice that $\mathfrak{S}_b \times \mathfrak{S}_c \times \mathfrak{S}_d$ is a subgroup of $\mathfrak{S}_a$ if $a \geq b+c+d$, dividing the set $\{1,\dots,a\}$ into three subsets of length $b$, $c$ and $d$.

$\endgroup$
  • $\begingroup$ The argument given by OP boils down to just this fact. If one colours, among $a$ objects, $b$ of them in one colour, $c$ in another, $d$ in yet another, and each remaining element in a unique colour of its own, then among the $a!$ permutations of the objects, there will be $b!c!d!$ that preserve each colouring, precisely because they form (a coset of) a subgroup as mentioned in this answer. The number of different colourings obtained by all permutations then is $a!$ divided by this $b!c!d!$. $\endgroup$ – Marc van Leeuwen Jun 25 '13 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.