Difference between revisions of "Denumerant"
From Encyclopedia of Mathematics
(Importing text file) |
(better) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | {{TEX|done}}{{MSC|05A17}} | |
| − | |||
| − | |||
| + | The number $D(n; a_1,\ldots,a_m)$ of partitions of an integer $n$ into parts equal to $a_1,\ldots,a_m$, i.e. the number of solutions in non-negative integers $x_1,\ldots,x_m$ of the equation | ||
| + | $$ | ||
| + | n = a_1 x_1 + \cdots + a_m x_m \ . | ||
| + | $$ | ||
The generating function of the denumerants is | The generating function of the denumerants is | ||
| − | + | $$ | |
| − | + | D(z; a_1,\ldots,a_m) = \sum_n D(n;a_1,\ldots,a_m) z^n = \frac{1}{\left({1-z^{a_1}}\right)\cdots\left({1-z^{a_m}}\right)} \ . | |
| − | + | $$ | |
| − | |||
The simplest method of computing a denumerant is by Euler's recurrence relation: | The simplest method of computing a denumerant is by Euler's recurrence relation: | ||
| + | $$ | ||
| + | D(n;1,\ldots,k) - D(n-k;1,\ldots,k) = D(n;1,\ldots,k-1) \ . | ||
| + | $$ | ||
| − | + | Explicit formulas for certain denumerants may be obtained from the following theorem: If $A$ is the least common multiple of the numbers $a_1,\ldots,a_m$, then the denumerant | |
| − | + | $$ | |
| − | Explicit formulas for certain denumerants may be obtained from the following theorem: If | + | D(An+b;a_1,\ldots,a_m) \ ;\ \ b=0,\ldots,A-1 |
| − | + | $$ | |
| − | + | is a polynomial of degree $(m-1)$ with respect to $n$. | |
| − | |||
| − | is a polynomial of degree | ||
====References==== | ====References==== | ||
| − | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> J. Riordan, "An introduction to combinational analysis" , Wiley ( | + | <table> |
| + | <TR><TD valign="top">[1]</TD> <TD valign="top"> J. Riordan, "An introduction to combinational analysis" , Wiley [1958] Dover (2002) ISBN 0-486-42536-3 {{ZBL|0078.00805}}</TD></TR> | ||
| + | </table> | ||
Revision as of 21:01, 21 April 2017
2020 Mathematics Subject Classification: Primary: 05A17 [MSN][ZBL]
The number $D(n; a_1,\ldots,a_m)$ of partitions of an integer $n$ into parts equal to $a_1,\ldots,a_m$, i.e. the number of solutions in non-negative integers $x_1,\ldots,x_m$ of the equation $$ n = a_1 x_1 + \cdots + a_m x_m \ . $$ The generating function of the denumerants is $$ D(z; a_1,\ldots,a_m) = \sum_n D(n;a_1,\ldots,a_m) z^n = \frac{1}{\left({1-z^{a_1}}\right)\cdots\left({1-z^{a_m}}\right)} \ . $$
The simplest method of computing a denumerant is by Euler's recurrence relation: $$ D(n;1,\ldots,k) - D(n-k;1,\ldots,k) = D(n;1,\ldots,k-1) \ . $$
Explicit formulas for certain denumerants may be obtained from the following theorem: If $A$ is the least common multiple of the numbers $a_1,\ldots,a_m$, then the denumerant $$ D(An+b;a_1,\ldots,a_m) \ ;\ \ b=0,\ldots,A-1 $$ is a polynomial of degree $(m-1)$ with respect to $n$.
References
| [1] | J. Riordan, "An introduction to combinational analysis" , Wiley [1958] Dover (2002) ISBN 0-486-42536-3 Zbl 0078.00805 |
How to Cite This Entry:
Denumerant. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Denumerant&oldid=16405
Denumerant. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Denumerant&oldid=16405
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article