2
$\begingroup$

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.

  • 0
    Sushruth: Please register your account so that you can then comment on your own question. Answer boxes are meant for actual answer to the question; it is ok to occasionally post comments there, but do not do so frequently.2012-01-31

1 Answers 1

2

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