{"id":{"repo_id":"msu","oai_identifier":"oai:d.lib.msu.edu:etd_3816"},"canonical_url":"https://search.ndltd.org/etd/msu/oai:d.lib.msu.edu:etd_3816","repository":{"repo_id":"msu","name":"Michigan State University","base_url":"https://d.lib.msu.edu/oai"},"display":{"title":"Patterns in set partitions and restricted growth functions","abstract":"In this thesis we study two related notions of pattern avoidance.One is in set partitions $\\sigma$ of $[n]=\\{1,2\\dots, n\\}$ which are families of nonempty subsets $B_1,\\dots,B_k$ whose disjoint union is $[n]$, written $\\sigma=B_1/\\dots/B_k\\vdash S$. The other is in restricted growth functions (RGFs) which are words $w=a_1a_2\\dots a_n$ of positive integers such that $a_1=1$ and $a_i\\leq 1+\\max\\{a_1,\\dots,a_{i-1}\\}$ for $i>1$. The concept of pattern avoidance is built on a standardization map $\\text{st}$ on an object $O$, be it a set partition or RGF, where $\\text{st}(O)$ is obtained by replacing the $i$th smallest integer with $i$. A set partition $\\sigma$ will contain a pattern $\\pi$ if $\\sigma$ has a subpartition which standardizes to $\\pi$, and when $\\sigma$ does not contain $\\pi$ we say $\\sigma$ avoids $\\pi$. Pattern avoidance in RGFs is defined similarly. This work is the study of the generating functions for Wachs and White's statistics on RGFs over the avoidance classes of set partitions and RGFs. The first half of the thesis concentrates on set partitions. We characterize most of these generating functions for avoiding single and multiple set partitions of length three, and we highlight the longer pattern $14/2/3$, a partition of $[4]$, as its avoidance class has a particularly nice characterization. The second half of this thesis will present our results about the generating functions for RGF patterns, starting with those of length three. We find many equidistribution properties which we prove using integer partitions and the hook decomposition of Young diagrams. For certain patterns of any length we provide a recursive formula for their generating functions including the pattern $12\\dots k$. We finish this presentation by discussing the patterns $1212$ and $1221$ which have connections to noncrossing and nonnesting partitions, respectfully. We find connections to two-colored Motzkin paths and define explicit bijections between these combinatorial objects.","abstract_html":"In this thesis we study two related notions of pattern avoidance.One is in set partitions <span class=\"etd-inline-math\">&sigma;</span> of $[n]=\\{1,2\\dots, n\\}$ which are families of nonempty subsets <span class=\"etd-inline-math\">B<sub>1</sub>,\\dots,B<sub>k</sub></span> whose disjoint union is $[n]$, written <span class=\"etd-inline-math\">&sigma;=B<sub>1</sub>/\\dots/B<sub>k</sub>\\vdash S</span>. The other is in restricted growth functions (RGFs) which are words <span class=\"etd-inline-math\">w=a<sub>1</sub>a<sub>2</sub>\\dots a<sub>n</sub></span> of positive integers such that <span class=\"etd-inline-math\">a<sub>1</sub>=1</span> and <span class=\"etd-inline-math\">a<sub>i</sub>\\leq 1+\\max\\{a<sub>1</sub>,\\dots,a<sub>i-1</sub>\\}</span> for $i&gt;1$. The concept of pattern avoidance is built on a standardization map $\\text{st}$ on an object $O$, be it a set partition or RGF, where $\\text{st}(O)$ is obtained by replacing the $i$th smallest integer with $i$. A set partition <span class=\"etd-inline-math\">&sigma;</span> will contain a pattern <span class=\"etd-inline-math\">&pi;</span> if <span class=\"etd-inline-math\">&sigma;</span> has a subpartition which standardizes to <span class=\"etd-inline-math\">&pi;</span>, and when <span class=\"etd-inline-math\">&sigma;</span> does not contain <span class=\"etd-inline-math\">&pi;</span> we say <span class=\"etd-inline-math\">&sigma;</span> avoids <span class=\"etd-inline-math\">&pi;</span>. Pattern avoidance in RGFs is defined similarly. This work is the study of the generating functions for Wachs and White&#x27;s statistics on RGFs over the avoidance classes of set partitions and RGFs. The first half of the thesis concentrates on set partitions. We characterize most of these generating functions for avoiding single and multiple set partitions of length three, and we highlight the longer pattern $14/2/3$, a partition of $[4]$, as its avoidance class has a particularly nice characterization. The second half of this thesis will present our results about the generating functions for RGF patterns, starting with those of length three. We find many equidistribution properties which we prove using integer partitions and the hook decomposition of Young diagrams. For certain patterns of any length we provide a recursive formula for their generating functions including the pattern $12\\dots k$. We finish this presentation by discussing the patterns $1212$ and $1221$ which have connections to noncrossing and nonnesting partitions, respectfully. We find connections to two-colored Motzkin paths and define explicit bijections between these combinatorial objects.","abstract_has_math":true,"creators":["Dahlberg, Samantha"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Sagan, Bruce","Bell, Robert","Hall, Jonathan","Magyar, Peter","Shapiro, Michael"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-11-18T18:41:16Z","subjects":["Combinatorial analysis","Generating functions","Partitions (Mathematics)"],"languages":["English"],"rights":["In Copyright"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:3816","isbn:9781339680026","isbn:1339680025","oclc:961269312","umi:10104468","local:Dahlberg_grad.msu_0128D_14371"],"render_values":[{"text":"etd:3816","href":null,"code":true},{"text":"isbn:9781339680026","href":null,"code":true},{"text":"isbn:1339680025","href":null,"code":true},{"text":"oclc:961269312","href":null,"code":true},{"text":"umi:10104468","href":null,"code":true},{"text":"local:Dahlberg_grad.msu_0128D_14371","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/doi:10.25335/zqsb-9611","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/doi:10.25335/zqsb-9611","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_3816","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Sagan, Bruce","Bell, Robert","Hall, Jonathan","Magyar, Peter","Shapiro, Michael"]},{"key":"dc:creator","label":"Author","values":["Dahlberg, Samantha"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016"]},{"key":"dc:relation","label":"Dc Relation","values":["Electronic Theses & Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["Text","Theses"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial analysis","Generating functions","Partitions (Mathematics)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:3816","isbn:9781339680026","isbn:1339680025","oclc:961269312","umi:10104468","local:Dahlberg_grad.msu_0128D_14371","https://doi.org/doi:10.25335/zqsb-9611"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis we study two related notions of pattern avoidance.One is in set partitions $\\sigma$ of $[n]=\\{1,2\\dots, n\\}$ which are families of nonempty subsets $B_1,\\dots,B_k$ whose disjoint union is $[n]$, written $\\sigma=B_1/\\dots/B_k\\vdash S$. The other is in restricted growth functions (RGFs) which are words $w=a_1a_2\\dots a_n$ of positive integers such that $a_1=1$ and $a_i\\leq 1+\\max\\{a_1,\\dots,a_{i-1}\\}$ for $i>1$. The concept of pattern avoidance is built on a standardization map $\\text{st}$ on an object $O$, be it a set partition or RGF, where $\\text{st}(O)$ is obtained by replacing the $i$th smallest integer with $i$. A set partition $\\sigma$ will contain a pattern $\\pi$ if $\\sigma$ has a subpartition which standardizes to $\\pi$, and when $\\sigma$ does not contain $\\pi$ we say $\\sigma$ avoids $\\pi$. Pattern avoidance in RGFs is defined similarly. This work is the study of the generating functions for Wachs and White's statistics on RGFs over the avoidance classes of set partitions and RGFs. The first half of the thesis concentrates on set partitions. We characterize most of these generating functions for avoiding single and multiple set partitions of length three, and we highlight the longer pattern $14/2/3$, a partition of $[4]$, as its avoidance class has a particularly nice characterization. The second half of this thesis will present our results about the generating functions for RGF patterns, starting with those of length three. We find many equidistribution properties which we prove using integer partitions and the hook decomposition of Young diagrams. For certain patterns of any length we provide a recursive formula for their generating functions including the pattern $12\\dots k$. We finish this presentation by discussing the patterns $1212$ and $1221$ which have connections to noncrossing and nonnesting partitions, respectfully. We find connections to two-colored Motzkin paths and define explicit bijections between these combinatorial objects.","Thesis (Ph. D.)--Michigan State University. Mathematics, 2016","Includes bibliographical references (pages 86-88)"]},{"key":"dc:format","label":"Dc Format","values":["vi, 88 pages","application/pdf"]},{"key":"dc:title","label":"Title","values":["Patterns in set partitions and restricted growth functions"]}]}],"canonical_facts":{"dc:contributor":["Sagan, Bruce","Bell, Robert","Hall, Jonathan","Magyar, Peter","Shapiro, Michael"],"dc:creator":["Dahlberg, Samantha"],"dc:date":["2016"],"dc:description":["In this thesis we study two related notions of pattern avoidance.One is in set partitions $\\sigma$ of $[n]=\\{1,2\\dots, n\\}$ which are families of nonempty subsets $B_1,\\dots,B_k$ whose disjoint union is $[n]$, written $\\sigma=B_1/\\dots/B_k\\vdash S$. The other is in restricted growth functions (RGFs) which are words $w=a_1a_2\\dots a_n$ of positive integers such that $a_1=1$ and $a_i\\leq 1+\\max\\{a_1,\\dots,a_{i-1}\\}$ for $i>1$. The concept of pattern avoidance is built on a standardization map $\\text{st}$ on an object $O$, be it a set partition or RGF, where $\\text{st}(O)$ is obtained by replacing the $i$th smallest integer with $i$. A set partition $\\sigma$ will contain a pattern $\\pi$ if $\\sigma$ has a subpartition which standardizes to $\\pi$, and when $\\sigma$ does not contain $\\pi$ we say $\\sigma$ avoids $\\pi$. Pattern avoidance in RGFs is defined similarly. This work is the study of the generating functions for Wachs and White's statistics on RGFs over the avoidance classes of set partitions and RGFs. The first half of the thesis concentrates on set partitions. We characterize most of these generating functions for avoiding single and multiple set partitions of length three, and we highlight the longer pattern $14/2/3$, a partition of $[4]$, as its avoidance class has a particularly nice characterization. The second half of this thesis will present our results about the generating functions for RGF patterns, starting with those of length three. We find many equidistribution properties which we prove using integer partitions and the hook decomposition of Young diagrams. For certain patterns of any length we provide a recursive formula for their generating functions including the pattern $12\\dots k$. We finish this presentation by discussing the patterns $1212$ and $1221$ which have connections to noncrossing and nonnesting partitions, respectfully. We find connections to two-colored Motzkin paths and define explicit bijections between these combinatorial objects.","Thesis (Ph. D.)--Michigan State University. Mathematics, 2016","Includes bibliographical references (pages 86-88)"],"dc:format":["vi, 88 pages","application/pdf"],"dc:identifier":["etd:3816","isbn:9781339680026","isbn:1339680025","oclc:961269312","umi:10104468","local:Dahlberg_grad.msu_0128D_14371","https://doi.org/doi:10.25335/zqsb-9611"],"dc:language":["English"],"dc:relation":["Electronic Theses & Dissertations"],"dc:rights":["In Copyright"],"dc:subject":["Combinatorial analysis","Generating functions","Partitions (Mathematics)"],"dc:title":["Patterns in set partitions and restricted growth functions"],"dc:type":["Text","Theses"]},"updated_at":"2026-11-18T18:41:16Z"}