Sorting numbers

The purpose of this page is to clarify the definitions and notation used by Motzkin in "Sorting numbers for cylinders and other classification numbers" (1971).

Sequence Notation Correspondence

Sequences of "Sorting Numbers" in the OEIS

Sequence	Motzkin's Notation
Partition numbers	A000041$(n)=\displaystyle {!}^{!n}$
Bell numbers	A000110$(n)=\displaystyle {!}^{n}$
Number of partitions of {1,...,n}	A000262$(n)=\displaystyle {!}^{n+}$
Fubini numbers	A000670$(n)=\displaystyle {\Sigma }_{>}^{n}$
E.g.f.: e^(2*(e^x - 1))	A001861$(n)=\displaystyle {!}^{{\underline {!}}\cdot n}$
Max_{k} { Number of partitions of n into k positive parts }	A002569$(n)=\displaystyle {!\max }_{>}^{!n}$
n!*2^(n-1)	A002866$(n)=\displaystyle {\Sigma }_{>}^{n+}$
(n+1)!*binomial(n,floor(n/2))	A002867$(n-1)=\displaystyle {\max }_{>}^{n+}$
Largest number in n-th row of triangle A008297	A002868$(n)=\displaystyle {!\max }_{>}^{n+}$
Largest number in n-th row of triangle A019538	A002869$(n)=\displaystyle {\max }_{>}^{n}$
Max_{k} Stirling2(n,k)	A002870$(n)=\displaystyle {!\max }_{>}^{n}$
Max_{k} 2^k*Stirling2(n,k)	A002871$(n)=\displaystyle {!\max }_{>}^{{\underline {!}}\cdot n}$
Column 2 of A162663	A002872$(n)=\displaystyle {!}^{{\underline {!}}2\cdot n}={!}^{{\underline {cy}}2\cdot n}$
Max_{k} #{partitions of 2n into k parts which are invariant under (12)(34)...(2n-1,2n)}	A002873$(n)=\displaystyle {!\max }_{>}^{{\underline {!}}2\cdot n}$
Column 3 of A162663	A002874$(n)=\displaystyle {!}^{{\underline {cy}}3\cdot n}$
?	A002875$(n)=\displaystyle {!\max }_{>}^{{\underline {cy}}{3\cdot n}}$
Stirling numbers of the second kind	A008277$(n,k)=\displaystyle {!k}_{>}^{n}$
Falling factorial	A008279$(n,k)=\displaystyle {n}_{<}^{k}$
Number of partitions of n into k positive parts	A008284$(n,k)=\displaystyle {!k}_{>}^{!n}$
k!*Stirling2(n,k)	A019538$(n,k)=\displaystyle {k}_{>}^{n}$
Number of partitions of n into at most k positive parts	A026820$(n,k)=\displaystyle {!k}^{!n}$
Column 5 of A162663	A036075$(n)=\displaystyle {!}^{{\underline {cy}}5\cdot n}$
Column 7 of A162663	A036077$(n)=\displaystyle {!}^{{\underline {cy}}7\cdot n}$
Column 11 of A162663	A036081$(n)=\displaystyle {!}^{{\underline {cy}}11\cdot n}$
Sum_{i<=k} Stirling2(n,i)	A102661$(n,k)=\displaystyle {!k}^{n}$
Column 13 of A162663	A141009$(n)=\displaystyle {!}^{{\underline {cy}}13\cdot n}$
n!*binomial(n-1,k-1)	A156992$(n,k)=\displaystyle {k}_{>}^{n+}$

See also

• Index entries for sequences related to sorting

References

• T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]