Problem of the Week 1172

Factorials Galore!!!!

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.


26 November 2013