Namespaces
Variants
Actions

Difference between revisions of "Denumerant"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: isbn link)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311701.png" /> of partitions of an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311702.png" /> into parts equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311703.png" />, i.e. the number of solutions in non-negative integers of the equation
+
{{TEX|done}}{{MSC|05A17}}
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311704.png" /></td> </tr></table>
 
  
 +
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
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311705.png" /></td> </tr></table>
+
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)} \ .
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311706.png" /></td> </tr></table>
 
  
 
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) \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311707.png" /></td> </tr></table>
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311708.png" /> is the least common multiple of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d0311709.png" />, then the denumerant
+
D(An+b;a_1,\ldots,a_m) \ ;\ \ b=0,\ldots,A-1
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d03117010.png" /></td> </tr></table>
+
is a polynomial of degree $(m-1)$ with respect to $n$.
 
 
is a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d03117011.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031170/d03117012.png" />.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> J. Riordan,   "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top"> J. Riordan, "An introduction to combinatorial analysis" , Wiley  [1958] Dover (2002) {{ISBN|0-486-42536-3}} {{ZBL|0078.00805}}</TD></TR>
 +
</table>

Latest revision as of 16:46, 23 November 2023

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 combinatorial 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
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article