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.

The question is this:

In how many partitions of $\{1,2,\ldots,n\}$ into three disjoint sets, $A$, $B$, and $C$, are there no two consecutive numbers in the set $A$?

thanks!

share|improve this question
    
Do you consider these ordered partitions, so that, for instance, $A=\{1,2\}$, $B=\{3\}$, $C=\{4\}$ does not qualify, but $A=\{3\}$, $B=\{1,2\}$, $C=\{4\}$ is okay? –  Arturo Magidin Feb 11 '11 at 21:29
    
exactly, second exmpale is okay. –  user6163 Feb 11 '11 at 21:32
add comment

1 Answer

up vote 1 down vote accepted

Number of ways of selecting $k$ numbers from $1,2,\dots,n$ such that no two are consecutive is

$\displaystyle \binom{n-k+1}{k}$, for instance see my answer here: Consecutive birthdays probability

Once you do that, count the number of partitions of the remaining into $B$ and $C$.

Which is given by $2S(n-k,2) + 2$ where $S(a,b)$ are the Stirling numbers of the second kind (for and explanation see the answer linked above).

Now I guess your answer is

$$\sum_{k=0}^{n} \binom{n-k+1}{k} (2S(n-k,2) + 2)$$

(Note: I haven't tried to confirm it, I leave that to you)

Hope that helps.

share|improve this answer
    
Having pulled out $k$ items for $A$, aren't there $2^{(n-k)}$ subsets that you could choose for $B$ so you would have $$\sum_{k=0}^{n} \binom{n-k+1}{k}2^{(n-k)}$$? It looks like your answer doesn't allow $B$ or $C$ to be empty and considers swapping $B$ and $C$ to be the same configuration. –  Ross Millikan Feb 11 '11 at 22:08
    
@Ross: $S(n,2) = 2^{n-1} -1$. I mentioned Strirling numbers because it generalizes to more sets :-) See here: en.wikipedia.org/wiki/… –  Aryabhata Feb 11 '11 at 22:17
    
@Moron: yes, I had seen that, which is how I figured out the differences between the approaches. It depends what you want to count. –  Ross Millikan Feb 11 '11 at 23:18
    
@Ross: Multiplying by 2 and adding 2 is supposed to take care of swapping B and C, and empty sets. The formula($2^{n-1}-1$) then gives what you wrote in your comment, so it does seem to match... Am I missing something, or do we agree now? –  Aryabhata Feb 11 '11 at 23:21
    
@Moron: we agreed all the time. And still do –  Ross Millikan Feb 11 '11 at 23:27
show 2 more comments

Your Answer

 
discard

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