Journal of Integer Sequences, Vol. 13 (2010), Article 10.6.8

## Counting Peaks and Valleys in a Partition of a Set

### Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa Israel Mark Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

Abstract:

A partition π of the set [n] = {1,2,...,n} is a collection {B1, B2, ... , Bk} of nonempty disjoint subsets of [n] (called blocks) whose union equals [n]. In this paper, we find an explicit formula for the generating function for the number of partitions of [n] with exactly k blocks according to the number of peaks (valleys) in terms of Chebyshev polynomials of the second kind. Furthermore, we calculate explicit formulas for the total number of peaks and valleys in all the partitions of [n] with exactly k blocks, providing both algebraic and combinatorial proofs.

Full version:  pdf,    dvi,    ps,    latex

(Concerned with sequences A000110 and A008277.)

Received April 19 2010; revised version received June 18 2010. Published in Journal of Integer Sequences, June 22 2010.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8553578,"math_prob":0.6432926,"size":1048,"snap":"2020-45-2020-50","text_gpt3_token_len":283,"char_repetition_ratio":0.08908046,"word_repetition_ratio":0.036144577,"special_character_ratio":0.2519084,"punctuation_ratio":0.14646465,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9571778,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-26T19:42:54Z\",\"WARC-Record-ID\":\"<urn:uuid:fcda34e6-0d9e-4d95-9cf3-a155b006c2c5>\",\"Content-Length\":\"2743\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6c114577-b136-45d6-9866-cfc97cc815ae>\",\"WARC-Concurrent-To\":\"<urn:uuid:db0a80ee-c69c-4a64-a2a0-23ebc14ff00d>\",\"WARC-IP-Address\":\"129.97.167.73\",\"WARC-Target-URI\":\"https://cs.uwaterloo.ca/journals/JIS/VOL13/Shattuck/shattuck3.html\",\"WARC-Payload-Digest\":\"sha1:D563KNEYHWSVUPECBW7OF5DQ4I4FO7RL\",\"WARC-Block-Digest\":\"sha1:N5IA5IGYUPULYDV5QD4AAU3G6Y6WG6Q7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107891624.95_warc_CC-MAIN-20201026175019-20201026205019-00508.warc.gz\"}"}