1 #if !defined HAVE_IS_CATALAN_STEP_RGS_H__
2 #define HAVE_IS_CATALAN_STEP_RGS_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2012, 2014 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8
9 #include "fxttypes.h"
10
is_catalan_step_rgs(const ulong * rgs,ulong n)11 inline bool is_catalan_step_rgs(const ulong *rgs, ulong n)
12 // Return whether rgs[] is a valid Catalan (step-)RGS.
13 // The RGS are a[] such that a[k] >= a[k-1] (weakly ascending) and a[k]<=k.
14 // The RGS describe lattice paths from (0,0) to (n,n) with steps
15 // (+1,0) and (+1,+1) that do not go below the diagonal.
16 // Same as: rising factorial numbers where the digits are sorted.
17 {
18 if ( n==0 ) return true; // nothing to check
19
20 for (ulong j=0; j<n; ++j) // digits in range?
21 if ( rgs[j] > j ) return false;
22
23 for (ulong j=1; j<n; ++j) // sorted?
24 if ( rgs[j] < rgs[j-1] ) return false;
25
26 return true;
27 }
28 // -------------------------
29
30
31
32 #endif // !defined HAVE_IS_CATALAN_STEP_RGS_H__
33