Algorithms for enumeration problem of linear congruence modulo <i>m</i> as sum of restricted partition numbers

doi:10.1007/s11464-014-0394-2

Front. Math. China

2015, Vol. 10

Issue (1) : 69-89 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¹, Peter J. -S. SHIUE¹(

)

¹. Department of Mathematics, Illinois Wesleyan University, Bloomington, IL 61702, USA
². Department of Mathematical Sciences, University of Nevada, Las Vegas, Las Vegas, NV 89154-4020, USA

Download: PDF(157 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

We consider the congruence x ₁ + x ₂ + $⋯$ + 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.

Keywords Congruence multiset congruence solution restricted integer partition

Corresponding Author(s): Peter J. -S. SHIUE

Issue Date: 30 December 2014

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]. Front. Math. China, 2015, 10(1): 69-89.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-014-0394-2
https://academic.hep.com.cn/fmc/EN/Y2015/V10/I1/69

1	G E Andrews. The Theory of Partitions. EncycloMath Appls, Vol 2. London: Addison-Wesley, 1976
2	P J Cameron. Combinatorics: Topics, Techniques, Algorithms. Cambridge: Cambridge University Press, 1994
3	W-S Chou, T X He, P J-S Shiue. Enumeration problems for a linear congruence modulo m.Taiwanese J Math, 2014, 18(1): 265–275 https://doi.org/10.11650/tjm.18.2014.2295
4	N J Fine. Binomial coefficients modulo a prime. Amer Math Monthly, 1947, 54: 589–592 https://doi.org/10.2307/2304500
5	R K Guy. Parker’s permutation problem involves the Catalan numbers. Amer Math Monthly, 1993, 100(March): 287–289 https://doi.org/10.2307/2324467
6	J D Opdyke. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions. J Math Model Algorithms, 2010, 9: 53–97 https://doi.org/10.1007/s10852-009-9116-2
7	H Rademacher. Topics in Analytic Number Theory. Grundlehren der mathematischen Wissenschaften, 169. New York-Heidelberg: Springer-Verlag, 1973
8	L A Sanchis, M B Squire. Parallel algorithms for counting and randomly generating integer partitions. J Paral Distrib Comput, 1996, 34: 29–35 https://doi.org/10.1006/jpdc.1996.0043
9	R P Stanley. Enumerative Combinatorics, Vol 2. Cambridge Stud Adv Math, Vol 62. Cambridge: Cambridge Univ Press, 1998
10	R P Stanley. Catalan Addendum.

[1]	Lingli XIA, Jing YANG. Sign or root of unity ambiguities of certain Gauss sums[J]. Front Math Chin, 2012, 7(4): 743-764.

Viewed

Full text

Abstract

Cited

Shared

Discussed