# Choosing $6$ of $20$ people in a row such that there is at least one other chosen beside any of them

There are $20$ people in a row. What is the number of ways to choose $6$ of them such that there is at least one adjoining person beside every chosen person.

I was trying to count number of ways of its complement. But it gets harder. Actually, I have no idea how to find an approach.

• If I understand the question well, none of the six persons chosen is isolated? Is that the condition? – Gribouillis Aug 16 '17 at 17:48
• Yes, that's right. Sorry I have no good English knowledge. – M. Chun Aug 16 '17 at 17:53
• Neither do I :) – Gribouillis Aug 16 '17 at 17:56
• Thanks for the edit, M.Chun. – Namaste Aug 16 '17 at 17:57
• Notice that the people must be grouped in one of the following ways: a group of $6$, a group of $4$ and a group of $2$, two groups of $3$, or three groups of $2$. – N. F. Taussig Aug 16 '17 at 18:07

Each admissible arrangement can be encoded as a binary word of length $20$ containing exactly $6$ ones. The $14$ not chosen people (zeros) create $15$ slots where groups of chosen people (ones) may be squeezed in. These groups may have sizes $(6)$, $(4,2)$, $(3,3)$, and $(2,2,2)$. It follows that the total number of admissible arrangements is given by $${15\choose 1}+2\cdot{15\choose 2}+{15\choose 2}+{15\choose3}=785\ .$$

• It looks convincing... – Gribouillis Aug 16 '17 at 18:56

Just to provide an alternative approch, we may utilise regular expressions.

This is equivalent to counting binary words of using the alphabet $\{A,B\}$ length $20$ with $6$ $A$s and 14 $B$s such that there are no isolated $A$s.

Consider that the regular expression for binary words with no isolated $A$s must be of the form

$$f=1 +f_A+f_B\tag{1}$$

where $1$ is the empty word, $f_A$ are all such words ending with $A$ and $f_B$ all such words ending with $B$.

It should be clear that words in $f_A$ either consist entirely of $A$s or are $f_B$ with $2,3,4\ldots$ $A$s appended

$$f_A=(A+AA+AAA+\cdots) +f_B(AA+AAA+AAAA+\cdots)$$ $$\implies f_A=(1+f_B)A^2(1-A)^{-1}\tag{2}$$

similarly words in $f_B$ consist entirely of words containing $B$ or are $f_A$ with $1,2,3,\ldots$ $B$s appended

$$f_B=(1+f_A)B(1-B)^{-1}\tag{3}$$

solving $(2)$ and $(3)$ simultaneously gives

$$f_A=\left(\frac{BA^2}{(1-A)(1-B)}+\frac{A^2}{1-A}\right)\left(1-\frac{BA^2}{(1-B)(1-A)}\right)^{-1}\tag{4}$$

$$f_B=\left(\frac{BA^2}{(1-A)(1-B)}+\frac{B}{1-B}\right)\left(1-\frac{BA^2}{(1-B)(1-A)}\right)^{-1}\tag{5}$$

plugging $(4)$ and $(5)$ into $(1)$ yields (after some simplification)

$$f=\frac{A^2-A+1}{1-A-B+AB-A^2B}\tag{6}$$

For this problem we evaluate the coefficient of $A^6B^{14}$ in the expansion of $f$ using sage input

y=var('y')
taylor((x^2-x+1)/(1-x-y+x*y-x^2*y),(x,0),
(y,0),25).coefficient(x^6).coefficient(y^14)


This evaluates to

$$[A^6B^{14}]\frac{A^2-A+1}{1-A-B+AB-A^2B}=785\tag{Answer}$$

• It is very impressive, do you have any references for the use of algebraic fractions in relation to regular expressions? I'd really like to understand this argument completely. – Gribouillis Aug 16 '17 at 22:00
• For me there was no single text although you could check out Flatjolet and Sedgewick which is quite formal. An appealingly simple book is Hollos, can't find a pdf of that. I'd also say that Concrete Mathematics has a great section on this in the guise of coin flipping probability, page 401 (there is a pdf online). – N. Shales Aug 16 '17 at 23:12
• See here for a flavour of what is in Hollos' book. – N. Shales Aug 16 '17 at 23:16
• Forgot to add the @Gribouillis . – N. Shales Aug 16 '17 at 23:59
• thank you, these references look very good. – Gribouillis Aug 17 '17 at 9:16