Részhalmazok száma, Binomiális együtthatók
Feladat:
Egy konvex n-szög csúcsai
`általános helyzetben' vannak.
A sokszög összes átlóját behúzzuk.
-
Az átlóknak hány metszéspontja lesz?
-
Hány tartományra osztják az átlók a sokszöget?
Feladat:
-
Hány páros elemszámú részhalmaza van egy n elemű halmaznak?
-
Hány páratlan elemszámú részhalmaza van egy n elemű halmaznak?
-
Legyen H egy nem üres halmaz.
Állítsuk párba H páros és páratlan elemszámú részhalmazait.
Feladat:
Bizonyítsuk be:
(nk)=(nn-k).
Feladat:
Bizonyítsuk be:
k(nk)=n(n-1k-1)=
(n-k+1)(nk-1).
Feladat:
Bizonyítsuk be:
(km)(nk)=
(nm)(n-mk-m)=
(nk-m)(n-k+mm).
Feladat:
Bizonyítsuk be - lehetőleg kombinatorikus módon -, hogy
2(2n-1n)=(2nn).
Feladat:
Bizonyítsuk be:
(nk)=
(n-1k-1)+(n-2k-1)+
(n-3k-1)+(n-4k-1)+
...+
(kk-1)+(k-1k-1).
Feladat:
Bizonyítsuk be:
-
(n+mk)=
(nk)(m0)+
(nk-1)(m1)+
(nk-2)(m2)+
...+
(n0)(mk),
-
(2nn)=
(nk)2+
(nk-1)2+
(nk-2)2+
...+
(n0)2.
Feladat:
Bizonyítsuk be:
-
(n0)+(n1)+
(n2)+(n3)+
...+
(nn-1)+(nn)=2n,
-
(n1)+
2(n2)+3(n3)+
...+
(n-1)(nn-1)+n(nn)=n2n-1,
-
(n2)+(32)(n3)+
(42)(n4)+
(52)(n5)+
...+
(n-12)(nn-1)+
(n2)(nn)=
(n2)2n-2,
-
12(n1)+
22(n2)+32(n3)+
...+
(n-1)2(nn-1)+
n2(nn)=n(n+1)2n-2.
Feladat:
-
Mi a paritása az ötös lottó lehetséges kimenetelei számának?
-
Bizonyítsuk be, hogy
(2n2k+1) páros.
-
Bizonyítsuk be, hogy
(2n2k) paritása megegyezik
(nk) paritásával.
-
Bizonyítsuk be, hogy
(2n2k+1) paritása megegyezik
(nk) paritásával.
-
Bizonyítsuk be, hogy
(2n+12k+1) paritása megegyezik
(nk) paritásával.
-
Adjunk eljárást
(nk) paritásának kiszámítására.
-
Milyen n-re lesz az
(n0), (n1),
(n2), (n3),
...,
(nn-1), (nn)
binomiális együtthatók mindegyike páratlan?
Feladat:
Legyen p prímszám.
Bizonyítsuk be, hogy (pk)
osztható p-vel, ha 0 < k < p.
Feladat:
Legyen n és m természetes számok.
Adjunk meg olyan összeszámlálási feladatokat, amelyekre
a válasz:
-
(m+1)n,
-
(n0)m0+(n1)m1+
(n2)m2+(n3)m3+
...+
(nn-1)mn-1+(nn)mn.
Feladat: *
Az előző feladat alapján bizonyítsuk be a binomiális tételt.
Azaz
-
(1+x)n=1+nx+(n2)x2+
(n3)x3+
...
(nn-1)xn-1+(nn)xn,
-
(x+y)n=xn+nxn-1y+
(n2)xn-2y2+
(n3)xn-3y3+
...
(nn-1)xyn-1+(nn)yn,
Feladat: *
Adjunk zárt formulát a következő összegekre:
-
(n0)+(n3)+
(n6)+(n9)+...,
-
(n1)+(n4)+
(n7)+(n10)+...,
-
(n2)+(n5)+
(n8)+(n11)+...