Wedderburn – Etherington nummer - Wedderburn–Etherington number

De Wedderburn-Etherington tall er et heltall sekvens navn Ivor Malcolm Haddon Etherington og Joseph Wedderburn som kan brukes til å telle visse typer binære trær . De første tallene i sekvensen er

0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ... ( OEIS :  A001190 )

Kombinerende tolkning

Ottertrær og svakt binære trær, to typer forankret binært tre som telles av Wedderburn - Etherington -tallene

Disse tallene kan brukes til å løse flere problemer i kombinatorisk oppregning . Det n. Tallet i sekvensen (starter med tallet 0 for n  = 0) teller

• Antall uordnede rotete trær med n blader der alle noder inkludert roten enten har null eller nøyaktig to barn. Disse trærne har blitt kalt ottertrær, etter arbeidet til Richard Otter med deres kombinatoriske oppregning. De kan også tolkes som umerkede og urangerte dendrogrammer med det angitte antallet blader.
• Antall uordnede rotte trær med n noder der roten har grad null eller en og alle andre noder har høyst to barn. Trær der roten har maksimalt ett barn kalles plantede trær, og tilleggstilstanden som de andre nodene har på det meste to barn definerer de svakt binære trærne. I kjemisk grafteori kan disse trærne tolkes som isomerer av polyener med et angitt bladatom valgt som rot.
• Antall forskjellige måter å organisere en enkelt-elimineringsturnering for n spillere (med spillernavnene tomme, før du setter spillere inn i turneringen). Paringen av en slik turnering kan beskrives av et ottertre.
• Antall forskjellige resultater som kan genereres ved forskjellige måter å gruppere uttrykket for en binær multiplikasjonsoperasjon som antas å være kommutativ, men verken assosiativ eller idempotent . For eksempel kan grupperes i binære multiplikasjoner på tre måter, som , eller . Dette var tolkningen som opprinnelig ble vurdert av både Etherington og Wedderburn. Et Otter-tre kan tolkes som et gruppert uttrykk der hver bladnode tilsvarer en av kopiene av og hver ikke-bladnode tilsvarer en multiplikasjonsoperasjon. I den andre retningen kan settet til alle ottertrærne, med en binær multiplikasjonsoperasjon som kombinerer to trær ved å gjøre dem til de to undertrærne til en ny rotnode, tolkes som den frie kommutative magmaen på en generator (treet med en node ). I denne algebraiske strukturen har hver gruppering av som en av n -blad -ottertrærne sin verdi .${\ displaystyle x^{n}}$${\ displaystyle x^{5}}$${\ displaystyle x (x (x (xx)))}}$${\ displaystyle x ((xx) (xx))}$${\ displaystyle (xx) (x (xx))}}$${\ displaystyle x}$ ${\ displaystyle x}$${\ displaystyle x^{n}}$

Formel

Wedderburn - Etherington -tallene kan beregnes ved å bruke gjentakelsesrelasjonen

${\ displaystyle a_ {2n-1} = \ sum _ {i = 1}^{n-1} a_ {i} a_ {2n-i-1}}$

${\ displaystyle a_ {2n} = {\ frac {a_ {n} (a_ {n} +1)} {2}}+\ sum _ {i = 1}^{n-1} a_ {i} a_ { 2n-i}}$

begynner med basiskassen . ${\ displaystyle a_ {1} = 1}$

Når det gjelder tolkningen av disse tallene som å telle rotete binære trær med n blader, teller summeringen i gjentakelsen de forskjellige måtene å dele disse bladene i to undergrupper, og for å danne et undertre med hvert delsett som sine blader. Formelen for jevne verdier av n er litt mer komplisert enn formelen for odde verdier for å unngå å telle trær med samme antall blader i begge undertrærne.

Vekstrate

Wedderburn - Etherington -tallene vokser asymptotisk som

${\ displaystyle a_ {n} \ approx {\ sqrt {\ frac {\ rho +\ rho ^{2} B '(\ rho ^{2})} {2 \ pi}}} {\ frac {\ rho ^ {-n}} {n^{3/2}}},}$

hvor B er tallenes genererende funksjon og ρ er dens konvergensradius , omtrent 0,4027 (sekvens A240943 i OEIS ), og hvor konstanten gitt av delen av uttrykket i kvadratroten er omtrent 0,3188 (sekvens A245651 i OEIS ).

applikasjoner

Young & Yung (2003) bruker Wedderburn - Etherington -tallene som en del av et design for et krypteringssystem som inneholder en skjult bakdør . Når en inngang som skal krypteres av systemet deres kan komprimeres tilstrekkelig av Huffman -koding , erstattes den av den komprimerte formen sammen med tilleggsinformasjon som lekker viktige data til angriperen. I dette systemet er formen på Huffman -kodetreet beskrevet som et Otter -tre og kodet som et binært tall i intervallet fra 0 til Wedderburn - Etherington -nummeret for antall symboler i koden. På denne måten bruker kodingen et veldig lite antall biter, base-2-logaritmen til Wedderburn-Etherington-nummeret.

Farzan & Munro (2008) beskriver en lignende kodingsteknikk for forankrede uordnede binære trær, basert på å dele trærne i små undertrær og kode hvert undertre som et tall avgrenset av Wedderburn - Etherington -tallet for størrelsen. Ordningen deres gjør at disse trærne kan kodes i et antall biter som er nær den informasjonsteoretiske nedre grensen (base-2-logaritmen til Wedderburn-Etherington-tallet), mens de fortsatt tillater navigasjon i konstant tid i treet.

Iserles & Nørsett (1999) bruker uordnede binære trær, og det faktum at Wedderburn - Etherington -tallene er betydelig mindre enn tallene som teller bestilte binære trær, for å redusere antall termer i en serierepresentasjon av løsningen til visse differensialligninger betydelig. .

Se også

• Katalansk nummer

Referanser

Videre lesning

• Finch, Steven R. (2003), Mathematical constants , Encyclopedia of Mathematics and its Applications, 94 , Cambridge: Cambridge University Press, s.  295–316 , doi : 10.1017/CBO9780511550447 , ISBN 978-0-521-81805-6, MR  2003519.