Numero di Permutazioni

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Nadal21

Numero di Permutazioni

Messaggio da Nadal21 »

Per ogni $ n \geq 2 $ sia $ S(n) $ il numero di permutazioni $ \sigma $ di $ \{1, 2, \ldots , n\} \quad $ t.c.

$ \forall i \leq (n-1) \quad \quad \mid \sigma(i) - \sigma (i+1) \mid \quad \leq 2 $

Trovare $ S(15) $ sapendo che $ \sigma(1)=1 $ e $ \sigma(2)=2 $
Ultima modifica di Nadal21 il 02 apr 2016, 15:39, modificato 1 volta in totale.
RiccardoKelso

Re: Numero di Permutazioni

Messaggio da RiccardoKelso »

Nadal21 ha scritto:
$ \quad \quad \mid \sigma(i) - \sigma (i-1) \mid \quad \leq 2 $
Scusami, per caso è $ \mid \sigma(i) - \sigma (i+1) \mid \quad \leq 2 $ ?? Chiedo solo perché mi sembrerebbe più intuitivo in questo modo, poi magari proprio per quello non è così
Nadal21

Re: Numero di Permutazioni

Messaggio da Nadal21 »

sì è col più :lol: ho corretto
RiccardoKelso

Re: Numero di Permutazioni

Messaggio da RiccardoKelso »

Chiedo conferma del risultato
Testo nascosto:
1966
Nadal21

Re: Numero di Permutazioni

Messaggio da Nadal21 »

scusa se ti rispondo solo ora, ma a me viene un numero più basso... ma non sono sicuro di quello che ho fatto.Tu come hai fatto a trovare quel numero?
RiccardoKelso

Re: Numero di Permutazioni

Messaggio da RiccardoKelso »

Io le ho contate suddividendo in casi a seconda della posizione di un estremo. Sia $C(n)$ il numero di permutazioni che rispettano le richieste del problema e che in più soddisfino: nella prima posizione a sinistra possono esserci solo $2$ degli $n$ elementi. Evidentemente il caso in cui $1$ è nel primo posto a sinistra racchiude $C(14)$ permutazioni. Se $1$ è in seconda posizione, abbiamo invece (a seconda che la permutazione inizi con $2-1-3$ o $3-1-2-4$, notiamo che in quest'ultimo caso il $4$ è obbligato) $C(13)+C(12)$. Procedendo così si arriva fino a quando $1$ è in posizione centrale, caso che racchiude $2$ sole permutazioni. Il resto è simmetrico, quindi si ha $S(n)=2\cdot (1+\sum_{i=1}^{n-1}C(i))$. Queste $C(n)$ sono delle brutte bestiacce (almeno a mio parere), ma abbiamo $C(1)=1,\: C(2)=2,\: C(3)=4$, poi vediamo come si comportano. Consideriamo a titolo esplicativo $C(5)$, cioè le permutazioni che soddisfano le richieste del problema $S(6)$ con $1$ in prima posizione. Mettendo il $2$ in seconda ci si riconduce ovviamente a $C(4)$. Mettendo invece il $3$ in seconda posizione notiamo che il $2$, potendo stare vicino solo al $4$ (in questo specifico caso, siamo a $1-3-$),dovrà essere necessariamente così $1-3-2-4-$, il che racchiude ancora $C(2)$, oppure lo si mette in fondo $1-3-...-2$. Notiamo allora che in quest'ultimo caso però c'è solo una permutazione possibile dato che si procede per passaggi obbligati, in quanto $1-3-...-2\rightarrow 1-3-...-4-2\rightarrow 1-3-5-...-4-2\rightarrow ...$. Si ha allora $C(n)=C(n-1)+C(n-3)+1$. Con una simpatica tabella si calcolano tutti senza problemi fino a $C(14)$ ed eccoci qui.
Rispondi