Divisor generating functions and insertion into a heap

DOI10.1016/0166-218X(87)90043-6MaRDI QIDQ1093664zbMATH OpenFDO

Authors Keisuke Uchimura

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(87)90043-6

zbMATH Keywords

asymptotic valuesBell polynomialexpected valueheapshigher moments of number of exchangesidentities for divisor generating functionssum of divisor function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Arithmetic functions; related numbers; inversion formulas (11A25) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Review text

The main result is an identity involving \(\sigma_ r(n)\) and the Bell polynomial. This is a generalization of the author's previous result concerning \(\sigma_ 0(n)\). Application to the analysis of heaps is shown.

Recommendations

• Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures
• A new look on the generating function for the number of divisors
• Recurrence relations on heaps
• scientific article; zbMATH DE number 3105852
• On the divisor function d ( n )
• Generating functions in the knapsack problem
• A generating function for numbers of insets
• A combinatorial proof of an identity for the divisor generating function
• Heap-orderd trees, 2-partitions and continued fractions
• On a generalization of the divisor additive problem

Cites work

• An identity for the divisor generating function arising from sorting theory
• scientific article; zbMATH DE number 3141365 (Why is no real title available?)
• scientific article; zbMATH DE number 3700229 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• Inserting a new element into a heap
• Priority queues with update and finding minimum spanning trees
• Repeated random insertion into a priority queue

Cited in

(3)

• Some \(q\)-series identities related to divisor functions
• On the \(k\)th smallest part of a partition into distinct parts
• A divisor generating q-series and cumulants arising from random graphs

This page was built for publication: Divisor generating functions and insertion into a heap

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