OliForum Matematico

In quanti modi posso scegliere il colore della prima regione?

In quanti modi posso scegliere il colore della seconda regione, una volta che ho scelto quello della prima?

E tutte le altre regioni?

Come sistemo il fatto che $n+1=1$?

$$k(k-1)^{n-2}(k-2)$$?

in questo caso non contano simmetrie e rotazioni

$(k-1)^n+(1-k)\cdot(-1)^{n-1}$

Cominciamo con una bella bigezione: vogliamo contare il numero di parole lunghe $n$ lettere, ciascuna scelta da un insieme di $k$ lettere date, tali che due lettere consecutive siano diverse e la prima e l'ultima lettera siano diverse. Ovviamente, dato un $n$-agono a ogni modo buono di colorare può essere assegnata una parola buona e viceversa, inoltre come sappiamo dalle ipotesi due configurazioni ottenibili per simmetria e/o rotazione l'una dall'altra, ma che a cose normali hanno almeno una regione colorata diversamente, sono da considerarsi distinte, quindi non avremo il problema di contare dei doppioni usando le lettere, dunque stiamo contando la cosa giusta!
Sia $B_n$ il numero di parole buone di $n$ lettere, e $C_n$ il numero di parole di $n$ lettere che non hanno lettere consecutive uguali, ma che hanno la prima e l'ultima lettera uguali.
Quanto vale $B_{n+1}$? Possiamo scegliere in $k-2$ modi la lettera da aggiungere a una delle $B_n$ parole buone ($-2$ perché dev'essere diversa da quella che prima era l'ultima e che ora sarà la penultima e dalla prima), oppure $k-1$ modi di scegliere la lettera da aggiungere a una delle $C_n$ parole non buone ($-1$ perché dev'essere diversa da quella che prima era l'ultima e che ora sarà la penultima e dalla prima, ma essendo in questo caso la stessa si toglie solo $1$ e non $2$), per un conto totale di $B_{n+1}=(k-2)B_n+(k-1)C_n$.
E $C_{n+1}$ quanto vale? Non possiamo formarlo dai $C_n$, altrimenti avrebbe l'ultima e la penultima lettera uguali, quindi dobbiamo formarlo dai $B_n$, e siccome la prima lettera dev'essere uguale all'ultima non abbiamo scelta, quindi $C_{n+1}=B_n$.
Dunque ci ricaviamo che $B_{n+1}=(k-2)B_n+(k-1)B_{n-1}$, inoltre è intuitivo che $B_3=k(k-1)(k-2)$ e possiamo, usando le relazioni trovate, tirar fuori che $B_4=k(k^3-4k^2+6k-3)$, dunque vi risparmio la risoluzione di questa ricorsione e vi scrivo subito che $B_n=(k-1)^n+(k-1)\cdot(-1)^n$ (ieri mi era venuto un risultato impostato in maniera diversa perché avevo fatto una ricorsione shiftata).