Frontiers of Mathematics in China >

2015 , Vol. 10 >Issue 1: 69 - 89

DOI: https://doi.org/10.1007/s11464-014-0394-2

RESEARCH ARTICLE

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

  • Tian-Xiao HE 1 ,
  • Peter J. -S. SHIUE , 1
Expand
  • 1. Department of Mathematics, Illinois Wesleyan University, Bloomington, IL 61702, USA
  • 2. Department of Mathematical Sciences, University of Nevada, Las Vegas, Las Vegas, NV 89154-4020, USA

Received date: 20 Jan 2014

Accepted date: 29 May 2014

Published date: 30 Dec 2014

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

Abstract

We consider the congruence x 1 + x 2 + ⋯+ x r ≡ c (mod m), where m and r are positive integers and c ∈ ℤ m : { 0 , 1 , ⋯ , m − 1 } ( m ≥ 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 1 ≤ x 2 ≤ ⋯ ≤ 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.

Key words： Congruence; multiset congruence solution; restricted integer partition

Cite this article

Tian-Xiao HE , Peter J. -S. SHIUE . Algorithms for enumeration problem of linear congruence modulo m as sum of restricted partition numbers[J]. Frontiers of Mathematics in China, 2015 , 10(1) : 69 -89 . DOI: 10.1007/s11464-014-0394-2

References

Publishing order | Descend order by publishing year | Descend order by cited within
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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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.

Options
Outlines

/

〈 〉