Coefficients in expansion of product(1-x^a, a=1n)?

[Sane]

I have an equation of the form $$(1-x)(1-x^2)(1-x^3)\cdot\cdot\cdot(1-x^n)$$. Or, in maple notation, product(1-x^a, a=1..n).

I've been trying to find a way to express this as an expanded polynomial in sigma notation so that I can extract coefficients (for an enumerative generating function). If the exponents were all the same then the binomial theorem could be applied, but unfortunately it is not that simple.

I have made little progress towards successfully expanding. I tried reforming it as a different counting problem and solving it indirectly, but still came to this same fundamental problem, just in a different form. However, in doing so, I think I've found a connection to a sum of sums; the answer may involve summing over i=0..n and j=i..n?

Has anyone seen this problem before? Any helpful links?

Thank you very much in advance,
Sane

(P.S. This is not homework. This is extracurricular fun to find a more efficient way to solve a computer science problem I stumbled across a while ago.)

 

[JSuarez]

Notice that in the expansion, the coefficient of $$x^k, 1\leq k\leq n$$, is the number of unordered integer partitions of $$k$$.

 

[Sane]

That observation is related to the problem I was trying to solve! I realize now that a subproblem of what I'm doing is counting the number of ways to partition a natural number into any number of unordered positive parts. This equation was a piece of the resulting generating function (the part I had trouble expanding), and thus that's what the coefficients should be counting.

You gave me the right words to look up. Found this page which looks like what I need:
http://en.wikipedia.org/wiki/Partition_(number_theory )

Thank you very much.

However, there are two problems:

(1) Maple seems to disagree with your post. Typing into Maple: sort(collect(expand(product(1-x^a,a=1..20)),x),x,ascending), does not appear to count partitions of $$k$$. Edit: According to Wikipedia, $$\frac{1}{1-x^a}$$ will. Is there a way I can still use this fact?

(2) There does not seem to be a usable expression for $$p(n)$$. But, if I feel confident that my expansion equals a summation over $$p(n)x^n$$, then I can at least use that to algebraically solve for a final answer, and then implement $$p(n)$$ into my program at the end.

 

[JSuarez]

You are right, I forgot to include "without repetition" in my earlier post. The product you refer gives the number of unrestricted partitions, in which the same numerical factor may apper several times; in your product, it cannot.

I am not sure, of the top of my head, if there is a relation between the two (like the classical one that states that the number of odd partitions equals the distinct factors ones), but I'll check it.

As far as I know, there isn't simple closed expression for that product (as there is not one to the p(n) numbers); it's one of the more classical problems in Combinatorics. Maybe Macmahon polynomials will help but, again, I'll have to check it; I haven't looked at these problems lately.

 

[Sane]

I just found an excellent resource.

http://functions.wolfram.com/IntegerFunctions/PartitionsQ/introductions/Partitions/ShowAll.html

It covers both of the functions you mentioned, $$p(n)$$ (unordered partitions of n with repetition) and $$q(n)$$ (unordered partitions of n without repetition) concisely, in the perfect amount of detail, as well as provides the formula that connects the two. And it turns out that I will need both.

There seems to be only one problem remaining since my product goes to $$n$$ rather than infinity. When $$k > n$$ (which it usually will be), the coefficient of $$x^k$$ is no longer $$p(n)$$ or $$q(n)$$. What do I do then? It seems like the answer will either be very simple, or next to unreasonable.

I have tried separating the infinite product to go from 1 .. n, and then n+1 .. infinity. Then I re-indexed the second product to make it look like what we already know. But that did not work. Any ideas? If it's a dead end, I can try to reformulate the problem yet again to have an infinite upper bound. Sigh, this is how I'm spending a Friday night.

Edit: The original equation I posted is apparently the Euler function (http://en.wikipedia.org/wiki/Euler's_function), which seems to have extractable coefficients by the Pentagonal Number Theorem (http://en.wikipedia.org/wiki/Pentagonal_number_theorem)... if the upper bound was infinity.

 

[Sane]

I stumbled across an interesting connection between partitioning $$n$$ into $$k$$ parts from any finite subset of the natural numbers and the partition functions $$p(n)$$ and $$q(n)$$.

To be precise, if $$n,k$$ are non-negative integers, $$S \subset \mathbb{N}$$, and $$S$$ has a maximum:

Let $$p_{S-k}(n)$$ be the number of ways to partition $$n$$ into $$k$$ unordered parts, where each part is restricted to the elements in set $$S$$, with repetition.

Let $$w = k + n(max(S)k+1)$$, $$P'(x) = 1 + x(max(S)k+1)$$, and $$Q'(x) = (k+1)P'(x)$$.

Let $$p_S(n)$$ be the number of ways to partition $$n$$ into unordered parts, where each part is restricted to the elements in set $$S$$ under the mapping $$P'$$, with repetition.

Let $$q_{S-even}(n)$$ be the number of ways to partition $$n$$ into an even number of unordered parts, where each part is restricted to the elements in set $$S$$ under the mapping $$Q'$$, without repetition.

Let $$q_{S-odd}(n)$$ be the number of ways to partition $$n$$ into an odd number of unordered parts, where each part is restricted to the elements in set $$S$$ under the mapping $$Q'$$, without repetition.

Then, $$p_{S-k}(n) = \sum_{i=0}^{w} p_S(i)(q_{S-even}(w-i) - q_{S-odd}(w-i))$$​

I have not found this result to be computationally useful for my initial problem. Nevertheless, I found it interesting. My proof is weak, but I have verified several cases computationally. Is this kind of result worth delving into to show similar connections and publishing? Or is it too trivial, obvious, or useless? Sorry if that question sounds naive.