Vol. 103, No. 2, 1982

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
Random mappings with constraints on coalescence and number of origins

James Arney and Edward A. Bender

Vol. 103 (1982), No. 2, 269–294

In §2 we tabulate for easy reference probability distributions associated with some functions of random mappings on large sets (e.g., number of points on cycles, size of the component containing x) when the number of immediate predecessors of each point is required to lie in some set 𝒟.

Our results allow the number of origins to be restricted, a useful constraint in some shift register situations. Although limiting the number of immediate predecessors to {0,1,2} and constraining the number of origins is in some ways a poor model for random shift registers, we show in §§3 and 4 that most of the tabulated results fit shift register data quite well.

Derivations of our results are given in §§5 through 9.

Mathematical Subject Classification 2000
Primary: 05C80
Secondary: 60C05
Received: 3 October 1979
Published: 1 December 1982
James Arney
Edward A. Bender