
(* Copyright 1988 Wolfram Research Inc. *)

		(** Combinatorial functions **)

BeginPackage["DiscreteMath`CombinatorialFunctions`"]

(* Subfactorials *)

Subfactorial::usage =
	"Subfactorial[n] gives the number of permutations of n objects
	which leave no object fixed."

(* Catalan numbers *)

CatalanNumber::usage =
	"CatalanNumber[n] gives the nth Catalan number."

(* Fibonacci numbers *)

Fibonacci::usage =
	"Fibonacci[n] gives the nth Fibonacci number."

(* Hofstadter's function *)

Hofstadter::usage = "Hoftstadter[n] gives Hoftstadter's function."

Begin["`Private`"]

Subfactorial[n_Integer?Positive] := 
	n! Block[{k}, Sum[(-1)^k/k!, {k, 0, n}]]

CatalanNumber[n_Integer] := Binomial[2n,n]/(n+1)

Fibonacci[n_Integer?Positive] := 
	Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2]

Fibonacci[0] = Fibonacci[1] = 1


Hofstadter[n_Integer?Positive] :=
	Hofstadter[n] =
	Hofstadter[n - Hofstadter[n-1]] + Hofstadter[n - Hofstadter[n-2]]

Hofstadter[1] = Hofstadter[2] = 1

End[ ]
EndPackage[ ]
