Pagina 2 di 2
Inviato: 15 mar 2009, 06:43
da Tibor Gallai
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!
Inviato: 15 mar 2009, 20:50
da kn
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
UPDATE: Guardate un po'
cosa ho trovato sull'OEIS! Sembra che la somma di piever non abbia una formula chiusa...
Inviato: 16 mar 2009, 16:48
da piever
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...
@ kn: preferisco non sapere in che modo tu abbia risolto il caso n=10 a mano
