function ways = mcnugget_ways ( a, nmax )

%*****************************************************************************80
%
%% mcnugget_ways() determines the number of solutions to a McNugget problem.
%
%  Discussion:
%
%     We are given a Diophantine equation 
%
%       a1 x1 + a2 x2 + ... + an * xn = n
%
%     for which the coefficients a are positive integers, and
%     the right hand side n is a nonnegative integer.
%
%     In particular, we might have a = [ 6, 9, 20 ] and n would be
%     the desired number of Chicken McNuggets.
%
%     We want to know the number of distinct ways of ordering the
%     desired number of McNuggets.
%
%     Here, we assume that none of the values in a can be written
%     as a linear combination of the other a values.
%
%     We have to be careful so that we only count a given arrangement
%     once, that is, the order in which we combine the values does not
%     matter.  Although 6+6+9 and 6+9+6 and 6+6+9 look "different",
%     they should only count here as a single solution to the problem
%     of ordering 21 McNuggets.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    24 December 2022
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Scott Chapman, Chris O’Neill,
%    Factoring in the Chicken McNugget Monoid,
%    Mathematics Magazine, 
%    Volume 91, Number 5, 2018, pages 323-336.
%
%  Input:
%
%    integer a(n): the number of McNuggets in each package size.
%
%    integer nmax: the maximum number of McNuggets desired.
%
%  Output:
%
%    integer ways(nmax+1): the number of distinct ways of ordering 0, 1, 2, ...,
%    nmax-1, nmax Chicken McNuggets.
%
  a_num = length ( a );
  a = sort ( a );
%
%  Count ways from 0 to nmax.
%
  ways = zeros ( nmax + 1, 1 );
%
%  ways(i) = 0 + sum ( 1 <= j <= a_num ) ways(i-a(j)) if i-a(i) > 0
%
  ways(1) = 1;
  for j = 1 : a_num
    for i = 1 : nmax
      pop = i - a(j);
      if ( 0 <= pop )
        ways(i+1) = ways(i+1) + ways(pop+1);
      end
    end
  end

  return
end

