Coelestis - Il Forum Italiano di Astronomia

Coelestis - Il Forum Italiano di Astronomia (http://www.trekportal.it/coelestis/index.php)
-   Rudi Mathematici (http://www.trekportal.it/coelestis/forumdisplay.php?f=11)
-   -   Estrazioni casuali (http://www.trekportal.it/coelestis/showthread.php?t=42400)

astromauh 30-10-13 01:45

Re: Estrazioni casuali
 
I conti tornano! :ok:

Sono andato a contare partendo da una prima cinquina fissa 1,2,3,4,5 quanti quadrati è possibile costruire e ho trovato che sono 1344.

1344 * 120 = 161.280

Se proprio interessa, penso che potrei tabulare questi 1344 quadrati che permutati comprendono tutte le combinazioni valide.

:hello:

Erasmus 30-10-13 02:59

Re: Estrazioni casuali
 
@aspesi.
a) Non sono pessimista! :)

b) Questo quiz è interessante.
Lasciamo perdere la probabilità.
A rovescio, una simulazione serve per trovare empiricamente quante sono quelle maledette combinazioni.
E' facilissimo codifcare le permutazioni di un insieme non troppo numeroso con un intero (per esempio generandole tutte ed assegnando loro il numero d'ordine man mano che vengono generate).
Il vantaggio, dal punto di vista pratico, non è poco!
Già in questo esempio di soli 5 elementi, (in cui le permutazioni sono appena 120) le disposizioni con possibile ripetizione sono ... tante quanti i numeri di 5 cifre in base 120, cioè:
120^5 = 2,48832·10^10
mentre il numero di combinazioni distinte è soltanto
C(120,5) = 119·118·117·116 = 1,90578024·10^8
ossia oltre 130 volte di meno.
Se facessimo analogamente per settuple invece che per cinquine avremmo:
7! = 5040
5040^7 ≈ 8,2606·10^25
C(5040, 7)≈ 5036,5^6 ≈ 1.6328·10^22
con un rapporto circa 5060.
[In generale, (n!)^n è un po' maggiore di n! volte C(n!, n)].


Mi interessa sapere se esiste una formula per calcolare di colpo il numero di combinazioni di n permutazioni di un insieme di n oggetti con quella proprietà (due qualsiasi di queste permutazioni [che sono elementi] della stessa combinazione hanno oggetti diversi in posti uguali). Se la sai, diccela!

c) A proposito di formule, il quiz che avevi messo sul prodotto delle distanze di un vertice di un poligono regolare da ciascun altro vertice meriterebbe un'analisi più approfondita fino a trovare la dimostrazione in generale.
La formula da dimostrare in generale ... è facile da scrivere!
Sia n un intero ≥ 2 e si ponga phi = π/n (radianti, un "ennesimo" di angolo piatto)).
Dimostrare che
P(n) = <Prodotto, per k da 1 a n–1 compresi, di 2·sin(kπ/n)> = n
Basta dimostrare questa uguaglianza per n dispari perché, se n è pari – diciamo n=2m – si trova facilmente che il primo membro vale il doppio di quel che varrebbe per n = m.
Aspesi: la persona giusta per questa dimostrazione sei tu! :D
Guarda che, anche se ho messo quell'emoticon della faccina che sganascia, sto parlando sul serio.
Il problema, infatti, si riconduce ad un problema "combinatorio".
Non posso qui dirti come funziona 'sta faccenda per ovvi motivi (se non per altro per motivi grafici!|). Ma in un prossimo futuro metterò un paper che spiega questa affermazione.

-----------------------
:hello:

aspesi 30-10-13 09:57

Re: Estrazioni casuali
 
Quote:

astromauh (Scrivi 698836)
I conti tornano! :ok:

Sono andato a contare partendo da una prima cinquina fissa 1,2,3,4,5 quanti quadrati è possibile costruire e ho trovato che sono 1344.

1344 * 120 = 161.280
:hello:

Perfetto! :ok:

Quello che hai trovato è il numero di quadrati latini di questa sequenza:
http://oeis.org/A000479

n. cifre ... n. quadrati
-------- ... ------------
... 1 ............ 1
... 2 ............ 1
... 3 ............ 2
... 4 ............ 24
... 5 ............ 1344
... 6 ............ 1128960
..........

(Non penso sia il caso di tabulare tutti questi quadrati, eventualmente estrai solo i 56 che oltre alla prima riga hanno anche la prima colonna composta da 12345)

:hello:

aspesi 30-10-13 10:28

Re: Estrazioni casuali
 
Quote:

Erasmus (Scrivi 698838)
b) Questo quiz è interessante.
Mi interessa sapere se esiste una formula per calcolare di colpo il numero di combinazioni d n permutazioni di un insieme di n oggetti con quella proprietà (due permutazioni qualisasi della stessa combinazione in ogni hanno oggetti diversi in posti uguali). Se la sai, diccela!

Non ho capito, forse se fai un esempio pratico... :o

Quote:

Erasmus (Scrivi 698838)
Il problema, infatti, si riconduce ad un problema "combinatorio".
Non posso qui dirti come funziona 'sta faccenda per ovvi motivi (se non per altro per motivi grafici!|). Ma in un prossimo futuro metterò un paper che spiega questa affermazione.

-----------------------
:hello:

Con semplicità, cerca di essere il più facile possibile :)

:hello:

nino280 30-10-13 11:40

Re: Estrazioni casuali
 
Dal MGM:
275.305.224 è il numero dei quadrati magici di ordine 5 calcolato con l'uso dell'elaboratore elettronico da Richard Schroeppel nel 1973.
Questo numero esclude rotazioni e riflessioni.
Ciao

aspesi 30-10-13 12:09

Re: Estrazioni casuali
 
Quote:

nino280 (Scrivi 698880)
Dal MGM:
275.305.224 è il numero dei quadrati magici di ordine 5 calcolato con l'uso dell'elaboratore elettronico da Richard Schroeppel nel 1973.
Questo numero esclude rotazioni e riflessioni.
Ciao

??????????
Questo numero o si riferisce a qualcosa di diverso dai quadrati latini o è sbagliato.
http://www.mi.imati.cnr.it/~alberto/mnD63qLAT.pdf
"Al crescere dell'ordine n la generazione di tutti i quadrati latini si fa subito estremamente onerosa: si
trova in particolare che i numeri dei quadrati latini degli ordini 4, 5, 6 e 7 sono, rispettivamente, 576,
161 280, 812 851 200 e 61 479 419 904 000."


:hello:

Infatti, ricordando il significato di quadrato magico:
Un quadrato magico è uno schieramento di numeri interi distinti in una tabella quadrata tale che la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali dia sempre lo stesso numero
questo è tutto un'altra cosa rispetto ai quadrati latini.

astromauh 30-10-13 13:11

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 698868)
(Non penso sia il caso di tabulare tutti questi quadrati, eventualmente estrai solo i 56 che oltre alla prima riga hanno anche la prima colonna composta da 12345)

Cosa hanno di speciale questi 56 quadrati?

(OK, mi vado a rileggere i post precedenti)

Ma non so se mi va di fare nemmeno questo.

Volevo invece spiegare una cosa interessante che è emersa dal mio conteggio.

Partendo dalla prima cinquina 1,2,3,4,5 le seconde cinquine che soddisfano la condizione data sono 44, e le cinquine valide per la terza riga sono 13.

Mentre per quello che riguarda la quarta riga, la maggior parte delle soluzioni prevede 2 cinquine, ma ce ne sono alcune che ne prevedono 4.

Se tutte le cinquine del 4 rigo prevedessero 2 soluzioni, il numero totale dei quadrati possibili sarebbe 2 * 13 * 44 = 1144, ma a causa della presenza di queste combinazioni che prevedono 4 soluzioni invece di 2, il numero totale dei quadrati è 1344.


Quote:

aspesi (Scrivi 698884)
Infatti, ricordando il significato di quadrato magico:
Un quadrato magico è uno schieramento di numeri interi distinti in una tabella quadrata tale che la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali dia sempre lo stesso numero
questo è tutto un'altra cosa rispetto ai quadrati latini.

Forse è un po' colpa mia, perché negli ultimi post parlavo di quadrati magici mentre in realtà si tratta di quadrati latini.

:hello:

Erasmus 30-10-13 14:04

Re: Estrazioni casuali
 
Quote:

aspesi (Scrivi 698870)
Quote:

Erasmus
Mi interessa sapere se esiste una formula per calcolare di colpo il numero di combinazioni d n permutazioni di un insieme di n oggetti con quella proprietà (due permutazioni qualisasi della stessa combinazione in ogni hanno oggetti diversi in posti uguali). Se la sai, diccela!

Non ho capito, forse se fai un esempio pratico... :o

Ma che esempio d'Egitto! Sto parlando della formula generale (per n intero qualsiasi invece che per n = 5) che risolve questo quiz.
Vabbeh... avevo scritto con qualche parola in più o sbagliata.. Adesso ho corretto; e la frase che non hai capito voleva essere questa:
Quote:

Erasmus
Mi interessa sapere se esiste una formula per calcolare di colpo il numero di combinazioni di n permutazioni di un insieme di n oggetti con quella proprietà (due qualsiasi di queste permutazioni [che sono elementi] della stessa combinazione hanno oggetti diversi in posti uguali). Se la sai, diccela!

Vedo adesso che hai già risposto alla mia domanda. Vediamo se ho capito la risposta:
R. «La formula generale non c'è. La funzione F(n) che dovrebbe dare 'sta formula (che però ancora non c'è e chissà se ci sarà mai) cresce sbalorditivamente al crescere di n e fino ad ora è nota per n tra 1 e 11 compresi».
[Ed F(11) è un numero di ordine di grandezza 10^35 – mi par di aver capito dal tuo 'post' # 985].
-----------
:hello:

aspesi 30-10-13 15:29

Re: Estrazioni casuali
 
Quote:

astromauh (Scrivi 698889)
Cosa hanno di speciale questi 56 quadrati?

Sono un insieme più piccolo (quindi maneggevole, almeno fino a n=5), mediante il quale si possono elaborare tutti gli altri quadrati latini (che per n=5 sono ben 161.280)

Ad es. per n=3
123
231 ----> permette con opportune inversioni sulle righe e sulle colonne
312 ....... di ottenere tutti gli altri 11 quadrati latini

Quote:

astromauh (Scrivi 698889)
Volevo invece spiegare una cosa interessante che è emersa dal mio conteggio.

Partendo dalla prima cinquina 1,2,3,4,5 le seconde cinquine che soddisfano la condizione data sono 44, e le cinquine valide per la terza riga sono 13.

Oltre al quadrato finale, si possono esaminare anche i rettangoli intermedi.
Infatti, se si toglie l'ultima riga dei quadrati ridotti, si hanno le quartine di cinquine (anch'esse sono 56, con una probabilità pari a 4*3*2*56/120^3)

Invece, le coppie di cinquine, abbiamo visto all'inizio che per ogni cinquina della prima riga sono 44 e la probabilità è: 4*11/120

Rimangono solo le triplette di cinquine, la cui probabilità è 4*3*2*46/120^2

Quote:

astromauh (Scrivi 698889)
Forse è un po' colpa mia, perché negli ultimi post parlavo di quadrati magici mentre in realtà si tratta di quadrati latini.

:hello:

Un po' è anche mia disattenzione, Nino aveva specificato quadrati magici, non latini.

:hello:

aspesi 30-10-13 15:54

Re: Estrazioni casuali
 
Quote:

Erasmus (Scrivi 698899)
Questa: Vedo adesso che hai già risposto alla mia domanda. Vediamo se ho capito la risposta:
R. «La formula generale non c'è. La funzione F(n) che dovrebbe dare 'sta formula (che però ancora non c'è e chissà se ci sarà mai) cresce sbalorditivamente al crescere di n e fino ad ora è nota per n tra 1 e 11 compresi».
[Ed F(11) è un numero di ordine di grandezza 10^35 – mi par di aver capito dal tuo 'post' # 985].
-----------
:hello:

Sì.
In effetti c'è questo documento (per me complicatissimo)
http://www.combinatorics.org/Volume_17/PDF/v17i1a1.pdf

che mi pare dica che fino a certi valori di n ci sono formule chiuse disponibili, una di un certo Doyle.
Con certi algoritmi è stato anche stimato con un certo errore ed un determinato livello di confidenza, il numero dei quadrati latini fino a n=100 (sarebbero un numero dell'ordine do 10^11396 :eek:

Dovrebbe esistere anche un cubo latino...

:hello:


Tutti gli orari sono GMT. Attualmente sono le 12:30.

Powered by vBulletin versione 3.6.7
Copyright ©: 2000 - 2021, Jelsoft Enterprises Ltd.
Traduzione italiana a cura di: vBulletinItalia.it