Um, well, I think the title pretty much says it all.

Nevertheless, allow me to explain.

I am aware of a certain partition function $Q(n, k)$ that is supposed to remove duplication of parts and $k$ is the number of terms it contains.

I have a hunch that like $P(n, k)$ where $k$ limits the number of parts is equivalent to $k$ being the largest part, the same would apply to $Q(n, k)$. But then, I think probably not.

I'd like to know if any generating functions exist for what I have described (both removal of duplicate/repeated parts and largest part $k$). And one last question if you can't (or can, whatever) answer that question, is $Q(n, k)$ always lesser than n? (I think so...)

Well, thanks for stopping to read this and to anyone who bothered to help! PS Note that $q(n, k)$ and $Q(n, k)$ are different! Head over to Wolfram|Alpha for more detail.

Edit 1

I'm sorry, but I'm just a high school student (Class IX) and don't know what that is supposed to mean. Hope you can help me with it, thanks again.

Question 1: Where did this new variable $x$ come in from?

Question 2: One more thing, does this generating function produce a result always lesser than $m$?

The last question: If I'm right, I can interpret the core of your statement (excl. the coefficient part) as the product $(1 + x^k)$ as $k$ varies from $1$ to $k$... where's $m$ in all this? And for what am I going to find the coefficient of $x^m$, given there is no $x^m$ in the equation? (I'm pretty sure that ain't an algebraic coefficient)

Edit 2

Heck Mr. Garry, I just forgot that! Well, if $x$ is a placeholder of sorts, but what is it actually doing there if it's not supposedto be there? That said, is it a reference to any kind of big pi notation or such?

Edit 3

Fine, I've understood it now. I'm telling this here as writing it as an answer seems to look like me answering myself. Anyway, now that I think about it, is it further possible to restrict $Q(n, k)$ so as to include only, say, $t$ parts, such that it becomes a function where n is partitioned into $t$ parts - no less, no more - and the largest part is $k$? Is that possible?

Oh my. I seriously ask a lot of questions.

  • 1
    $\begingroup$ The number of partitions of $m$ such that each number appears at most once and no numbers bigger than $k$ appear is given by the coefficient of $x^m$ in $(1+x)(1+x^2)\cdots (1+x^k)$. $\endgroup$ – Bill Cook Jan 30 '12 at 14:17
  • 1
    $\begingroup$ @Sushruth: please don't post clarifications and further questions as answers. They should be edited into the original post. It will also help if you register your account, this way the system can keep track of your log-on information between different IPs and computers, so you'll be able to access and modify this question. $\endgroup$ – Willie Wong Jan 30 '12 at 15:47
  • $\begingroup$ @BillCook: OP posted some further remarks which I edited into the question itself. This is just to ping you since those seems to be addressing your comment above. $\endgroup$ – Willie Wong Jan 30 '12 at 15:48
  • $\begingroup$ @WillieWong I hope this is permitted, thanks for happening to correct my question. $\endgroup$ – Mach9 Jan 30 '12 at 16:57
  • 2
    $\begingroup$ You have been asked not to "post clarifications and further questions as answers." SO DON'T DO IT! Anyway, $x$ is a place-holder. "values of $x$" have nothing to do with this formula. $\endgroup$ – Gerry Myerson Jan 31 '12 at 11:55

A slightly expanded version of my comment...

The number of partitions of $m$ such that each number appears at most once and no numbers bigger than $k$ appear is given by the coefficient of $x^m$ in $(1+x)(1+x^2)\cdots (1+x^k)$.

So for example, if we consider $k=5$ (no numbers bigger than $5$), then the generating function is: $$(1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)=$$ $$1+x+x^2+2x^3+2x^4+3x^5+3x^6+3x^7+3x^8+3x^9$$ $$+3x^{10}+2x^{11}+2x^{12}+x^{13}+x^{14}+x^{15}$$ Consider the coefficient of $x^8$ is 3. There are 3 ways of writing 8 as a sum of numbers between 1 and 5 such that no number is repeated. These are: $1+2+5$, $1+3+4$, and $3+5$. These partitions correspond to $x\cdot x^2 \cdot x^5$, $x\cdot x^3 \cdot x^4$, and $x^3\cdot x^5$.

In general, if $$ \sum_{k=1}^\infty \prod_{j=1}^k (1+x^j)y^k = \sum_{k=1}^\infty \sum_{m=1}^\infty Q(m,k)x^m y^k$$ then $Q(m,k)$ is the number of partitions of $m$ without repeating parts and involving numbers no bigger than $k$.

Note: Keep in mind, we don't really care about the convergence of the infinite products/sums here. Also, we don't want to think about these as multivariate functions. Just think of $x$ and $y$ as convenient placeholders which make the calculations work (turning multiplication of terms into addition of exponents).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.