Proving that : $ fracW(x)xe^x=sumlimits_n=0^infty frac(-1)^nn!T(n)x^n $ [closed] The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Number of possible Prüfer codesEnumerating Rooted labeled trees without Lagrange inversion formulaExistence of increasing pair of labeled trees in an infinite sequenceHow many ways can I connect labeled trees into a tree.Counting the number of Prüfer codesrooted labeled trees with root degree 2Proof of identity via binomial theoremThe relationship between $sum_kgeq1frack^k+ak!(4e)^k/2$ and the number of labeled rooted trees of subsets of an n-setThe number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?How would we evaluate the definite integral $ int_0^e^frac1efrac -W(-ln(x))ln(x)dx $
Semisimplicity of the category of coherent sheaves?
How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?
Is there a writing software that you can sort scenes like slides in PowerPoint?
Did the new image of black hole confirm the general theory of relativity?
What's the point in a preamp?
What was the last x86 CPU that did not have the x87 floating-point unit built in?
In horse breeding, what is the female equivalent of putting a horse out "to stud"?
Keeping a retro style to sci-fi spaceships?
Python - Fishing Simulator
Finding the path in a graph from A to B then back to A with a minimum of shared edges
Is it ethical to upload a automatically generated paper to a non peer-reviewed site as part of a larger research?
does high air pressure throw off wheel balance?
Is every episode of "Where are my Pants?" identical?
University's motivation for having tenure-track positions
How to test the equality of two Pearson correlation coefficients computed from the same sample?
How should I replace vector<uint8_t>::const_iterator in an API?
What can I do if neighbor is blocking my solar panels intentionally?
Is above average number of years spent on PhD considered a red flag in future academia or industry positions?
Does Parliament hold absolute power in the UK?
how can a perfect fourth interval be considered either consonant or dissonant?
Why does the Event Horizon Telescope (EHT) not include telescopes from Africa, Asia or Australia?
Can the DM override racial traits?
Are my PIs rude or am I just being too sensitive?
Netflix Recommendations?
Proving that : $ fracW(x)xe^x=sumlimits_n=0^infty frac(-1)^nn!T(n)x^n $ [closed]
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Number of possible Prüfer codesEnumerating Rooted labeled trees without Lagrange inversion formulaExistence of increasing pair of labeled trees in an infinite sequenceHow many ways can I connect labeled trees into a tree.Counting the number of Prüfer codesrooted labeled trees with root degree 2Proof of identity via binomial theoremThe relationship between $sum_kgeq1frack^k+ak!(4e)^k/2$ and the number of labeled rooted trees of subsets of an n-setThe number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?How would we evaluate the definite integral $ int_0^e^frac1efrac -W(-ln(x))ln(x)dx $
$begingroup$
How to prove that:
$$ fracW(x)xe^x=sum_n=0^infty frac(-1)^nn!T(n)x^n $$
where
$T(n)$
counts the number of forests of rooted labeled trees using labels in a subset of
$1,ldots,n$ and $W(x)$ is the Lambert $W$ function?
Also, as shown in this video at 6:54, does $T (n)=n^n-2 $ ?
combinatorics trees lambert-w
edited Mar 31 at 14:19
rtybase
11.6k31534
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
$endgroup$
closed as off-topic by Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi Apr 1 at 10:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi
add a comment |
$begingroup$
How to prove that:
$$ fracW(x)xe^x=sum_n=0^infty frac(-1)^nn!T(n)x^n $$
where
$T(n)$
counts the number of forests of rooted labeled trees using labels in a subset of
$1,ldots,n$ and $W(x)$ is the Lambert $W$ function?
Also, as shown in this video at 6:54, does $T (n)=n^n-2 $ ?
combinatorics trees lambert-w
edited Mar 31 at 14:19
rtybase
11.6k31534
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
$endgroup$
closed as off-topic by Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi Apr 1 at 10:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi
add a comment |
$begingroup$
How to prove that:
$$ fracW(x)xe^x=sum_n=0^infty frac(-1)^nn!T(n)x^n $$
where
$T(n)$
counts the number of forests of rooted labeled trees using labels in a subset of
$1,ldots,n$ and $W(x)$ is the Lambert $W$ function?
Also, as shown in this video at 6:54, does $T (n)=n^n-2 $ ?
combinatorics trees lambert-w
edited Mar 31 at 14:19
rtybase
11.6k31534
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
$endgroup$
How to prove that:
$$ fracW(x)xe^x=sum_n=0^infty frac(-1)^nn!T(n)x^n $$
where
$T(n)$
counts the number of forests of rooted labeled trees using labels in a subset of
$1,ldots,n$ and $W(x)$ is the Lambert $W$ function?
Also, as shown in this video at 6:54, does $T (n)=n^n-2 $ ?
combinatorics trees lambert-w
combinatorics trees lambert-w
edited Mar 31 at 14:19
rtybase
11.6k31534
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
edited Mar 31 at 14:19
rtybase
11.6k31534
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
edited Mar 31 at 14:19
rtybase
11.6k31534
edited Mar 31 at 14:19
rtybase
11.6k31534
edited Mar 31 at 14:19
rtybase
11.6k31534
11.6k31534
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
asked Mar 31 at 11:45
Rithik KapoorRithik Kapoor
39010
39010
closed as off-topic by Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi Apr 1 at 10:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi
closed as off-topic by Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi Apr 1 at 10:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, Abcd, Eevee Trainer, Cesareo, Javi
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Start by making some definitions. The combinatorial class
$mathcalT$ of labelled trees has the specification
$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2mathcalT =
mathcalZ times textscSET(mathcalT)$$
which gives the functional equation
$$T(z) = z exp T(z).$$
We have by Cayley that
$$T(z) = sum_nge 1 n^n-1 fracz^nn!.$$
We seek to prove that
$$bbox[5px,border:2px solid #00A000]
W(z) = z exp(z) sum_nge 0 (-1)^n Q_n
fracz^nn!$$
where $Q_n$ is the number of rooted subtrees for a fixed root in the
complete graph $K_n+1$ on $n+1$ vertices. These have from $k=0$ to
$k=n$ nodes not including the fixed root and represent a forest that
is attached to the root. (Specification as in OEIS
A088957, example given by A. Chin.) The
combinatorial class $mathcalF$ of forests is given by
$$mathcalF = textscSET(mathcalT)$$
and hence has EGF
$$F(z) = exp T(z) = frac1z T(z).$$
We also have by construction that
$$Q_n = sum_k=0^n nchoose k
k! [z^k] F(z).$$
Here we chose the labels that go into the forest and substitute them
into the forest respecting the ordering of the nodes in the source
forest. It follows by convolution of EGFs that (recall that $n! [z^n]
exp(z) = 1$)
$$Q(z) = sum_nge 0 Q_n fracz^nn!
= exp(z) frac1z T(z).$$
Now by definition the principal branch of the Lambert W function
is
$$W(z) = sum_nge 1 (-1)^n-1 n^n-1 fracz^nn!$$
and hence we obtain
$$bbox[5px,border:2px solid #00A000]
sum_nge 0 Q_n
fracz^nn! = frac1z T(z) exp(z)
= - frac1z W(-z) exp(z).$$
The claim now follows by replacing $z$ by $-z$ to get
$$sum_nge 0 (-1)^n Q_n
fracz^nn! = frac1z W(z) exp(-z).$$
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
$endgroup$
add a comment |
$begingroup$
This is not an answer.
This is a problem of Taylor series composition using
$$W(x)=sum_n=1^infty (-1)^n,fracn^(n-1)n!x^n$$ (have a look here)
$$e^-x=sum_n=0^infty (-1)^n,fracx^nn!$$ So, computing the first terms, we have, as a series,
$$fracW(x)xe^x=1-2 x+3 x^2-frac29 x^36+frac53 x^46-frac2117 x^5120+frac2683
x^672-frac82403 x^71008+Oleft(x^8right)$$ making the $T_n$ to be the sequence
$$1,2,6,29,212,2117,26830,412015$$ which is sequence $A088957$ in $OEIS$.
In a comment, Alex Chin wrote that these coefficients are "the number of rooted subtrees (for a fixed root) in the complete graph on $n$ vertices" (please : do not ask me what this means !).
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Start by making some definitions. The combinatorial class
$mathcalT$ of labelled trees has the specification
$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2mathcalT =
mathcalZ times textscSET(mathcalT)$$
which gives the functional equation
$$T(z) = z exp T(z).$$
We have by Cayley that
$$T(z) = sum_nge 1 n^n-1 fracz^nn!.$$
We seek to prove that
$$bbox[5px,border:2px solid #00A000]
W(z) = z exp(z) sum_nge 0 (-1)^n Q_n
fracz^nn!$$
where $Q_n$ is the number of rooted subtrees for a fixed root in the
complete graph $K_n+1$ on $n+1$ vertices. These have from $k=0$ to
$k=n$ nodes not including the fixed root and represent a forest that
is attached to the root. (Specification as in OEIS
A088957, example given by A. Chin.) The
combinatorial class $mathcalF$ of forests is given by
$$mathcalF = textscSET(mathcalT)$$
and hence has EGF
$$F(z) = exp T(z) = frac1z T(z).$$
We also have by construction that
$$Q_n = sum_k=0^n nchoose k
k! [z^k] F(z).$$
Here we chose the labels that go into the forest and substitute them
into the forest respecting the ordering of the nodes in the source
forest. It follows by convolution of EGFs that (recall that $n! [z^n]
exp(z) = 1$)
$$Q(z) = sum_nge 0 Q_n fracz^nn!
= exp(z) frac1z T(z).$$
Now by definition the principal branch of the Lambert W function
is
$$W(z) = sum_nge 1 (-1)^n-1 n^n-1 fracz^nn!$$
and hence we obtain
$$bbox[5px,border:2px solid #00A000]
sum_nge 0 Q_n
fracz^nn! = frac1z T(z) exp(z)
= - frac1z W(-z) exp(z).$$
The claim now follows by replacing $z$ by $-z$ to get
$$sum_nge 0 (-1)^n Q_n
fracz^nn! = frac1z W(z) exp(-z).$$
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
$endgroup$
add a comment |
$begingroup$
Start by making some definitions. The combinatorial class
$mathcalT$ of labelled trees has the specification
$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2mathcalT =
mathcalZ times textscSET(mathcalT)$$
which gives the functional equation
$$T(z) = z exp T(z).$$
We have by Cayley that
$$T(z) = sum_nge 1 n^n-1 fracz^nn!.$$
We seek to prove that
$$bbox[5px,border:2px solid #00A000]
W(z) = z exp(z) sum_nge 0 (-1)^n Q_n
fracz^nn!$$
where $Q_n$ is the number of rooted subtrees for a fixed root in the
complete graph $K_n+1$ on $n+1$ vertices. These have from $k=0$ to
$k=n$ nodes not including the fixed root and represent a forest that
is attached to the root. (Specification as in OEIS
A088957, example given by A. Chin.) The
combinatorial class $mathcalF$ of forests is given by
$$mathcalF = textscSET(mathcalT)$$
and hence has EGF
$$F(z) = exp T(z) = frac1z T(z).$$
We also have by construction that
$$Q_n = sum_k=0^n nchoose k
k! [z^k] F(z).$$
Here we chose the labels that go into the forest and substitute them
into the forest respecting the ordering of the nodes in the source
forest. It follows by convolution of EGFs that (recall that $n! [z^n]
exp(z) = 1$)
$$Q(z) = sum_nge 0 Q_n fracz^nn!
= exp(z) frac1z T(z).$$
Now by definition the principal branch of the Lambert W function
is
$$W(z) = sum_nge 1 (-1)^n-1 n^n-1 fracz^nn!$$
and hence we obtain
$$bbox[5px,border:2px solid #00A000]
sum_nge 0 Q_n
fracz^nn! = frac1z T(z) exp(z)
= - frac1z W(-z) exp(z).$$
The claim now follows by replacing $z$ by $-z$ to get
$$sum_nge 0 (-1)^n Q_n
fracz^nn! = frac1z W(z) exp(-z).$$
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
$endgroup$
add a comment |
$begingroup$
Start by making some definitions. The combinatorial class
$mathcalT$ of labelled trees has the specification
$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2mathcalT =
mathcalZ times textscSET(mathcalT)$$
which gives the functional equation
$$T(z) = z exp T(z).$$
We have by Cayley that
$$T(z) = sum_nge 1 n^n-1 fracz^nn!.$$
We seek to prove that
$$bbox[5px,border:2px solid #00A000]
W(z) = z exp(z) sum_nge 0 (-1)^n Q_n
fracz^nn!$$
where $Q_n$ is the number of rooted subtrees for a fixed root in the
complete graph $K_n+1$ on $n+1$ vertices. These have from $k=0$ to
$k=n$ nodes not including the fixed root and represent a forest that
is attached to the root. (Specification as in OEIS
A088957, example given by A. Chin.) The
combinatorial class $mathcalF$ of forests is given by
$$mathcalF = textscSET(mathcalT)$$
and hence has EGF
$$F(z) = exp T(z) = frac1z T(z).$$
We also have by construction that
$$Q_n = sum_k=0^n nchoose k
k! [z^k] F(z).$$
Here we chose the labels that go into the forest and substitute them
into the forest respecting the ordering of the nodes in the source
forest. It follows by convolution of EGFs that (recall that $n! [z^n]
exp(z) = 1$)
$$Q(z) = sum_nge 0 Q_n fracz^nn!
= exp(z) frac1z T(z).$$
Now by definition the principal branch of the Lambert W function
is
$$W(z) = sum_nge 1 (-1)^n-1 n^n-1 fracz^nn!$$
and hence we obtain
$$bbox[5px,border:2px solid #00A000]
sum_nge 0 Q_n
fracz^nn! = frac1z T(z) exp(z)
= - frac1z W(-z) exp(z).$$
The claim now follows by replacing $z$ by $-z$ to get
$$sum_nge 0 (-1)^n Q_n
fracz^nn! = frac1z W(z) exp(-z).$$
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
$endgroup$
Start by making some definitions. The combinatorial class
$mathcalT$ of labelled trees has the specification
$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2mathcalT =
mathcalZ times textscSET(mathcalT)$$
which gives the functional equation
$$T(z) = z exp T(z).$$
We have by Cayley that
$$T(z) = sum_nge 1 n^n-1 fracz^nn!.$$
We seek to prove that
$$bbox[5px,border:2px solid #00A000]
W(z) = z exp(z) sum_nge 0 (-1)^n Q_n
fracz^nn!$$
where $Q_n$ is the number of rooted subtrees for a fixed root in the
complete graph $K_n+1$ on $n+1$ vertices. These have from $k=0$ to
$k=n$ nodes not including the fixed root and represent a forest that
is attached to the root. (Specification as in OEIS
A088957, example given by A. Chin.) The
combinatorial class $mathcalF$ of forests is given by
$$mathcalF = textscSET(mathcalT)$$
and hence has EGF
$$F(z) = exp T(z) = frac1z T(z).$$
We also have by construction that
$$Q_n = sum_k=0^n nchoose k
k! [z^k] F(z).$$
Here we chose the labels that go into the forest and substitute them
into the forest respecting the ordering of the nodes in the source
forest. It follows by convolution of EGFs that (recall that $n! [z^n]
exp(z) = 1$)
$$Q(z) = sum_nge 0 Q_n fracz^nn!
= exp(z) frac1z T(z).$$
Now by definition the principal branch of the Lambert W function
is
$$W(z) = sum_nge 1 (-1)^n-1 n^n-1 fracz^nn!$$
and hence we obtain
$$bbox[5px,border:2px solid #00A000]
sum_nge 0 Q_n
fracz^nn! = frac1z T(z) exp(z)
= - frac1z W(-z) exp(z).$$
The claim now follows by replacing $z$ by $-z$ to get
$$sum_nge 0 (-1)^n Q_n
fracz^nn! = frac1z W(z) exp(-z).$$
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
edited Mar 31 at 22:00
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
answered Mar 31 at 20:48
Marko RiedelMarko Riedel
41.5k341112
41.5k341112
add a comment |
add a comment |
$begingroup$
This is not an answer.
This is a problem of Taylor series composition using
$$W(x)=sum_n=1^infty (-1)^n,fracn^(n-1)n!x^n$$ (have a look here)
$$e^-x=sum_n=0^infty (-1)^n,fracx^nn!$$ So, computing the first terms, we have, as a series,
$$fracW(x)xe^x=1-2 x+3 x^2-frac29 x^36+frac53 x^46-frac2117 x^5120+frac2683
x^672-frac82403 x^71008+Oleft(x^8right)$$ making the $T_n$ to be the sequence
$$1,2,6,29,212,2117,26830,412015$$ which is sequence $A088957$ in $OEIS$.
In a comment, Alex Chin wrote that these coefficients are "the number of rooted subtrees (for a fixed root) in the complete graph on $n$ vertices" (please : do not ask me what this means !).
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
add a comment |
$begingroup$
This is not an answer.
This is a problem of Taylor series composition using
$$W(x)=sum_n=1^infty (-1)^n,fracn^(n-1)n!x^n$$ (have a look here)
$$e^-x=sum_n=0^infty (-1)^n,fracx^nn!$$ So, computing the first terms, we have, as a series,
$$fracW(x)xe^x=1-2 x+3 x^2-frac29 x^36+frac53 x^46-frac2117 x^5120+frac2683
x^672-frac82403 x^71008+Oleft(x^8right)$$ making the $T_n$ to be the sequence
$$1,2,6,29,212,2117,26830,412015$$ which is sequence $A088957$ in $OEIS$.
In a comment, Alex Chin wrote that these coefficients are "the number of rooted subtrees (for a fixed root) in the complete graph on $n$ vertices" (please : do not ask me what this means !).
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
add a comment |
$begingroup$
This is not an answer.
This is a problem of Taylor series composition using
$$W(x)=sum_n=1^infty (-1)^n,fracn^(n-1)n!x^n$$ (have a look here)
$$e^-x=sum_n=0^infty (-1)^n,fracx^nn!$$ So, computing the first terms, we have, as a series,
$$fracW(x)xe^x=1-2 x+3 x^2-frac29 x^36+frac53 x^46-frac2117 x^5120+frac2683
x^672-frac82403 x^71008+Oleft(x^8right)$$ making the $T_n$ to be the sequence
$$1,2,6,29,212,2117,26830,412015$$ which is sequence $A088957$ in $OEIS$.
In a comment, Alex Chin wrote that these coefficients are "the number of rooted subtrees (for a fixed root) in the complete graph on $n$ vertices" (please : do not ask me what this means !).
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
This is not an answer.
This is a problem of Taylor series composition using
$$W(x)=sum_n=1^infty (-1)^n,fracn^(n-1)n!x^n$$ (have a look here)
$$e^-x=sum_n=0^infty (-1)^n,fracx^nn!$$ So, computing the first terms, we have, as a series,
$$fracW(x)xe^x=1-2 x+3 x^2-frac29 x^36+frac53 x^46-frac2117 x^5120+frac2683
x^672-frac82403 x^71008+Oleft(x^8right)$$ making the $T_n$ to be the sequence
$$1,2,6,29,212,2117,26830,412015$$ which is sequence $A088957$ in $OEIS$.
In a comment, Alex Chin wrote that these coefficients are "the number of rooted subtrees (for a fixed root) in the complete graph on $n$ vertices" (please : do not ask me what this means !).
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
answered Mar 31 at 14:30
Claude LeiboviciClaude Leibovici
125k1158135
125k1158135
add a comment |
add a comment |
