Mixing
Partitions with at most k parts, each of at most l
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify:
$$ P^(leq l, 1,ldots,k)(z) = frac(1-z)ldots(1-z^k+l)((1-z)ldots(1-z^k))cdot((1-z)ldots(1-z^l)) $$
Where the left hand means the generating function of the class of partitions with at most k parts, each $ leq l $
Truth is I already tried by multiple ways, but with no success:
First, looking at the formula I guessed that:
$$ P^(leq l, 1,ldots,k) times P^(1,ldots,k +l) tilde = P^(<l) times P^(1,ldots,k) $$ but i couldn't understand why.
Secondly, using the same reasoning as to find that p(k,l,n) = p(l,k-1,n) + p(l-1,k,n -k), I thought that:
$$ P^(leq l, 1,ldots,k) tilde = P^(leq l, 1,ldots,k-1) +mathcal Z^k times P^(leq l - 1, 1,ldots,k) $$
but i could't solve the recurrence.
and so on...
As you can see, I'm quite confused... can someone give a tip that put me in my way?
thank you in advanced!
combinatorics integer-partitions
asked Apr 16 '17 at 19:18
Mauricio Irace
184
add a comment |Â
up vote
3
down vote
favorite
I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify:
$$ P^(leq l, 1,ldots,k)(z) = frac(1-z)ldots(1-z^k+l)((1-z)ldots(1-z^k))cdot((1-z)ldots(1-z^l)) $$
Where the left hand means the generating function of the class of partitions with at most k parts, each $ leq l $
Truth is I already tried by multiple ways, but with no success:
First, looking at the formula I guessed that:
$$ P^(leq l, 1,ldots,k) times P^(1,ldots,k +l) tilde = P^(<l) times P^(1,ldots,k) $$ but i couldn't understand why.
Secondly, using the same reasoning as to find that p(k,l,n) = p(l,k-1,n) + p(l-1,k,n -k), I thought that:
$$ P^(leq l, 1,ldots,k) tilde = P^(leq l, 1,ldots,k-1) +mathcal Z^k times P^(leq l - 1, 1,ldots,k) $$
but i could't solve the recurrence.
and so on...
As you can see, I'm quite confused... can someone give a tip that put me in my way?
thank you in advanced!
combinatorics integer-partitions
asked Apr 16 '17 at 19:18
Mauricio Irace
184
I would quite like to answer but fear it would be a pale imitation of this fabulous book. You want theorem $1.9$ on page $10$ but I would read pages $1$ to $10$ too if I were you as they lead nicely up to it.
– N. Shales
Apr 17 '17 at 0:42
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify:
$$ P^(leq l, 1,ldots,k)(z) = frac(1-z)ldots(1-z^k+l)((1-z)ldots(1-z^k))cdot((1-z)ldots(1-z^l)) $$
Where the left hand means the generating function of the class of partitions with at most k parts, each $ leq l $
Truth is I already tried by multiple ways, but with no success:
First, looking at the formula I guessed that:
$$ P^(leq l, 1,ldots,k) times P^(1,ldots,k +l) tilde = P^(<l) times P^(1,ldots,k) $$ but i couldn't understand why.
Secondly, using the same reasoning as to find that p(k,l,n) = p(l,k-1,n) + p(l-1,k,n -k), I thought that:
$$ P^(leq l, 1,ldots,k) tilde = P^(leq l, 1,ldots,k-1) +mathcal Z^k times P^(leq l - 1, 1,ldots,k) $$
but i could't solve the recurrence.
and so on...
As you can see, I'm quite confused... can someone give a tip that put me in my way?
thank you in advanced!
combinatorics integer-partitions
asked Apr 16 '17 at 19:18
Mauricio Irace
184
I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify:
$$ P^(leq l, 1,ldots,k)(z) = frac(1-z)ldots(1-z^k+l)((1-z)ldots(1-z^k))cdot((1-z)ldots(1-z^l)) $$
Where the left hand means the generating function of the class of partitions with at most k parts, each $ leq l $
Truth is I already tried by multiple ways, but with no success:
First, looking at the formula I guessed that:
$$ P^(leq l, 1,ldots,k) times P^(1,ldots,k +l) tilde = P^(<l) times P^(1,ldots,k) $$ but i couldn't understand why.
Secondly, using the same reasoning as to find that p(k,l,n) = p(l,k-1,n) + p(l-1,k,n -k), I thought that:
$$ P^(leq l, 1,ldots,k) tilde = P^(leq l, 1,ldots,k-1) +mathcal Z^k times P^(leq l - 1, 1,ldots,k) $$
but i could't solve the recurrence.
and so on...
As you can see, I'm quite confused... can someone give a tip that put me in my way?
thank you in advanced!
combinatorics integer-partitions
asked Apr 16 '17 at 19:18
Mauricio Irace
184
edited Apr 16 '17 at 20:11
asked Apr 16 '17 at 19:18
Mauricio Irace
184
asked Apr 16 '17 at 19:18
Mauricio Irace
184
asked Apr 16 '17 at 19:18
Mauricio Irace
184
184
I would quite like to answer but fear it would be a pale imitation of this fabulous book. You want theorem $1.9$ on page $10$ but I would read pages $1$ to $10$ too if I were you as they lead nicely up to it.
– N. Shales
Apr 17 '17 at 0:42
add a comment |Â
I would quite like to answer but fear it would be a pale imitation of this fabulous book. You want theorem $1.9$ on page $10$ but I would read pages $1$ to $10$ too if I were you as they lead nicely up to it.
– N. Shales
Apr 17 '17 at 0:42
I would quite like to answer but fear it would be a pale imitation of this fabulous book. You want theorem $1.9$ on page $10$ but I would read pages $1$ to $10$ too if I were you as they lead nicely up to it.
– N. Shales
Apr 17 '17 at 0:42
I would quite like to answer but fear it would be a pale imitation of this fabulous book. You want theorem $1.9$ on page $10$ but I would read pages $1$ to $10$ too if I were you as they lead nicely up to it.
– N. Shales
Apr 17 '17 at 0:42
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Let $p(l,k,n)$ denote the number of partitions of $n$ into at most $k$ parts each $leq l$. Observe that
beginalign*
p(l,k,n)&=0qquadqquadtextif n>kl\
p(l,k,kl)&=1
endalign*
Therefore the generating function
beginalign*
P^(leq l, 1,ldots,k)(z)=sum_ngeq 0p(l,k,n)z^ntag1
endalign*
is a polynomial in $z$ of degree $kl$.
Introducing the short-hand notation $(z)_p=(1-z)(1-z^2)cdots (1-z^p)$, we want to show for $k,lgeq 0$
beginalign*
P^(leq l, 1,ldots,k)(z)=frac(z)_l+k(z)_l(z)_ktag2
endalign*
Recurrence relation for $p(l,k,n)$:
We observe $$p(l,k,n)-p(l,k-1,n)$$
enumerates the number of partitions of $n$ into exactly $k$ parts, each $leq l$. We transform each of these partitions by deleting every $1$ that is a part, and subtracting $1$ from each part larger than $1$. The resulting partitions of $n-k$ have at most $k$ parts and each part is $leq l-1$.
Since this transformation is reversible, it establishes a bjiection between the partitions enumerated by $p(l,k,n)-p(l,k-1,n)$ and those enumerated by $p(l-1,k,n-k)$. Therefore
beginalign*
p(l,k,n)-p(l,k-1,n)=p(l-1,k,n-k)tag3
endalign*
Thus (3) corresponds with respect to the generating function in (1) to
beginalign*
P^(leq l, 1,ldots,k)(z)-P^(leq l, 1,ldots,k-1)(z)=z^kP^(leq l-1, 1,ldots,k)(z)tag4
endalign*
We have the boundary conditions
beginalign*
p(l,0,n)=p(0,k,n)=
begincases
1&qquad text if k=l=n=0\
0&qquad text otherwise
endcases
endalign*
since the empty partition of $0$ is the only partition in which no part is positive and is also the only partition in which the number of parts is nonpositive.
This corresponds with respect to (1) to
beginalign*
P^(leq l, 0)(z)=P^(0, 1,ldots,k)(z)=1
endalign*
We want to show that the right hand side of (2) fulfils the same recurrence relation as (4). We introduce the short-hand notation $Q^(l,k)(z)$ and define
beginalign*
Q^(l,k)(z):=frac(z)_l+k(z)_l(z)_k
endalign*
Recurrence relation for $Q^(l,k)(z)$:
We obtain
beginalign*
Q^(l,k)(z)-Q^(l,k-1)(z)&=frac(z)_l+k(z)_l(z)_k-frac(z)_l+k-1(z)_l(z)_k-1\
&=frac(z)_l+k-1(z)_l(z)_kleft[left(1-z^l+kright)-left(1-z^kright)right]\
&=frac(z)_l+k-1(z)_l(z)_kz^kleft(1-z^lright)\
&=z^kfrac(z)_l+k-1(z)_l-1(z)_k\
&=z^kQ^(l-1,k)(z)
endalign*
We also have
beginalign*
Q^(l,0)(z)=Q^(0,k)(z)=1
endalign*
Conclusion: Since $Q^(l,k)(z)$ and $P^(leq l, 1,ldots,k)(z)$ satisfy the same initial conditions and the same defining recurrence they are identical and the claim follows.
Note: This answer is more or less verbatim Theorem 3.1 of The Theory of Partitions by G.E. Andrews.
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
add a comment |Â
up vote
0
down vote
These are the partitions whose Ferrers diagrams fit into a $k$-by-$l$
rectangle. Their generating functions are the
Gaussian binomial coefficients or "$q$-binomial coefficients"
as given by your formula.
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Let $p(l,k,n)$ denote the number of partitions of $n$ into at most $k$ parts each $leq l$. Observe that
beginalign*
p(l,k,n)&=0qquadqquadtextif n>kl\
p(l,k,kl)&=1
endalign*
Therefore the generating function
beginalign*
P^(leq l, 1,ldots,k)(z)=sum_ngeq 0p(l,k,n)z^ntag1
endalign*
is a polynomial in $z$ of degree $kl$.
Introducing the short-hand notation $(z)_p=(1-z)(1-z^2)cdots (1-z^p)$, we want to show for $k,lgeq 0$
beginalign*
P^(leq l, 1,ldots,k)(z)=frac(z)_l+k(z)_l(z)_ktag2
endalign*
Recurrence relation for $p(l,k,n)$:
We observe $$p(l,k,n)-p(l,k-1,n)$$
enumerates the number of partitions of $n$ into exactly $k$ parts, each $leq l$. We transform each of these partitions by deleting every $1$ that is a part, and subtracting $1$ from each part larger than $1$. The resulting partitions of $n-k$ have at most $k$ parts and each part is $leq l-1$.
Since this transformation is reversible, it establishes a bjiection between the partitions enumerated by $p(l,k,n)-p(l,k-1,n)$ and those enumerated by $p(l-1,k,n-k)$. Therefore
beginalign*
p(l,k,n)-p(l,k-1,n)=p(l-1,k,n-k)tag3
endalign*
Thus (3) corresponds with respect to the generating function in (1) to
beginalign*
P^(leq l, 1,ldots,k)(z)-P^(leq l, 1,ldots,k-1)(z)=z^kP^(leq l-1, 1,ldots,k)(z)tag4
endalign*
We have the boundary conditions
beginalign*
p(l,0,n)=p(0,k,n)=
begincases
1&qquad text if k=l=n=0\
0&qquad text otherwise
endcases
endalign*
since the empty partition of $0$ is the only partition in which no part is positive and is also the only partition in which the number of parts is nonpositive.
This corresponds with respect to (1) to
beginalign*
P^(leq l, 0)(z)=P^(0, 1,ldots,k)(z)=1
endalign*
We want to show that the right hand side of (2) fulfils the same recurrence relation as (4). We introduce the short-hand notation $Q^(l,k)(z)$ and define
beginalign*
Q^(l,k)(z):=frac(z)_l+k(z)_l(z)_k
endalign*
Recurrence relation for $Q^(l,k)(z)$:
We obtain
beginalign*
Q^(l,k)(z)-Q^(l,k-1)(z)&=frac(z)_l+k(z)_l(z)_k-frac(z)_l+k-1(z)_l(z)_k-1\
&=frac(z)_l+k-1(z)_l(z)_kleft[left(1-z^l+kright)-left(1-z^kright)right]\
&=frac(z)_l+k-1(z)_l(z)_kz^kleft(1-z^lright)\
&=z^kfrac(z)_l+k-1(z)_l-1(z)_k\
&=z^kQ^(l-1,k)(z)
endalign*
We also have
beginalign*
Q^(l,0)(z)=Q^(0,k)(z)=1
endalign*
Conclusion: Since $Q^(l,k)(z)$ and $P^(leq l, 1,ldots,k)(z)$ satisfy the same initial conditions and the same defining recurrence they are identical and the claim follows.
Note: This answer is more or less verbatim Theorem 3.1 of The Theory of Partitions by G.E. Andrews.
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
add a comment |Â
up vote
2
down vote
accepted
Let $p(l,k,n)$ denote the number of partitions of $n$ into at most $k$ parts each $leq l$. Observe that
beginalign*
p(l,k,n)&=0qquadqquadtextif n>kl\
p(l,k,kl)&=1
endalign*
Therefore the generating function
beginalign*
P^(leq l, 1,ldots,k)(z)=sum_ngeq 0p(l,k,n)z^ntag1
endalign*
is a polynomial in $z$ of degree $kl$.
Introducing the short-hand notation $(z)_p=(1-z)(1-z^2)cdots (1-z^p)$, we want to show for $k,lgeq 0$
beginalign*
P^(leq l, 1,ldots,k)(z)=frac(z)_l+k(z)_l(z)_ktag2
endalign*
Recurrence relation for $p(l,k,n)$:
We observe $$p(l,k,n)-p(l,k-1,n)$$
enumerates the number of partitions of $n$ into exactly $k$ parts, each $leq l$. We transform each of these partitions by deleting every $1$ that is a part, and subtracting $1$ from each part larger than $1$. The resulting partitions of $n-k$ have at most $k$ parts and each part is $leq l-1$.
Since this transformation is reversible, it establishes a bjiection between the partitions enumerated by $p(l,k,n)-p(l,k-1,n)$ and those enumerated by $p(l-1,k,n-k)$. Therefore
beginalign*
p(l,k,n)-p(l,k-1,n)=p(l-1,k,n-k)tag3
endalign*
Thus (3) corresponds with respect to the generating function in (1) to
beginalign*
P^(leq l, 1,ldots,k)(z)-P^(leq l, 1,ldots,k-1)(z)=z^kP^(leq l-1, 1,ldots,k)(z)tag4
endalign*
We have the boundary conditions
beginalign*
p(l,0,n)=p(0,k,n)=
begincases
1&qquad text if k=l=n=0\
0&qquad text otherwise
endcases
endalign*
since the empty partition of $0$ is the only partition in which no part is positive and is also the only partition in which the number of parts is nonpositive.
This corresponds with respect to (1) to
beginalign*
P^(leq l, 0)(z)=P^(0, 1,ldots,k)(z)=1
endalign*
We want to show that the right hand side of (2) fulfils the same recurrence relation as (4). We introduce the short-hand notation $Q^(l,k)(z)$ and define
beginalign*
Q^(l,k)(z):=frac(z)_l+k(z)_l(z)_k
endalign*
Recurrence relation for $Q^(l,k)(z)$:
We obtain
beginalign*
Q^(l,k)(z)-Q^(l,k-1)(z)&=frac(z)_l+k(z)_l(z)_k-frac(z)_l+k-1(z)_l(z)_k-1\
&=frac(z)_l+k-1(z)_l(z)_kleft[left(1-z^l+kright)-left(1-z^kright)right]\
&=frac(z)_l+k-1(z)_l(z)_kz^kleft(1-z^lright)\
&=z^kfrac(z)_l+k-1(z)_l-1(z)_k\
&=z^kQ^(l-1,k)(z)
endalign*
We also have
beginalign*
Q^(l,0)(z)=Q^(0,k)(z)=1
endalign*
Conclusion: Since $Q^(l,k)(z)$ and $P^(leq l, 1,ldots,k)(z)$ satisfy the same initial conditions and the same defining recurrence they are identical and the claim follows.
Note: This answer is more or less verbatim Theorem 3.1 of The Theory of Partitions by G.E. Andrews.
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Let $p(l,k,n)$ denote the number of partitions of $n$ into at most $k$ parts each $leq l$. Observe that
beginalign*
p(l,k,n)&=0qquadqquadtextif n>kl\
p(l,k,kl)&=1
endalign*
Therefore the generating function
beginalign*
P^(leq l, 1,ldots,k)(z)=sum_ngeq 0p(l,k,n)z^ntag1
endalign*
is a polynomial in $z$ of degree $kl$.
Introducing the short-hand notation $(z)_p=(1-z)(1-z^2)cdots (1-z^p)$, we want to show for $k,lgeq 0$
beginalign*
P^(leq l, 1,ldots,k)(z)=frac(z)_l+k(z)_l(z)_ktag2
endalign*
Recurrence relation for $p(l,k,n)$:
We observe $$p(l,k,n)-p(l,k-1,n)$$
enumerates the number of partitions of $n$ into exactly $k$ parts, each $leq l$. We transform each of these partitions by deleting every $1$ that is a part, and subtracting $1$ from each part larger than $1$. The resulting partitions of $n-k$ have at most $k$ parts and each part is $leq l-1$.
Since this transformation is reversible, it establishes a bjiection between the partitions enumerated by $p(l,k,n)-p(l,k-1,n)$ and those enumerated by $p(l-1,k,n-k)$. Therefore
beginalign*
p(l,k,n)-p(l,k-1,n)=p(l-1,k,n-k)tag3
endalign*
Thus (3) corresponds with respect to the generating function in (1) to
beginalign*
P^(leq l, 1,ldots,k)(z)-P^(leq l, 1,ldots,k-1)(z)=z^kP^(leq l-1, 1,ldots,k)(z)tag4
endalign*
We have the boundary conditions
beginalign*
p(l,0,n)=p(0,k,n)=
begincases
1&qquad text if k=l=n=0\
0&qquad text otherwise
endcases
endalign*
since the empty partition of $0$ is the only partition in which no part is positive and is also the only partition in which the number of parts is nonpositive.
This corresponds with respect to (1) to
beginalign*
P^(leq l, 0)(z)=P^(0, 1,ldots,k)(z)=1
endalign*
We want to show that the right hand side of (2) fulfils the same recurrence relation as (4). We introduce the short-hand notation $Q^(l,k)(z)$ and define
beginalign*
Q^(l,k)(z):=frac(z)_l+k(z)_l(z)_k
endalign*
Recurrence relation for $Q^(l,k)(z)$:
We obtain
beginalign*
Q^(l,k)(z)-Q^(l,k-1)(z)&=frac(z)_l+k(z)_l(z)_k-frac(z)_l+k-1(z)_l(z)_k-1\
&=frac(z)_l+k-1(z)_l(z)_kleft[left(1-z^l+kright)-left(1-z^kright)right]\
&=frac(z)_l+k-1(z)_l(z)_kz^kleft(1-z^lright)\
&=z^kfrac(z)_l+k-1(z)_l-1(z)_k\
&=z^kQ^(l-1,k)(z)
endalign*
We also have
beginalign*
Q^(l,0)(z)=Q^(0,k)(z)=1
endalign*
Conclusion: Since $Q^(l,k)(z)$ and $P^(leq l, 1,ldots,k)(z)$ satisfy the same initial conditions and the same defining recurrence they are identical and the claim follows.
Note: This answer is more or less verbatim Theorem 3.1 of The Theory of Partitions by G.E. Andrews.
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
Let $p(l,k,n)$ denote the number of partitions of $n$ into at most $k$ parts each $leq l$. Observe that
beginalign*
p(l,k,n)&=0qquadqquadtextif n>kl\
p(l,k,kl)&=1
endalign*
Therefore the generating function
beginalign*
P^(leq l, 1,ldots,k)(z)=sum_ngeq 0p(l,k,n)z^ntag1
endalign*
is a polynomial in $z$ of degree $kl$.
Introducing the short-hand notation $(z)_p=(1-z)(1-z^2)cdots (1-z^p)$, we want to show for $k,lgeq 0$
beginalign*
P^(leq l, 1,ldots,k)(z)=frac(z)_l+k(z)_l(z)_ktag2
endalign*
Recurrence relation for $p(l,k,n)$:
We observe $$p(l,k,n)-p(l,k-1,n)$$
enumerates the number of partitions of $n$ into exactly $k$ parts, each $leq l$. We transform each of these partitions by deleting every $1$ that is a part, and subtracting $1$ from each part larger than $1$. The resulting partitions of $n-k$ have at most $k$ parts and each part is $leq l-1$.
Since this transformation is reversible, it establishes a bjiection between the partitions enumerated by $p(l,k,n)-p(l,k-1,n)$ and those enumerated by $p(l-1,k,n-k)$. Therefore
beginalign*
p(l,k,n)-p(l,k-1,n)=p(l-1,k,n-k)tag3
endalign*
Thus (3) corresponds with respect to the generating function in (1) to
beginalign*
P^(leq l, 1,ldots,k)(z)-P^(leq l, 1,ldots,k-1)(z)=z^kP^(leq l-1, 1,ldots,k)(z)tag4
endalign*
We have the boundary conditions
beginalign*
p(l,0,n)=p(0,k,n)=
begincases
1&qquad text if k=l=n=0\
0&qquad text otherwise
endcases
endalign*
since the empty partition of $0$ is the only partition in which no part is positive and is also the only partition in which the number of parts is nonpositive.
This corresponds with respect to (1) to
beginalign*
P^(leq l, 0)(z)=P^(0, 1,ldots,k)(z)=1
endalign*
We want to show that the right hand side of (2) fulfils the same recurrence relation as (4). We introduce the short-hand notation $Q^(l,k)(z)$ and define
beginalign*
Q^(l,k)(z):=frac(z)_l+k(z)_l(z)_k
endalign*
Recurrence relation for $Q^(l,k)(z)$:
We obtain
beginalign*
Q^(l,k)(z)-Q^(l,k-1)(z)&=frac(z)_l+k(z)_l(z)_k-frac(z)_l+k-1(z)_l(z)_k-1\
&=frac(z)_l+k-1(z)_l(z)_kleft[left(1-z^l+kright)-left(1-z^kright)right]\
&=frac(z)_l+k-1(z)_l(z)_kz^kleft(1-z^lright)\
&=z^kfrac(z)_l+k-1(z)_l-1(z)_k\
&=z^kQ^(l-1,k)(z)
endalign*
We also have
beginalign*
Q^(l,0)(z)=Q^(0,k)(z)=1
endalign*
Conclusion: Since $Q^(l,k)(z)$ and $P^(leq l, 1,ldots,k)(z)$ satisfy the same initial conditions and the same defining recurrence they are identical and the claim follows.
Note: This answer is more or less verbatim Theorem 3.1 of The Theory of Partitions by G.E. Andrews.
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
answered Apr 17 '17 at 20:38
Markus Scheuer
55.9k450135
55.9k450135
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
add a comment |Â
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
Verified one time,will check some more. (+1), good work. I hope it gets more votes, it certainly deserves them.
– Marko Riedel
Apr 17 '17 at 21:59
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
@MarkoRiedel: Thanks a lot, Marko. OPs question was a good opportunity to repeat this theorem.
– Markus Scheuer
Apr 17 '17 at 22:05
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
Excellent, thank you very much
– Mauricio Irace
Apr 18 '17 at 12:26
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
@MauricioIrace: You're welcome! :-)
– Markus Scheuer
Apr 18 '17 at 12:28
add a comment |Â
up vote
0
down vote
These are the partitions whose Ferrers diagrams fit into a $k$-by-$l$
rectangle. Their generating functions are the
Gaussian binomial coefficients or "$q$-binomial coefficients"
as given by your formula.
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
add a comment |Â
up vote
0
down vote
These are the partitions whose Ferrers diagrams fit into a $k$-by-$l$
rectangle. Their generating functions are the
Gaussian binomial coefficients or "$q$-binomial coefficients"
as given by your formula.
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
add a comment |Â
up vote
0
down vote
up vote
0
down vote
These are the partitions whose Ferrers diagrams fit into a $k$-by-$l$
rectangle. Their generating functions are the
Gaussian binomial coefficients or "$q$-binomial coefficients"
as given by your formula.
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
These are the partitions whose Ferrers diagrams fit into a $k$-by-$l$
rectangle. Their generating functions are the
Gaussian binomial coefficients or "$q$-binomial coefficients"
as given by your formula.
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
answered Apr 16 '17 at 21:40
Lord Shark the Unknown
84.9k950111
84.9k950111
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
add a comment |Â
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
Thank you! my question is more related on "how to understand the formula" than in the formula itself.
– Mauricio Irace
Apr 16 '17 at 22:05
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2237261%2fpartitions-with-at-most-k-parts-each-of-at-most-l%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I would quite like to answer but fear it would be a pale imitation of this fabulous book. You want theorem $1.9$ on page $10$ but I would read pages $1$ to $10$ too if I were you as they lead nicely up to it.
– N. Shales
Apr 17 '17 at 0:42