Kombinatorik mit dem Computer: Partitionen und Frankaturen. (Combinatorics with the computer: partitions and the postage stamp problem) (Q914676)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Kombinatorik mit dem Computer: Partitionen und Frankaturen. (Combinatorics with the computer: partitions and the postage stamp problem) |
scientific article |
Statements
Kombinatorik mit dem Computer: Partitionen und Frankaturen. (Combinatorics with the computer: partitions and the postage stamp problem) (English)
0 references
1987
0 references
There are given computer programs to solve the following two combinatorical problems. Given a set \(R=\{a_ 1,a_ 2,...,a_ p\}\subseteq {\mathbb{N}}\) with (*) \(a_ 1<a_ 2<...<a_ p\) and given \(n\in {\mathbb{N}}\) compute the number \(f^ R_ n\) of all R-partitions of n, i.e. all \((x_ 1,x_ 2,...,x_ p)\) with \(x_ 1a_ 1+...+x_ pa_ p=n\) and \(x_ i\in {\mathbb{N}}_ 0,\) \(i=1,...,p\) and list them. The computation of \(f^ R_ n\) is based on the recursion formula \[ f_ j^{\{a_ 1,...,a_{k+1}\}}=f_ j^{\{a_ 1,...,a_ k\}}+f_{j-a_{k+1}}^{\{a_ 1,...,a_ k\}}+f_{j- 2a_{k+1}}^{\{a_ 1,...,a_ k\}}+... \] for \(a_{k+1}\leq j\leq n\) and \(1\leq k\leq p-1.\) Rearward lexicographical arrangement of \(x_ 2,x_ 3,...,x_ p\in {\mathbb{N}}_ 0\) with \(0\leq s:=x_ 2a_ 2+...+x_ pa_ p\leq n\) and \(a_ 1| n-s\) gives the list of all R-partitions of n where \(x_ 1:=\frac{n-s}{a_ 1}.\) By few suitable modifications these two programs are also used to count and list all \(p_ n\) ``free'' partitions of n (use \({\mathbb{N}}\) instead of the finite set R) and to solve a sort of postage stamp problem (in (*) ``\(\leq ''\) is allowed instead of \(``<'')\).
0 references
lexicographical arrangement
0 references
partitions
0 references