[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

431.0. "straighten a recursive function" by CORVUS::THALLER () Thu Jan 16 1986 14:27

Is there a one line formula that will express the following recursive function?

F(2) = 1
F(3) = 2
F(n) = (n-1)[F(n-1)+F(n-2)]  for n>2

and n is an integer > 1

Actually, I'm looking for a simpler way to calculate  F(n)/[(n-1)^n]
        
For an arbirtrary n > 10

T.R	Title	User	Date	Lines
431.1		TOOLS::STAN	`Fri Jan 17 1986 14:24`	27
	The numbers in the sequence obtained, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961 are known as subfactorials (written !n, for example, !4=9, read as subfactorial 4 equals 9). The numbers are also known as Rencontre Numbers after the famous "Le Probleme des rescontres". These numbers represent the number of derangements of the first n integers (see "derangements" in the math notes concordance), that is, the number of permutations of 1,2,3,...,n leaving no number fixed. A good reference is Daniel I. A. Cohen, Basic Techniques of Combinatorial Theory, pp 89-92. Other references are Riordan, Introduction to Combinatorial Analysis, page 188, and Ryser, Combinatorial Mathematics p. 23. See also Comtet, Advanced Combinatorics. Many books on recreational mathematics also talk about these numbers. There is no closed form formula for the nth subfactorial. A one line non-recursive formula is f(n)=n!(1-1/1!+1/2!-1/3!+1/4!-1/5!+...-...+(-1)^n/n!). A simple way to evaluate f(n) for large n is that it is approximately n!/e. In fact, f(n) is precisely the nearest integer to n!/e. For even larger n, apply Stirlings approximation for n! to get a formula easier to calculate. If we divide each term by (n-1), we get the related sequence, 1, 1, 3, 11, 53, 309, 2119, 16687, 148329. It is defined by the recurrence g(n)=ng(n-1)+(n-1)g(n-2).
431.2		SPRITE::OSMAN	`Fri Jan 17 1986 14:35`	22
	The following may or may not help: If you had asked the simpler question, namely F(0) = 0 F(1) = 1 F(n) = (1)[F(n-1)+F(n-2)] you'd have the well-known "Fibonacci" sequence. The one-line formula for it is F(n) = ((1+SQR(5))n - (1-SQR(5))n) / (SQR(5)(2n)) Perhaps this will offer a clue. Perhaps someone out there has a more general recurrence formula for F(n) = (1)[aF(n-1)+b*F(n-2)] That might offer even more of a clue. /Eric
431.3		TURTLE::STAN	`Fri Jan 17 1986 17:15`	4
	F(n)=aF(n-1)+bF(n-2) is just a simple linear recurrence with constant coefficients. The theory of this is well-known. The solution is of the form p^n+q^n. The original problem though is a recurrence with non-constant coefficients. That is another ball of wax.