Counting Multiple Cyclic Choices Without Adjacencies

http://dx.doi.org/10.4153/CMB-2005-022-4
Canad. Math. Bull. 48(2005), 244-250

  Published:2005-06-01
 Printed: Jun 2005

We give a particularly elementary solution to the following well-known problem. What is the number of $k$-subsets $X \subseteq I_n=\{1,2,3,\dots,n\}$ satisfying ``no two elements of $X$ are adjacent in the circular display of $I_n$''? Then we investigate a new generalization (multiple cyclic choices without adjacencies) and apply it to enumerating a class of 3-line latin rectangles.