[Mat06] Kombinatorika

[Tűz Csaba]

Üdv.

 

Valaki aki volt első kombinatorika gyakorlaton le tudná nekem írni röviden,
tömören hogy mi a megoldás nyitja a köv. feladattípusnál?:

 

Hány olyan fa adható meg az 1,2,.,n cimkézett pontokon, amelyeknek legalább
k elsőfokú csúcsa van.

 

A másik fajta az, amikor meg van adva hogy melyik indexű pontok elsőfokúak.

 

Ugye legalább két elsőfokú csúcs van. Az ilyen fák száma n^(n-2)

Jó megközelítésnek tűnik kivonni ebből azoknak a számát, amiknek k-nál
kevesebb elsőfokú csúcsa van. 

 

Konkrétan: k=3

Ekkor a megoldás: n^(n-2)-{2 elsőfokú csúcs} 

Akkor a kérdés átfogalmazódik: Hány fa van 1,2,.,n cimkézett csúcsokon, ha
pontosan m elsőfokú csúcs van. (m>=2)

 

Valaki legyen már kedves egy viszonylag tömör, de használható támpontot adni
ezzel kapcsolatban? 

Tuttira bejönnek biomiális cuccok a képletbe, de zárt alakot még nem tudtam
adni rá.

 

 

Köcce

Tűz Cs.

--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: http://lists.math.bme.hu/pipermail/mat06/attachments/20061020/fef51983/attachment.html