En matemàtiques, específicament en combinatòria, les funcions d'aparcament són unes funcions que generalitzen les permutacions.
Definició i aplicacions Una funció d'aparcament de longitud és una seqüència de enters positius, cadascun en el rang d'1 a , amb la propietat que, per a cada fins a la longitud de la seqüència, la seqüència conté com a mínim valors que són com a màxim . És a dir, ha de contenir com a mínim un 1, com a mínim dos valors que siguin 1 o 2, com a mínim tres valors que siguin 1, 2 o 3, etc. De manera equivalent, si la seqüència està ordenada, aleshores per a cada en el mateix rang, el el valor de la seqüència ordenada és com a màxim
Existeixen 16 funcions d'aparcament de longitud 3:
(1,2,3), (2,3,1), (3,1,2), (3,2,1), (2,1,3), (1,3,2), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2), (2,1,2), (2,2,1), (1,1,1).
miniatura|Aparcament en un carrer de sentit únic El nom s'explica amb el següent experiment mental. Una seqüència de els conductors de cotxes circulen per un carrer de sentit únic places d'aparcament, on cada conductor té una plaça d'aparcament preferida. Cada conductor viatja fins a arribar a la seva plaça preferida i aparca a la primera plaça disponible. Una funció d'aparcament descriu les preferències per les quals tots els cotxes poden aparcar. Per exemple, la funció d'aparcament (2,1,2,1) descriu les preferències per les quals el primer i el tercer conductor prefereixen el segon espai, mentre que els altres dos conductors prefereixen el primer espai. El primer conductor aparca a la plaça 2, el segon a la plaça 1 i el tercer a la plaça 3 (perquè la plaça 2 està ocupada). El quart conductor comença a buscar un espai lliure a l'espai 1, però no el troba fins a l'espai 4; tots els espais anteriors estaven ocupats. La seqüència (3,3,1,3) no és una funció d'aparcament: massa conductors prefereixen l'espai 3, de manera que l'últim conductor comença a buscar un espai després d'haver passat l'únic espai lliure i no podrà aparcar. Si una funció és d'aparcament, aleshores qualsevol permutació d'aquella funció d'aparcament continuarà sent funció d'aparcament.
Les funcions d'aparcament també tenen una aplicació més seriosa en l'estudi de taules hash basades en el linear probing, una estratègia per col·locar claus en una taula hash que s'assembla molt a l'estratègia d'aparcament unidireccional per a cotxes.
Enumeració combinatòria El nombre de funcions d'aparcament de longitud és exactament Per exemple, per a aquest número és
John Riordan atribueix a Henry O. Pollak el següent argument per a aquesta fórmula. En una carretera circular d'un sol sentit amb espais, cadascun dels els cotxes sempre podran aparcar, independentment de la preferència que tingui cada conductor pel que fa al seu espai de sortida. Hi ha opcions per a les preferències, cadascuna de les quals deixa un espai buit. Tots els espais són simètrics entre si, per tant, per simetria, hi ha opcions per a preferències que deixen espai com l'espai vacant. Aquestes opcions són exactament les funcions d'aparcament. Les funcions d'aparcament també es poden col·locar en bijecció amb els arbres d'expansió en un graf complet amb vèrtexs, un dels quals es designa com a arrel. Aquesta bijecció, juntament amb fórmula de Cayley per al nombre d'arbres d'expansió, mostra de nou que hi ha funcions d'aparcament.
Moltes investigacions han estudiat el nombre de funcions d'aparcament d'una forma especial. Com a cas especial molt simple, les funcions d'aparcament que permeten que cada cotxe aparqui al seu lloc preferit són exactament les permutacions, comptades pels factorials. Les funcions d'aparcament que permeten a cada cotxe aparcar al seu lloc preferit o al següent lloc es compten mitjançant els números de Bell ordenats.
Referències
Categoria:Combinatòria