Question

Prove, by a combinatorial argument, that for all positive integers n, the number ( binom3nn, n, n ) is divisible by six.

Answer 1

To show that (binom3nn, n, n) is divisible by six, we consider the arrangements of 3n items into three equal groups and account for the interchangeability of the groups. Since the resulting formula, n! × n! × n! / 6, involves dividing by 6, the multinomial coefficient is always divisible by six.

Step-by-step explanation:

To prove that the multinomial coefficient ( binom3nn, n, n ) is divisible by six for any positive integer n, consider that this coefficient represents the number of ways to arrange 3n items into three groups of n items each. A combinatorial argument can be constructed as follows:

1. Start by dividing the 3n items into three groups arbitrarily. This yields n! arrangements for each group, and since there are three groups, we have n! × n! × n! total arbitrary arrangements.
2. Next, consider that each grouping of n items can occur in any order, thus we have to divide by the number of ways these groups can be interchanged, which is 3! (or 6). So the formula for the number of distinct groupings is n! × n! × n! / 6.
3. Now, since n! is always an integer and 6 is multiplying the factorial product, it's clear that the multinomial coefficient is always divisible by 6.