Cayleyn puiden lukumäärä -lause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. tammikuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Cayleyn puiden lukumäärä -lause on lause, joka sanoo, että puiden lukumäärä, joilla on numeroidut pisteet, on . $n$ $n^{{n-2}}$

Historia

Lause on nimetty Arthur Cayleyn mukaan, joka todisti sen vuonna 1889. [1] Cayley itse myönsi, että saman väitteen oli todistanut aiemmin Carl Borchard ja vastaavassa muodossa jopa aikaisemmin James Joseph Sylvesterin vuoden 1857 artikkelissa. [2]

Kirjoituksessaan Cayley todistaa pohjimmiltaan yleisemmän lausunnon. Jos avaat lausekkeen sulut

{(x_{1}+\dots +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \cdot x_{n}),

silloin muodon monomin kerroin on yhtä suuri kuin niiden puiden lukumäärä, joiden kärkiasteet ovat yhtä suuret kuin tietyn termin muuttujien asteet: . $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ ${\displaystyle d_{1},\dots ,d_{n))$

Cayley tarkentaa tapausta ja toteaa, että todiste on helposti yleistettävissä. $n = 6$

Formulaatiot

Kaksi vastaavaa formulaatiota:

Huippupisteissä olevien eri puiden lukumäärä , numeroitu alkaen - on yhtä suuri kuin . $n$ $yksi$ $n$ $n^{{n-2}}$

Virittävien puiden lukumäärä täydellisessä kaaviossa on . $K_n$ $n^{{n-2}}$

Aiheeseen liittyvät lausunnot

Numeroiduissa pisteissä olevien puiden lukumäärä on myös yhtä suuri kuin -syklin dekompositioiden lukumäärä transponoinnin tuloksi . $n$ $n$ ${\näyttötyyli (1\pisteet n)}$ $n-1$

Numeroiduissa pisteissä olevien puiden lukumäärä on myös yhtä suuri kuin (sopivasti normalisoitujen) astepolynomien määrä annetuilla kriittisillä arvoilla yleisasemassa. $n$ $n$ $n-1$
- Lopuksi tämä jälkimmäinen on erikoistapaus
Riemannin pallon haarautuneiden päällysteiden topologisesta luokittelusta - siten puiden lukumäärän laskeminen osoittautuu erikoistapaukseksi laskettaessa Hurwitz-lukuja , jotka vastaavat peitepinnan tapausta. suvusta 0.

Tietoja todisteista

Cayleyn kaava seuraa välittömästi Prufer-koodin ominaisuuksista , tapa koodata yksilöllisesti n- vertex-merkitty puu sen kärkinumeroiden järjestetyllä sekvenssillä . $n$ $n-2$

Cayleyn kaava on myös helposti johdettavissa matriisipuulauseesta .

Yksi todisteista perustuu seuraavaan suhteeseen ${\displaystyle a(x)=x\cdot e^{a(x)))$

eksponentiaaliseen generointifunktioon

a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n !}}\cdot a_{n}\cdot x^{n}+\dots

jossa tarkoittaa juurtuneiden puiden lukumäärää annetuissa pisteissä. Sarjojen käännöstä koskevan Lagrangen lauseen mukaan tästä suhteesta seuraa, että . Jälkimmäinen tarkoittaa Cayleyn kaavaa, koska jokaiselle virittävälle puulle on täsmälleen tapoja valita juuripiste. [3]

a_n

n

{\displaystyle a_{n}=n^{n-1))

n

Muunnelmia ja yleistyksiä

Useita tapoja linkittää graafi, joka koostuu katkaistuista komponenteista, joista kullakin on kärkikoko $m$ $x_{i}$ $T[x_{m}]=x_{1}\cdot x_{2}\dots x_{m}\cdot (x_{1}+x_{2}+\dots +x_{m})^{ m-2}=[x_{m}]!\ n^{m-2}$ Tässä on graafin kärkien kokonaismäärä. ${\displaystyle n=x_{1}+x_{2}+\pisteet +x_{m))$ Jos jokainen komponentti koostuu yhdestä kärjestä , niin , ja kaava antaa alkuperäisen Cayleyn luvun . ${\näyttötyyli (x_{i}=1)}$ $n=m$ $n^{{n-2}}$

Virittävien puiden lukumäärä täydellisessä kaksiosaisessa graafissa on $K_{{m,n}}$ $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

Matriisipuulause antaa lausekkeen graafin virittävien puiden lukumäärälle graafin laplalaisen (Kirchhoff-matriisin) determinanttina.

Muistiinpanot

↑ Cayley A. Lause puista. Quart. J. Pure Appl. Math., 23 (1889), 376-378; Collected Mathematical Papers, Voi. 13, Cambridge University Press, 1897 , 26–28.
↑ Biggs NL, Lloyd EK, Wilson RJ Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.
↑ Harari F., Palmer E. Graafeiden luettelointi. - Maailma, 1977.

Kirjallisuus

Yu. M. Burman, kurssin muistiinpanot " Polynomien kriittiset arvot ": [1] , [2] , [3] , [4] .
M. E. Kazaryan, kurssin " Pyöreän haaroittuneiden päällysteiden geometria, topologia ja kombinatoriikka " muistiinpanot .
A. Cayley. Lause puista (neopr.) // Quart. J Math. - 1889. - T. 23 . - S. 376-378 .
T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz-luvut ja Hodge-integraalit .