Dwyer Function

 

Definition

 

A multifactorial function of two positive integers x and y, defined recursively by the recurrence relation

 

 

D(0,0) = 1,

 

D(0,1) = 1,

 

D(1,0) = 1,

 

D(1,1) = 1,

 

D(x,y) = x(y-2).(x!!)2.y(y-1).D(x-2,y-2) for x ≥ 2 and x ≥ 2

 

 

Tables of Values of D(x,y)

Values are given in index form because of their rapidly increasing properties

 

╔    y

 x

0

1

2

3

4

5

6

0

1

1

2

3.2

4.3.2

5.4.3.2

6.5.4.3.2

1

1

1

2

3.2

4.3.2

5.4.3.2

6.5.4.3.2

2

1

2

22.2

 3.24

 4.3.25

 5.4.3.26

 6.5.4.3.27

3

1

3

32.2

34.2

 4.35.2

 5.4.36.2

6.5.4.37.2

4

1

4.2

 42.23

 43.3.24

45.3.25

5.46.3.26 

6.5.47.3.27

5

1

5.3

 52.32.2

 53.34.2

 54.4 35.2

56.4.36.2

6.57.4.37.2

6

1

6.4.2

62.42.23

63.43 3.24

64.45.3.25

65.5.46.3.26

67.5.47.3.27

 

 

Properties of D(x,y)

D(0,y) = y!, for all positive integer y

 

 

D(x,0) = 1, for all positive integer x

 

 

D(x,x) = x! [x!!]x, for all positive integer

 

e.g D(3,3) = 3!(3.1)3 = 162 ü

 

 

D(x,y) = xy D(x-2,y), for integer x ≥ 2

 

 

D(x,y) = x!! y D(x,y-1), for integer y ≥ 1

 

 

D(x,y) = y! [x!!]y, for positive integers x ≥ 0 and y ≥ 0

 

 

 

 

Negative Values of D(x,y)

 

 

The function can be extended to negative values using properties

 of the Gamma function and the double factorial function.

 

 

 

Integral Representations of D(x,y)

 

The function can be extended to real and complex values using integral properties

 of the Gamma function and the double factorial function. For z = x + iy,

 

n\equiv 0(\mbox{mod k})

 

 

 

Values of D(x,y)

 

 

D(x,1) = 3, 15, 105, 945, 10395, ...

 

 

 

Graphical Representation of D(x,1)

 

 

 
x D(x,1)
1 3.00E+00
2 1.50E+01
3 1.05E+02
4 9.45E+02
5 1.04E+04
6 1.35E+05
7 2.03E+06
8 3.45E+07
9 6.55E+08
10 1.37E+10
11 3.16E+11
12 7.91E+12
13 2.13E+14
14 6.19E+15
15 1.92E+17
16 6.33E+18
17 2.22E+20
18 8.20E+21
19 3.20E+23
20 1.31E+25

 

 

 

 

History of Fn(x,y)

 

The D function is named after British mathematician John Dwyer, currently at the Unversity of Roehampton, London UK.

Work on its applications started in the year 2005 including project students at Richmond University.

 

Applications of D(x,y)

1. The number of Hamiltonian circuits in a complete labelled graph Kn is given by

 (n-1)D(0,n-2)

 

For example, there are (5-1)D(0,3) = 24 Hamiltonian circuits in K5. 

These include [(1,2,3,4,5), (1,2,3,5,4), ...].

 

 

2. The number of Eulerian circuits in a complete labelled graph Kn for odd values of n is given by

 (n-1)D(n-2,n-2).

 

For example, there are (5-1)D(3,3) = 648 Euler circuits in K5.

These include [((1,2),(2,3),(3,4),(4,5),(5,1),(1,3),(3,5),(5,2),(2,4),(4,1)), ...].

 

Note: Hamilton circuits pass once through each and every vertex whereas Euler circuits pass once through each and every edge.

 

3. In compiler testing, the recurrence relation can be used to test the ability to handle recursion efficiently.

A A A