[PDF] COUNTING LABELLED TREES reunir les elements d'un

View - Download COUNTING LABELLED TREES

Previous PDF

Next PDF

"COUNTING

LABELLEDTREES

J.W.MOON

MadeandprintedinGreatBritainby

longueserie. avaientparusousformedelivre. inbookform. standardforotherstofollow. finitemathematicsorprobabilitytheory. encouragement.

Edmonton,Alberta

February,1970

1.Introduction

1.1Definitions

1.2PropertiesofTrees

1.3Summary

AssociatingSequenceswithTrees

2.1PriiferSequences

2.2TreeFunctions

2.4SpecialCases

,3.InductiveArguments

3.1SomeIdentities

3.2TreeswithaGivenDegreeSequence

3.4TheNumberofk-Trees

.3.5ForestsofTreeswithSpecifiedRoots

3.6ConnectedGraphswithOneCycle

3.7TreeswithaGivenNumberofEndnodes

3.8RecurrenceRelationsforT(n)

4.ApplicationsofGeneratingFunctions

4.1CountingConnectedGraphs

4.2CountingRootedTreesandForests

4.3CountingUnrootedTreesandForests

4.4BipartiteTreesandForests

4.5CountingTreesbyNumberofInversions

4.6ConnectedGraphswithGivenBlocks

5.TheMatrixTreeTheorem

5.1Introduction

5.2TheIncidenceMatrixofaGraph

5.3TheMatrixTreeTheorem

5.4Applications

5.5TheMatrixTreeTheoremforDirectedGraphs

5.6TreesintheArc-GraphofaDirectedGraph

5.7ListingtheTreesinaGraph

6.TheMethodofInclusionandExclusion

6.1Introduction

6.2TheNumberofTreesSpannedbyaGivenForest

6.3TheNumberofSpanningTreesofaGraph

6.4Examples

6.6MiscellaneousResults

7.ProblemsonRandomTrees

7.1RandomMappingFunctions

7.2TheDegreesoftheNodesinRandomTrees

7.3TheDistancebetweenNodesinRandomTrees

7.4TreeswithGivenHeightandDiameter

7.6RemovingEdgesfromRandomTrees

7.7ClimbingRandomTrees

7.8CuttingDownRandomTrees

AuthorIndex

SubjectIndex30

32
33
39
39
41
43
46
48
51
52
52
54
54
62
64
66
70
76
78
79
83
86
90
99
i109I112 1 "ii1 graphisanodeofdegreeone.

Figures1and2.

ofanyshortestpathjoiningthem. 1 2

Introduction

1111•

\23L23623..23. 1 1•

31\23..2

1 1

3/.23.-\2FIGURE1

•••-UD~12]••--

LLbJ

Manvel(1968».

endnodes. longestpathsinthetree. example,Riordan(1958)andKnuth(1968a). S 73

2.VI••12864

FIGURE4

correspondingsequences. canbeformedfromthenumbers1,2,...,n. sequencecorrespondstosometreeTn. T n betweenthesesequencesandthetreesTn. +6afJy1060 125
a 4 4 labelledn.) multinomialcoefficient (n-2)d1-1,...,dn-1. theselatterqnodesequals2(q-I)+p.) root. problemsforadifferenttypeoftree. ofthetype7icalledloops. h). h-1 c(H)=L{rrIr(SI)181-1"lf(SI)I}, f1=1 form somespanningsubtreeofD. sequences. thereare ofnodes. graphs. x"SlS2)-1+(S2SS)-1+...+(ShS1)-1). spanningsubtreestoconsider. thenh c(H)=Il!r(Sj)!St-1stt-1.

COROLLARY2.2.4.

nC1>...,Cte1>...,et (s-l)(r-l)r1-1,...,rT-1.Sl-1,...,ss-1 endnodes. n

L:(~)kn-k-1(n-k)k-1=2nn-2;

k=O wherethesumisoverallisuchthataj;::1.

THEOREM3.1.Ifn;::3,then

that wherethesumisoverallisuchthatdj;::2. d whenn=3. relation. n

An(x,y;p,q)=L(~)(x+k)k+P(y+n-k)n-k+q.

k=O listedinthefollowingtable. -10x-1(x+y+n)n -1-1(x-1+y-l)(X+Y+n)n-l

1-1y-l(x+y+n+f3(xW

2-1y-l{(X+Y+n+f3(x;2))n+(x+Y+n+a+y(x))n}

Theconventionisadoptedthat

a k==ak=k!,f3k(X)==f3ix)=k!(x+k), showthatthereare r"-l(r-1)(8_1)r-1Ck-1 followsfromformula(2.2». appealtoTheorem3.2,weobtaintheidentity n-2) (1965». obtainedfromdifferenttreesRninthisway. nlnodesintheithsubtree,thentherearen-k-l

C(n,k)=(n~1)2:C(n-k,t)kt,

t=l (n-1-nl)+...+(n-1-nk)=k(n-1)-(n-1) equalsone. obtaintherecurrencerelation n-k-1

C(n,k)=(n~1)L:(n~~~2)(n_k_l)n-k-t-1kt

t=1 =k(n~1)(n-l)n-k-2=(~=:D(n_l)n-k-1.

Theorem3.2nowfollowsbyinductiononn.

ofkdisjointtrees). n-cl-k

Ck(n,d)=(n~k)LCk(n-d,t)(kd)t.

t=1n-k

Rk(n)=LCk(n,d)={k(n-k)+W-k-1

cl=1 (~)Rin)={k(n-k)+l}Bk(n).

THEOREM3.3.If1~k~n,thenF(n,k)=knn-k-1.

Gobel(1963)provedthisbyfirstshowingthat

n-k

F(n,k)=L(n~k)ktF(n-k,t);

t=1 (rl+sk-kl)r8-1-1sr-k-1 andinthegeneralcasebyMoon(1967b).

Riordan(1964,1968b».

letv=nandu=n-k. whichthecyclehaslengthk,where1~k~n. thenodesatdifferentdistances,wefindthat (x)t=x(x-1)...(x-t+1)fort=1,2,....) inthegraphofjbelongtocycles,then "v"=2:F(t,u,v). theidentity ""knl-1n~2-1nf!.11-1_nn-k-1

Itisnotdifficulttoseethat

F(t,u,v)=(~)t!F(O,u-t,v),

""=F(O,u,v)+2:(u)tV"-t-2:(U)t+1V"-T(n)=n-1D(n,1)=nn-2. relation(3.8).Noticethat nn,

T(n)=LR(n,k)=L~iS(n-2,n-k)

1<=21<=2

n-2 =LS(n-2,k)(n)1<=nn-2, 1<=0

D(n,k)=(k-I)!(~)F(n,k)=(n)~n-1<-l.

functionsflater.by(3.7).. identityn (2x+l)n=LM(n,k)(x)1<" 1<=0 n x n=LS(n,k)(x)1<" thatthereare n-l x·x n

1=L(k+x-k)S(n-1,k)(x)1<

1<=0 n-ln-l =LkS(n-1,k)(x)1<+LS(n-1,k)(x)1<+1>

1<=01<=0~:.J{S(s-1,r-k)S(r-1,s-I)

(3.8)S(n,k)=kS(n-1,k)+S(n-1,k-1) thenumberoftreesTnwithexactlykendnodes. kn- 1 consequently, n-l

2(n-I)T(n)=L(~)T(OT(n-Oi(n-i).

1=1 moregeneralsetting.)

L(-I)f(~)(n-j)k=0

1=0] empty;italsoisequaltoanQk=n!S(k,n). nodes,then n-l

2(n-I)nn-2=L(7)il-1(n-on-I-I.

1=1

H(n,m,I)=L(-I)1-l(1)(~)C(n-j,m-j)(n-j)f,

1=1] byLemma1.1.Therefore, n-l

L(-I)i(~)T(n-j)(n-j)f=0

1=0] yieldsanotherproofofTheorem3.5,since n-l

R(n,k)=H(n,n-1,k)=L(-I)f-k(i)(~)(n-j)n-2

1=k] obtaintherelation n

2+C.L.T.

equaltothecoefficientofxkin (x+x2+...)1(1+X+x2+..-)n-I=xl(1_x)-n, (-I)k-l(-n)=(k+n-1-I).k-In-l

Therefore,

E(n+k,m+k,k)

kquotesdbs_dbs47.pdfusesText_47

[PDF] math sup exercices corrigés

[PDF] Math super compliquer milieu d'un segment

[PDF] math sur les conversion

[PDF] Math sur les distances ? une droite

[PDF] math svp

[PDF] math SVP urgent pour demain !!!!!!!!!!!!!

[PDF] math terminal l2 exercices corrigés pdf

[PDF] Math thales facile mais

[PDF] math théoreme de pythagore

[PDF] math triangle et cercle

[PDF] math trigonométrie

[PDF] Math trop énèrvant s**vp

[PDF] math type brevet

[PDF] Math un appartement a une superfine de 72 m2

[PDF] math un seul exo