Cayleyn kaava - Cayley's formula

Täydellinen luettelo kaikista 2,3,4-merkittyjen pisteiden puista: puu, jossa on kaksi kärkeä, puut, joissa on kolme kärkeä, ja puut, joissa on 4 kärkeä. ${\ displaystyle 2 ^ {2-2} = 1}$${\ displaystyle 3 ^ {3-2} = 3}$${\ displaystyle 4 ^ {4-2} = 16}$

Vuonna matematiikan , Cayley kaava on tulos graafiteoria nimetty Arthur Cayley . Siinä todetaan, että jokainen positiivinen kokonaisluku , määrä puita on merkitty kärjet on . ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n ^ {n-2}}$

Kaavan vastaavasti laskee, montako virittävät puut on täydellinen kuvaajan leimatun kärjet (sekvenssi A000272 on OEIS ).

Todiste

Monet todisteet Cayleyn puukaavasta tunnetaan. Yksi klassista todiste, jolla on kaava käytetään Kirchoffin matriisi puu lause , kaava määrä ulottuu puiden mielivaltaisella kaavio johon tekijä on matriisin . Prüfer-sekvenssit antavat bijektiivisen todistuksen Cayleyn kaavasta. Toinen André Joyalin todistusvoimainen todiste löytää yksilöllisen muutoksen n- solmupuun välillä, jossa on kaksi erilaista solmua ja maksimaaliset suunnatut pseudometsät . Jim Pitmanin aiheuttama kaksoislaskemalla saatu todiste laskee kahdella eri tavalla suunnattujen reunojen erilaisten sekvenssien lukumäärän, jotka voidaan lisätä tyhjään kaavioon n kärjessä muodostaakseen siitä juurtuneen puun; katso Kaksinkertainen laskenta (todistustekniikka) § Puiden laskeminen .

Historia

Kaavan löysi ensimmäisen kerran Carl Wilhelm Borchardt vuonna 1860, ja se osoittautui determinantin avulla . Lyhyessä vuoden 1889 muistiinpanossa Cayley laajensi kaavaa useaan suuntaan ottamalla huomioon pisteiden asteet. Vaikka hän viittasi Borchardtin alkuperäiseen paperiin, nimestä "Cayleyn kaava" tuli alalla vakio.

Muut ominaisuudet

Cayley kaava välittömästi antaa määrä leimatun juuret metsien on n pisteiden, nimittäin ( n + 1) ^{n - 1} . Jokainen merkitty juurtunut metsä voidaan muuttaa merkityksi puuksi, jossa on yksi ylimääräinen kärki, lisäämällä kärki, jonka etiketti on n + 1, ja yhdistämällä se kaikkiin metsän puiden juuriin.

Juurtuneisiin metsiin ja pysäköintitoimintoihin on läheinen yhteys , koska myös n auton pysäköintitoimintojen määrä on ( n + 1) ^{n - 1} . MP Schützenberger antoi vuonna 1968 juuret metsien ja pysäköintitoimintojen välillä .

Yleistykset

Seuraavassa yleistetään Cayleyn kaava leimattuihin metsiin: Olkoon T _{n , k} leimattujen metsien lukumäärä n pisteessä, joissa on k kytkettyjä komponentteja, niin että kaikki pisteet 1, 2, ..., k kuuluvat eri yhdistettyihin komponentteihin. Sitten T _{n , k} = k n ^{n - k - 1} .

Viitteet