2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If I understand the question well, none of the six persons chosen is isolated? Is that the condition? $\endgroup$ – Gribouillis Aug 16 '17 at 17:48
  • $\begingroup$ Yes, that's right. Sorry I have no good English knowledge. $\endgroup$ – M. Chun Aug 16 '17 at 17:53
  • $\begingroup$ Neither do I :) $\endgroup$ – Gribouillis Aug 16 '17 at 17:56
  • $\begingroup$ Thanks for the edit, M.Chun. $\endgroup$ – Namaste Aug 16 '17 at 17:57
  • 1
    $\begingroup$ 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$. $\endgroup$ – N. F. Taussig Aug 16 '17 at 18:07
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It looks convincing... $\endgroup$ – Gribouillis Aug 16 '17 at 18:56
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gribouillis Aug 16 '17 at 22:00
  • $\begingroup$ 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). $\endgroup$ – N. Shales Aug 16 '17 at 23:12
  • $\begingroup$ See here for a flavour of what is in Hollos' book. $\endgroup$ – N. Shales Aug 16 '17 at 23:16
  • $\begingroup$ Forgot to add the @Gribouillis . $\endgroup$ – N. Shales Aug 16 '17 at 23:59
  • 1
    $\begingroup$ thank you, these references look very good. $\endgroup$ – Gribouillis Aug 17 '17 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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