Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
What would the desired number be numerically? –  fosho Jan 14 '13 at 20:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.