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 ∈ 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).