Polynomial or Exponential Complexity of Bell Polynomials

by Dunkel   Last Updated June 13, 2019 12:20 PM

I would like to know if the total number of partitions (all sizes) of $ n $ elements into non-empty sets (defined by the exponential Bell polynomial) has polynomial complexity or exponential complexity.

Additional information
Specifically, I am referring to the sum of all the coefficients of the polynomial $$ B_{n,k}(x_1,x_2,\dots,x_{n-k+1}) = \sum^n_{k=1} \sum_{j_1 + j_2 + \cdots + j_{n-k+1} = k, \\ j_1 + 2 j_2 + 3 j_3 + \cdots + (n-k+1)j_{n-k+1} = n} {n! \over j_1!j_2!\cdots j_{n-k+1}!} \left({x_1\over 1!}\right)^{j_1}\left({x_2\over 2!}\right)^{j_2}\cdots\left({x_{n-k+1} \over (n-k+1)!}\right)^{j_{n-k+1}}, $$ For instance, if I would want to say something about all the potential partitions, would I say that they grow exponentially or polynomially?



Related Questions


Updated April 03, 2019 22:20 PM

Updated August 21, 2019 10:20 AM

Updated October 05, 2017 19:20 PM

Updated October 25, 2016 09:08 AM