¿Cuántos arreglos de $\{a,2b,3c,4d, 5e\}$ no tienen letras consecutivas idénticas?

Question

¿Cuántos arreglos de $\{a,2b,3c,4d, 5e\}$ no tienen letras consecutivas idénticas?

Me parece muy difícil... ¿Alguien podría tener algunas buenas maneras?

Answer 1

Este es un enfoque alternativo para calcular estos números utilizando un ordenador. El conjunto de todas las palabras que intentamos contar es, por supuesto, finito, ya que se trata de un lenguaje regular. Por suerte, es fácil construir un autómata que lo reconozca, así que podemos mirar la matriz de adyacencia de la máquina y calcular sus potencias. El autómata obvio tiene $(2+n)n!$ vértices, que es bastante grande.

El cálculo real de las potencias de las matrices lleva un tiempo similar a $$\log\binom{n+1}{2}(n+2)^3n!^3$$ si se utiliza la cuadratura repetida.

¿Puede alguien hacerse una idea asintótica del resultado real que estamos calculando para comparar este algoritmo con algo como el de Jiri (que obviamente se basa en un tiempo lineal en el resultado)?

En mathematica, podemos codificar esto con

vertices[n_] := 
 Join[
  {start, bottom},
  Flatten[
   Table[st[a, is], {a, 1, n},  {is, 
     Tuples[Table[Range[0, i], {i, 1, n}]]}
    ], 1]
  ]

rules[n_] := 
 Join[
  Table[{start, i} -> st[i, MapAt[# - 1 &, Range[n], i]], {i, 
    1, n}],
  Table[{bottom, i} -> bottom, {i, 1, n}],
  Flatten[Table[
    {st[a, is], b} -> 
     If[a == b || is[[b]] == 0, 
      bottom, st[b, MapAt[# - 1 &, is, b]]],
    {a, 1, n}, {b, 1, n}, {is, Tuples[Table[Range[0, i], {i, 1, n}]]}
    ], 2]
  ]

toMatrix[rs_, n_, vs_] := 
 SparseArray[
  Flatten@Table[
    With[{src = Position[vs, v][[1, 1]], 
      dest = Position[vs, {v, i} /. rs][[1, 1]]},
     {src, dest} -> If[src === bottom || dest === bottom, 0, 1]
     ], {v, vs}, {i, n}] ,
  {Length[vs], Length[vs]}
  ]

go[n_] := Module[{vs = vertices[n], a, m},
  a = Position[vs, start][[1, 1]];
  Print[n, ": Matrix size : ", Length[vs]];
  m = MatrixPower[
    Transpose@toMatrix[rules[n], n, vs], 
    Binomial[n + 1, 2],
    SparseArray[{a -> 1}, {Length[vs]}]
    ];
  Total[m[[Position[vs, st[_, {0 ..}]][[All, 1]]]]]
  ]

Usando este código, puedo evaluar

go /@ Range[1..5]

para conseguir

1, 1, 10, 1074, 1637124

en 57 segundos.

Answer 2

No tengo ninguna fórmula explícita (esto podría ser difícil), pero he invertido algo de tiempo en un programa de enumeración. Se trata de un bonito ejercicio de backtracking. El corazón del algoritmo es el procedimiento recursivo generate() :

void generate(int* avail, int N, int* a, int pos) {
    // avail[i]: number of available letters i (i = 0, 1, .. N-1)
    // a: generated arrangement a[0], a[1], ... a[n-1] (small n, n = N(N+1)/2)
    // pos: currently generated position in the arrangement a

    int n = N * (N + 1) / 2; // length of the generated sequence
    if (pos >= n) {
        visit(a, n); // one final arrangement, break recursion
        return;
    }
    for (int k = 0; k < N; ++k) {
        if (avail[k] > 0) { // skip if no available letters
            if (pos == 0 || a[pos-1] != k) { // skip equal neighbors
                a[pos] = k; // fill position pos with letter k
                avail[k] -= 1; // consume the letter k
                generate(avail, N, a, pos + 1); // recurse at next position
                avail[k] += 1; // put the used letter back
            }
        }
    }
}

Proporciono un programa general completo en C++, para todos los acuerdos {1*a, 2*b, 3*c, ... N*letter[N]} (bueno, hasta que se produce un desbordamiento - esto podría evitarse portando a Java y utilizando BigInteger).

Number of arrangements: 
1*a : 1
1*a 2*b : 1
1*a 2*b 3*c : 10
1*a 2*b 3*c 4*d : 1074
1*a 2*b 3*c 4*d 5*e : 1637124

Los resultados coinciden con los de OEIS .

Answer 3

Aquí hay una implementación del algoritmo de backtracking en Perl para enriquecer la colección.

#! /usr/bin/perl -w
#

sub generate {
    my ($n, $cur, $lref, $cref) = @\_;

    my $sofar = scalar(@$cur);

    if($sofar == 1/2\*$n\*($n+1)){
        $$cref++;
        return;
    }

    for(my $ltype = 0; $ltype < $n; $ltype++){
        if($lref->\[$ltype\] > 0 &&
           ($sofar == 0 || $cur->\[-1\] != $ltype+1)){
            $lref->\[$ltype\]--;
            push @$cur, $ltype+1;

            generate($n, $cur, $lref, $cref);

            pop @$cur;
            $lref->\[$ltype\]++;
        }
    }
}

MAIN: {
    my $n = shift || 3;

    my @letters = (1..$n);
    my $count;

    generate($n, \[\], \\@letters, \\$count);

    print "$count\\n";
}

Esto da los siguientes tiempos:

$ time ./consec.pl 4
1074

real    0m0.135s
user    0m0.015s
sys     0m0.046s

y

$ time ./consec.pl 5
1637124

real    0m26.317s
user    0m26.052s
sys     0m0.030s

Answer 4

Una posible forma de obtener una fórmula de recursión para dichos números:

Supongamos que tenemos letras $1$ , $2$ , $3$ , $\ldots$ y que la carta $k$ tiene que ser utilizado $j_k$ tiempos. Denote por $A(n,r)$ el conjunto de palabras con el número prescrito de $1$ 's, $2$ 's, $\ldots$ , $n$ y exactamente $r$ espacios incorrectos (es decir, espacios entre letras consecutivas idénticas).

Una palabra $w\in A(r,n)$ tiene $N:=\sum_{k=1}^n j_k$ cartas, de donde $N+1$ espacios donde se pueden escribir nuevas letras, y $r$ de estos espacios son malos.

La siguiente carta $n+1=:a$ tiene que ser utilizado $j_{n+1}=:j$ tiempos. Estos $j$ ocurrencias de $a$ se puede dividir en un número elegido $s$ de "carreras" de $\geq1$ letras consecutivas $a$ en ${j-1\choose s-1}$ formas. Un ejemplo: Si $j=8$ y $s=4$ tal partición $P$ sería $aaa|aa|a|aa$ .

Dada dicha partición podemos decidir escribir $t$ se encuentra con espacios malos y el resto $s-t$ se encuentra con buenos espacios de $w$ . Estos espacios pueden ser seleccionados en un total de $${r\choose t}\cdot{N+1-r \choose s-t}$$ formas. Una vez realizada la selección, la partición real $P$ se escribe "de corrido" en los espacios seleccionados. Ahora tenemos una palabra $w'\in \bigcup_{l\geq0}A(n+1,l)$ .

Para establecer la contabilidad real tenemos que llevar un control del número $l$ de espacios malos. Una partición con $s$ ejecuta crea $j-s$ espacios malos entre las nuevas letras $a$ y por otro lado $t$ de los espacios malos en $w$ desaparecer. Por lo tanto, la palabra $w'$ tiene exactamente $r-t+j-s$ espacios malos, por lo que $w'\in A(n+1,r-t+j-s)$ .

Answer 5

Una aproximación de probabilidad gruesa (podría usarse como límite inferior) : disponemos $N = n (n +1)/2$ bolas, que contienen $1$ bola con la etiqueta ' $1$ ', 2 bolas (idénticas) etiquetadas como ' $2$ ', etc. Sea $E_{k;N}$ sea el caso de que ninguna bola consecutiva etiquetada como ' $k$ ' aparecen. Hagamos una aproximación

$$P(E_{1,N} \wedge E_{2,N} \wedge \cdots E_{n,N}) \approx P(E_{1,N}) P(E_{2,N}) \cdots = \prod_{k=1}^n p_{k;N} = \prod_{k=1}^n \frac{{N-k +1 \choose k }}{{N \choose k}}$$

Para obtener el número de arreglos multiplicamos lo anterior por el número total de arreglos: $\frac{N!}{1! 2! \cdots 5!} $ (número multinomial), y hemos terminado.

Que este procedimiento subestima sistemáticamente la probabilidad puede verse considerando, por ejemplo $P(E_{n} \wedge E_{n-1}) = P(E_{n}) P( E_{n-1} | E_{n} ) \approx P(E_{n}) P( E_{n-1}) $ : está claro que en realidad $P( E_{n-1} | E_{n} ) $ debe ser bastante mayor que $P( E_{n-1})$ .

Algunos valores (los asteriscos marcan los valores aproximados)

4 1074
4 784 *
5 1637124
5 1149984 * 
6 45156692400
6 31054238854 *
7 27230193578558160
7 18475740397262659 *
8 420296434943941609215120 
8 282538479666138391751418 * 1.48
9 190200071567439616748736269178720
9 126998208007147929560523405442263 *
10 2843464512159537301384360263178682136716160
10 1888894892392835311969217872041768221924841 *
11 1562137388408002436396705025296003247844758163480828800
11 1033559722879546585836352002087561697926190676739283028 * 
12 34720858746642455813825034034587385646933035729452542224864163980800
12 22898499225407403297457831507428356090039853373301743612832739138105 * 
13 34083077613811306138835793220030269055400932913570487721385259423732425090293132800
13 22418597515964652640688160805444777997079801940730225617807157721379083786488375692 *