[math-fun] OEIS: conjecture about certain forests and their exponential generating functions
I'd like to know whether the following is known (I bet it is, and in a more general context): cf. https://oeis.org/A187761 and https://oeis.org/A179455 Let C(n,x) be the e.g.f of the monotonic-labeled forests on n vertices with rooted trees of height less than n. (A labeled rooted tree is monotonic-labeled if the label of any parent vertex is (strictly) smaller than the label of any offspring vertex.) I conjecture that the C(n,x) are as follows. Let C(0,x) = 1 and for n>=1, C(n, x) = exp(integral(C(n-1,x)) ) For n=1 (C(1,x)=exp(x), constant sequence of ones) and n=2 (C(2,x)=exp(exp(x)-1), Bell numbers) this is obviously true. (note that integration of an e.g.f. essentially shifts it to smaller powers and drops the constant term; for the corresponding sequences: it just drops the first term). So clueless, jj
On 14/01/2013 11:22, Joerg Arndt wrote:
I'd like to know whether the following is known (I bet it is, and in a more general context): cf. https://oeis.org/A187761 and https://oeis.org/A179455
Let C(n,x) be the e.g.f of the monotonic-labeled forests on n vertices with rooted trees of height less than n. (A labeled rooted tree is monotonic-labeled if the label of any parent vertex is (strictly) smaller than the label of any offspring vertex.)
I conjecture that the C(n,x) are as follows.
Let C(0,x) = 1 and for n>=1, C(n, x) = exp(integral(C(n-1,x)) )
Well, if F is the e.g.f. for Things Of Size n, then exp F is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.) Which means your conjecture is right. (The integral turns that into "multisets of things whose sizes plus 1 add up to n"; a tree is a forest together with a new node on top.) I'm sure all this is well known to those who know these things well. I am not such a person. -- g
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Jan 15. 2013 08:27]:
On 14/01/2013 11:22, Joerg Arndt wrote:
I'd like to know whether the following is known (I bet it is, and in a more general context): cf. https://oeis.org/A187761 and https://oeis.org/A179455
Let C(n,x) be the e.g.f of the monotonic-labeled forests on n vertices with rooted trees of height less than n. (A labeled rooted tree is monotonic-labeled if the label of any parent vertex is (strictly) smaller than the label of any offspring vertex.)
I conjecture that the C(n,x) are as follows.
Let C(0,x) = 1 and for n>=1, C(n, x) = exp(integral(C(n-1,x)) )
Well, if F is the e.g.f. for Things Of Size n, then exp F is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.)
Which means your conjecture is right. (The integral turns that into "multisets of things whose sizes plus 1 add up to n"; a tree is a forest together with a new node on top.)
I'm sure all this is well known to those who know these things well. I am not such a person.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I am thoroughly impressed. I cited (and (very slightly) rephrased), please peek at https://oeis.org/draft/A187761 and give your OK (else just edit): ------------------------ Gareth McCaughan, on the math-fun mailing list (Jan 14 2013), writes "If F is the e.g.f. for Things Of Size n, then exp(F) is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.) Which means the conjecture is right. (The integral turns that into "multisets of things whose sizes plus 1 add up to n"; a tree is a forest together with a new node on top.) " ------------------------ Thanks very much indeed! Best regard, jj P.S.: If you have an OEIS account, I can make your name a link to your user page, improving our universe even more.
On 15/01/2013 18:17, Joerg Arndt wrote:
I cited (and (very slightly) rephrased), please peek at https://oeis.org/draft/A187761 and give your OK (else just edit):
------------------------ Gareth McCaughan, on the math-fun mailing list (Jan 14 2013), writes "If F is the e.g.f. for Things Of Size n, then exp(F) is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.) Which means the conjecture is right. (The integral turns that into "multisets of things whose sizes plus 1 add up to n"; a tree is a forest together with a new node on top.) " ------------------------
Looks OK to me. I did a quick search and found this, which states and explains a nice general principle of which the above is a very special case. http://math.berkeley.edu/~mhaiman/math172.../exponential.pdf In particular, look at the section called "The function composition principle". (To be explicit: it generalizes what I said about applying exp to egfs; it doesn't generalize your discovery about labelled forests.) -- g
I wrote:
Looks OK to me. I did a quick search and found this, which states and explains a nice general principle of which the above is a very special case.
http://math.berkeley.edu/~mhaiman/math172.../exponential.pdf
In particular, look at the section called "The function composition principle".
Oops. http://math.berkeley.edu/~mhaiman/math172-spring10/exponential.pdf (Thanks to Charles Greathouse for pointing out that I screwed up the link. No thanks to Google for making it painful to get the original URL for a link found by their search.) -- g
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Jan 16. 2013 18:36]:
[...]
http://math.berkeley.edu/~mhaiman/math172-spring10/exponential.pdf
[...]
These are fine resources. I had already peeked into Philippe Flajolet, Robert Sedgewick: {Analytic Combinatorics}, Cambridge University Press, \bdate{2009}. http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html and thought my observation *must* be true, but could not prove. Thanks again, jj
participants (2)
-
Gareth McCaughan -
Joerg Arndt