Featured Posts

We are happy to announce the first results of a partnership between Maplesoft and the University of Waterloo to provide effective, engaging online education for technical courses.

Combining rich course materials developed by the University with Maple T.A. and Maplesoft technology for developing, managing, and displaying dynamic content, the Secondary School Courseware project supports high school students and teachers from around the world in their Precalculus and Calculus courses. The site includes interactive investigations, videos, and self-assessment questions that provide immediate feedback.

Feel free to take a look. The site is free, and no login is required.  

For more information about the project, see Online Mathematical Courseware.

eithne

The well-known  combinat[composition]  command computes and returns a list containing all distinct ordered  k-tuples of positive integers whose elements sum to  . 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, - a positive integer. The parameter  res  is the optional parameter (by default  res is  ). 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


MaplePrimes Questions Recent Unanswered Maple MapleSim Maple T.A.