propozicija 21 komb. dokaz

[kreso]

knjiga Darka Veljana, kombinatorika i dikretna matematika, propozicija 21

suma k=0 do n (c(n,k)x^k)=x^n nadvuceno.

ako mi netko može pokušati malo razjasniti kombinatorni dokaz.
ne kužim zasto su uredjene n-torke tipa (a1,a2...an) oblika:
0<=a1<=x+n-2
0<=ai<=x+n-i-1
0<=an<=x-1
??

[krcko]

Nemam knjigu. Pretpostavljam da je desna strana ovo: x(x+1)...(x+n-1). To je ocito broj takvih uredjenih n-torki. Sto je c(n,k) s lijeve strane, Stirlingovi brojevi prve vrste?

Kombinatorni dokazi identiteta poput ovog svode se na dvostruko prebrojavanje. Prvo moras izmisliti objekte koje ces prebrojavati - u ovom slucaju lakse je krenuti s desne strane. Sad bi trebalo te iste n-torke prebrojiti na drugi nacin i pritom dobiti lijevu stranu...

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.