It is ok to post! # Name:Treasa Bency Biju Jose # Date: 12-15-2020 # Combinatorics Finals ===================================================================================================================================================== 1. (a) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0], or [0,0,1] NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}); 2478456799816702091914145225486880 ------------------------------------------------------------------------------------------------------------------------------------------------ (b) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0], or [0,0,1] and you MUST stay in the region x>=y>=z [Hint: this is part of the 3D ballot problem, you are welcome to look it up.] NuGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}); 41512613892711511465063226481480 ------------------------------------------------------------------------------------------------------------------------------------------------ (c) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0],[0,0,1], [1,1,1], or [2,2,2] NuW([30, 25, 20], {[1, 1, 1]}) + NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 1, 1]}) + NuW([30, 25, 20], {[2, 2, 2]}); 0 ------------------------------------------------------------------------------------------------------------------------------------------------ (d) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0],[0,0,1], [1,1,1], or [2,2,2] and you must stay in x>=y Union x>=z (but y and z can be anything as long as they are both <=x) NuGW := proc(Pt, A) local a; option remember; if Pt[1] < 0 or Pt[2] < 0 or Pt[3] < 0 or (Pt[1] < Pt[2]) and (Pt[1] < Pt[3]) then RETURN(0); elif Pt = [0, 0, 0] then RETURN(1); else add(NuGW(Pt - a, A), a in A); end if; end proc NuGW([30, 25, 20], {[1, 0, 0]}) + NuGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 1, 1]}) + NuGW([30, 25, 20], {[2, 2, 2]}); 0 ------------------------------------------------------------------------------------------------------------------------------------------------ (e) In how many ways can you walk, in the k-dimensional hyper-cubic lattice (the k-DIm Manhattan) from [0,0,..., 0] (with k 0's) to [n,n,....n] (with k n's) always staying in the region x[1]>=x[2]>=... >=x[k]. For example with n=1 there is only one way [0,0,...0]->[1,0,...0]->[1,1,0,...]->...->[1,1,1,1,1] Give an explicit formula in terms of n and k. ===================================================================================================================================================== 2. (a) How many words in the alphabet {0,1,2,3} are there of length 30? L := seq(nops(Words({0, 1, 2, 3}, i)), i = 1 .. 10); L := 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576 with(gfun); guessgf([L], x); [ 4 ] [--------, ogf] [-4 x + 1 ] coeff(taylor(4/(-4*x + 1), x = 0, 32), x^30); 4611686018427387904 ------------------------------------------------------------------------------------------------------------------------------------------------ (b) How many words in the alphabet {1,2,3,4} are there that add-up to 300? GFseq(CompsGF({1, 2, 3, 4}, x), x, 300)[301]; 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 ------------------------------------------------------------------------------------------------------------------------------------------------ (c) How many words are there in the alphabet {1,2,3,....} (all positive integers) that add-up to n? For general n. Give an explicit formula. ------------------------------------------------------------------------------------------------------------------------------------------------ (d) Let a(n) be the number of words in the alphabet {1,4,7,10,....} (all positive integers that give remainder 1 when divided by 3) that add-up to n. Find an explicit expression for Sum(a(n)*x^n,n=0..infinity) ------------------------------------------------------------------------------------------------------------------------------------------------ (e) Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity. ===================================================================================================================================================== 3. (a) What is the egf enumerating set-partitions. exp(exp(x)-1) How many are there of the set {1,2,...,51}? egf := exp(exp(x) - 1)*exp(exp(x) - 1); coeff(taylor(egf, x = 0, 52), x, 51)*51!; 958885193611127267829688989103376399915484429211486342 ------------------------------------------------------------------------------------------------------------------------------------------------ (b) What is the egf enumerating set partitions where the number of components belongs to {1,4,7,10,...}, but the components themselves can be of any (positive, of course) size. How many are there of the set {1,2,...,51}? a := proc(n) local L, count, i; L := [2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51]; count := 0; for i to nops(L) do sinh(exp(x) - 1 - x^i/i!); count := count + coeff(taylor(egf, x = 0, 52), x, 51)*51!; end do; end proc; a(n); 55487733349947011945807735082218048028733151763780 ------------------------------------------------------------------------------------------------------------------------------------------------ (c) What is the egf enumerating set partitions where the number of components can be any non-negative integer but the components themselves must be of odd size. How many are there of the set {1,2,...,51}? coeff(taylor(add(x^(2*i + 1)/(2*i + 1)!, i = 0 .. 25), x = 0, 52), x, 51)*51!; 1 ------------------------------------------------------------------------------------------------------------------------------------------------ (d) What is the egf enumerating set partitions are there where the number of components belongs to {1,4,7,10,... and and the components themselves must be of odd size. How many are there of the set {1,2,...,51}? a := proc(n) local L, count, i; L := [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52]; count := 0; for i to nops(L) do count := count + coeff(taylor(add(x^(2*i + 1)/(2*i + 1)!, i = 0 .. 25)^i/i!, x = 0, 52), x, 51)*51!; end do; end proc; a(n); 96301098418978556806144289897903023397401765 ===================================================================================================================================================== 4. Define a super-set-partition of order 2 to be a set of set partitions {P1,P2, ...,Pk} where k can be any positive integer and P1,P2,..., Pk are set partitions such that the labels in each of P1,P2,..,Pk are all different and altogether there n members. For example {{{2,4},{6}}, {{1},{5},{3}}} is such a creature with n=6, as is {{1}}, {{2}},{{3}},{{4}},{{5}},{{6}}}, and many others. Let s[2](n) be the number of such creatures. (a) Write all super-set partitions with n=3. {{{1, 2, 3}}, {{1}, {2, 3}}, {{2}, {1, 3}}, {{3}, {1, 2}}, {{1}, {2}, {3}}} ------------------------------------------------------------------------------------------------------------------------------------------------ (b) What is Sum(s[2](n)*x^n/n!, n=0..infinity)? Is s[2](n) in the OEIS? seq(s[2](n), n = 0 .. 9); 0, 1, 2, 5, 15, 52, 203, 877, 4140, 21147 It is in the OEIS. A-number := A000110 ------------------------------------------------------------------------------------------------------------------------------------------------ (c) Define a super-set-partition of order m to be a set of set-partitions of order m-1 all with different labels such that total of individuals is n. Let s[m](n) be the number of such creatures. What is the smallest m for which it is NOT in the OEIS? ===================================================================================================================================================== 5. (a) How many integer partitions are there of 1000? pn(1000); 24061467864032622473692149727991 ------------------------------------------------------------------------------------------------------------------------------------------------ (b) How many integer partitions of 1000 are there where all the parts are odd? pnC(1000,{1},2); 8635565795744155161506 ------------------------------------------------------------------------------------------------------------------------------------------------ (c) How many integer partitions of 1000 are there where all the parts are different than each other? pnD(1000, 1); 8635565795744155161506 ------------------------------------------------------------------------------------------------------------------------------------------------ (d) How many integer partitions of 1000 are there where all the parts are different than each other and all the parts are odd. pnkDC := proc(n, k, C, m, d) local k1, S; option remember; if n < k then RETURN(0); end if; if k = n then if member(k mod m, C) then RETURN(1); else RETURN(0); end if; end if; if n = 1 then if member(1, C) and k = 1 then RETURN(1); else RETURN(0); end if; end if; if not member(k mod m, C) then RETURN(0); end if; S := 0; for k1 to k - d do if member(k1 mod m, C) then S := S + pnkDC(n - k, k1, C, m, d); end if; end do; S; end proc; pnDC := proc(n, d, C, m) local k; add(pnkDC(n, k, C, m, d), k = 1 .. n); end proc; pnDC(1000, 1, {1}, 2); 517035762467311 ===================================================================================================================================================== 6. (a) How many rooted labelled trees are there with 31 vertices? L:= TreeSeq(32): L[31] 17761887753093897979823770061456102763834271 ------------------------------------------------------------------------------------------------------------------------------------------------ (b) How many rooted labelled trees are there with 31 vertices where the root has exactly two children. coeff(TreeSeqL(31, t)[31], t^2); 1788467407283698212855309926400000000 ------------------------------------------------------------------------------------------------------------------------------------------------ (c) How many rooted labelled trees are there with 31 vertices where each vertex must have either zero, one, three, or four children. SeqRTchild:=proc(S,N) local eq, s, L: eq := 1: for s in S do eq := eq + (z^s / s!): od: L := FunEqToSeq(eq, z, N): [seq(L[n]*n!, n = 1..N)]: end: SeqRTchild({0, 1, 3, 4}, 31)[31]; 2881718802782387225562210536898177269760000000 ------------------------------------------------------------------------------------------------------------------------------------------------ (d) How many rooted labelled trees are there with 31 vertices where each vertex can have any number of children (including no children, of course) EXCEPT that it can't have one, three, or four children. SeqRTchildNone:=proc(S,N) local eq, s, L: eq := exp(z): for s in S do eq := eq - (z^s / s!): od: L := FunEqToSeq(eq, z, N): [seq(L[n]*n!, n = 1..N)]: end: SeqRTchildNone({1, 3, 4}, 31)[31]; 2863465748628395267057869436794752181 ===================================================================================================================================================== 7. A complete (unlabelled, ordered) BINARY tree is defined recursively by T= [] (denoting a single vertex, just the root) or otherwise T=[T1,T2] where T1, T2, are smaller such creatues. Let BT(n) be the number of such creatues with n leaves. For example BT(1)={[]}; BT(2)={[[],[]]}; BT(3)={[[], [[], []]], [[[], []], []]} (a) Either by hand, or with Maple, find BT(4). BT(4) := {[[], [[], []]], [[[], []]], []], [[[[]], [[], []], [[[], []]], [[[[], []]]]} ------------------------------------------------------------------------------------------------------------------------------------------------ (b) Let b(n) be the number of complete binary trees with n leaves. For example b(1)=1, b(2)=1, b(3)=2. Let B(x)=Sum(b(n)*x^n,n=0..infinity) Prove that B(x)=x+ B(x)^2 =====================================================================================================================================================