hook-length formula: “Fibonaccized”hook-length formula: “Fibonaccized”: Part IINekrasov-Okounkov hook length formulaInequality for hook numbers in Young diagramspartitions into odd parts vs hooks and symplectic contentsan identity for a sum over partitionsLemmas involving two partitions of integershooks and contents: Part IA discrete operator begets even/odd polynomialsPartitions, $q$-polynomials and generating functionsPartitions and $q$-integersA link between hooks, contents and parts of a partition
hook-length formula: “Fibonaccized”
hook-length formula: “Fibonaccized”: Part IINekrasov-Okounkov hook length formulaInequality for hook numbers in Young diagramspartitions into odd parts vs hooks and symplectic contentsan identity for a sum over partitionsLemmas involving two partitions of integershooks and contents: Part IA discrete operator begets even/odd polynomialsPartitions, $q$-polynomials and generating functionsPartitions and $q$-integersA link between hooks, contents and parts of a partition
$begingroup$
Consider the Young diagram of a partition $lambda = (lambda_1,ldots,lambda_k)$. For a square $(i,j) in lambda$, define the hook numbers $h_(i,j) = lambda_i + lambda_j' -i - j +1$ where $lambda'$ is the conjugate of $lambda$.
The hook-length formula shows, in particular, that if $lambdavdash n$ then
$$text$n!prod_square,in,lambdafrac1h_square$ qquad textis an integer.$$
Recall the Fibonacci numbers $F(0)=0, , F(1)=1$ with $F(n)=F(n-1)+F(n-2)$. Define $[0]!_F=1$ and $[n]!_F=F(1)cdot F(2)cdots F(n)$ for $ngeq1$.
QUESTION. Is it true that
$$text$[n]!_Fprod_square,in,lambdafrac1F(h_square)$ qquad textis an integer?$$
nt.number-theory co.combinatorics partitions algebraic-combinatorics
$endgroup$
|
show 6 more comments
$begingroup$
Consider the Young diagram of a partition $lambda = (lambda_1,ldots,lambda_k)$. For a square $(i,j) in lambda$, define the hook numbers $h_(i,j) = lambda_i + lambda_j' -i - j +1$ where $lambda'$ is the conjugate of $lambda$.
The hook-length formula shows, in particular, that if $lambdavdash n$ then
$$text$n!prod_square,in,lambdafrac1h_square$ qquad textis an integer.$$
Recall the Fibonacci numbers $F(0)=0, , F(1)=1$ with $F(n)=F(n-1)+F(n-2)$. Define $[0]!_F=1$ and $[n]!_F=F(1)cdot F(2)cdots F(n)$ for $ngeq1$.
QUESTION. Is it true that
$$text$[n]!_Fprod_square,in,lambdafrac1F(h_square)$ qquad textis an integer?$$
nt.number-theory co.combinatorics partitions algebraic-combinatorics
$endgroup$
5
$begingroup$
More generally, this interesting question can be asked of any strong divisibility sequence instead of the Fibonacci sequence. But let's perhaps not abuse the notation $Fleft(nright)!$ for something that's not the factorial of $Fleft(nright)$.
$endgroup$
– darij grinberg
2 days ago
1
$begingroup$
Maybe call it $F!(n)$ instead of $F(n)!$. How far has this been checked?
$endgroup$
– Noam D. Elkies
2 days ago
9
$begingroup$
Maybe this expression can be obtained by a clever substitution of the $q$-hook length formula?
$endgroup$
– Sam Hopkins
2 days ago
1
$begingroup$
@darijgrinberg what is a strong divisibility sequence? Product of any $k$ consecutive guys is divisibly by the product of first $k$ guys?
$endgroup$
– Fedor Petrov
yesterday
5
$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
yesterday
|
show 6 more comments
$begingroup$
Consider the Young diagram of a partition $lambda = (lambda_1,ldots,lambda_k)$. For a square $(i,j) in lambda$, define the hook numbers $h_(i,j) = lambda_i + lambda_j' -i - j +1$ where $lambda'$ is the conjugate of $lambda$.
The hook-length formula shows, in particular, that if $lambdavdash n$ then
$$text$n!prod_square,in,lambdafrac1h_square$ qquad textis an integer.$$
Recall the Fibonacci numbers $F(0)=0, , F(1)=1$ with $F(n)=F(n-1)+F(n-2)$. Define $[0]!_F=1$ and $[n]!_F=F(1)cdot F(2)cdots F(n)$ for $ngeq1$.
QUESTION. Is it true that
$$text$[n]!_Fprod_square,in,lambdafrac1F(h_square)$ qquad textis an integer?$$
nt.number-theory co.combinatorics partitions algebraic-combinatorics
$endgroup$
Consider the Young diagram of a partition $lambda = (lambda_1,ldots,lambda_k)$. For a square $(i,j) in lambda$, define the hook numbers $h_(i,j) = lambda_i + lambda_j' -i - j +1$ where $lambda'$ is the conjugate of $lambda$.
The hook-length formula shows, in particular, that if $lambdavdash n$ then
$$text$n!prod_square,in,lambdafrac1h_square$ qquad textis an integer.$$
Recall the Fibonacci numbers $F(0)=0, , F(1)=1$ with $F(n)=F(n-1)+F(n-2)$. Define $[0]!_F=1$ and $[n]!_F=F(1)cdot F(2)cdots F(n)$ for $ngeq1$.
QUESTION. Is it true that
$$text$[n]!_Fprod_square,in,lambdafrac1F(h_square)$ qquad textis an integer?$$
nt.number-theory co.combinatorics partitions algebraic-combinatorics
nt.number-theory co.combinatorics partitions algebraic-combinatorics
edited 2 days ago
T. Amdeberhan
asked 2 days ago
T. AmdeberhanT. Amdeberhan
18.1k229132
18.1k229132
5
$begingroup$
More generally, this interesting question can be asked of any strong divisibility sequence instead of the Fibonacci sequence. But let's perhaps not abuse the notation $Fleft(nright)!$ for something that's not the factorial of $Fleft(nright)$.
$endgroup$
– darij grinberg
2 days ago
1
$begingroup$
Maybe call it $F!(n)$ instead of $F(n)!$. How far has this been checked?
$endgroup$
– Noam D. Elkies
2 days ago
9
$begingroup$
Maybe this expression can be obtained by a clever substitution of the $q$-hook length formula?
$endgroup$
– Sam Hopkins
2 days ago
1
$begingroup$
@darijgrinberg what is a strong divisibility sequence? Product of any $k$ consecutive guys is divisibly by the product of first $k$ guys?
$endgroup$
– Fedor Petrov
yesterday
5
$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
yesterday
|
show 6 more comments
5
$begingroup$
More generally, this interesting question can be asked of any strong divisibility sequence instead of the Fibonacci sequence. But let's perhaps not abuse the notation $Fleft(nright)!$ for something that's not the factorial of $Fleft(nright)$.
$endgroup$
– darij grinberg
2 days ago
1
$begingroup$
Maybe call it $F!(n)$ instead of $F(n)!$. How far has this been checked?
$endgroup$
– Noam D. Elkies
2 days ago
9
$begingroup$
Maybe this expression can be obtained by a clever substitution of the $q$-hook length formula?
$endgroup$
– Sam Hopkins
2 days ago
1
$begingroup$
@darijgrinberg what is a strong divisibility sequence? Product of any $k$ consecutive guys is divisibly by the product of first $k$ guys?
$endgroup$
– Fedor Petrov
yesterday
5
$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
yesterday
5
5
$begingroup$
More generally, this interesting question can be asked of any strong divisibility sequence instead of the Fibonacci sequence. But let's perhaps not abuse the notation $Fleft(nright)!$ for something that's not the factorial of $Fleft(nright)$.
$endgroup$
– darij grinberg
2 days ago
$begingroup$
More generally, this interesting question can be asked of any strong divisibility sequence instead of the Fibonacci sequence. But let's perhaps not abuse the notation $Fleft(nright)!$ for something that's not the factorial of $Fleft(nright)$.
$endgroup$
– darij grinberg
2 days ago
1
1
$begingroup$
Maybe call it $F!(n)$ instead of $F(n)!$. How far has this been checked?
$endgroup$
– Noam D. Elkies
2 days ago
$begingroup$
Maybe call it $F!(n)$ instead of $F(n)!$. How far has this been checked?
$endgroup$
– Noam D. Elkies
2 days ago
9
9
$begingroup$
Maybe this expression can be obtained by a clever substitution of the $q$-hook length formula?
$endgroup$
– Sam Hopkins
2 days ago
$begingroup$
Maybe this expression can be obtained by a clever substitution of the $q$-hook length formula?
$endgroup$
– Sam Hopkins
2 days ago
1
1
$begingroup$
@darijgrinberg what is a strong divisibility sequence? Product of any $k$ consecutive guys is divisibly by the product of first $k$ guys?
$endgroup$
– Fedor Petrov
yesterday
$begingroup$
@darijgrinberg what is a strong divisibility sequence? Product of any $k$ consecutive guys is divisibly by the product of first $k$ guys?
$endgroup$
– Fedor Petrov
yesterday
5
5
$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
yesterday
$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
yesterday
|
show 6 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Sam is correct of course about $q$-hook formula. Below is a short self-contained proof not relying on such advanced combinatorics.
Denote $h_1>ldots>h_k$ the set of hook lengths of the first column of diagram $lambda$. Then the multiset of hooks is $cup_i=1^k 1,2,ldots,h_isetminus h_i-h_j:i<j$ and $n=sum_i h_i-frack(k-1)2$.
Recall that $F(m)=P_m(alpha,beta)=prod_dPhi_d(alpha,beta)=prod_d (Phi_d(alpha,beta))^eta_d(m)$, where
$alpha,beta=(1pm sqrt5)/2$;
$P_n(x,y)=x^n-1+x^n-2y+ldots+y^n-1$;
$Phi_d$ are homogeneous cyclotomic polynomials;
$eta_d(m)=chi_mathbbZ(m/d)$ (i.e., it equals to 1 if $d$ divides $m$, and to 0 otherwise).
Therefore it suffices to prove that for any fixed $d>1$ we have
$$
sum_m=1^n eta_d(m)+sum_i<jeta_d(h_i-h_j)-sum_i=1^ksum_j=1^h_ieta_d(j)geqslant 0.quad (ast)
$$
$(ast)$ rewrites as
$$
[n/d]+|i<j:h_iequiv h_j pmod d|-sum_i=1^k [h_i/d]geqslant 0.quad (bullet)
$$
LHS of $(bullet)$ does not change if we reduce all $h_i$'s modulo $d$ (and accordingly change $n=sum_i h_i-frack(k-1)2$, of course), so we may suppose that $0leqslant h_ileqslant d-1$ for all $i$. For $a=0,1,dots, d-1$ denote $t_a=|i:h_i=a|$. Then $(bullet)$ rewrites as
$$
left[frac-binomsum_i=0^d-1 t_i2+sum_i=0^d-1 it_idright]+
sum_i=0^d-1 binomt_i2geqslant 0. quad (star)
$$
It remains to observe that LHS of $(star)$ equals to
$$
left[frac1dsum_i<jbinomt_i-t_j2 right].
$$
$endgroup$
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
add a comment |
$begingroup$
This is a less elementary but maybe more conceptual proof, also giving some combinatorial meaning:
Use the formulas
$F(n) = fracvarphi^n -psi^nsqrt5$, $varphi =frac1+sqrt52, psi = frac1-sqrt52$. Let $q=fracpsivarphi = fracsqrt5-32$, so that
$F(n) = fracvarphi^nsqrt5 (1-q^n)$
Then the Fibonacci hook-length formula becomes:
DeclareMathOperatorlalambda
beginalign*
f^lambda_F:= frac[n]!_Fprod_uin lambdaF(h(u)) = frac varphi^ binomn+12 [n]!_q varphi^sum_u in lambda h(u) prod_u in lambda (1-q^h(u))
endalign*
So we have an ordinary $q$-analogue of the hook-length formula. Note that
$$sum_u in lambda h(u) = sum_i binomlambda_i2 + binomlambda'_j2 + |lambda| = b(lambda) +b(lambda') +n$$
Using the $q-$analogue hook-length formula via major index (EC2, Chapter 21) we have
beginalign*
f^lambda_F = varphi^ binomn2 -b(lambda)-b(lambda') q^-b(lambda) sum_Tin SYT(lambda) q^maj(T) = (-q)^frac12( -binomn2 +b(lambda') -b(lambda))sum_T q^maj(T)
endalign*
Now, it is clear from the q-HLF formula that $q^maj(T)$ is a symmetric polynomial, with lowest degree term $b(lambda)$ and maximal degree $b(lambda) + binomn+12 - n -b(lambda) -b(lambda') =binomn2 - b(lambda')$ so the median degree term is
$$M=frac12 left(b(lambda) +binomn2 - b(lambda')right)$$
which cancels with the factor of $q$ in $f^lambda_F$, so the resulting polynomial is of the form
beginalign*
f^lambda_F = (-1)^M sum_T: maj(T) leq M (q^M-maj(T) + q^maj(T)-M) \
= (-1)^M sum_T (-1)^M-maj(T)( varphi^2(M-maj(T)) + psi^2(M-maj(T)) =
sum_T (-1)^maj(T) L(2(M-maj(T)))
endalign*
where $L$ are the Lucas numbers.
**byproduct of collaborations with A. Morales and I. Pak.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f326860%2fhook-length-formula-fibonaccized%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Sam is correct of course about $q$-hook formula. Below is a short self-contained proof not relying on such advanced combinatorics.
Denote $h_1>ldots>h_k$ the set of hook lengths of the first column of diagram $lambda$. Then the multiset of hooks is $cup_i=1^k 1,2,ldots,h_isetminus h_i-h_j:i<j$ and $n=sum_i h_i-frack(k-1)2$.
Recall that $F(m)=P_m(alpha,beta)=prod_dPhi_d(alpha,beta)=prod_d (Phi_d(alpha,beta))^eta_d(m)$, where
$alpha,beta=(1pm sqrt5)/2$;
$P_n(x,y)=x^n-1+x^n-2y+ldots+y^n-1$;
$Phi_d$ are homogeneous cyclotomic polynomials;
$eta_d(m)=chi_mathbbZ(m/d)$ (i.e., it equals to 1 if $d$ divides $m$, and to 0 otherwise).
Therefore it suffices to prove that for any fixed $d>1$ we have
$$
sum_m=1^n eta_d(m)+sum_i<jeta_d(h_i-h_j)-sum_i=1^ksum_j=1^h_ieta_d(j)geqslant 0.quad (ast)
$$
$(ast)$ rewrites as
$$
[n/d]+|i<j:h_iequiv h_j pmod d|-sum_i=1^k [h_i/d]geqslant 0.quad (bullet)
$$
LHS of $(bullet)$ does not change if we reduce all $h_i$'s modulo $d$ (and accordingly change $n=sum_i h_i-frack(k-1)2$, of course), so we may suppose that $0leqslant h_ileqslant d-1$ for all $i$. For $a=0,1,dots, d-1$ denote $t_a=|i:h_i=a|$. Then $(bullet)$ rewrites as
$$
left[frac-binomsum_i=0^d-1 t_i2+sum_i=0^d-1 it_idright]+
sum_i=0^d-1 binomt_i2geqslant 0. quad (star)
$$
It remains to observe that LHS of $(star)$ equals to
$$
left[frac1dsum_i<jbinomt_i-t_j2 right].
$$
$endgroup$
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
add a comment |
$begingroup$
Sam is correct of course about $q$-hook formula. Below is a short self-contained proof not relying on such advanced combinatorics.
Denote $h_1>ldots>h_k$ the set of hook lengths of the first column of diagram $lambda$. Then the multiset of hooks is $cup_i=1^k 1,2,ldots,h_isetminus h_i-h_j:i<j$ and $n=sum_i h_i-frack(k-1)2$.
Recall that $F(m)=P_m(alpha,beta)=prod_dPhi_d(alpha,beta)=prod_d (Phi_d(alpha,beta))^eta_d(m)$, where
$alpha,beta=(1pm sqrt5)/2$;
$P_n(x,y)=x^n-1+x^n-2y+ldots+y^n-1$;
$Phi_d$ are homogeneous cyclotomic polynomials;
$eta_d(m)=chi_mathbbZ(m/d)$ (i.e., it equals to 1 if $d$ divides $m$, and to 0 otherwise).
Therefore it suffices to prove that for any fixed $d>1$ we have
$$
sum_m=1^n eta_d(m)+sum_i<jeta_d(h_i-h_j)-sum_i=1^ksum_j=1^h_ieta_d(j)geqslant 0.quad (ast)
$$
$(ast)$ rewrites as
$$
[n/d]+|i<j:h_iequiv h_j pmod d|-sum_i=1^k [h_i/d]geqslant 0.quad (bullet)
$$
LHS of $(bullet)$ does not change if we reduce all $h_i$'s modulo $d$ (and accordingly change $n=sum_i h_i-frack(k-1)2$, of course), so we may suppose that $0leqslant h_ileqslant d-1$ for all $i$. For $a=0,1,dots, d-1$ denote $t_a=|i:h_i=a|$. Then $(bullet)$ rewrites as
$$
left[frac-binomsum_i=0^d-1 t_i2+sum_i=0^d-1 it_idright]+
sum_i=0^d-1 binomt_i2geqslant 0. quad (star)
$$
It remains to observe that LHS of $(star)$ equals to
$$
left[frac1dsum_i<jbinomt_i-t_j2 right].
$$
$endgroup$
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
add a comment |
$begingroup$
Sam is correct of course about $q$-hook formula. Below is a short self-contained proof not relying on such advanced combinatorics.
Denote $h_1>ldots>h_k$ the set of hook lengths of the first column of diagram $lambda$. Then the multiset of hooks is $cup_i=1^k 1,2,ldots,h_isetminus h_i-h_j:i<j$ and $n=sum_i h_i-frack(k-1)2$.
Recall that $F(m)=P_m(alpha,beta)=prod_dPhi_d(alpha,beta)=prod_d (Phi_d(alpha,beta))^eta_d(m)$, where
$alpha,beta=(1pm sqrt5)/2$;
$P_n(x,y)=x^n-1+x^n-2y+ldots+y^n-1$;
$Phi_d$ are homogeneous cyclotomic polynomials;
$eta_d(m)=chi_mathbbZ(m/d)$ (i.e., it equals to 1 if $d$ divides $m$, and to 0 otherwise).
Therefore it suffices to prove that for any fixed $d>1$ we have
$$
sum_m=1^n eta_d(m)+sum_i<jeta_d(h_i-h_j)-sum_i=1^ksum_j=1^h_ieta_d(j)geqslant 0.quad (ast)
$$
$(ast)$ rewrites as
$$
[n/d]+|i<j:h_iequiv h_j pmod d|-sum_i=1^k [h_i/d]geqslant 0.quad (bullet)
$$
LHS of $(bullet)$ does not change if we reduce all $h_i$'s modulo $d$ (and accordingly change $n=sum_i h_i-frack(k-1)2$, of course), so we may suppose that $0leqslant h_ileqslant d-1$ for all $i$. For $a=0,1,dots, d-1$ denote $t_a=|i:h_i=a|$. Then $(bullet)$ rewrites as
$$
left[frac-binomsum_i=0^d-1 t_i2+sum_i=0^d-1 it_idright]+
sum_i=0^d-1 binomt_i2geqslant 0. quad (star)
$$
It remains to observe that LHS of $(star)$ equals to
$$
left[frac1dsum_i<jbinomt_i-t_j2 right].
$$
$endgroup$
Sam is correct of course about $q$-hook formula. Below is a short self-contained proof not relying on such advanced combinatorics.
Denote $h_1>ldots>h_k$ the set of hook lengths of the first column of diagram $lambda$. Then the multiset of hooks is $cup_i=1^k 1,2,ldots,h_isetminus h_i-h_j:i<j$ and $n=sum_i h_i-frack(k-1)2$.
Recall that $F(m)=P_m(alpha,beta)=prod_dPhi_d(alpha,beta)=prod_d (Phi_d(alpha,beta))^eta_d(m)$, where
$alpha,beta=(1pm sqrt5)/2$;
$P_n(x,y)=x^n-1+x^n-2y+ldots+y^n-1$;
$Phi_d$ are homogeneous cyclotomic polynomials;
$eta_d(m)=chi_mathbbZ(m/d)$ (i.e., it equals to 1 if $d$ divides $m$, and to 0 otherwise).
Therefore it suffices to prove that for any fixed $d>1$ we have
$$
sum_m=1^n eta_d(m)+sum_i<jeta_d(h_i-h_j)-sum_i=1^ksum_j=1^h_ieta_d(j)geqslant 0.quad (ast)
$$
$(ast)$ rewrites as
$$
[n/d]+|i<j:h_iequiv h_j pmod d|-sum_i=1^k [h_i/d]geqslant 0.quad (bullet)
$$
LHS of $(bullet)$ does not change if we reduce all $h_i$'s modulo $d$ (and accordingly change $n=sum_i h_i-frack(k-1)2$, of course), so we may suppose that $0leqslant h_ileqslant d-1$ for all $i$. For $a=0,1,dots, d-1$ denote $t_a=|i:h_i=a|$. Then $(bullet)$ rewrites as
$$
left[frac-binomsum_i=0^d-1 t_i2+sum_i=0^d-1 it_idright]+
sum_i=0^d-1 binomt_i2geqslant 0. quad (star)
$$
It remains to observe that LHS of $(star)$ equals to
$$
left[frac1dsum_i<jbinomt_i-t_j2 right].
$$
edited 11 hours ago
answered yesterday
Fedor PetrovFedor Petrov
51.5k6120237
51.5k6120237
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
add a comment |
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
yesterday
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$endgroup$
– T. Amdeberhan
12 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
11 hours ago
add a comment |
$begingroup$
This is a less elementary but maybe more conceptual proof, also giving some combinatorial meaning:
Use the formulas
$F(n) = fracvarphi^n -psi^nsqrt5$, $varphi =frac1+sqrt52, psi = frac1-sqrt52$. Let $q=fracpsivarphi = fracsqrt5-32$, so that
$F(n) = fracvarphi^nsqrt5 (1-q^n)$
Then the Fibonacci hook-length formula becomes:
DeclareMathOperatorlalambda
beginalign*
f^lambda_F:= frac[n]!_Fprod_uin lambdaF(h(u)) = frac varphi^ binomn+12 [n]!_q varphi^sum_u in lambda h(u) prod_u in lambda (1-q^h(u))
endalign*
So we have an ordinary $q$-analogue of the hook-length formula. Note that
$$sum_u in lambda h(u) = sum_i binomlambda_i2 + binomlambda'_j2 + |lambda| = b(lambda) +b(lambda') +n$$
Using the $q-$analogue hook-length formula via major index (EC2, Chapter 21) we have
beginalign*
f^lambda_F = varphi^ binomn2 -b(lambda)-b(lambda') q^-b(lambda) sum_Tin SYT(lambda) q^maj(T) = (-q)^frac12( -binomn2 +b(lambda') -b(lambda))sum_T q^maj(T)
endalign*
Now, it is clear from the q-HLF formula that $q^maj(T)$ is a symmetric polynomial, with lowest degree term $b(lambda)$ and maximal degree $b(lambda) + binomn+12 - n -b(lambda) -b(lambda') =binomn2 - b(lambda')$ so the median degree term is
$$M=frac12 left(b(lambda) +binomn2 - b(lambda')right)$$
which cancels with the factor of $q$ in $f^lambda_F$, so the resulting polynomial is of the form
beginalign*
f^lambda_F = (-1)^M sum_T: maj(T) leq M (q^M-maj(T) + q^maj(T)-M) \
= (-1)^M sum_T (-1)^M-maj(T)( varphi^2(M-maj(T)) + psi^2(M-maj(T)) =
sum_T (-1)^maj(T) L(2(M-maj(T)))
endalign*
where $L$ are the Lucas numbers.
**byproduct of collaborations with A. Morales and I. Pak.
$endgroup$
add a comment |
$begingroup$
This is a less elementary but maybe more conceptual proof, also giving some combinatorial meaning:
Use the formulas
$F(n) = fracvarphi^n -psi^nsqrt5$, $varphi =frac1+sqrt52, psi = frac1-sqrt52$. Let $q=fracpsivarphi = fracsqrt5-32$, so that
$F(n) = fracvarphi^nsqrt5 (1-q^n)$
Then the Fibonacci hook-length formula becomes:
DeclareMathOperatorlalambda
beginalign*
f^lambda_F:= frac[n]!_Fprod_uin lambdaF(h(u)) = frac varphi^ binomn+12 [n]!_q varphi^sum_u in lambda h(u) prod_u in lambda (1-q^h(u))
endalign*
So we have an ordinary $q$-analogue of the hook-length formula. Note that
$$sum_u in lambda h(u) = sum_i binomlambda_i2 + binomlambda'_j2 + |lambda| = b(lambda) +b(lambda') +n$$
Using the $q-$analogue hook-length formula via major index (EC2, Chapter 21) we have
beginalign*
f^lambda_F = varphi^ binomn2 -b(lambda)-b(lambda') q^-b(lambda) sum_Tin SYT(lambda) q^maj(T) = (-q)^frac12( -binomn2 +b(lambda') -b(lambda))sum_T q^maj(T)
endalign*
Now, it is clear from the q-HLF formula that $q^maj(T)$ is a symmetric polynomial, with lowest degree term $b(lambda)$ and maximal degree $b(lambda) + binomn+12 - n -b(lambda) -b(lambda') =binomn2 - b(lambda')$ so the median degree term is
$$M=frac12 left(b(lambda) +binomn2 - b(lambda')right)$$
which cancels with the factor of $q$ in $f^lambda_F$, so the resulting polynomial is of the form
beginalign*
f^lambda_F = (-1)^M sum_T: maj(T) leq M (q^M-maj(T) + q^maj(T)-M) \
= (-1)^M sum_T (-1)^M-maj(T)( varphi^2(M-maj(T)) + psi^2(M-maj(T)) =
sum_T (-1)^maj(T) L(2(M-maj(T)))
endalign*
where $L$ are the Lucas numbers.
**byproduct of collaborations with A. Morales and I. Pak.
$endgroup$
add a comment |
$begingroup$
This is a less elementary but maybe more conceptual proof, also giving some combinatorial meaning:
Use the formulas
$F(n) = fracvarphi^n -psi^nsqrt5$, $varphi =frac1+sqrt52, psi = frac1-sqrt52$. Let $q=fracpsivarphi = fracsqrt5-32$, so that
$F(n) = fracvarphi^nsqrt5 (1-q^n)$
Then the Fibonacci hook-length formula becomes:
DeclareMathOperatorlalambda
beginalign*
f^lambda_F:= frac[n]!_Fprod_uin lambdaF(h(u)) = frac varphi^ binomn+12 [n]!_q varphi^sum_u in lambda h(u) prod_u in lambda (1-q^h(u))
endalign*
So we have an ordinary $q$-analogue of the hook-length formula. Note that
$$sum_u in lambda h(u) = sum_i binomlambda_i2 + binomlambda'_j2 + |lambda| = b(lambda) +b(lambda') +n$$
Using the $q-$analogue hook-length formula via major index (EC2, Chapter 21) we have
beginalign*
f^lambda_F = varphi^ binomn2 -b(lambda)-b(lambda') q^-b(lambda) sum_Tin SYT(lambda) q^maj(T) = (-q)^frac12( -binomn2 +b(lambda') -b(lambda))sum_T q^maj(T)
endalign*
Now, it is clear from the q-HLF formula that $q^maj(T)$ is a symmetric polynomial, with lowest degree term $b(lambda)$ and maximal degree $b(lambda) + binomn+12 - n -b(lambda) -b(lambda') =binomn2 - b(lambda')$ so the median degree term is
$$M=frac12 left(b(lambda) +binomn2 - b(lambda')right)$$
which cancels with the factor of $q$ in $f^lambda_F$, so the resulting polynomial is of the form
beginalign*
f^lambda_F = (-1)^M sum_T: maj(T) leq M (q^M-maj(T) + q^maj(T)-M) \
= (-1)^M sum_T (-1)^M-maj(T)( varphi^2(M-maj(T)) + psi^2(M-maj(T)) =
sum_T (-1)^maj(T) L(2(M-maj(T)))
endalign*
where $L$ are the Lucas numbers.
**byproduct of collaborations with A. Morales and I. Pak.
$endgroup$
This is a less elementary but maybe more conceptual proof, also giving some combinatorial meaning:
Use the formulas
$F(n) = fracvarphi^n -psi^nsqrt5$, $varphi =frac1+sqrt52, psi = frac1-sqrt52$. Let $q=fracpsivarphi = fracsqrt5-32$, so that
$F(n) = fracvarphi^nsqrt5 (1-q^n)$
Then the Fibonacci hook-length formula becomes:
DeclareMathOperatorlalambda
beginalign*
f^lambda_F:= frac[n]!_Fprod_uin lambdaF(h(u)) = frac varphi^ binomn+12 [n]!_q varphi^sum_u in lambda h(u) prod_u in lambda (1-q^h(u))
endalign*
So we have an ordinary $q$-analogue of the hook-length formula. Note that
$$sum_u in lambda h(u) = sum_i binomlambda_i2 + binomlambda'_j2 + |lambda| = b(lambda) +b(lambda') +n$$
Using the $q-$analogue hook-length formula via major index (EC2, Chapter 21) we have
beginalign*
f^lambda_F = varphi^ binomn2 -b(lambda)-b(lambda') q^-b(lambda) sum_Tin SYT(lambda) q^maj(T) = (-q)^frac12( -binomn2 +b(lambda') -b(lambda))sum_T q^maj(T)
endalign*
Now, it is clear from the q-HLF formula that $q^maj(T)$ is a symmetric polynomial, with lowest degree term $b(lambda)$ and maximal degree $b(lambda) + binomn+12 - n -b(lambda) -b(lambda') =binomn2 - b(lambda')$ so the median degree term is
$$M=frac12 left(b(lambda) +binomn2 - b(lambda')right)$$
which cancels with the factor of $q$ in $f^lambda_F$, so the resulting polynomial is of the form
beginalign*
f^lambda_F = (-1)^M sum_T: maj(T) leq M (q^M-maj(T) + q^maj(T)-M) \
= (-1)^M sum_T (-1)^M-maj(T)( varphi^2(M-maj(T)) + psi^2(M-maj(T)) =
sum_T (-1)^maj(T) L(2(M-maj(T)))
endalign*
where $L$ are the Lucas numbers.
**byproduct of collaborations with A. Morales and I. Pak.
answered 41 mins ago
Greta PanovaGreta Panova
15613
15613
add a comment |
add a comment |
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f326860%2fhook-length-formula-fibonaccized%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
$begingroup$
More generally, this interesting question can be asked of any strong divisibility sequence instead of the Fibonacci sequence. But let's perhaps not abuse the notation $Fleft(nright)!$ for something that's not the factorial of $Fleft(nright)$.
$endgroup$
– darij grinberg
2 days ago
1
$begingroup$
Maybe call it $F!(n)$ instead of $F(n)!$. How far has this been checked?
$endgroup$
– Noam D. Elkies
2 days ago
9
$begingroup$
Maybe this expression can be obtained by a clever substitution of the $q$-hook length formula?
$endgroup$
– Sam Hopkins
2 days ago
1
$begingroup$
@darijgrinberg what is a strong divisibility sequence? Product of any $k$ consecutive guys is divisibly by the product of first $k$ guys?
$endgroup$
– Fedor Petrov
yesterday
5
$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
yesterday