The well-known ** combinat[composition]** command computes and returns a list containing all distinct ordered **k**-tuples of positive integers whose elements sum to **n **. These are known as the compositions of ** n** . For some applications, additional constraints are required for the elements of these **k**-tuples, for example, that they are within a certain range.

The **Composition** procedure solves this problem. Required parameters: **n** - a nonnegative integer, **k **- a positive integer. The parameter **res** is the optional parameter (by default **res** is **0 **). If **res** is a number, all elements of **k**-tuples must be greater than or equal ** res **. If **res** is a range ** a .. b** , ** **all elements of** ****k**-tuples must be greater than or equal** **** a **and less than or equal** **** b** . **Composition(n,k,1)** is equivalent to **combinat[composition](n,k)** .

The code of the procedure:

**Composition := proc (n::nonnegint, k::posint, res::{range, nonnegint} := 0) **

**local a, b, It, L0;**** **

**if res::nonnegint then a := res; b := n-(k-1)*a else a := lhs(res); b := rhs(res) fi; **

**if b < a or b*k < n then return `No solutions` fi;**** **

**It := proc (L) **

**local m, j, P, R, i, N; **

**m := nops(L[1]); j := k-m; N := 0; **

**for i to nops(L) do **

**R := n-`+`(op(L[i])); **

**if R <= b*j and a*j <= R then N := N+1; **

**P[N] := [seq([op(L[i]), s], s = max(a, R-b*(j-1)) .. min(R, b))] fi; **

**od; **

**[seq(op(P[s]), s = 1 .. N)]; **

**end proc;**

**L0 := [[]]; **

**(It@@k)(L0);**** **

**end proc:**

Three simple examples:

**Composition(10,3); ``; **# All terms greater than or equal 0

**Composition(10,3, 2); **# All terms greater than or equal 2

**Composition(10,3, 2..4); ** # All terms greater than or equal 2 and less than or equal to 4

A more complex example. The problem - to find all the numbers in the range **1 .. 99999999** whose digits sum is equal to **21 **.

Each number is represented by a list of digits from left to right, replacing missing digits at the left with zeros.

**M:=Composition(21,8, 0..9): **

**nops(M); **# The number of solutions

**[seq(M[1+100000*i], i=0..9)]; **# 10 solutions from the list M starting the first one

**seq(add(%[i,k]*10^(8-k), k=1..8),i=1..nops(%)); **# Conversion into numbers

Composition.mws