I folding come generalizzazione delle $u$-parking function

Problemi enumerativi, teoria dei grafi ...

Moderatore: Moderatori

I folding come generalizzazione delle $u$-parking function

Messaggioda salvo.tringali il lun 3 nov 2014, 10:52

Siano $n$ un intero positivo e $\mathbf u$ una funzione $[n] \to \mathbf N^+$, dove $[n] := \{1, \ldots, n\}$. Una $\mathbf u$-parking function, nel senso di Yan, è una qualsiasi funzione $\mathbf a: [n] \to [n]$, qui identificata con la sequenza $(a_i)_{i=1}^n$, con la proprietà che $a_{\sigma(i)} \le \mathbf u(i)$ per ogni $i \in [n]$, dove $\sigma$ è una qualche permutazione di $[n]$ tale che $a_{\sigma(1)} \le \cdots \le a_{\sigma(n)}$; cf. qui (la definizione data nell'articolo è leggermente diversa, ma equivalente).

Provate che esistono un protocollo semplice $\mathcal P_n$, indipendente da $\mathbf u$, e un pattern $r_{\mathbf u}$ di $\mathcal P_n$ tali che ogni $\mathbf u$-parking function sia un $\mathcal P_n$-folding di pattern $r_{\mathbf u}$, e viceversa (v. qui per la terminologia).
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Torna a Combinatoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite