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$ This is a joke (like Fermat's ). For real, I have a verbose proof, that is without mathematical rigor.

[gugo82]

Just use Induction and an elementary identity.

Testo nascosto, fai click qui per vederlo

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\)

[Martino]

Testo nascosto, fai click qui per vederlo

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

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

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

[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"...

[Gi8]

prove that if \( \displaystyle n,a,b \) are positive integers with \( \displaystyle n=ab \) then \( \displaystyle \frac{n!}{a!^b b!} \) 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:

Testo nascosto, fai click qui per vederlo

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).