Tavoli rotondi e distinzione di sessi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 15 mar 2009, 06:43

piever ha scritto:Tra l'altro, sai se il risultato finale si può scrivere decentemente??
Il criterio oggettivo di decenza di una formula è l'efficienza di calcolo. Ovvero, una formula è essenzialmente un algoritmo, che ha una certa complessità computazionale. Esempio tipico: quanti sono i sottoinsiemi di {1,...,n}? Una formula brutta è 1+1+1+..., che corrisponde ad enumerarli tutti uno per uno, in tempo esponenziale in n. Una formula bella è 2^n, che si calcola in tempo polinomiale in n.
Ora, il fatto è questo: stabilire se la tua formula è decente o no è un problema aperto. Quindi non so risponderti. :(

P.S. Però è carina, dai! :wink:

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 15 mar 2009, 20:50

Per curiosità aggiungo altri valori trovati a mano:

n = 1 dà 1 modi
n = 2 dà 2 modi
n = 3 dà 4 modi
n = 4 dà 10 modi
n = 5 dà 26 modi
n = 6 dà 80 modi
n = 7 dà 246 modi
n = 8 dà 810 modi
n = 9 dà 2704 modi
n = 10 dà 9252 modi

La somma di piever funziona sempre 8)

UPDATE: Guardate un po' cosa ho trovato sull'OEIS! Sembra che la somma di piever non abbia una formula chiusa...
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 16 mar 2009, 16:48

Tibor Gallai ha scritto:Ora, il fatto è questo: stabilire se la tua formula è decente o no è un problema aperto. Quindi non so risponderti. :(
Ah ok. Ti spiego: mi è capitato di convincermi di aver risolto un problema di combinatoria trovando come risultato una certa sommatoria. Ho scoperto solo in seguito che tale sommatoria valeva $ n! $. Fortunatamente stavolta non ho fatto lo stesso... :D

@ kn: preferisco non sapere in che modo tu abbia risolto il caso n=10 a mano :o
"Sei la Barbara della situazione!" (Tap)

Rispondi