Counting Labeled Forests with a Fixed Number of Binary Trees

Given a positive integer \(n\), consider all forests on \(n\) labeled nodes. A forest is defined as a collection of labeled rooted trees on the set \(\{1,2,\dots,n\}\) (two forests are considered different if and only if there exists a node whose parent is different; note that a root is regarded as having no parent). A binary tree is defined to be a labeled rooted tree in which every node has at most 2 children.

For each \(s=0,1,\dots,n\), count the number of forests (modulo \(998244353\)) that have exactly \(s\) trees which are binary trees. In other words, if a forest consists of several trees, some of which (and only those) are binary trees – count the forest toward \(s\) if exactly \(s\) of its trees are binary trees.

Note: In a forest, the trees are not ordered. Two forests are considered distinct if and only if there exists at least one node whose parent differs.

In the input, only \(n\) is given. The output should contain \(n+1\) space‐separated integers, where the \(i\)th integer (0-indexed) is the count of forests having exactly \(i\) binary trees, modulo \(998244353\).

Remark. A key idea to solve the problem is to use the exponential generating function. Observe that every forest on \(n\) nodes can be seen as a set of trees. For a tree with \(k\) nodes, the total number of (labeled rooted) trees is \(T(k)=k^{k-1}\) (by Cayley’s formula) while the number of binary trees (i.e. those in which every node has at most 2 children) is denoted by \(A(k)\). Thus if we mark a tree by a weight \(y\) if it is binary and weight \(1\) otherwise, then the weight for a tree of size \(k\) is \[ B(k)=T(k)-A(k)+y\,A(k). \] Using the exponential generating function for trees, the EGF for forests is \[ F(x,y)=\exp\Bigl(\sum_{k\ge1}B(k)\frac{x^k}{k!}\Bigr). \] A dynamic programming in \(x\) (by total nodes) and in \(y\) (by number of binary trees) leads to a solution.

inputFormat

The input consists of a single line containing one integer \(n\) \( (1 \le n \le \text{small})\).

outputFormat

Output \(n+1\) space‐separated integers. The \(i\)th integer (starting from \(i=0\)) denotes the number of forests on \(n\) nodes that contain exactly \(i\) binary trees, taken modulo \(998244353\).

sample

1

0 1