Anàlisi Combinatòria(x)

Pub . Mat . UAB hó 10, - Desembre1978 , Anhlisi Combinatfria(x) CárlesSim6 Secci6 de Matemhtiques IIniversitat Autónoma de Barcelona introduoci6 .- La combinatoriaapareix ja a 1'antiguetat lligar da a moltaproblemas "populars" al tractor de donar respostaala pregunta : de quantesmaneras hompotferuna oerta cosa? Estavatambéenrelac16 amo problemas de Teoria elemental ds Nombres (aue no és pos certament senzilla!) i, molt després, amo problemas de chlcul de probabilitats . El fet de que sigui poc corrent el tenir contacte amo 1'Anhlisi Combinatoriadegut ala plana d'estudi actuala és una de les motivacions d'aquesta conferbncia . El nom Anhlisi Combinatória és,degut a August de Morgan (Differential and Integral Calculus, Londres 1842, p .335) : "Consisteix principalment en l'anhlisi de desenvolupaments complicate per mitjh de la consideraci6 i agrupaci6 a priori de les diferents combinaciona de termas que entren en ola coeficiente" . Veurem Que en certscasos s'ha donat la volta a aix8 : ala chlculs de cortes combinaciona es fan mitjangant 1'estudi de .desenvolupamente(usant les funciona generatrius) . Más modernament (Riordan) es diu objectiu de l'A .C . el trobar el nombre de maneres que hi ha de fer alguna operaci6 ben definida . Berge ho defineix con larecerca de configuras ciona (és a dir : aplicacione d'unconjunt d'objectes en un (x) Conferbncia Teta el 7 de desembre-de 1977 a la IIniversitat Autónoma ; de Barcelona . 7 1 conjunt abstracto finit), la seva enumeraoió i recompteo ffom pot distingir vhries qüestions s " Estad¡ d'una configuraci6 coneguda, recerca d'una configuració desconeguda, recompteexacto del nombre de configuracions, recompte aproximat, enumeracl6 de configuracions i classificaci6o Per aquestes dltimestasques és gairebé lmpresoindiblo l'ásdo calculadora . automhticso El mateix 'succeeix per les aplicacions,a problemas - d'optimització, de les que el problema del viatjant de comerq n'ésun é~ple s Qonéixent el cost per anard'una ciutat , Ai a una A j , quina és la manera más económica de fer un recorre~ gut sortint de la ciutat origen A o 1 tornant a elladesprés d'haver paseat per totes les altres? Apareixen problemescombinatoris enchlcul de probabilitats, estadística,teoria de nombres, topologia, estructura química, recerca d'operacions, teoria de la informaci6, atoo Sovint és important "reduir" un problema a combinatoria, perb pot ésser encara molt difícil . Per exemple, hom . had'omplir un tauler de n filos 1 n columnas posant a cadaquadre una lletra i uw número de manera que cadalletra i cada número han de aparbixer exactament un cop a cadafila ia cada columna, perb no es pot repetir cap de les parelles(llétra,número)e Unatal configuraci6 s'anomena un biquadrat llatf ortogonal . Es coneixien antigament exemples fins a  n = 5o Eulerdigub queper a n > 5  no hi havia soluci6e La resposta exacta no ha estat donada sin6 al lg6o en qué hom provh que hi ha soluci6 per a tot n diferent de 6 0 Fem un parbntesi per a destacar que en el treball amó calcolador automhtic de habitual, per la ena=raoi6 de configurar cions, e] . generar-les °ordenadament" (per exemple, les permutacions o els subconjunts d'un conjunt donat)o Si les configu7 2 Gi0il8 : q119 :,C,B,3rgWm -esM cotip9,aea $  , S8 V8 .2'j f'icai 91 Q18 , óomg],eixea . Ea bbaic per l,'eatalvi de t~ el trectar de decilo =da M .at' posglbler . (Adhuc a ~ generar) al l a configarad6 que en genera aatisfark les' condiciona establertes . 31 no da , així hom pases : a . la se4ent . La técnica anomenada backtrao _ktng ea, basada en aqueata abservacid . Per exemple, podem preguntar-nos quia " és el nombre mhxim de salta del cavan en un .tauler d'escaca . de manera quelea línies que uneixen ala centres delsquadressuccessivamentocupatspela cavalls no es tallin . Ela temesde obloul a6n molt grana . No de siné recentment que_ hom ha trovat la soluci6 usant backtracking : 36 . Es ja problema difícilla estimació acurada del nombre de pasaos a fer . Ea problemes d'optimitsaaió discreta és moltcorrentusar la mateixatécnica si b6 hom la coneix sota el nom dembtode de branch and bound . Si el nombre de pasaos a fer per aconseeguir 1'bptim és inabastable hom . pot generar configuraciono alcathriment . Aixi . potserno boa arribaal bptimperb si a solucionsquasi-bptimes . Parlarem a continuaci6 d'üns poca temes dintro de 1'A .C . . Elemento .- Sabem que si Card(A)- m  i  Card(1) Card{f lfs% --a A} - vi  i s'obtenen les variaoione amb repetaci6 . Card(fIfsX - A, f injectiva} a m(m-1) . . .(m-n4l) _ (m) n o variaciona . Si  ía= ?, tenim el nombre de permataciono . Daltrabanda Card{$EP(A)j6ard(B)=n-1 - (nm)  . (combinacioas, donarles pela coe .ficients binomialo) . Diguem que el polinomi factorial (x) n es pot escriure com (x) = s o 4. al x 4. ... i s nxn n n : n  n llavora 9 a on  s9 ., s'anomenen nombres de Stirl  ...  . . ing de ? primeraeephcie i satiofan . los relacionsYs e n = o, re n = 1, ' e n ~ .1  e n  .  n s~ . , ., !Un altrenombre de . tipus factorial és (m) n =  ,(Wn-1) queens . diu, ;d®-ouantos maneree k hp  pot,aóllgcar, n olnjectes orv denats . en m oapses, SiA éá ~un tohjunt ordenat1laeorg ,, ~ , Card{f [1s á --A,f creixent c (m) /n?  i  teáirlí Y lms-cómbinaefons , amb repetición Ezom . generalitzafhcilment élsnombres binómials als multi= nomials ,  .  _ .  . Es clac  q,  p  n,  n que el . nom , bé de,  ue (  si)n = . n~ .  (nl .0 . . . n  T Ta, ip P11 i=1=P, 57 ni n i=1 Un exemple de aplicaci6 és el chicu1 del nombre de camine _n  _ %T 74 al Si Card(X) = n  per uxia partici6 de Z del ti pus 1  2 ? ee yak entendrem una partici6en al parts~de 1 element cada una, a2 . . e, . de 2 elements, etc . El nombre de tala particions val bbviament . El nombre de particions de % en m classes (no buides), m é n es din nombre de Stirling de segona espbcie S m i da lo n mateix que Hbm ven fhcilment que xn S k 3 k-l 4 .kSk , 1<k<n n! k a T(a !(1!) i i=1 i m . Card {f l f : % -- A, exhaustiva} n 7Sñ (x) k  i que  Sñ = Sa,= 1 , imatge m&xima 6 6 3o  n 1 m 12o 36o  n!( m \?-2a .  6~  1  62 54o 156* 18o\2 m primer exemple que  n~ m  m! S n donem de ftiuici6 generatriu . Funcionsgeneratrius .- Sigui S = {a,b, . . .}  unconjunt desordenat . La funci6 generatriu de subconjunts (formal) da (l4 . a) (l4 . b) (14 . c) . . . = l4~aib4o4, . . .4 .ab4.ac4 . . . .  (1=O) . El total de Aplicacions de % en A d maneres de partir [m --l 2 3 4 5 X . enclasses és n=l1 l`-, 2 3 4 5 Sñ . . . Sñ = .B 21 l"-, 2 6 12 20 (nombre de Bell) . 3 1 6 6 24 6o Hom demostra que 4I 1 14 36 24 120 °° ñ - ., .n, e (et-1) 51 1 30 lr.a 24o\12 Per generar amb repetició enscal la funció generatriu (l4 . a4-aa~aaaa .° ° ,) (l4 .b~bb& . tíbb°°°)°,°°° = sigui S = ~a,b,,c,°°°} un conjunt ordenat° Si volem escriure'1 de totes les manerespossiblessegonal'ordre(permutacions), la f°g° és a b C Per serveix per a designar el permenent, definit així s n Per(s ij ) = Z  TT a d(i)91  , a om  S n vol dir el grup simbtrio° i , j =l .n  TES n i=1 Destaquem que P(AB) ;IP(A)°P(B) ° El cálcul de Det(A) requereix 0(a 3 /3) operacions (usant la triangulació d® Gauaa ; s partir d® la definició és 0((n-1)n!) )° Per contra, lo millor que hom ha obtingutquant al cálcul de P(A) ésfer-ho en 0(n2 n-l ) operacions, 1 és problemaobert el millorar-ho° Si  ~ a lj =1  i  Z a ij = 1  la matriu A e9 diu doblement j esto(-ágtica° Llavors van der ;Naerden va . conjecturar que Fgr(A)  n!/n n , i que el mínim s'obté si a ij = 1/n ° Se sap que ós Certa en dimensió baixa, que el puntdonatéa mínim local, peyó no hom té encara una demostraci6 de la conjeCtura° La f°g° de subconjunt9 ordenata a ° obté fb .cilment com El generador de subconjunts de m elements ordenata és (a 4.b4- °°°)(a4b4- °°é)°°°  -(a .4 :b4 . c& °°°) m ,  ¡si volem Iota els subconjunts ordenats ens cal usar  1 - s+b + . . .~  ' Es possible construir f .g . mambriques : Si donam a cortes variables valor 1 1 a d'altres el zero quedaran els termes que portentotes les variables amb 1, 1 ola podem comptar . Exemple : quants subconjunts de k elements menta? Donem a tots els elements (1 1 * x) n . Llavors només cal veure Quantssubconjunts ordenate k 1  k" hi ha en un conjunt de n eleel valor x . La f .g . val ara el coeficient de xk : (k` amb reDetici6 hi ha de k elements? Cal calcular simplement el coeficient de x  a  1nx , és a dir n . En general, donada una successi6 (a n ) hom defineixen funcions generatrius  0 (t) _  a t n i  q(t) _  b t n /n!  , i en vtn  n k  r . ries variables  O(t,u) = Z a nk t u  . Vegem uns quanta exemples de l'ús de les f .g . per a obtenir informaci6 sobre successiona donados per recurréncies Consideremla successi6 de Fibonacci : F o=F 1 = 1, 1  F n = F n-1 +F n-2 . Llavors hom té  = 14 . t+ ~-- F nt n = n32 1 1-t-t 2 Si r l i r 2 s6n les arrels del denominador és immediat que Fn = (rl+l - r2+1) / (r l-r 2 ) l+t+ Z- : (F n-1 +Fn-2)tn = l+ t0+t 2 0 nr2 que implica 0 = l+ 1sñ nñ uk = (1+t) u ,  1+ZSñ nn uk = exp(u(et-1)) Aquesttipue de raonament és aplicable a multa polinomis ortogonals, funciona esoecials, nombres de Bernoulli i d'Euler, etc . El método usat pel nombres de Fibonacci pot usar-se per tota equac16 en diferbncias finitos de coeficiente constants . Pels nombres de Stirling tenim les següents f .g . Vegemalgunes aplicacions no tan elementals de les feg . El problema de Catalan consisteiz en calcular de quantes maneres hom pot posarparbntesien,laexpressi6 del producte P = X1%2 eo .X n o Per exemple, si n= 4 podem escriure P= X2 .X2 .(X 2 .X)X = (X.X 2 )X = X(X 2 .X) = X(X .X 2 )  i e4 = 5 , La recun-1 rrbncia és  a n = 37 alea n-k , amb ao =o, a l =1 o Construim la 1  .  n-1 funci6generatriu s  O (t) = t&~ a tn = t& T t n ( E a a  ) n~2 n  111 :2  1 k ~k tó  7~  ahakt k4rh = t4 . (Fa ht h ) ( 57 akt k ) = t4»02(t) i per tsnt h,káo ~(t)=2(11-4 t) = 2L1-Z( 1 á 2 1(-4t) n , de on  an = ñ 1 2 n-1) 9 ques6nels anomenats nombres de Catalano per np 4  tindriem  (X 2 .X)X = (X.X 2 )X = X(X 2 .X) = X(X .X 2 ) i nomás ens resta b 4 = 2 , La recurréncia és más complicada < b 2P-1 = bl b 2p-2 '- . . . 4.bp-2bp  ,  si  p=2 i d'aixa surt b2p = b 1 b 2p-1  oeo  bp_ 1b p`11 41 1 bp }l jv Ia1 2 ~(t) = t~2~2(t)4 .2¢(t2) o si fem  _  -1 tenimfinalment 1'equaci6 funcional  1 2(t) 4~ j(t 2 ) 4 .2t = o e La seva soluci6 és encara problema obert, i Mhuc la estimaci6 asimptbtica dele "'coeficients romhn desconeguda . Principi d'inclusi6-exclusi6 oLa basen'éslo que en probabilitats hom coneix com a farmulad'Euler-Poincaré s Card(UA ) _ 57 Card(A ) -  Z :  Card(A i nA) 4 . . . . 1i l~i~n  il :5i<jin  3 Si hom considera els parhntesi commutatius ('Wedderburn) 4. (-1 . ) n-l Card(A l nA 2 . . .nA n ) Sigui % un conjunt de n objectes . Homdin que una permutaci6 ade . % és un desarranjament si no té cap punt fix . Comptem els desarranjamente usánt .l a fbrmula d'Euler-Poincaré : d( n ) =n ! - ( n . ( n -l)! - (2) ( n -2)! + . . .) = n!  (1-i! 4 . 2! . . . . - n!/e  (si n és gran) . La f .g . dels desarranjamente és e t(1~ t) -1 . Vegem general¡tzacions del desarranjaments : Un k .n rectángle llatí és una matriu d'aquestes dimensions, formada amb elements de % tal que a cap fila ni columna hi ha elements repetits . Si k= 2 tenim els desarranjamente . .Si k= 3 hi ha recurréncies i estimaci6 asimptbtiea del nombre de rectangles llatins, perb, si k>3 no tenim ni Puna cosa ni 1'altra . Si k=n hom parla de quadratsllatins . Actualment es coneix la següent taula n , 2 3 45 6  7  8 nombre de quadratsllatins 114 56 940816942o8o 5352814o1856 L'estudi per nr9 és problema obert i difícil . Dintre aquesta familia hi ha el ben conegatprobléme des ménages : En una taularodona hi ha n parelles alternades (homedona) . Quantesmaneres hi ha d'asseure's sense que ningú tingui al costat la seva prbpia parella? Hom " fa el chlcul per reducci6 . Primer hom suposatotes lea dones assegudes (n!^2 possibilitato) . Sigui ~(n) el valor reduit . Definim una permutaeió 6 tal que 6(i)~i, £4 .1 si i-1-n-l ; 0-(n)~l,n . A 21  =  i41} , i=1=n-1} hom té ~(n)=Card(nA i ) A 2n  =  { 6 1 Q ( n ) - 11  J Llavors s'arriba a  ~(n) . = ~(-1) k (n - . k)! V k (n) , on V k (n) és k