I numeri di catalan

[Gerald Lambeau]

Ok, penso sia fattibile, ci penso un po' su.

[Gerald Lambeau]

Per intenderci, un quadrato $2 \times 2$ non è ottenibile in questo modo, giusto?

[Gerald Lambeau]

C'è qualcosa che non mi torna: per $n=3$ se non contiamo il quadrato $2 \times 2$ sono $4$ poliomini, se lo contiamo sono $6$ perché per ottenerlo dobbiamo considerare anche la L fatta di tre quadrati (quella senza l'angolo in alto a destra), ma $C_3=5$. Sbaglio qualcosa?

[Ila_mengu]

il quadrato 2x2 me lo considera tra i poliomini con semiperimetro 4 ma la L che dici tu invece no. quindi i casi rimangono 5 per n=3

[Ila_mengu]

http://www.geometer.org/mathcircles/catalan.pdf in questo file a pag. 5 c è la figura che volevo inviarti

[Gerald Lambeau]

Sono definiti in un modo un po' strano, sono riuscito a cavarci ben poco... Tu che ci hai sicuramente pensato più a lungo di me, hai avuto qualche idea che secondo te vale la pena di considerare?

[Ila_mengu]

http://www-math.mit.edu/~rstan/ec/catsol.pdf in questo file nella parte (l) dimostra una biiezione tra i poliomini parallelogramma e l insieme delle parentesi bilanciate solo che non l ho molto capito.

[Ila_mengu]

http://www.dsi.unifi.it/~pinzani/article.pdf oppure qui C è un equivalenza con i cammini di dick mi basta anche dimostrare questo .

[Gerald Lambeau]

È difficile da formalizzare, per adesso butto giù qualche idea per non scordarmi tutto il ragionamento che ho fatto, domani cercherò di sistemare.
Guardo i due percorsi, quello superiore e inferiore, nel quale è chiuso il poliomino parallelo: chiamo $SS$ e $SD$ le mosse di aggiungere rispettivamente un trattino in su o uno a destra al percorso superiore, analogamente chiamiamo $IS$ e $ID$ per quello inferiore.
Farò corrispondere gli $SS$ e $ID$ a delle "(" e gli $SD$ e $IS$ a delle ")".
Passo 1: a ogni poliomino parallelo di perimetro $2(n+1)$ assegno una stringa di $n$ "(" e $n$ ")". Guardo colonna per colonna: nella prima ignoro il trattino più in basso, poi conto i trattini $SS$ e scrivo altrettante "(", poi aggiungo una ")" per il trattino $SD$, poi chiudo con tante ")" quanti gli $IS$. Nelle colonne in mezzo faccio così: parto con l'$ID$ e gli $SS$ per aggiungere le "(", poi considero il $SD$ e gli $IS$ per aggiungere le ")". Nell'ultima colonna seguo lo stesso ordine, solo ignorando il trattino $SD$.
Applicando questo meccanicismo trovo da una serie di "(" e ")" il poliomino: basta ricordare che per la prima serie di "(", quella che rappresenta la prima colonna, non è rappresentato il trattino $ID$, che altrimenti è sempre rappresentato dalla prima di una serie di "(", mentre nell'ultima serie di ")", quella che rappresenta l'ultima colonna, non è rappresentato il trattino $SD$, che altrimenti è sempre rappresentato dalla prima di una serie di ")".

Ora immaginiamo una pulce $A$ che si muove seguendo le $SS$ e le $SD$ a partire dal punto $(0, 0)$ e una pulce $B$ che segue le $IS$ e le $ID$ a partire dal punto $(1, 0)$: dato che alla fine ci saranno tante $SS$ quante $IS$ e tante $SD$ quante $ID$ (di queste ne ignoriamo una sia sopra che sotto), alla fine le due pulci avranno sempre distanza 1 in orizzontale e 0 in verticale. Queste pulci ci aiuteranno dopo (o forse domani).

Ci piacerebbe che ad ogni colonna che guardo il numero di "(" che vado a scrivere è maggiore del numero di ")", e viceversa che per ogni stringa di "(" e ")" che rispetta questa cosa trovo un poliomino che funzioni: avrei così la bigezione voluta!
Facciamo la prima freccia. Qui ci vuole un po' di immaginazione visiva: supponiamo di essere ad una colonna che non sia l'ultima. Ogni $ID$, tranne il primo che lo ignoriamo, mi "chiude" il $SD$ precedente, resta solo l'ultimo $SD$. Ora, se fosse per assurdo che il numero totale di $IS$+1 (il +1 è l'unico $SD$ non eliminato) fosse maggiore del numero di $SS$, allora la pulce $B$ non solo a toccato $A$, chiudendo prima il poliomino, ma forse l'ha anche superata!
Viceversa, se io suppongo di avere una stringa di parentesi che soddisfa e inizio a costruirci il poliomino, se mi fermo a una colonna che non sia l'ultima ovviamente, grazie alle ipotesi, ottengo il contrario dell'assurdo di prima, e cioè che ho sempre un "buco" per aggiungere un'altra colonna, che era quello che volevo. NB: il buco è di lato e non sopra perché per ogni colonna tranne l'ultima il trattino che "chiude" da disegnare per primo è sempre quello $SD$.

E vabbè, farà schifo sta spiegazione, spero tanto tu sia molto bravo a leggermi nella mente perché lì (qui per me) dentro è chiara la cosa, mentre la trasposizione che ho fatto è una cosa incomprensibile...

[Ila_mengu]

Grazie mille davvero .. Poi appena riesco ci do una letta.. Devo cercare di formalizzare al massimo perché la devo scrivere sulla tesi