Namespaces
Variants
Actions

Difference between revisions of "Composition (combinatorics)"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Composition (combinatorics))
 
m (→‎References: isbn link)
 
Line 6: Line 6:
  
 
====References====
 
====References====
* Luoto, Kurt; Mykytiuk, Stefan; van Willigenburg, Stephanie, "An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux", Springer  (2013) ISBN 978-1-4614-7299-5  {{ZBL|1277.16027}}
+
* Luoto, Kurt; Mykytiuk, Stefan; van Willigenburg, Stephanie, "An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux", Springer  (2013) {{ISBN|978-1-4614-7299-5}} {{ZBL|1277.16027}}
* Riordan, John "Introduction to Combinatorial Analysis", Wiley [1958] Dover (2002) ISBN 0-486-42536-3 {{ZBL|0078.00805}}
+
* Riordan, John "Introduction to Combinatorial Analysis", Wiley [1958] Dover (2002) {{ISBN|0-486-42536-3}} {{ZBL|0078.00805}}

Latest revision as of 14:20, 12 November 2023

2020 Mathematics Subject Classification: Primary: 05A17 Secondary: 11P81 [MSN][ZBL]

A composition of a natural number $n$ is an expression of $n$ as an ordered sum of positive integers. Thus the compositions of $4$ are $4, 3+1, 1+3, 2+2, 2+1+1, 2+1+1, 1+1+2, 1+1+1+1$. The underlying partition of a composition is the corresponding unordered sum.

A composition on $n$ may be represented as a sequence of $n$ dots separated by bars with no two bars adjacent: thus $4 = 1+2+1$ is represented by $( \bullet \vert \bullet\bullet \vert \bullet )$. The number of compositions of $n$ into $k$ parts is thus $\left({ \begin{array}{cc} n-1 \\ k-1 \end{array} }\right)$ and the total number of compositions of $n$ is $2^{n-1}$

References

  • Luoto, Kurt; Mykytiuk, Stefan; van Willigenburg, Stephanie, "An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux", Springer (2013) ISBN 978-1-4614-7299-5 Zbl 1277.16027
  • Riordan, John "Introduction to Combinatorial Analysis", Wiley [1958] Dover (2002) ISBN 0-486-42536-3 Zbl 0078.00805
How to Cite This Entry:
Composition (combinatorics). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Composition_(combinatorics)&oldid=54402