Binomial coefficient

[Zero87]

Let $k,n$ a positive integers, $k\le n$ and $((n),(k))$ the binomial coefficient defined in the usual way.
Prove - with mathematical rigor ( ) - that $((n),(k))$ is an integer too.

I have a wonderful proof of this fact, but it is so long to write in a thread$^1$.

___
$^1$[size=90] This is a joke (like Fermat's ). For real, I have a verbose proof, that is without mathematical rigor.[/size]

[Gi81]

"Martino": prove that if [tex]n,a,b[/tex] are positive integers with [tex]n=ab[/tex] then [tex]\frac{n!}{a!^b b!}[/tex] is an integer.

Let's fix $a in NN$. We define $f:\ NN to QQ$ in this way: $f(b)= [(ab)!]/[(a!)^b * b!]$.
We're going to prove that $AA b in NN$ we have $f(b) in NN$ using induction:

Basis: $f(1)= (a!)/(a!)=1 in NN$.
Inductive step: Let's suppose that $f(b) in NN$. We're going to prove that $f(b+1) in NN$:
We have:

- $[a(b+1)]! = (ab)! * prod_{i=0}^{a-1} [a(b+1)-i]$

-$(a!)^{b+1}= (a!)^b * a!$

- $(b+1)! = (b+1)*b!$

So we have $f(b+1)= {[a(b+1)]!}/{(a!)^{b+1}*(b+1)!}= {(ab)! * prod_{i=0}^{a-1} [a(b+1)-i]}/{(a!)^b * a! *(b+1)*b! }= f(b) *{prod_{i=1}^{a-1} [a(b+1)-i]}/{(a-1)!}$

Now, ${prod_{i=1}^{a-1} [a(b+1)-i]}/{(a-1)!}= prod_{i=1}^{a-1} {ab+ a -i}/{a-i}=_{j= a-i} prod_{j=1}^{a-1} {ab+ j}/{j}$ which is integer (look here).

[Zero87]

@ gugo82... only ... But I don't have to surprise myself because your answers are enciclopaedics...

@Martino... I don't understand not even a word $^1$
My relationship with algebra is equal to the one I have with calisthenics .
___
$^1$ It is an elegant way to say "n'ho capito un tubo", oh, I mean "i don't understand a pipe"...

[Studente Anonimo]

Let [tex]H[/tex] be the subgroup of the symmetric group [tex]S_n[/tex] defined by
\[
H = \{\sigma \in S_n\ :\ \{ \sigma(1),\ldots, \sigma(k)\} = \{1,\ldots,k\}\}.
\]
Then it is quite clear that [tex]H \cong S_k \times S_{n-k}[/tex] (the two [tex]H[/tex]-orbits [tex]\{1,\ldots,k\}[/tex], [tex]\{k+1,\ldots,n\}[/tex] can be stirred in all possible ways).

The index of [tex]H[/tex] in [tex]S_n[/tex] is an integer by Lagrange's Theorem, and its value is [tex]|S_n:H| = |S_n|/|H| = \binom{n}{k}[/tex].

I propose to solve this: prove that if [tex]n,a,b[/tex] are positive integers with [tex]n=ab[/tex] then [tex]\frac{n!}{a!^b b!}[/tex] is an integer.

[gugo82]

Just use Induction and an elementary identity.

Clearly:
\[
\binom{n}{0}=1=\binom{n}{n}\; ,
\]
Hence \(\binom{n}{0}\) and \(\binom{n}{n}\) are positive integers for any \(n\).
Therefore, it suffices to prove that:

For any \(n\geq 2\), all the binomial coefficients \(\binom{n}{k}\) with lower index \(k=1,\ldots ,n-1\) are integers.

Proof: For \(n=2\) the claim is true by inspection.

Now assume that the claim is true for \(n\) and prove it holds for \(n+1\).
The binomial coefficents satisfy the identity:
\[
\forall k\in \{ 1,\ldots ,n\},\quad \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}\; ;
\]
thus all the coefficients \(\binom{n+1}{k}\) with \(k=1,\ldots ,n\) are positive integers, for they are sum of the two positive integers \(\binom{n}{k-1},\ \binom{n}{k}\). \(\square\)