# Alphabet subset

Consider the following sequence of letters: a,b,c,d,e,f,g,h,i,j,k,l,m,n. How many ways are there to arrange the letters into sets of any length (empty set included) such that no sequence contains consecutive letters.

-

I’ll replace the set $\{a,b,\dots,n\}$ by the set $[14]=\{1,2,\dots,14\}$. First I’ll count the $k$-element subsets of $[14]$ that do not contain two consecutive integers, where $0\le k\le 14$. Imagine that I’ve chosen such a subset; call it $K$. I write down the sequence $1,2,\dots,14$, and then I replace each member of $K$ with a bar and each member of $[14]\setminus K$ with a star. Let $x_0$ be the number of stars before the first bar; for $i=1,\dots,k-1$ let $x_i$ be the number of stars between the $i$-th and $(i+1)$-st bars; and let $x_k$ be the number of stars after the $k$-th bar. Bars may not occupy consecutive positives, so $x_i\ge 1$ for $i=1,\dots,k-1$, and of course $\sum_{i=0}^kx_i=14-k$. By the usual stars-and-bars calculation there are $$\binom{\big((14-k)-(k-1)\big)+(k+1)-1}{(k+1)-1}=\binom{15-k}k$$ such sequences of stars and bars and hence $\binom{15-k}k$ $k$-element subsets of $[14]$ without consecutive members. Each of those can of course be permuted in $k!$ ways, so the desired number is

\begin{align*} \sum_{k=0}^{14}k!\binom{15-k}k&=\sum_{k=0}^7k!\binom{15-k}k\\ &=\sum_{k=0}^7\frac{(15-k)!}{(15-2k)!}\\ &=\frac{15!}{15!}+\frac{14!}{13!}+\frac{13!}{11!}+\frac{12!}{9!}+\frac{11!}{7!}+\frac{10!}{5!}+\frac{9!}{3!}+\frac{8!}{1!}\\\\ &=140,451\;. \end{align*}

-

You can count those using the inclusion–exclusion principle:
(For convinince I'll use numbers $1,...,14$ instead of letters) Let $X$ be the set of all sequences of letters of any length, with no restrictions. Then $$|X|=\sum_{k=0}^{14}k!\binom{14}{k}$$ Now denote $A_i$, $i=1,...,13$ be the set of all such sequences that include both $i$ and $i+1$. Then $$|A_i|=\sum_{k=2}^{14}k!\binom{12}{k-2}$$ Since any such sequence is of length at least 2, choose the remaining elements and arrange them.
Now find $|A_i\cap A_j|$ for $i<j$: there are two options: if $j=i+1$ then $|A_i\cap A_{i+1}|=\sum_{k=3}^{14}k!\binom{11}{k-3}$ and if $j\neq i+1$ then $|A_i\cap A_j|=\sum_{k=4}^{14}k!\binom{10}{k-3}$.
Continue in the manner (it is quite tedious, but it works).
In the end, the disered number will be $$|X|-\sum_{k=1}^{13}(-1)^{k+1}\left(\sum_{1\leq i_1<...<i_k\leq 13}|A_{i_1}\cap...\cap A_{i_k}|\right)$$

-
What would the desired number be numerically? – fosho Jan 14 '13 at 20:00