Discrete Mathematics: K-ary Trees and Generating Functions Assignment

This document presents solutions to a homework assignment in theoretical computer science, focusing on several key concepts. The assignment covers k-ary trees, exploring their properties and enumeration. It includes solutions to problems related to ordered trees and their degree distributions. Furthermore, the assignment delves into generating series, demonstrating their application in proving combinatorial identities and analyzing partitions, specifically those with constraints on divisibility and repetition. The solutions provide detailed explanations, mathematical proofs, and examples to illustrate the concepts. References to relevant literature, such as works by Andrews and Deo, are included to support the presented solutions. The assignment aims to enhance understanding of graph theory, discrete mathematics, and combinatorial analysis through practical problem-solving.

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 ∈ Tn 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

vertices. It is sufficient to draw a circle for each nonroot vertex and insert a circle inside another
one if the second one is the parent of the first one (Deo, 2017).
Question 6
Let an , bn , cn , respectively, be the number of partitions of n in which no part is divisible by 4, no
part appears more than three times, and no even part appears more than once.
a) Sow by example a6=b6 =c6.
The partition of 6 in which no part is divisible by 4 are [ 5+1 ] , [ 3+3 ] ,[3+1+1+1] and
[1+1+1+1+1+1].
The partition of 6 in which no part occur two or more times (both even or odd) are
[ 6 ] , [5+1 ] , [ 4+ 2 ] and [ 3+2+1 ]. There are four of them.
Can take, a6 , b6 and c6 from any of these to fit on conditions.
Thus,
a6={5+1 , 3+3 , 1+1+1+ 1+ 1+1 , 6 , 5+1 ,3+2+ 1}
No part is divisible by 4
b6={5+1 , 3+3 , 3+1+1+1 ,6 , 5+1 , 4 +2 ,3+2+1 }
No part appears more than 3 times.
c6={5+1 ,3+ 3 ,3+1+1+1 , 1+1+ 1+ 1+1+1 , 6 , 3+2+1 }
No even part appears more than once .
b) Prove using generating series that an=bn=cn for all n.
For generating series that an=bn=cn for all n.
For an=bn=cn
Suppose we take generating series as [3 ,5 , 7]
That is, a3=b5 =c7
The partition of 3, 5, 7 in which no part is divisible by 4 and no part appears more than 3
times and no even part appears more than once (Andrews, 2009).
For a3 → [ 2+1 ] , [ 1+1+1 ] ,[3]
For b5 → [ 3+ 2 ] , [ 3+1+1 ] , [2+1+1+1]
For c7 → [ 5+2 ] , [ 5+1+1 ] , [ 3+ 3+1 ] , [3+2+1+1]
Thus,

a3={2+1 , 1+1+1 , 3 }
b5= { 3+2 , 3+1+ 1, 2+1+1+1 }
c7= { 5+ 2, 5+1+1 , 3+3+1 ,3+ 2+ 1+ 1 }
References
Andrews, G.E., 2009. Partitions with initial repetitions. Acta Mathematica Sinica, English Series,
25(9), pp.1437-1442.
Deo, N., 2017. Graph theory with applications to engineering and computer science. Courier
Dover Publications.
Levin, D., Pudwell, L.K., Riehl, M. and Sandberg, A., 2016. Pattern avoidance in k-ary heaps.
Australasian Journal of Combinatorics, 64(1).