¿Cuántas formas?

Regreso con el arameo, escribí un problema hace unos días, una parte es:

Tomo un subconjunto del alfabeto y lo ordeno de manera aleatoria. Ahora bien, ¿cuántas cadenas de texto de longitud L puedo crear de tal modo que se usen solo caracteres del subconjunto y en el mismo orden? Se pueden usar las mismas letras solo si son continuas y L puede llegar a ser muy alto.

O de otra forma más ¿arameoso?, dada una sucesión de caracteres $S=\lbrace{X}_{1},X_{2}\dots{X}_{M}\rbrace$ , tienes que buscar el número de cadenas de texto $X_{a_1}X_{a_2}\dots{X}_{a_L}$ en que para cada $i$ y $j$ donde $i<j$ entonces $1\le{a_i}\le{a_j}\le{M}$ .

Por ejemplo, para $S=ABC$ y $N=3$ , entonces las posibilidades son diez: $AAA,AAB,AAC,ABB,ABC,ACC,BBB,BBC,BCC,CCC$ .

Daré la solución en unos días, pero por ahora, ¿alguna idea?

Nota: esto es una prueba para ver el gusto con este tipo de temas.

Posts Relacionados

Solución a ¿Cuántas formas? Primero, no importan que caracteres son, con o da la...
Potencias y series de potencias a un gran entero Como habré hecho notar en la solución para el problema...

7 Comentarios

Kalith dice:
marzo 21, 2010 en 4:25 am

No creo que sea la forma (ni siquiera estoy seguro que tenga sentido) pero para la primera se puede tomar como permutaciones repetidas y calcular algo como:

(X1!*X2!*…*XM!)*L!

la segunda si no se me ocurre nada mas alla de pensar en un aparato algo asi:

(la sumatoria de i = 1 hasta N – 1 de i + 2) + 1

no se llyn iluminanos :D
Usando Firefox 3.6 en Windows Vista

Inicia sesión para responder
- Kalith dice:
  marzo 21, 2010 en 4:36 am
  
  no la segunda no tiene sentido sería algo asi:
  
  dado un S
  
  X1 = 1
  
  Xn = X n – 1 + 2
  Usando Firefox 3.6 en Windows Vista
- Llyn dice:
  marzo 22, 2010 en 7:12 am
  
  Estoy de acuerdo, no tiene sentido, je je. Y ciertamente estás algo lejos.
  
  Ok, dos pistas:
  
  Primero, ¿importan cuales son los caracteres?
  Segundo, si lo vemos en forma de un grafo, ¿como lo puedes representar? ¿quien va a va quien?, por así decirlo.
  Usando Opera 10.50 en Windows Vista
- Kalith dice:
  marzo 22, 2010 en 4:23 pm
  
  jajaja ya entendi con lo que me dijiste ahora cada caracter va a representar el nodo del grafo y las posibles combinaciones seran cada una de las aristas donde el grafo puede conectar.
  
  P.D. Fecro eres gay.
  Usando Firefox 3.6 en Windows Vista
- b@ch0 dice:
  marzo 23, 2010 en 2:41 pm
  
  Se manejan por pistas O.O… mejor dicelo sino no va a poder dormir ajjajaja (enserio) , esperen ya lo resolvio (seguramente despues de no dormir unos 3 dias)
  Usando Firefox 3.6 en Windows 7
- Llyn dice:
  marzo 23, 2010 en 4:21 pm
  
  Los hombres de negro te harán una visita. No tomaran mucho de tu tiempo.
  
  Nota: me falto una posibilidad, ACC, ya lo añadí.
  Usando Opera 10.50 en Windows Vista
FeCr_88 dice:
marzo 22, 2010 en 7:41 am

Y esto uno se lo debe fumar acompañado con que, para entenderlo. Kalith estas seguro que Llyn es humano?.

No sera un ser de otro planeta :s… jajajajajaja Yo ni quiero empezar ;)… esperare la solucion
Usando Firefox 3.6 en Windows 7

Inicia sesión para responder