Partitions with initial repetitions Question Solution 2022

Question 2
A k-ary tree is an ordered tree in which every vertex has outdegree either 0 or k. Find the number
of k-ary trees containing exactly n nodes of degree k.
Solution
By ordering the n matches vertically, we may get a permutation of kn elements. Thus, the
number of trees on n+1 vertices is kn !
n ! . Dividing the value by ( k +1 ) n+1 we obtain the following
(Levin, 2016):
The number of possible k −ary trees with n nodes of degree k is
Cn= 1
( k−1 ) n+1 (kn
n )
Question 3
Show that there are k
n ( 2 n−k−1
n−1 ) ordered trees on n+1 vertices whose root has degree k.
Solution
Suppose a tree t ∈ T n has a root of degree k. Then the lattice path l ' (t ) begins with
( 0 , 0 ) → ( 0 , k ) →(1 , k ). The number of admissible paths ( 1 , k ) →( n , n) is by symmetry equal to the
number of admissible paths ( 0 , 0 ) → ( n−k , n−1 ) : k
n ( 2 n−k−1
n−1 )
Question 5
Prove that the number of distinct arrangements of n nonintersecting circles is equal to the
number of rooted unlabelled trees on n+1 vertices.
Solution
Let Bn be the number of distinct arrangements of n nonintersecting circles. There exists one-to-
one correspondence between n nonintersecting circles and an unlabelled rooted tree with n+1