A bijection for ordered factorizations

DOI10.1016/0097-3165(90)90040-4MaRDI QIDQ914675zbMATH OpenOpenAlexWikidataFDO

Authors Richard Garfield, Donald E. Knuth, Herbert S. Wilf

Publication date 1990

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0097-3165(90)90040-4

zbMATH Keywords

generating functionsMöbius functionordered factorization

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Factorization; primality (11A51)

Review text

An ordered factorization of n is a representation of n as a product of integers \(\geq 2\); two such factorizations are considered the same only if they agree in both factors and order. Let \(\Psi\) (n) denote the class of all ordered factorizations \(\psi\) of n; and write \(k=k(\psi)\) for the number of factors in \(\psi\). The authors give two short proofs of the result: \(\sum_{\psi \in \Psi (n)}(-1)^{k(\psi)}=\mu (n)\) where \(\mu\) is the Möbius function. The first proof uses generating functions; the second exhibits an explicit bijection.

Recommendations

• scientific article; zbMATH DE number 3946129
• The Möbius function of factor order
• On the number of ordered factorizations of natural numbers
• scientific article; zbMATH DE number 3882435
• scientific article; zbMATH DE number 3271678

Cited in

(2)

• A Bijection in the Theory of Derangements
• A SURVEY OF FACTORIZATION COUNTING FUNCTIONS

This page was built for publication: A bijection for ordered factorizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q914675)