Problem of the Week 1172

Factorials Galore!!!!

Consider all strings of length 11 that can be made from 10 "!"s and one "x." For example, !!!x!!!!!!! or !!!!!!!!!!x.

How many different functions can be described by such a string (using different parenthetizations), where these three functions are in play?

• x! is the factorial of x;
• !x is the subfactorial of x (same as the number of derangements of x objects);
• x!! is the double factorial of x: x(x − 2) ... 1 or 2

It turns out one can find a closed form here even with the 11 replaced by n. We are concerned here only with the abstract functions, not with any possible coincidences of values. So the actual functions used are not really relevant; for example, x!! can be read as (x!)! or x!!.

I know the answer to this question, but have not thought about extensions, with n "1"s and m variables instead of just 1 (and using multiplication for concatenation; e.g., with two variables, expressions such as !!!x!!!y!!!).

Source: Inspired by a student here at Macalester who told me about the !x notation for derangements, which was new to me.

© Copyright 2013 Stan Wagon. Reproduced with permission.

[View the solution]