# Tag Info

Supposing your constituent values are $0,1,2,\ldots,q$ the answer is given by the following Polya Enumeration formula: $$[z^N] Z(S_k)\left(\sum_{m=0}^q z^m\right).$$ In the example we have $k=3$ and $N=6$ so we obtain the generating function $$f(z) = [z^6] Z(S_3)\left(\sum_{m=0}^4 z^m\right).$$ Now $$Z(S_3) = ... 1 You’ve made a pretty good start. You’re right that an n-cycle has n spanning trees. Another way to explain it is to notice that deleting one edge leaves n vertices and n-1 edges, so you have a tree; clearly that tree spans the cycle, and there are n possible edges to remove, so there are n spanning trees. With K_4, the tetrahedron, you got 4 ... 1 For A\subseteq L let U(A)=\{u\in U:\ell<u\text{ for some }\ell\in A\}. Let$$r=\max\{|A|-|U(A)|:A\subseteq L\}\;;\tag{1}$$then |U(A)|\ge|A|-r for all A\subseteq L, so there is an A\subseteq L such that |A|=|L|-r, and \{U(a):a\in A\} has a transversal (SDR). Let T be a transversal for \{U(a):a\in A\}, and for each a\in A let u_a be ... 1 Recall the species of set partitions with the constituents marked which is$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$which gives the generating function$$G(z, u) = \exp(u(\exp(z)-1)).$$It follows that the exponential generating function of Bell numbers is given by$$G(z) = \exp(\exp(z)-1). Suppose we are trying to compute ...