/* 

  Telephone number in Picat.

  http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29

  Via Spiked Math: http://spikedmath.com/545.html
  """
  ...
  Also called the involution numbers, they can be determined by the recurrence:

      a_0 = a_1 = 1;
      a_n = a_{n−1} + (n − 1) a_{n−2}, for n > 1.

  More interesting, they also count the number of involutions on a set
  with n elements -- note that an involutary function, is a function f 
  that is its own inverse, that is,

     f(f(x)) = x for all x in the domain of f. 
  """
  
  The sequence is
  1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, ...
  "Number of self-inverse permutations on n letters, also known as 
   involutions; number of Young tableaux with n cells.":
  http://oeis.org/A000085

  See young_tableaux.pi for generating (and counting) Young tableaux.

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

go =>
  garbage_collect(300_000_000),
  Seq = [],
  foreach(I in 0..42)
     a(I,R), 
     println([I,R]),
     Seq := Seq ++ [R]
  end,
  writeln(seq=Seq),
  nl.


go2 ?=>
  member(I,0..1000),
  a(I,R),
  println(I=R),
  fail,
  nl.
go2 => true.

table
a(0,X) ?=> X = 1.
a(1,X) ?=> X = 1.
a(N,Res) =>
  N > 1,
  N1 = N-1,
  N2 = N-2,
  a(N1,N1Res),
  a(N2,N2Res),
  Res = N1Res + N1* N2Res.