# 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?

-
What does, for instance, 2b mean? That we have something like 2 of the letter b? – mixedmath Oct 26 '11 at 23:23
– Mariano Suárez-Alvarez Oct 27 '11 at 0:10
OEIS has very sparse information on this sequence. If anything general comes out of this question, it should probably be submitted there. – Henning Makholm Oct 27 '11 at 0:30
I'm no expert, but I think these problems are pretty hard. There is a fun article by Blom, Englund, and Sandell called The Mississippi problem (American Statistician, Vol 52 (1998) 49-50) that outlines naive attacks on similar problems. – Byron Schmuland Oct 27 '11 at 0:32
@mixedmath It means 2 b's. – Vladimir Oct 27 '11 at 0:41

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.

-

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.

-
Impressive! (spaces) – Byron Schmuland Oct 28 '11 at 15:20
This is the computation of a row of a power of a very, very sparse $01$-matrix. There are better ways to do that than use mathematica, so maybe this can compute a couple more of the elements. The 2843464512159537301384360263178682136716160 mentioned in the OEIS is out of reach for this method, though! – Mariano Suárez-Alvarez Oct 28 '11 at 15:23
Moreover, the matrix is somewhat structured (it is a Kronecker product and the factors are a "parallelepided" and an extremely symmetric graph) so one shoudl be able, after thinking a bit harder, to exploit that. – Mariano Suárez-Alvarez Oct 28 '11 at 15:25
I want to draw your attention to math.stackexchange.com/questions/129451/… where a new user has a formula that can be used to calculate these numbers in no time. Using Maple I found the answer to the problem with the full alphabet $\{a, 2b, 3c, \dots, 26z\}$ in ten seconds! Please take a look and consider upvoting his answer. – Byron Schmuland Apr 10 '12 at 19:35

A coarse probability approximation (could be used as a lower bound) : we arrange $N = n (n +1)/2$ balls, containing $1$ ball labeled '$1$', 2 (identical) balls labeled '$2$', etc. Let $E_{k;N}$ be the event that no consecutive balls labeled '$k$' appear. Let's approximate

$$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}}$$

To get the number of arrangements we multiply the above by the total number of arrangements: $\frac{N!}{1! 2! \cdots 5!}$ (multinomial number), and we are done.

That this procedure sistematically underestimate the probability can be see by considering for example $P(E_{n} \wedge E_{n-1}) = P(E_{n}) P( E_{n-1} | E_{n} ) \approx P(E_{n}) P( E_{n-1})$ : its clear that actually $P( E_{n-1} | E_{n} )$ must be quite greater than $P( E_{n-1})$.

Some values (the asterisks mark the approximated values)

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 *

-

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  - 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)\$.

-