#Proving that Binomial coefficient is an integer

90 messages · Page 1 of 1 (latest)

finite echo
#

Hi, can someone help me prove that the binomial coefficient is an integer without using p adic valuation ( because I didn't learn it yet )

Show that the binomial coefficient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ belongs to $\mathbb{Z}$.

chilly dawnBOT
white iceBOT
median grail
#

you can look at the binomial coefficient through the lens of combinations

#

the 1/(n - k)! product just means that you're getting the first k products of n!

#

the 1/k! term just means you're excluding the number of ways to do something

median grail
median grail
finite echo
#

I didn't really understand

median grail
#

think of it like this

#

how many ways are there to seat 6 people in 3 seats

finite echo
#

20

median grail
#

yes

#

can you show me how you'd do it with the fundamental counting principle

finite echo
#

I just directly used the binomial coefficient

#

\binom{6}{3}

finite echo
median grail
#

well you can do it like this

#

there are 3 spots

#

and there are 6 people

#

so you can also do it like this

#

after choosing a person, you have 5 people left to choose and after choosing another person, you have 4 people left to choose

#

this means 6x5x4

finite echo
#

ohhh i get it

#

we did a principle similar to this

median grail
#

but at the same time you don't want repetition of the arrangements

#

yeah it's probably just called different in english

finite echo
#

yeah we study in french

median grail
#

or 3x2x1

finite echo
#

why ?

median grail
#

you sometimes get like

#

p1 p2 p3

#

but here it doesn't matter the index because we didn't create any distinction

#

here p1 p2 p3 different from p2 p1 p3 and p3 p1 p2

finite echo
#

yes

median grail
#

so the reasonable thing to do is just split it by dividing by number of ways

finite echo
#

what is the 'number of ways'

median grail
#

like 3!

#

3x2x1

#

earlier we got 6x5x4

finite echo
#

yes

median grail
#

so (6x5x4)/(3x2x1)

#

gives us 2x5x2

#

or 20

#

same thing as binomial coefficient

finite echo
#

how do you calculate the number of ways ? I don't get this part

median grail
#

well you know how k is like

#

number of things you can put

#

say you have n

#

you want to put n things into k spots

#

that's 1/k! product in binomial coefficient

#

the 1/(n - k)! thing just gives us first k product of n

#

so say n = 6 and k = 3 just like last time

#

first 3 things of n is just 6x5x4

#

number of ways can be calculated just from 3!

#

because k = 3

finite echo
#

oh okay

#

And just to be sure, in the 20 we found, we consider that p1 p2 p3 is different than p2 p3 p1 right ?

median grail
#

we consider both same because

#

we didn't make difference between p1 p2 p3 and p2 p3 p1

#

which is why we divide by number of ways

#

we only want one of them

finite echo
#

i get it now

median grail
#

and 3! ways to arrange 3 indices

finite echo
#

yesss

#

finally understood lol

#

and for example if i say i have 6 persons sitting at a table and I want to know how many ways are possible for them to sit ( like each time two of them exchange place that's a possible way) idk if I was clear

#

Can we use the binomial coefficient in this case ?

finite echo
median grail
median grail
finite echo
median grail
#

so like just two people given

#

that's it

finite echo
#

oh okay

#

and can you give an example where we have two different persons ?

median grail
#

that would be called a permutation

#

but yeah

#

suppose you want to seat bob, alice and james in two seats

#

find number of ways to seat them

finite echo
#

I guess i would use the binomial coeffcient : n equals 3 and k=2

median grail
#

because three of them are distinct you can't use it here

#

except if you multiply by number of ways to arrange three things in three spots

finite echo
median grail
#

it is different here because bob, alice and james are distinct

#

suppose you had sets

#

{bob, alice, james} will definitely have size 3

#

but {person, person, person} is just {person} which is size 1