[대학교이상] 님들 꼭짓점이 n+1 개인 수형도의...

[익명(14.5)]

님들 꼭짓점이 n+1 개인 수형도의 개수(동형인건 하나로 간주할때)는 분할수 P(n)인가요?

[유사수학자(lonelymath)]

다름. multiset에 대한 생성함수 식을 고려하면, A(z)를 n개의 꼭지점을 갖는 unlabeled rooted tree에 대한 생성함수라 할때 A(z) = z*exp(A(z) + A(z^2)/2 + A(z^3)/3 + ...)이 나오고, 이 생성함수를 통해서 n개의 꼭지점을 갖는 unlabeled rooted tree의 개수의 asymptotic formula를 구할 수 있음.
https://oeis.org/A000081
https://www.jstor.org/stable/1969046

[유사수학자(lonelymath)]

n개의 꼭지점을 갖는 unlabeled rooted tree의 개수는 점근적으로 a = 0.439... , b = 2.955...에 대해서 an^{-3/2} b^n (1 + O(1/n)) 개가 나옴.

[유사수학자(lonelymath)]

반면 분할수 P(n)은 점근적으로 1/(4n*sqrt(3)) * exp(pi * sqrt(2n/3))으로서 n에 대해서 subexponential함.

[익명(106.101)]

ㄱㅅㄱㅅ