Qual è il numero di isomeri non ciclici di un alcano con n atomi di Carbonio?
Matematizziamo il problema:
Siano dati n tetraedri uguali tali che possano unirsi a due a due tramite un solo vertice (che corrisponde all'impossibilità di legami multipli), tali che i vertici liberi siano in tutto 2n+2 (questo dovrebbe impedire le strutture ad anello), quante sono le possibili strutture? Due strutture sono diverse se non sono sovrapponibili (per mezzo di rotazioni, anche dei teraedri intorno ai vertici, ma NON effettuando simmetrie).
Buon divertimento
* This message was transmitted on 100% recycled electrons.
Marco, credo che tu abbia frainteso, perché già per n=4 ci sono almeno 2 configurazioni. Inoltre, il testo non dice se i tetraedri sono regolari, ma penso sia molto meglio supporre che lo siano!!
Mi pare che in generale il problema sia aperto.
Si, i tetraedri sono regolari (effettivamente, a torto, credevo che dire tetraedro significasse anche regolare... ), e tanto per dare un po' i numeri, ecco cosa succede in alcuni casi (preso da un libro):
n -> configurazioni
1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 3
6 -> 5
7 -> 9
8 -> 18
9 -> 35
10 -> 75
Uhm, decisamente il problema mi sembra non elementare, se non addirittura un problema aperto. Aursic, se mi confermi che non conosci la soluzione, sposto il thread in Matematica non elementare.
Una cosa molto importante qui è cercare di fare qualche passo avanti sull'annosa questione di capire cosa si intenda con "quante sono". Perché la funzione che chiedi di trovare è banalmente una funzione calcolabile. Ora, esibirti un programma o una funzione del lambda-calcolo che faccia questo lavoro mi sembra un'idiozia, e quindi ti chiedo in quale forma vorresti la risposta.
[Non conosco la soluzione... a dire il vero il problema l'ho "inventato"]
@Mind, cosa intendi con
>>cercare di fare qualche passo avanti sull'annosa questione di capire cosa si intenda con "quante sono"<< ?
Spostato da Combinatoria a Matematica non elementare.
----------------------------------
Aursic, con quella frase intendevo dire che non è chiaro che cosa vuoi sentirti dare come risposta. Se vuoi una dimostrazione che quella funzione è calcolabile, è un lavoretto di poco conto. Se vuoi trovare un'espressione che la calcola, è presto fatto.
Il guaio è che prima di scriverti qui un programma o una funzione del lambda-calcolo che restituisce il numero di isomeri in funzione di n, vorrei essere sicuro che tu non intenda qualcos'altro con "quante sono". Per esempio, potresti volere un'espressione particolare per quella funzione, o la vorresti vedere scritta come composizione di un certo insieme finito di funzioni.
Quindi, soprattutto se tu stesso non hai una soluzione, dovresti per prima cosa chiarire che cos'è una soluzione, e definire dei confini chiari al problema.
Credo fosse chiaro che si chiedeva una funzione (di qualsiasi tipo) che dato n fornisce il numero cercato. D'altra parte non ho parlato di dimostrazioni...
Anyway, credo che il problema (postato forse troppo ingenuamente) rischi di sconfinare troppo oltre i limiti di questo forum.
A te Mind la decisione se continuare o no!
* This message was transmitted on 100% recycled electrons.
Beh, allora possiamo costruire la tua funzione così:
- Prima definiamo una codifica per gli atomi di Carbonio: ogni atomo di Carbonio ha un numero d'ordine (positivo), e 4 numeri di riferimento ad altri atomi di Carbonio (che corrispondono agli atomi attaccati ai vertici del "tetraedro"). Inoltre, un vertice con uno 0 è un vertice non collegato.
- Adesso definiamo una codifica per gli alcani: ogni alcano è semplicemente un insieme di k atomi di Carbonio, con numeri d'ordine da 1 a k.
- Poi definiamo la funzione accettabile(alcano), che dato un alcano stabilisce se è ben formato, e se è aciclico. Anzitutto deve verificare che i vertici abbiano riferimenti "accoppiati". Se l'atomo i ha un vertice con riferimento j>0, allora l'atomo j ha un unico vertice con riferimento i. Infine, il grafo associato all'alcano non deve avere cicli, e dev'essere connesso (dove il grafo associato ha un vertice per ogni atomo, ed un arco per ogni coppia di vertici uniti). E' banale verificare che la funzione accettabile() è calcolabile, perché per ogni alcano si riduce ad un numero finito di operazioni "elementari" su grafi (per l'ultima parte, è sufficiente che verifichi che i vertici con 0 siano 2n+2, che non richiede nemmeno la costruzione del grafo associato).
- Poi definiamo un'altra funzione, isomorfi(alcano1,alcano2), che dice se i 2 alcani dati sono isomorfi, ovvero se esiste una permutazione degli indici degli atomi di alcano2, ed una permutazione dei riferimenti di ogni suo atomo, tale per cui i due alcani siano uguali. Anche questa funzione è calcolabile, perché deve solo permutare e confrontare un numero finito di interi.
- Adesso siamo pronti per enunciare la funzione aursic(n), che dato n restituisce il numero di alcani aciclici con n atomi di Carbonio, e quindi che risolve il problema. Basta che enumeri tutti i possibili alcani con n atomi, che si fa con un numero finito di operazioni: gli n indici sono fissati, ed è sufficiente far variare ogni riferimento di ogni atomo da 0 a n. Per ognuno di questi viene calcolata la funzione accettabile(), e se ritorna "vero" l'alcano viene memorizzato. Fatto questo, è sufficiente considerare gli alcani memorizzati, ed applicare la funzione isomorfi() su ogni loro coppia, eliminando gli alcani di troppo. A questo punto, la funzione restituisce il numero di alcani rimasti.
Matematizziamo il problema:
), e tanto per dare un po' i numeri, ecco cosa succede in alcuni casi (preso da un libro):