Permutazioni che (non) si mordono la coda.

[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}\)

[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?

[Gottinger95]

Up