9
$\begingroup$

Can you give an idea, how to find out whether the result of ${1000!}/{100!^{10}}$ an integer.

Modulo division? But what I met was about powers like $2^{100}/125$...

$\endgroup$
24
$\begingroup$

What's the number of ways to split $1000$ people into $10$ teams of $100$ ?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That is the number of ways to put them into 10 ordered teams. Considering just deciding who will be teammates shows that even if you throw 10! Into the denominator it is still an integer. $\endgroup$ – Aaron Meyerowitz Jun 12 '15 at 20:56
  • 1
    $\begingroup$ I have to add that this is @Zev Chonoles's answer in disguise though. $\endgroup$ – mercio Jun 12 '15 at 23:29
20
$\begingroup$

Since you tagged this abstract algebra, I will give a hint based on it: the group $$\underbrace{S_{100}\times\cdots\times S_{100}}_{10\text{ copies}}$$ has an obvious embedding as a subgroup of $S_{1000}$.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Now I'm asking myself why I hadn't ever made that connection before. $\endgroup$ – Mark Bennet Jun 12 '15 at 20:25
  • $\begingroup$ The formula for multinomial coefficients is in fact an immediate consequence of applying the orbit-stabilizer theorem involving a subgroup of $S_n$ of the form $S_a\times S_b\times \cdots\times S_c$. $\endgroup$ – anon Jun 12 '15 at 20:32
6
$\begingroup$

Consider the binomial coefficents ${200 \choose 100},{300 \choose 100},{400 \choose 100},{500 \choose 100},{600 \choose 100},{700 \choose 100},{800 \choose 100},{900 \choose 100},{1000 \choose 100}$

For example,

$${700 \choose 100} = \frac{700!}{600!100!} = \frac{700\cdot 699\ldots 602\cdot 601}{100!}$$ and this is an integer...

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ $$\binom{1000}{100}= \frac{1000!}{100!^{10} \binom{900}{100}\binom{800}{100} \binom{700}{100}\binom{600}{100}\binom{500}{100} \binom{400}{100}\binom{300}{100} \binom{200}{100}}$$ is an integer. It gives you a stronger statement than OP's. $\endgroup$ – user26486 Jun 12 '15 at 20:40
  • $\begingroup$ @user26486 Nice enhancement :-) $\endgroup$ – Joffan Jun 12 '15 at 20:45
5
$\begingroup$

Here’s a non-combinatorial, more number-theoretic proof. For any prime $p$ the number of factors of $p$ in $n!$ is

$$\sum_{k\ge 0}\left\lfloor\frac{n!}{p^k}\right\rfloor\;,$$

so it suffices to show for an arbitrary prime $p$ that

$$10\sum_{k\ge 0}\left\lfloor\frac{100}{p^k}\right\rfloor\le\sum_{k\ge 0}\left\lfloor\frac{1000}{p^k}\right\rfloor\;.\tag{1}$$

$(1)$ will certainly be true if

$$10\left\lfloor\frac{100}{p^k}\right\rfloor\le\left\lfloor\frac{1000}{p^k}\right\rfloor\tag{2}$$

for primes $p$ and $k\ge 0$. But

$$\left\lfloor\frac{100}{p^k}\right\rfloor\le\frac{100}{p^k}\;,$$

so

$$10\left\lfloor\frac{100}{p^k}\right\rfloor\le\frac{1000}{p^k}\;,$$

and $(2)$ (and hence $(1)$) follows immediately.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

The basic result is that the product of $k$ consecutive numbers is divisible by $k!$.

This is the fact that ${{n}\choose{k}}$ is an integer when $n \ge k$.

Now, $1000!$ can be decomposed into $10$ products of $100$ consecutive numbers.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I like this one. $\endgroup$ – Tim B. Jun 12 '15 at 20:56
2
$\begingroup$

I have a stronger statement:

$$\binom{1000}{100}=\frac{1000!}{100!^{10}\binom{900}{100}\binom{800}{100}\binom{700}{100}\binom{600}{100}\binom{500}{100}\binom{400}{100}\binom{300}{100}\binom{200}{100}}$$

is an integer. More generally:

$$\binom{ab}{b}=\frac{(ab)!}{b!^{a}\binom{(a-1)b}{b}\binom{(a-2)b}{b}\cdots\binom{2b}{b}}$$

is an integer (for $a\ge 2, b\ge 0$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Namely the integer $\binom{ab}{b}$ $\endgroup$ – Aaron Meyerowitz Jun 12 '15 at 21:12
  • $\begingroup$ @AaronMeyerowitz I added that 11 mins ago. $\endgroup$ – user26486 Jun 12 '15 at 21:15

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.