# combinatorics - partitions of sets

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!

• 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? Feb 11, 2011 at 21:29
• exactly, second exmpale is okay.
– user6163
Feb 11, 2011 at 21:32

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).

$$\sum_{k=0}^{n} \binom{n-k+1}{k} (2S(n-k,2) + 2)$$
• 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. Feb 11, 2011 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/… Feb 11, 2011 at 22:17
• @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? Feb 11, 2011 at 23:21
{"ft_lang_label":"__label__en","ft_lang_prob":0.9306515,"math_prob":0.9996075,"size":1338,"snap":"2022-40-2023-06","text_gpt3_token_len":356,"char_repetition_ratio":0.1011994,"word_repetition_ratio":0.23584905,"special_character_ratio":0.27204782,"punctuation_ratio":0.14335664,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99999,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-02T02:40:45Z\",\"WARC-Record-ID\":\"<urn:uuid:5e06fa65-bd09-4be4-8fe7-8f27c3319b8b>\",\"Content-Length\":\"230465\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:83a7c321-88d1-4c07-aa47-b0e98771ac16>\",\"WARC-Concurrent-To\":\"<urn:uuid:db9ca574-aa90-4ff2-9477-ecf3695b22fa>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/21588/combinatorics-partitions-of-sets\",\"WARC-Payload-Digest\":\"sha1:6EFSAGMBVEPYQ5HUQES3JOTW6PID23GH\",\"WARC-Block-Digest\":\"sha1:DAHVDZEIUKBUHJW25COF6OB3CG5G7EQO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030337244.17_warc_CC-MAIN-20221002021540-20221002051540-00469.warc.gz\"}"}