número de strings, quando cada caractere deve ocorrer mesmo vezes

Estou batendo no meu crânio com esse problema há algum tempo, e está realmente começando a me frustrar. O problema é:

Eu tenho um conjunto de caracteres, A, B, C, e D. Eu tenho que dizer de quantas maneiras uma string pode ser construída a partir desses caracteres, quando o comprimento é ne cada caractere deve ocorrer mesmo vezes.

Por exemplo, a resposta para n = 24 é:

AA
BB
CC
DD

A resposta n = 4é 40. Algumas dessas cadeias válidas são:

AAAA
AABB
CACA
DAAD
BCCB

Estou preso em inventar uma lógica. Eu sinto que poderia haver uma solução de DP para isso. Forçar brutalmente o meu caminho está fora de questão: o número de soluções cresce rapidamente em grandes números.

Eu tentei desenhar todos os tipos de idéias no papel, sem sucesso. Quase todas essas idéias eu tive que descartar, porque sua complexidade era muito grande. A solução deve ser eficiente para n = 10^4.

Uma das minhas idéias era nunca acompanhar as seqüências reais, mas apenas se cada personagem apareceu em momentos pares ou ímpares. Não consegui encontrar uma maneira de aplicar essa lógica.

Alguém pode me ajudar?

Configure f(n,d)como uma função fornecendo o número de permutações de comprimento (par) nusando dcaracteres distintos (por exemplo, d=4no seu caso).

Claramente f(0,d) = 1e f(n,1) = 1como há apenas um arranjo quando você tem apenas um caractere ou zero espaços.

Agora a etapa de indução:

Para criar uma sequência válida usando dcaracteres, pegue uma sequência menor de caracteres pares usando d-1caracteres e complete-a adicionando um múltiplo par desse novo caractere. O número de arranjos é choose(n,n_newdigits)porque você pode escolher n_newdigitlocais fora do comprimento total da string para ter o novo dígito e o restante é preenchido pela string original em ordem.

Para implementar isso usando recursão ingênua em R, eu fiz:

f <- function(n,d)
{
  if(n==0) return(1)
  if(d==1) return(1)
  retval=0
  for (i in seq(from=0, to=n, by=2)) retval=retval+f(n-i,d-1)*choose(n,i)
  return(retval)
}

f(4,4)
# 40    

f(500,4)
# 1.339386e+300 takes about 10 secs

para o tipo de números que você está interessado, eu pensaria que seria mais eficiente armazenar números em uma matriz bidimensional e iterar com o aumento de d, mas isso pode depender da sua escolha de idioma.

A resposta de Miff é definitivamente elegante. Desde que eu terminei o meu de qualquer maneira, eu o forneço. O bom é que eu recebo o mesmo resultado para n = 500 :-)

Seja d o número de caracteres diferentes que são permitidos, d = 4 no seu caso.

Seja n o comprimento da string, em última análise, você verá valores pares de n.

Seja u o número de caracteres não emparelhados em uma string.

Seja N (n, d, u) o número de cadeias de comprimento n, construídas a partir de d caracteres diferentes e com u caracteres não emparelhados. Vamos tentar calcular N.

Existem alguns casos de esquina a serem observados:

u> d ou u> n => N = 0

u <0 => N = 0

n% 2! = u% 2 => N = 0.

Ao passar de n para n + 1, você deve aumentar em 1 ou diminuir em 1, para que tenhamos uma recursão de acordo com

N (n, d, u) = f (N (n-1, d, u-1), N (n-1, d, u + 1))

Quantas maneiras existem para reduzir você em um. Este é fácil, porque temos que emparelhar um dos u caracteres não emparelhados, o que o torna apenas u. Portanto, a segunda parte de f lerá (u + 1) * N (n-1, d, u + 1), com a ressalva, é claro, que devemos observar que N = 0 se u + 1> n-1 ou u +1> d.

Depois de entendermos isso, é fácil ver qual é a primeira parte de f: de quantas maneiras podemos aumentar u quando existem caracteres u-1 não pareados. Bem, temos que escolher um dos caracteres (k- (u-1)) que estão emparelhados.

Portanto, considerando todos os casos de canto, a fórmula recursiva para N é

N (n, d, u) = (d- (u-1)) * N (n-1, d, u-1) + (u + 1) * N (n-1, d, u + 1)

Não vou ler em http://en.wikipedia.org/wiki/Concrete_Mathematics como resolver a recursão.

Em vez disso, escrevi algum código Java. Novamente, um pouco mais desajeitado, assim como o Java, devido à sua verbosidade. Mas eu tinha a motivação de não usar a recursão, já que ela quebra muito cedo, pelo menos em Java, quando a pilha excede em 500 ou 1000 níveis de aninhamento.

O resultado para n = 500, d = 4 e u = 0 é:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

calculado em 0,2 segundos, devido à memorização de resultados intermediários. N (40000,4,0) calcula em menos de 5 segundos. Código também aqui: http://ideone.com/KvB5Jv

import java.math.BigInteger;

public class EvenPairedString2 {
  private final int nChars;  // d above, number of different chars to use
  private int count = 0;
  private Map<Task,BigInteger> memo = new HashMap<>();

  public EvenPairedString2(int nChars) {
    this.nChars = nChars;
  }
  /*+******************************************************************/
  // encodes for a fixed d the task to compute N(strlen,d,unpaired).  
  private static class Task {
    public final int strlen;
    public final int unpaired;

    Task(int strlen, int unpaired) {
      this.strlen = strlen;
      this.unpaired = unpaired;
    }
    @Override
    public int hashCode() {
      return strlen*117 ^ unpaired;
    }
    @Override
    public boolean equals(Object other) {
      if (!(other instanceof Task)) {
        return false;
      }
      Task t2 = (Task)other;
      return strlen==t2.strlen && unpaired==t2.unpaired;
    }
    @Override
    public String toString() {
      return "("+strlen+","+unpaired+")";
    }
  }
  /*+******************************************************************/
  // return corner case or memorized result or null  
  private BigInteger getMemoed(Task t) {
    if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
        || t.strlen%2 != t.unpaired%2) {
      return BigInteger.valueOf(0);
    }

    if (t.strlen==1) {
      return BigInteger.valueOf(nChars);
    }
    return memo.get(t);
  }

  public int getCount() {
    return count;
  }

  public BigInteger computeNDeep(Task t) {
    List<Task> stack = new ArrayList<Task>();
    BigInteger result = null;
    stack.add(t);

    while (stack.size()>0) {
      count += 1;
      t = stack.remove(stack.size()-1);
      result = getMemoed(t);
      if (result!=null) {
        continue;
      }

      Task t1 = new Task(t.strlen-1, t.unpaired+1);
      BigInteger r1 = getMemoed(t1);
      Task t2 = new Task(t.strlen-1, t.unpaired-1);
      BigInteger r2 = getMemoed(t2);
      if (r1==null) {
        stack.add(t);
        stack.add(t1);
        if (r2==null) {
          stack.add(t2);
        }
        continue;
      }
      if (r2==null) {
        stack.add(t);
        stack.add(t2);
        continue;
      }
      result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
      memo.put(t,  result);
    }
    return result;
  }
  private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
    r1 = r1.multiply(BigInteger.valueOf(u1));
    r2 = r2.multiply(BigInteger.valueOf(u2));
    return r1.add(r2);
  }
  public static void main(String[] argv) {
    int strlen = Integer.parseInt(argv[0]);
    int nChars = Integer.parseInt(argv[1]);

    EvenPairedString2 eps = new EvenPairedString2(nChars);

    BigInteger result = eps.computeNDeep(new Task(strlen, 0));
    System.out.printf("%d: N(%d, %d, 0) = %d%n", 
                      eps.getCount(), strlen, nChars, 
                      result); 
  }
}

Tentei encontrar uma solução, mas falhei e fiz a mesma pergunta no Mathematics.StackExchange . Graças a Rus May , aqui está uma solução, no Common Lisp:

(defun solve (n)
  (if (evenp n)
      (/ (+ (expt 4 n) (* 4 (expt 2 n))) 8)
      0))

Isso sempre retorna 0 para valores ímpares de n. Pois n = 500, aqui está a saída com SBCL :

* (time (solve 500))

    Evaluation took:
      0.000 seconds of real time
      0.000000 seconds of total run time (0.000000 user, 0.000000 system)
      100.00% CPU
      51,100 processor cycles
      0 bytes consed

    1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360