hook-length formula: “Fibonaccized” Part Ihook-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 partitionshooks and contents: Part Ihooks and contents: Part IIPartitions, $q$-polynomials and generating functionsPartitions and $q$-integersA link between hooks, contents and parts of a partitionhook-length formula: “Fibonaccized”: Part II

hook-length formula: “Fibonaccized” Part I


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 partitionshooks and contents: Part Ihooks and contents: Part IIPartitions, $q$-polynomials and generating functionsPartitions and $q$-integersA link between hooks, contents and parts of a partitionhook-length formula: “Fibonaccized”: Part II













16












$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?$$











share|cite|improve this question











$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
    Apr 1 at 3:50







  • 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
    2 days ago






  • 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
    2 days ago















16












$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?$$











share|cite|improve this question











$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
    Apr 1 at 3:50







  • 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
    2 days ago






  • 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
    2 days ago













16












16








16


8



$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?$$











share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 12 hours ago







T. Amdeberhan

















asked Apr 1 at 3:42









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
    Apr 1 at 3:50







  • 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
    2 days ago






  • 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
    2 days ago












  • 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
    Apr 1 at 3:50







  • 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
    2 days ago






  • 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
    2 days ago







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
Apr 1 at 3:50





$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
Apr 1 at 3:50





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
2 days ago




$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
2 days ago




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
2 days ago




$begingroup$
For searching purposes: the product of consecutive Fibonacci numbers is sometimes referred to as a fibonorial.
$endgroup$
– J. M. is not a mathematician
2 days ago










2 Answers
2






active

oldest

votes


















10












$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_m,d>1Phi_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].
$$






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Nice. So what does this integer count?
    $endgroup$
    – Brian Hopkins
    2 days ago










  • $begingroup$
    Yes, that was my plan to ask next.
    $endgroup$
    – T. Amdeberhan
    2 days ago











  • $begingroup$
    @Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
    $endgroup$
    – T. Amdeberhan
    yesterday










  • $begingroup$
    @T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
    $endgroup$
    – Fedor Petrov
    yesterday


















6












$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:



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.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
    $endgroup$
    – T. Amdeberhan
    11 hours ago










  • $begingroup$
    Thanks! I just pasted it there.
    $endgroup$
    – Greta Panova
    9 hours ago











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



);













draft saved

draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f326860%2fhook-length-formula-fibonaccized-part-i%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









10












$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_m,d>1Phi_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].
$$






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Nice. So what does this integer count?
    $endgroup$
    – Brian Hopkins
    2 days ago










  • $begingroup$
    Yes, that was my plan to ask next.
    $endgroup$
    – T. Amdeberhan
    2 days ago











  • $begingroup$
    @Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
    $endgroup$
    – T. Amdeberhan
    yesterday










  • $begingroup$
    @T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
    $endgroup$
    – Fedor Petrov
    yesterday















10












$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_m,d>1Phi_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].
$$






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Nice. So what does this integer count?
    $endgroup$
    – Brian Hopkins
    2 days ago










  • $begingroup$
    Yes, that was my plan to ask next.
    $endgroup$
    – T. Amdeberhan
    2 days ago











  • $begingroup$
    @Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
    $endgroup$
    – T. Amdeberhan
    yesterday










  • $begingroup$
    @T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
    $endgroup$
    – Fedor Petrov
    yesterday













10












10








10





$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_m,d>1Phi_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].
$$






share|cite|improve this answer











$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_m,d>1Phi_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].
$$







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited yesterday

























answered 2 days ago









Fedor PetrovFedor Petrov

51.6k6121238




51.6k6121238











  • $begingroup$
    Nice. So what does this integer count?
    $endgroup$
    – Brian Hopkins
    2 days ago










  • $begingroup$
    Yes, that was my plan to ask next.
    $endgroup$
    – T. Amdeberhan
    2 days ago











  • $begingroup$
    @Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
    $endgroup$
    – T. Amdeberhan
    yesterday










  • $begingroup$
    @T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
    $endgroup$
    – Fedor Petrov
    yesterday
















  • $begingroup$
    Nice. So what does this integer count?
    $endgroup$
    – Brian Hopkins
    2 days ago










  • $begingroup$
    Yes, that was my plan to ask next.
    $endgroup$
    – T. Amdeberhan
    2 days ago











  • $begingroup$
    @Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
    $endgroup$
    – T. Amdeberhan
    yesterday










  • $begingroup$
    @T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
    $endgroup$
    – Fedor Petrov
    yesterday















$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
2 days ago




$begingroup$
Nice. So what does this integer count?
$endgroup$
– Brian Hopkins
2 days ago












$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
2 days ago





$begingroup$
Yes, that was my plan to ask next.
$endgroup$
– T. Amdeberhan
2 days ago













$begingroup$
@Fedor: what are $alpha$ and $beta$? What's the connection between $P_m$ and $eta_d$, etc?
$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
yesterday












$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
yesterday




$begingroup$
@T.Amdeberhan sorry, forgot to copy the notations from my previous Fibonacci answer. Hope now it is clear.
$endgroup$
– Fedor Petrov
yesterday











6












$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:



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.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
    $endgroup$
    – T. Amdeberhan
    11 hours ago










  • $begingroup$
    Thanks! I just pasted it there.
    $endgroup$
    – Greta Panova
    9 hours ago















6












$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:



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.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
    $endgroup$
    – T. Amdeberhan
    11 hours ago










  • $begingroup$
    Thanks! I just pasted it there.
    $endgroup$
    – Greta Panova
    9 hours ago













6












6








6





$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:



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.






share|cite|improve this answer











$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:



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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 1 hour ago









darij grinberg

18.4k373188




18.4k373188










answered 21 hours ago









Greta PanovaGreta Panova

23623




23623











  • $begingroup$
    Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
    $endgroup$
    – T. Amdeberhan
    11 hours ago










  • $begingroup$
    Thanks! I just pasted it there.
    $endgroup$
    – Greta Panova
    9 hours ago
















  • $begingroup$
    Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
    $endgroup$
    – T. Amdeberhan
    11 hours ago










  • $begingroup$
    Thanks! I just pasted it there.
    $endgroup$
    – Greta Panova
    9 hours ago















$begingroup$
Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
$endgroup$
– T. Amdeberhan
11 hours ago




$begingroup$
Nice, thank you. This would be even more fitting to the 2nd part of this question mathoverflow.net/questions/327015/… Therefore, do you like to post it there as well?
$endgroup$
– T. Amdeberhan
11 hours ago












$begingroup$
Thanks! I just pasted it there.
$endgroup$
– Greta Panova
9 hours ago




$begingroup$
Thanks! I just pasted it there.
$endgroup$
– Greta Panova
9 hours ago

















draft saved

draft discarded
















































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.




draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f326860%2fhook-length-formula-fibonaccized-part-i%23new-answer', 'question_page');

);

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







Popular posts from this blog

Crop image to path created in TikZ? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Crop an inserted image?TikZ pictures does not appear in posterImage behind and beyond crop marks?Tikz picture as large as possible on A4 PageTransparency vs image compression dilemmaHow to crop background from image automatically?Image does not cropTikzexternal capturing crop marks when externalizing pgfplots?How to include image path that contains a dollar signCrop image with left size given

រឿង រ៉ូមេអូ និង ហ្ស៊ុយលីយេ សង្ខេបរឿង តួអង្គ បញ្ជីណែនាំ

Ромео және Джульетта Мазмұны Қысқаша сипаттамасы Кейіпкерлері Кино Дереккөздер Бағыттау мәзірі