Permutazioni che (non) si mordono la coda.

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Permutazioni che (non) si mordono la coda.

Messaggio da Gottinger95 »

Sia \(\sigma\) una permutazione di \(A= \{1, \ldots, kn\}\). Sia \(m=|C|\), con \(C \subset A\) tale che \(x \in C \rightarrow \sigma(x), \ldots, \sigma^{k-1}(x) \not \in C\).
Fissato \(k\), trovare la probabilità che \(m\) sia massimo al variare di \(\sigma, n\).

A me viene:
Testo nascosto:
\(P= \frac{1}{2k}\)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Permutazioni che (non) si mordono la coda.

Messaggio da Gottinger95 »

Il problema secondo me è istruttivo, perciò metto qualche hint:

Hint 1:
Testo nascosto:
Sia \(G\) un grafo orientato di \(kn\) vertici: da \(u\) parte una freccia a \(v\) sse \( \sigma(u)=v\). Cosa cerchiamo adesso? Che significa \(m\) massimo?
Hint 2:
Testo nascosto:
Visto che la permutazione è biunivoca, \(G\) è un digrafo 1-regolare, perciò composto da cicli disgiunti. Quanti elementi posso mettere in \(C\) da ogni ciclo in modo che la proprietà di \(C\) venga rispettata? Quando questo numero è massimo?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Permutazioni che (non) si mordono la coda.

Messaggio da Gottinger95 »

Up
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Rispondi