You're given a bag of the integers from 1 to n. Choose n of those numbers, possibly with repetition, in a particular order. How many ways W(n) can the product of your choices be equal to n factorial? How is this related to n! ?

An equivalent problem statement if you're really in to functions is: how many functions f:[n]->[n] exist such that \product_i f(i) = n! ?

Example:
Let n=6. 6! = 1*2*3*4*5*6, which gives one combination. You can also rearrange the above to find other combinations--for instance, 2*1*3*4*5*6 gives another combination. But not all valid combinations are simply rearrangements of this product. Sometimes you can substitute numbers in, for instance, I could go with 1*1*6*4*5*6 = 720 = 6!.

I haven't calculated W(6), though it could be done by a computer script. Right now my guess is that W(6) = 4*6!.

Example:
Let n=2. 2! = 1*2 = 2; all possible combinations of 2 numbers from {1, 2} with order are 1:1, 1:2, 2:1, 2:2, though only 1:2 and 2:1 give the proper product. Thus W(2) = 2! = 2.


I haven't worked through this question myself, and I don't know the answer. I thought it might interest some of you. I encountered it when trying to find a simple test to see if I had found a permutation of n numbers; my test was to see if their product was n!. The failure of this test leads me to other questions, but I think this is enough for now .