Combinations of numbers

[jemidiah]

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 :).

[Rich2189]

Hopefully I have not misinterpreted the question. I had a quick think about W(6). I came to the conlusion that W(6) would be 6*6!

W(6)
1: 1,2,3,4,5,6 No factor substitutions.

2: 2,2,3,2,5,6 (1,4) -> (2,2)

3: 2,2,3,4,5,3 (1,6) -> (2,3)

4: 1,1,6,4,5,6 (2,3) -> (1,6)

Composition of individual factor substitutions.

5: 1,2,6,2,5,6 (1,4) -> (2,2), (2,3) -> (1,6)

6: 1,4,3,4,5,3 (1,6) -> (2,3), (2,2) -> (1,4)

I love questions like this but I lack mathematical talent, the marbles question was fantastic!

[jemidiah]

Yup, I think you've got the question just fine. Your second substitution (1,4)->(2,2) might not give the full 6! rearrangements:

1:2:3:4:5:6 under (1,4)->(2,2) gives 2:2:3:2:5:6
4:2:3:1:5:6 ""
2:1:3:4:5:6 ""
2:4:3:1:5:6 ""
1:4:3:2:5:6 ""
4:1:3:2:5:6 ""

Moving the 1, 2, and 4, around, they'll all become 3 2's after the substitution. They can be moved around in 3! = 6 ways as listed above, which should mean that this substitution gives 6! / 3! arrangements. I think dealing with these special cases is at the heart of the matter.

[Rich2189]

Looks like the same goes for the others, apologies If I make silly errors. So the number of combinations is actually:


W(6)
1: 1,2,3,4,5,6 No factor substitutions. 6!

2: 2,2,3,2,5,6 (1,4) -> (2,2) 6!/3!

3: 2,2,3,4,5,3 (1,6) -> (2,3) 6!/(2!*2!)

4: 1,1,6,4,5,6 (2,3) -> (1,6) 6!/(2!*2!)

Composition of individual factor substitutions.

5: 1,2,6,2,5,6 (1,4) -> (2,2), (2,3) -> (1,6) 6!/(2!*2!)

6: 1,4,3,4,5,3 (1,6) -> (2,3), (2,2) -> (1,4) 6!/(2!*2!)


= 1560

D: nightmare. I was hoping for it to be an neat relationship between the common factors of those numbers which are not prime and 1.

[Milk]

I am right in that any solution is dependent on frequency of primes up to n?

[jemidiah]

I am right in that any solution is dependent on frequency of primes up to n?

In some manner, yes; only non-primes can initiate factor substitutions. Not all composites are created equal, though, so the relationship might be complicated.


I think your list is exhaustive Rich, and it gives W(6) = 6!*(1+1/4+1/4+1/4+1/4+1/6) = 2*6! + 5!. There must be some recursion going on here; every arrangement of 5 can be made into an arrangement of 6 by just sticking a 6 in somewhere, which can be done 6*W(5) ways. The 6 may itself split up in new ways, adding extra arrangements--how could we count them?

I think we need the first few values of W.

[Rich2189]

w(0) = 0

w(1) = 1! = 1

W(2) = 2! = 2

w(3) = 3! = 6

W(4) = (4! + 4!/3!) = 28

W(5) = (5! + 5!/3!) = 140

W(6) = 6! + (6!/3!) + (6!/(2!*2!)) + 6!/(2!*2!) + 6!/(2!*2!) + 6!/(2!*2!) = 1560

When a prime is added to the sequence as in the case of W(4) to W(5) then the new result is as you suggested simply 5*W(4). From this I can see that W(7) is 7*W(6) = 10920 since 7 is prime.

I am going to need a bright idea to determine how many extra combinations are added in the event of a non-prime as we have been presented with the special case of a square number 4 which has a repeated factor which is going to impact on the number of extra substitutions (4 extra). It can not really be compared to the number of extra combinations for W(6) (720 extra) as this has no repeated factors.

I will continue thinking.

[jemidiah]

I wonder if a more large-scale pattern emerges after a while. I'm certain we can approximate W for large n--after a while, adding one composite is probably about the same as adding another. This is a much more complex problem than I thought at first.

[Milk]

Surely if this problem hinges around prime/composite frequency and magnitude then there can be no pattern, only approximation. Or does it not work like that?

It looks like an interesting brute force problem. Has anyone had a go at coding anything yet?

[jemidiah]

Since I personally can figure out W(n) for any n by hand given enough time, assuming I only use operations a Turing machine can do, the problem is computable, with some pattern we could find. The trick is to find a nice closed-form expression, and not an algorithm to compute it for some n given an arbitrarily large amount of time.

In short, there's probably a pattern, but like prime numbers tend to be, the pattern may well be too complex to express in ways we're used to. Then again, it may not :). I'm hoping it's not, and that we can see something. Even if we just found a relation to the prime counting function, itself maddeningly complex, I'd be happy.

[jemidiah]

I know this is an old thread, but I asked my old combinatorics professor for his thoughts and at least got a better result than the above.

First, he defined a(n, m, k) to be the number of k-term ordered factorizations of n using terms of size <= m. For instance, a(6, 3, 2) counts the following factorizations of the number 6 using 2 terms of size at most 3: 2*3, 3*2. Any other factorization must include the number 6 as a term, which is greater than 3, so this list is complete. So, apparently a(6, 3, 2) = 2.

He noticed that a(n, m, k) can be calculated recursively using a(n, m, k) = sum over all factors d of n of a(n/d, m, k-1). This formula boils down to the following observation: any factorization of n can be said to start with some factor d of n. For n=6, we have 2-term factorizations 1*6, 6*1, 2*3, 3*2. Each of these starts with a factor of 6--1, 6, 2, or 3 respectively. More generally, n = d * (n/d). The n/d term itself can be factored into the remaining k-1 terms of the overall factorization of n into k terms, where each term is restricted to size <= m. This factorization of n/d is where the recursive calculation comes into play: simply add up the number of ways to factor n/d for each factor d of n to find the number of ways to factor n.

Equations of this form can be studied at least a little using something called a Dirichlet series generating function (http://mathworld.wolfram.com/DirichletSeriesGeneratingFunction.html). Without going into any real details, a generating function is a way to apply some results of other areas of math to arbitrary sequences of numbers by considering (often Taylor) polynomial series whose coefficients are exactly the sequence in question. For instance, the sequence (0!=1, 1!=1, 2!=2, 3!=6, 4!=24, ...) can be said to have generating function 0! + (1!)x/1! + (2!)x^2/2! + (3!)x^3/3! + ... = 1 + x + x^2 + x^3 + ... = 1/(1-x). Certain operations on the sequence above can thus be encoded in arithmetic using the function 1/(1-x).

Using the identity on the page I linked above and induction, one can show that the Dirichlet generating function A(m,k; s) of the sequence {a(n, m, k)} where n varies from 1 to infinity is (using LaTeX markup)

A(m,k; s) = \sum_{n=1}^\infty a(n, m, k) / n^s = [\zeta(s)|_m] \zeta(s)^{k-1}

where \zeta(s) is the Riemann zeta function and \zeta(s)|_m is the usual definition of the Riemann zeta function cut off after the first m terms [explicitly, \sum_{n=1}^m 1/n^s].

The original question asked for the number of ways to rearrange the product n! using n terms and restricting each term to size <= n. That is, the original question asked us to compute a(n!, n, n). We can say, then, that a(n!, n, n) = (A(n,n; s))_n!, that is, the coefficient of the n!'th term of the Dirichlet generating function for A(n,n; s). If one could find the coefficients of \zeta(s)^{k-1}, it turns out to require a simple n-term sum of certain of those coefficients to compute the coefficients of A(n,n; s), which would essentially solve the problem using n additions. [This is much faster than using the recursive solution above, i.e. a(n!, n, n) = \sum_{d | n} a(n!/d, n, n-1), which takes over a(n!, n, n) operations, which is larger than n! and therefore *much* larger than n.]