# OK to post homework
# Robert Dougherty-Bliss
# 2021-02-14
# Assignment 8

# 1.

with(combinat):

# The new approach was to pick the neighbors of n, then partition the remaining
# elements recursively.

SPnF := proc(n)
    possible_partners := [seq(choose(n - 1, k), k=0..n-1)]:

    res := []:

    for k from 0 to n - 1 do
        for partners in possible_partners[k + 1] do
            part := {op(partners), n}:
            rest := SPnF(n - 1):
        od:
    od:
end:

# 2.

# I could use a refresher!

# An exponential generating function is something of the form

#       sum(a(k) / k! * x^k, k >= 0).

# They are good at counting / manipulating / gluing together labeled objects.

# Suppose that we have two classes of labeled objects, A and B.
# Every object in B is made up of "connected components" of some sizes in A.
# That is, you take some "atomic" things from A, relabel them, glue them
# together, and you get something in B.

# Then the egf of B, i.e., the egf of a(n) = number of things of size n in B,
# is exactly exp(egf(A)).

# This is a special case of a more general result that you can find in
# generatingfunctionology, Chapter 3.

# 3.

# This is an application of the previous theorem!

# "Labeled graphs" are made up of "labeled, connected graphs." Thus,

#   egf(labeled graphs graphs) = exp(egf(labeled, connected graphs)),

# which gives

#       egf(labeled, connected graphs) = log(egf(labeled graphs)).

# How many labeled graphs on there with n vertices? Exactly 2^(binomial(n, 2)).
# This is why the egf of "labeled, connected graphs" is what Dr. Z claims it
# is.


A := sum(2^(binomial(n, 2)) * x^n / n!, n=0..infinity):
terms := taylor(log(A), x, 30):
terms := [seq(k! * coeff(terms, x, k), k=0..29)];

# This is, of course, in the OEIS: A1187.

# 4.

# Actually, I'm not quite convinced. (I'm always a little confused about
# weighted generating functions. Here's what I manage to work out every time
# before I get confused.)

# A *weighted* egf for a sequence a(k) is of the form

#   sum(a(k) * / k! * c(k), k >= 0),

# where c(k) satisfies c(u + v) = c(u) c(v). [You could take, for example, c(k)
# = x^k to recover the usual definition.] The important thing is that the
# standard theorem for exponential generating functions still works when you
# use arbitrary weights.

# Let B_n(a) be the ogf of a(k) = # of labeled graphs on n vertices with k
# edges. Then

#   B_n(a) = sum(binomial(binomial(n, 2), k) * a^k, k)
#          = (1 + a)^(binomial(n, 2)).

# Now let P_n(a) be the ogf of a(k) = "number of connected, labeled graphs on
# exactly k edges," which is a polynomial of degree binomial(n, 2).

# Now, for some reason, we can apply the exponential theorem to B_n(a) and
# P_n(a)! This is what I don't understand...

# 5.

# ...but I'll still use it.

NuCG := proc(n, k)
    rhs_gf := sum((1 + a)^(i * (i - 1) / 2) * x^i / i!, i=0..infinity):
    xn_coeff := n! * coeff(taylor(log(rhs_gf), x, n + 1), x, n):

    coeff(xn_coeff, a, k):
end:

# NuCG(n, n - 1) appears to be A272.
# After some thought, of course it is! A connected graph on n vertices is a
# tree iff it has n - 1 edges.

rSeq := r -> seq(NuCG(n, n + r), n=1..10);

# It looks like these sequences do not appear for r >= 12 (as of 2021-02-21).
# I'll let someone else claim the honor of posting a new sequence :)