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.

  • 1
    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)$.2012-01-30
  • 1
    @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.2012-01-30
  • 0
    @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.2012-01-30
  • 0
    @WillieWong I hope this is permitted, thanks for happening to correct my question.2012-01-30
  • 0
    The idea is you multiply out the product Bill Cook gave, and that gives you a polynomial. Then, for any particular value of $m$ that interests you, you look at that polynomial until you find the term that has $x^m$ in it: the coefficient of that term is the number you want.2012-01-31
  • 2
    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.2012-01-31
  • 0
    @GerryMyerson Fine, but what just is $x$ supposed to mean? Can it just be any positive integer I choose? Like for example, $x=1$, that would return (when solved) $2^k$... is that what it is? I don't think so, as this way, the result turns out different for different values of $x$... the question just boils down to - what is $x$?2012-01-31
  • 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).