How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters? 
How many arrangements of $\{a,2b,3c,4d, 5e\}$  have no identical consecutive letters?

I find it very tough... Could anyone have some good ways?
 A: This is an alternative approach to compute this numbers using a computer.
The set of all words we are trying to count is of course finite, to it is a regular language. Luckily, it is easy to construct an automaton which recognizes it, so we can look at the adjacency matrix of the machine and compute its powers. The obvious automaton has $(2+n)n!$ vertices, which is pretty huge.
The actual computation of the matrix powers takes time similar to
$$\log\binom{n+1}{2}(n+2)^3n!^3$$ if one uses repeated squaring. 

Can someone get an asymtotics idea of the actual result we are computing to compare this algorithm with something like Jiri's (which obviously taes time linear in the result) ?

In mathematica, we can code this with 
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]]]]]
  ]

Using this code, I can evaluate
go /@ Range[1..5]

to get 
1, 1, 10, 1074, 1637124

in 57 seconds.
A: I do not have any explicit formula (this could be hard), but invested some time into an enumeration program. This is a nice exercise in backtracking. The heart of the algorithm is the recursive procedure 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
            }
        }
    }
}

I provide a general complete running program in C++, for all arrangements {1*a, 2*b, 3*c, ... N*letter[N]} (well, until overflow occurs - this could be avoided by porting to Java and using 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

The results agree with those on OEIS.
A: A possible way to get a recursion formula for such numbers:
Assume that we have letters $1$, $2$, $3$, $\ldots$ and that the letter $k$ has to be used $j_k$ times. Denote by $A(n,r)$ the set of words  with the prescribed number of $1$'s, $2$'s, $\ldots$, $n$'s and exactly $r$ bad spaces (i.e., spaces between identical consecutive letters).
A word $w\in A(r,n)$ has $N:=\sum_{k=1}^n j_k$ letters, whence $N+1$ spaces where new letters can be written, and $r$ of these spaces are bad. 
The next letter $n+1=:a$ has to be used $j_{n+1}=:j$ times. These $j$ occurrences of $a$ can be partitioned into  a chosen number $s$ of  "runs" of $\geq1$ consecutive letters $a$ in ${j-1\choose s-1}$ ways. An example: If $j=8$ and $s=4$ such a partition $P$ would be $aaa|aa|a|aa$.
Given such a partition we can decide to write $t$ runs into bad spaces and the remaining $s-t$ runs into good spaces of $w$. These spaces can be selected in a total of 
$${r\choose t}\cdot{N+1-r \choose s-t}$$
ways. After the selection has been made the actual partition $P$ is written "runwise"   into the selected spaces. We now have a word $w'\in \bigcup_{l\geq0}A(n+1,l)$.
To set up the actual bookkeeping we have to keep track of the number $l$ of bad spaces. A partition with $s$ runs creates $j-s$ bad spaces between the new letters $a$, and on the other hand $t$ of the bad spaces in $w$ disappear. Therefore the word $w'$ has exactly $r-t+j-s$ bad spaces, so that $w'\in A(n+1,r-t+j-s)$.
A: Here is an implementation of the backtracking algorithm in Perl to enrich the collection.

#! /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";
}

This gives the following timings:

$ time ./consec.pl 4
1074

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

and

$ time ./consec.pl 5
1637124

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

