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.

I'm trying to understand the following solution (based on http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.8324).

Problem: What is the number of ways of selecting $k$ objects from $n$, which are arrayed in a circle and are not consecutive? (A different solution is at Choose K items from N in a circle)

Given Solution: There are $n$ choices for the first object selected. Next, we must select the remaining $\color{green}{k - 1}$ objects. In addition, to prevent consecutiveness, we must select the $\color{brown}{k}$ objects which lie between the $\color{green}{k - 1}$ objects.

Therefore, the number of objects UNaccounted for $:= U = (n - 1) - (\color{green}{k - 1} + \color{brown}{k}) = n - 2k$. We can only place these $U$ objects in between the selected $\color{brown}{k}$ objects, so the number of possible positions for these $U$ objects is $\color{brown}{k}$.

Therefore, the number of ways to select these $U$ positions = $\left( \begin{matrix} { k - 1 + U} \\ {U} \\ \end{matrix} \right)$. (Rest of soln omitted).

I don't understand this last sentence. I understand that we are choosing $U$ objects, but how are we choosing from $(k - 1 + U)$? Where did this number come from?

As a recourse to the general case, I appealed to the simpler case where $n = 8$ and $k = 3$. Then $U$ = 2 and the number of ways to select these $U$ positions = $\left( \begin{matrix} { 4} \\ {2} \\ \end{matrix} \right)$. But I can't see where 4 comes from either (We need to place U1 and U2 so I understand why we're choosing 2.). Here's my picture, where green denotes the $\color{green}k$ selected objects and black denotes the objects unaccounted for:

enter image description here


In response to Prof Scott's post, I thought to add that the bars in the stars-and-bars analogy aren't actually the $\color{brown}{\text{brown separators}}$ drew above. The bars, which I draw in pink below, actually separate the intervals between the $\color{brown}{\text{brown separators}}$. Pictorially: enter image description here

share|improve this question
1  
Look here also: math.stackexchange.com/questions/154763/… –  Byron Schmuland Apr 15 '13 at 17:34
    
@ByronSchmuland: Thank you for the link. However, your solution appears to differ from the given one above? The idea behind your solution appears to be (the number of ways to choose $k$ non-consecutive objects from a line/row of size $n$) $-$ (the number of arrangements where both positions 1 and $n$ are chosen). The above appears to construct the number of ways directly, without recourse to the simpler case involving the line/row? –  LePressentiment Apr 15 '13 at 22:39
add comment

2 Answers 2

up vote 2 down vote accepted

It’s just a stars-and-bars calculation. You have $\color{brown}k$ separators arranged in a circle, so they define $k$ gaps between neighboring separators. You have $U$ objects to place arbitrarily in those $k$ gaps. This can be done in

$$\binom{U+k-1}{k-1}=\binom{U+k-1}U\tag{1}$$

ways. The justification for this result in the linked article is reasonably clear, but I’ll sketch it here. Break the circle at the first separator and stretch it out into a line. Then the $U$ objects and the remaining $k-1$ separators form a string of $U+k-1$ objects, and the distribution of the $U$ objects is determined by their places in that string (or by the places of the $k-1$ separators); $(1)$ gives the number of ways to choose those places.

share|improve this answer
    
Thank you very much for your post, in light of which I added a supplement to my original post. Does my supplement encapsulate what you explain here? Or is it overly complicated, since you didn't mention the intervals between the $\color{brown}{\text{separators}}$? –  LePressentiment Apr 16 '13 at 11:52
add comment

The expression $k+U-1\choose U$ counts the number of multisets of size $U$ drawn from $\{1,2,\dots,k\}$.

When $k=3$ and $U=2$, they are $\{1,1\}$, $\{1,2\}$, $\{1,3\}$, $\{2,2\}$, $\{2,3\}$, and $\{3,3\}$. These correspond to inserting the two unlabelled objects $U$ together with various separators. For example, $\{1,1\}$ corresponds to putting both $U$s with separator 1, while $\{1,2\}$ corresponds to putting one of the $U$s with separator 1 and the other one with separator 2. Each of these six multisets gives a "pattern" of 3 non-consecutive values in a circle of 8 unlabelled objects. Here are the six patterns, where a white dot is either a separator or one of the $U$s:

enter image description here

For each pattern, there are $n$ consistent ways to number the objects: put any value from 1 to $n$ at the top and add one (modulo $n$!) as you go around clockwise. The numbers in positions marked with $k$s (black dots in my picture) gives us a selection of $k$ non-consecutive values from $\{1,2,\dots,n\}$. As you run through all the patterns and all the numberings, each selection appears exactly $k$ times.

Therefore $\#\text{distinct selections}={n\over k}\times\#\text{patterns}.$

share|improve this answer
    
@BryonSchumuland: Thank you very much, Professor. Unfortunately, MSE does not allow me to vote for multiple Answers. i have upvoted though. –  LePressentiment Jul 18 '13 at 13:40
add comment

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.