Hosted by The Math Forum

Problem of the Week 1172

Factorials Galore!!!!

_____________________________________________
MacPOW Home || Math Forum POWs || Search MacPOW
_____________________________________________

Solution

I received comment only from Joseph DeVincentis, who correctly identified the numbers that arise as the Pell numbers.

He wrote:

What we really have here is some sequence of the three functions applied to x.

Define F(n) as the number of functions using n !s and one x. F(0) = 1 (the identity function) and F(1) = 2 (either subfactorial or factorial of x). Then when we add one more function to reach two !s, it can be either factorial or subfactorial after one of F(1) or double factorial after F(0), so

F(2) = 2F(1) + F(0),

and in general,

F(n) = 2F(n − 1) + F(n − 2).

This yields the sequence

1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, ...

To answer the original question, F(10) = 5741.

OEIS records this sequence as the Pell numbers.

If you have more than one variable, it gets considerably more complicated. With 2 variables and n !s, for each partition of n into three labeled parts a, b, and c, you get to perform F(a) operations on x and F(b) operations on y before you multiply them, and F(c) operations on their product. Then F(a, b, c) can be solved as a three-variable recurrence in a similar manner to the original problem, but it gets tremendously complicated quickly.

[Back to Problem 1172]

© Copyright 2013 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


26 November 2013