Problema di stringhe

[Lama3]

Ultimamente stavo riflettendo su un problema che mi è stato proposto di cui vorrei discutere in modo da arrivare ad una soluzione.. Se qualcuno vuole apere gli steps intermedi ai quali sono giunto, io sono qui a disposizione e pronto al dibattito, nel frattempo propongo il problema:

Supponiamo di prendere i 90 numeri del lotto e scriverli a casaccio di seguito fino a formare un stringa di 90 numeri. Quante sono le stringe che contengono ALMENO una cinquina di numeri (che nella stringa da 90 siano consecutivi) disposti in ordine crescente?

ad es. ...1 6 4 5 17 19 31 27 34 57 90 88..


spero di essere riuscito a spiegarmi...

[Andrea2976]

Il problema che proponi non è di agevole soluzione, in generale.

Se sei interessato a tale tematica ti consiglio di cercare su google: "longest increasing subsequences".

[Umby2]

Non penso sia particolarmente difficile, che tipo di difficoltà hai avuto ?

[Andrea2976]

Umby devo dire che non mi sono cimentato nel risolverlo per ora;
la mia indicazione voleva essere di tipo più generale in quanto l'interesse non risiede molto nell'enumerazione di sequenze possibili o nel calcolo di una probabilità specifica, piuttosto è interessante avere informazioni sulla distribuzione delle sequenze crescenti.

[Lama3]

Vi espongo il mio ragionamento, così capite l'intoppo.

considero tutte le cinquine [tex]\binom{90}{5}[/tex]; ognuna di queste poi la posso risistemare mettendo gli elementi in ordine crescente.
chiamo una delle cinquine A.
rimangono 85 elementi da sistemare; li posso sistemare in 85! modi. all'interno di ogni stringa di 85 elementi, A la posso sistemare in 86 posizioni, quindi le stringhe vengono A x 86!
il problema è che, consideriamo la cinquina A, disponendo gli altri 85 numeri, potrebbe essere che io vada a formare un'altra (una o più) cinquina B, andando così a contarla due volte, perche in [tex]\binom{90}{5}[/tex] io le conto già entrambe.... secondo il mio ragionamento, dunque, conto dei casi più volte, cosa che non va bene...