Algorithms for enumeration problem of linear congruence modulo m as sum of restricted partition numbers

Abstract

We consider the congruence x ₁ + x ₂ + \cdots+ x _r ≡ c (mod m), where m and r are positive integers and c\in {\mathbb{Z}}_m:\{\mathrm{0},\mathrm{1},\cdots ,m-\mathrm{1}\}(m\ge \mathrm{2}). Recently, W. -S. Chou, T. X. He, and Peter J. -S. Shiue considered the enumeration problems of this congruence, namely, the number of solutions with the restriction x_{\mathrm{1}}\le x_{\mathrm{2}}\le \cdots \le x_r, and got some properties and a neat formula of the solutions. Due to the lack of a simple computational method for calculating the number of the solution of the congruence, we provide an algebraic and a recursive algorithms for those numbers. The former one can also give a new and simple approach to derive some properties of solution numbers.

Keywords

Congruence / multiset congruence solution / restricted integer partition

References

[1] Andrews G E. The Theory of Partitions. EncycloMath Appls, Vol 2. London: Addison-Wesley, 1976

[2] Cameron P J. Combinatorics: Topics, Techniques, Algorithms. Cambridge: Cambridge University Press, 1994

[3] Chou W-S, He T X, Shiue P J-S. Enumeration problems for a linear congruence modulo m.Taiwanese J Math, 2014, 18(1): 265–275

[4] Fine N J. Binomial coefficients modulo a prime. Amer Math Monthly, 1947, 54: 589–592

[5] Guy R K. Parker’s permutation problem involves the Catalan numbers. Amer Math Monthly, 1993, 100(March): 287–289

[6] Opdyke J D. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions. J Math Model Algorithms, 2010, 9: 53–97

[7] Rademacher H. Topics in Analytic Number Theory. Grundlehren der mathematischen Wissenschaften, 169. New York-Heidelberg: Springer-Verlag, 1973

[8] Sanchis L A, Squire M B. Parallel algorithms for counting and randomly generating integer partitions. J Paral Distrib Comput, 1996, 34: 29–35

[9] Stanley R P. Enumerative Combinatorics, Vol 2. Cambridge Stud Adv Math, Vol 62. Cambridge: Cambridge Univ Press, 1998

[10] Stanley R P. Catalan Addendum.

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg