0

I’m looking at partition numbers. OEIS A008284 says that the number of partitions of $n$ in which the greatest part is $k$, $1 \le k \le n$, is equal to the number of partitions of $n$ into $k$ positive parts ($1 \le k \le n$). (This also easily follows from Ferrers diagrams.)

However, I want to find out how many partitions of $n$ are if the greatest part is at most $k_1$ and the number of positive parts is $k_2$, where possibly $k_1 \ne k_2$. For instance, for $n = 8, k_1 = 4, k_2 = 3$, we have 431, 422, and 332. Is there anything known about this?

Actually … I’m not only interested in this number, but in the number of permutations of these partitions. Since 431 has six permutations and both 422 and 332 have three, the number I’m interested in in the above example would be 12.

I couldn’t find anything at all even about permutations in combination with permutation numbers, let alone my additional restrictions above. Maybe someone who’s a bit more into number theory can help?

Sacha
  • 377
  • 1
  • 8
  • You are asking for the number of solutions of $x_1+x_2+\cdots+x_{k_2}=n$, subject to $x_i\le k_1$, which is a standard intro discrte math type question that has been asked and answered here many times over. Well, not quite, because that gives you the number where no variable exceeds $k_1$, so you have to subtract away the number where no variable exceeds $k_1-1$ to get the number where at least one variable equals $k_1$. But, wait: you're counting 332 as having greatest part 4, so you don't have to do the subtraction. – Gerry Myerson Jul 03 '14 at 09:39
  • Sorry for that. I rephrased the question. If this has been done many times, can you please give me at least one link? I didn’t find anything helpful. – Sacha Jul 03 '14 at 10:56
  • 1
    http://math.stackexchange.com/questions/739198/can-we-solve-this-using-stars-and-bars – Gerry Myerson Jul 03 '14 at 12:21
  • So does that answer your question? – Gerry Myerson Jul 04 '14 at 13:07
  • Um yeah … kind of. It seems there is no explicit form, only these weird trinomial, quadrinomial etc. coefficients. But thanks a lot for the link! – Sacha Jul 04 '14 at 14:56
  • I've written an answer now. Anything to say? – Gerry Myerson Jul 07 '14 at 07:36

1 Answers1

1

The number of partitions of $n$ into $k_2$ positive parts, no part exceeding $k_1$, is the coefficient of $x^n$ in $(x+x^2+x^3+\cdots+x^r)^s$, where I have written $r$ for $k_1$, and $s$ for $k_2$. This is the coefficient of $x^t$ in $(1+x+x^2+\cdots+x^{r-1})^s$, where I have written $t$ for $n-s$. Now $$(1+x+x^2+\cdots+x^{r-1})^s=(1-x^r)^s(1-x)^{-s}=\sum_0^s(-1)^p{s\choose p}x^{rp}\sum_0^{\infty}{s-1+q\choose s-1}x^q$$ so the answer is the sum, over all pairs $p,q$ such that $rp+q=t$, of $(-1)^p{s\choose p}{s-1+q\choose s-1}$.

Try this out on your original example. $n=8$, $k_1=r=4$, $k_2=s=3$, $t=n-s=5$; the solutions of $4p+q=5$ are $p=0$, $q=5$ and $p=1$, $q=1$, so you get $$(-1)^0{3\choose0}{7\choose2}+(-1)^1{3\choose1}{3\choose2}=(1)(21)-(3)(3)=21-9=12$$

Note there are no trinomial, quadrinomial, whatever coefficients, just binomials.

Gerry Myerson
  • 179,216
  • How did you get the polynomial decomposition? Because my original problem (http://math.stackexchange.com/questions/694015/what-are-the-coefficients-of-these-almost-boolean-polynomials) was to get the coefficients of polynomials. Maybe this can also be done with some decomposition. – Sacha Jul 08 '14 at 11:19
  • When you use the distributive law to multiply out $(x+\cdots+x^r)^s$, you get a sum of terms of the form $x^{a_1}x^{a_2}\cdots x^{a_s}$ with $1\le a_i\le r$ for each $i$. So the coefficient of $x^n$ is the number of solutions of $$a_1+\cdots+a_s=n,\quad1\le a_i\le r,\quad1\le i\le s$$ – Gerry Myerson Jul 08 '14 at 12:57