Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many undirected graphs with $N+M$ labeled nodes exist where there's only one cycle and it's length is $N$ in such a way that every element of the cycle has at most one tree growing out of it?

Choosing the cycle elements and arranging them can be done in $\left(N-1\right)! {N+M \choose N}$ unique ways.

The rest of the labeled $M$ nodes can be distributed into up to $N$ trees, each of which will be attached to some node of the cycle. Let node $i$ of the cycle have $k_i$ elements grown onto it as a tree, then for every such partition,

$$\sum_{i=0}^N k_i = M$$

The number of tree node choices for every such partition is ${{M} \choose k1 \ldots k_N}$. For a non zero tree ($k_i>0$), there are $k_i^{k_i-2}$ ways to arrange the tree (Cayley's formula) or having picked one of it's nodes as the root, $k_i^{k_i-1}$. For a total of

$$\left(N-1\right)!{{N+M} \choose N}\sum_{k_1+...+k_N=M} \left( {{M} \choose k1 \ldots k_N} \prod_{i,k_i>0} k_i^{k_i-1} \right)$$

Can this expression be simplified? Impossible as it may seem, is a closed formula here possible? Under what nontrivial conditions can it be simplified? What's its asymptotic behavior like? What's the entropy of such a system?


Here's a simple implementation for small $N$, $M$ in the hope of saving others some time,

from itertools import product
from operator import mul

def fact(x, ans=1):
    if x<2: return ans
    else: return fact(x-1, x*ans)

def choose(n, m):
    return fact(n)/(fact(m)*fact(n-m))

def foo(n,m):
    ans = 0
    fact_m = fact(m)

    for num in product(range(m+1), repeat=n):
        if sum(num) == m:
            prod = fact_m
            for x in num:
                if x>0:
                    prod = prod * x**(x-1) / fact(x)
            ans += prod

    return ans * fact(n-1) * choose(n+m, n)

for n in range(1,7):
    print '%d:'%n,
    print ', '.join(str(foo(n,m)) for m in range(1,9))

Resulting in

   m=1  m=2    m=3     m=4      m=5        m=6         m=7           m=8
1: 2    6      36      320      3750       54432       941192        18874368
2: 6    36     300     3360     47250      798336      15731352      353894400
3: 24   240    2760    38640    646800     12628224    281781360     7071989760
4: 120  1800   27720   480480   9510480    213373440   5365206000    149582315520
5: 720  15120  302400  6410880  149052960  3824029440  107915734080  3330566553600
6: 5040 141120 3568320 91324800 2476504800 72313274880 2282004204480 77725396869120

The program and it's results can be found here.


I'm not sure where to put it, so I'll put it here for now. Being unfamiliar with analytic combinatorics (Though I have signed up to the course in Coursea just now :), I can only try to reach the result Marko Riedel shows from the previously stated formula,

$$\left(N-1\right)!{{N+M} \choose N}\sum_{k_1+...+k_N=M} \left( {{M} \choose k1 \ldots k_N} \prod_{i,k_i>0} k_i^{k_i-1} \right)$$

by rewriting it as

$$\frac{(M+N)!}{N} \sum_{k_1+...+k_N=M} \left( \prod_{i,k_i>0} \frac{k_i^{k_i-1}}{k_i!} \right)$$

Wanting to express the sum as the $[X_M]$th element of the $N$th power of a formal series, as $k$s can be $0$ we rewrite t as

$$ \frac{(M+N)!}{N} \cdot [x_M] \left(1 + \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k \right)^N = \frac{(M+N)!}{N} \cdot [x_M] \left(1 - W(-x)\right)^N$$

Where $W$ is the Lambert W function. Yes hindsight is nice... :)


Somewhat similar interesting problems are:

(1) The same problem removing the restriction of growing a single tree onto every node of the cycle. This is the same as asking for the number of undirected graphs with $N+M$ labeled nodes where only a single cycle exists and it's length is $N$.

$$\frac{(N+M)!}{N} \sum_{k_1+\ldots+k_N=M}\prod_{i,k_i>0}\left(N\frac{k_i^{k_i-1}}{k_i!}\right)$$

(2) The same problem but having the cycle already in place. That is the amount of ways to grow $M$ labeled nodes as trees (One per cycle node at most) onto a given cycle of length $N$.

$$M! \sum_{k_1+\ldots +k_N=M}\prod_{i,k_i>0} \frac{k_i^{k_i-1}}{k_i!}$$

(3/4) The same problem having the labeled cycle already in place but the trees being grown onto it (Either with the restriction of one tree at most per cycle node or without) are unlabeled.

share|improve this question
    
Thanks for sharing. Are you sure we are counting the same structures? For example, for $N=3$ and $M=1$ your table has $3$. That looks to me like undercounting. You choose the label of the singleton tree (recall that $M=1$) and the label where it is attached to the cycle, giving $12$ possibilities. There are two possibilities to label the remaining vertices on the cycle, giving $12 \times 2 = 24 > 3.$ –  Marko Riedel Jan 26 '13 at 23:23
    
I think I understand what you meant - You pick both the elements of the cycle and those outside of it from a marked $N+M$ size collection and create the graphs. I was thinking that the cycle was a given constant. Looking at the problems wording again, I think you interpretation makes more sense. –  Guest 86 Jan 27 '13 at 0:42
    
You got it. Very kind. You originally wrote that the cycle was labeled too, that's why I picked this interpretation. –  Marko Riedel Jan 27 '13 at 0:45
    
I will look into this a bit later and we can continue tomorrow. –  Marko Riedel Jan 27 '13 at 0:55
    
I've rewritten the problems formulation and put a new program up. The results still differ from the ones you've shown (See ideone.com/j7Ucya ). I'm not sure if it's an algorithmic problem, me being new to python or if we're still talking of different structures... :/ –  Guest 86 Jan 27 '13 at 11:35
add comment

4 Answers

up vote 3 down vote accepted

Here are some ideas which, even though they do not completely answer your question, might help you make progress toward a complete solution.

Use exponential generating functions as we are working with labelled structures. The combinatorial class $\mathcal{Q}$ that we are investigating is quite simple, it is given by $$\mathcal{Q} = \mathfrak{C}_N (\mathcal{Z} \times (\epsilon + \mathcal{T}))$$ where $\mathcal{T}$ is the class of rooted labeled trees. This specification reflects the fact that the graphs in $\mathcal{Q}$ are cycles of doubly rooted trees (there is a marked node attached to the root of an ordinary rooted tree), where the topmost roots form the cycle.

Translating to generating functions we obtain $$ Q(z) = \frac{\left( z \, (1 + T(z) ) \right)^N}{N},$$ where $T(z)$ is the generating function of rooted labelled trees, with specification $$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T}),$$ which yields the well-known functional equation $$ T(z) = z\,e^{T(z)},$$ whose solution is $$ T(z) = -\operatorname{LambertW}(-z),$$ in terms of the Lambert $W$ function (short form $W(z).$)

It follows that we have $$Q(z) = \frac{\left( z \, (1 - W(-z) ) \right)^N}{N}.$$ The answer $q_{N,M}$ that we are looking for is then given by the following coefficient extraction operation: $$ q_{N,M} = (M+N)! [z^{M+N}] \frac{\left( z \, (1 - W(-z) ) \right)^N}{N} = (M+N)! [z^M] \frac{(1 - W(-z) )^N}{N}.$$

While I don't have a closed form expression yet, it appears that the coefficient $[z^M] (1 - W(-z) )^N$ can be calculated.

Here is a list of the first few values for $N$ from one to six. $$ \begin{align} [z^M] (1-W(-z))^1 & = {\frac {{M}^{M-2}}{ \left( M-1 \right) !}} \\ [z^M] (1-W(-z))^2 & = 2\,{\frac {{M}^{M-3} \left( 2\,M-1 \right) }{ \left( M-1 \right) !}} \\ [z^M] (1-W(-z))^3 & = {\frac {{M}^{M-4} \left( 12\,{M}^{2}-15\,M+6 \right) }{ \left( M-1 \right) !}}\\ [z^M] (1-W(-z))^4 & = 4\,{\frac {{M}^{M-5} \left( 4\,M-3 \right) \left( 2\,{M}^{2}-3\,M+2 \right) }{ \left( M-1 \right) !}}\\ [z^M] (1-W(-z))^5 & = {\frac {{M}^{M-6} \left( 80\,{M}^{4}-280\,{M}^{3}+455\,{M}^{2}-370\,M+120 \right) }{ \left( M-1 \right) !}}\\ [z^M] (1-W(-z))^6 & = {\frac {{M}^{M-7} \left( 192\,{M}^{5}-960\,{M}^{4}+2340\,{M}^{3}-3210\,{M}^{2}+2364\,M-720 \right) }{ \left( M-1 \right) !}}\\ \end{align}$$ This yields the following closed form expressions for $q$: $$\begin{align} q_{1, M} & = {M}^{M-1} \left( M+1 \right) \\ q_{2. M} & = {M}^{M-2} \left( 2\,M-1 \right) \left( M+1 \right) \left( M+2 \right) \\ q_{3, M} & = {M}^{M-3} \left( 4\,{M}^{2}-5\,M+2 \right) \left( M+1 \right) \left( M+2 \right) \left( M+3 \right) \\ q_{4, M} & = {M}^{M-4} \left( 4\,M-3 \right) \left( 2\,{M}^{2}-3\,M+2 \right) \left( M+1 \right) \left( M+2 \right) \left( M+3 \right) \left( M+4 \right) \\ q_{5, M} & = {M}^{M-5} \left( 16\,{M}^{4}-56\,{M}^{3}+91\,{M}^{2}-74\,M+24 \right) \\ & * \left( M+1 \right) \left( M+2 \right) \left( M+3 \right) \left( M+4 \right) \left( M+5 \right) \\ q_{6, M} & = {M}^{M-6} \left( 32\,{M}^{5}-160\,{M}^{4}+390\,{M}^{3}-535\,{M}^{2}+394\,M-120 \right) \\ & * \left( M+1 \right) \left( M+2 \right) \left( M+3 \right) \left( M+4 \right) \left( M+5 \right) \left( M+6 \right) \end{align}$$ The structure here is obvious except for the polynomial in the center of these expressions, and even this is not quite hopeless since the leading and trailing coefficients look doable. The case $q_{1,M}$ is trivial, as it consists of a rooted tree on $M$ nodes attached to a cycle of size one, a singleton node.

It appears we have the asymptotic result that $$ q_{N,M} \sim M^{M-N} 2^{N-1} M^{N-1} \frac{(M+N)!}{M!} = 2^{N-1} M^{M-1} \frac{(M+N)!}{M!}.$$ The term $\frac{M^{M-1}}{M!}$ simplifies nicely using Stirling's expansion.

The reader is invited to continue this investigation. To do: I, verify independently that the generating function gives the correct model of the problem, II, spot the pattern in the results and III, formulate and prove a theorem.

Credit goes to the OEIS for spotting the patterns in these sequences.

share|improve this answer
    
I cannot follow through with your logic, I have little experience with this subject and reading up on it I've stumbled on a few things and I cannot spend the time needed to study it until after the tests but hopefully I will be able to do it afterwards. Thank you for the effort. (My apologies) –  Guest 86 Jan 24 '13 at 23:22
    
Why don't you post your algorithm, I believe this is what SE is for. An algorithm is easier to evaluate than a series of numbers. Thanks! –  Marko Riedel Jan 26 '13 at 20:47
    
So as structures, $\mathfrak{C}_N$ is cycles of length $N$, and $\mathcal{Z}$ is "split one point from the rest", and $\epsilon$ is the empty set, and $\mathfrak{P}(T)$ is partitions into rooted labelled trees. This is just inferred from the generating function computations. –  zyx Jan 30 '13 at 1:10
    
This article on symbolic combinatorics has a complete list of the operators and an introduction to the method. –  Marko Riedel Jan 30 '13 at 1:12
    
I'm familiar with the method but did not know of any standardized notation for the different species. In fact, I had checked Bergeron's book, which is the reference cited in the article, using books.google.com and its list of common structures did not include \epsilon. But it can be figured out from the computations, so no problem (assuming the decoding is correct). –  zyx Jan 30 '13 at 1:19
show 8 more comments

Treating problem number one proposed at 2pm CET 01/28/13 we find that the specification of the corresponding combinatorial class $\mathcal{Q}_1$ is $$ \mathcal{Q}_1 = \mathfrak{C}_N(\mathcal{Z} \times \mathfrak{P}(\mathcal{T})) $$ giving the generating function $$ Q_1(z) = \frac{(z \exp T(z))^N}{N} = \frac{T(z)^N}{N}.$$ This reflects the well-known bijection between ordinary trees and rooted ones. As above, the answer $q_{N,M}$ that we are looking for is then given by the following coefficient extraction operation: $$ q_{N,M} = (M+N)! [z^{M+N}] \frac{(- W(-z))^N}{N}.$$

I don't have a closed form for the above yet. Can someone confirm these for me? It is possible to construct a recurrence, however. We have $$\frac{q_{N,M} N}{(M+N)!} = [z^{M+N}] \left( - W(-z) \right)^N = \sum_{k=N-1}^{M+N-1} [z^k] \left(- W(-z) \right)^{N-1} [z^{M+N-k}] \left( - W(-z) ) \right) = \sum_{k=0}^M [z^{k+N-1}] \left(- W(-z) \right)^{N-1} [z^{M-k+1}] \left( - W(-z) ) \right). $$ The sum is $$\sum_{k=0}^M \frac{q_{N-1,k} (N-1)}{(k+N-1)!} [z^{M-k+1}] \left( - W(-z) \right) = \sum_{k=0}^M \frac{q_{N-1,k} (N-1)}{(k+N-1)!} \frac{(M-k+1)^{M-k}}{(M-k+1)!}$$ This yields the recurrence $$ q_{N, M} = \frac{(M+N)!}{N} \sum_{k=0}^M \frac{q_{N-1,k} (N-1)}{(k+N-1)!} \frac{(M-k+1)^{M-k}}{(M-k+1)!}.$$ The base cases are $N=1$, when we have a rooted tree on $M+1$ nodes, giving $q_{1,M} = (M+1)^M$ and $M=0$, when we have a cycle on $N$ nodes, giving $N!/N = (N-1)!.$ It would be interesting to know if this recurrence has a combinatorial proof.

We really ought to compute the asymptotics of the generating function coefficients, that is where the real challenge lies. We need a detailed examination of the structure of the recurrence above. The asymptotics of the second term in the inner product look doable.

This is the Maple code.

solve(T=z*exp(T), T);
Tv := %;
cf := (N, M) -> (M+N)!*coeftayl(Tv^N/N, z=0, M+N);

Q :=
proc(N, M)
        if M=0 then return (N-1)! fi;
        if N=1 then return (M+1)^M fi;

        (M+N)!/N*
        add(Q(N-1,k)*(N-1)/(k+N-1)!*(M-k+1)^(M-k)/(M-k+1)!, k=0..M);
end;
share|improve this answer
    
Now that I think about it, if we introduce $$r_{N,M} = q_{N,M} \frac{N}{(M+N)!}$$ the recurrence suddenly looks highly tractable, giving $$ r_{N,M} = \sum_{k=0}^M r_{N-1,k} \frac{(M-k+1)^{M-k}}{(M-k+1)!}.$$ –  Marko Riedel Jan 29 '13 at 2:55
    
Sorry for the silly question, but in the first sum: $\sum_{k=N-1}^{M+N-1}$, why isn't the lower bound $k=1$? –  Guest 86 Jan 29 '13 at 19:11
    
Actually, are we still thinking of the same problem? A graph over labeled N+M nodes where exactly one cycle exists and it's length is N? Unless I'm missing something obvious, I cannot see if the formula I wrote in the question is the same as your $q_{N,M}$. –  Guest 86 Jan 29 '13 at 19:30
    
I am fairly confident that my formula is right, but I will look into this. The lower bound is $N-1$ because $-W(-z)$ has no constant terms and hence all the coefficients of $(-W(-z))^{N-1}$ of degree less than $N-1$ are zero. Are you sure you are not confusing circular with dihedral symmetry? I am using circular symmetry. –  Marko Riedel Jan 29 '13 at 20:02
    
@Guest86 If you would move some of your commentary from the original post into a separate message that would make it easier for me to award the bounty. –  Marko Riedel Jan 30 '13 at 0:52
add comment

This answer is to exibit a certificate that shows that the proposed decomposition and the algorithm in Python are probably incorrect or at any rate not referring to the same combinatorial structure. (This message refers to the state of the question as of 11pm CET 01/27/13.) The Python code proposes that $$q_{3,3} = 2400$$ whereas my formula gives $$q_{3,3} = 2760.$$

We can calculate $q_{3,3}$ by hand. There are four cases:

  • three-node path attached somewhere on the cycle
  • balanced three-node tree attached somewhere on the cycle
  • two-node path and singleton tree attached at two different points on the cycle
  • three singleton trees attached to three nodes on the cycle.

This is the enumeration.

  • choose three nodes for the cycle, which is now considered marked by the path attached to it, giving $${6\choose 3} \times 3! \times 3! = 720$$
  • choose the three nodes for the cycle, now marked, and attach one of three trees, giving $${6\choose 3} \times 3! \times 3 = 360$$
  • choose the three nodes for the cycle, now marked, choose one of three points to attach the two-node path and one of two to attach the singleton, there are two possibilities to label the two-node path, giving $${6\choose 3} \times 3! \times 3 \times 2 \times 2 = 1440$$
  • choose three pairs of nodes from the six and one of two orientations for each pair, taking into account the rotational symmetry, giving $${6\choose 2,\,2, \,2} 2^3/3 = 240.$$ The total is $$ 720 + 360 + 1440 + 240 = 2760.$$
share|improve this answer
    
My apologies, using the formula I've written, it's $2\cdot 20(27+36+6) = 2760$, the program must be wrong, I'll look into it... Sorry. –  Guest 86 Jan 27 '13 at 22:26
    
prod *= x**(x-1) / fact(x) was wrong: the rhs is 9/6 and suffers from int rounding... I was thinking this is always dividable because of the initial value of prod. I'll replace it with prod = prod * x**(x-1) / fact(x), it should solve the problem... really sorry :) –  Guest 86 Jan 27 '13 at 22:34
    
So once we agree on the problem definition we could try to prove a recurrence for $q_{N,M}$ in terms of $q_{N-1,M}, q_{N-2,M} \ldots$ or maybe even tackle the asymptotic formula. –  Marko Riedel Jan 27 '13 at 22:37
    
Looks good, I checked several cases and they all agree with what I have. –  Marko Riedel Jan 27 '13 at 23:16
    
I've added a short demonstration that the formula I wrote and used in the program is the same as the generating function you got, to the question! So that rounding mistakes and such ignored, the results should be always identical... =) –  Guest 86 Jan 28 '13 at 0:22
add comment

In response to the query from 9pm CET 01/29/13 concerning the case where multiple trees can be attached to a single node of the cycle (as opposed to at most one per node), I offer some evidence that my generating function is correct. First, we must include the cases of at most one tree attached to a node on the cycle, which we already calculated and found to be $$2760.$$

Now there are three more cases:

  • three singleton trees attached to a single node from the cycle
  • two singleton trees attached to a single node from the cycle, with the remaining singleton attached to some other node
  • a singleton tree and a path on two nodes attached to a single node from the cycle.

This is the enumeration.

  • choose three nodes for the cycle, now considered marked; choose one of three points to attach the singletons, take rotational symmetry into account, giving $$ {6\choose 3} \times 3! \times 3 /3 = 120$$

  • choose three nodes for the cycle, now considered marked; choose one point to attach the two singletons and another for the remaining singleton, choose two labels for the two singletons, take rotational symmetry into account, giving $$ {6\choose 3} \times 3! \times 3 \times 2 \times {3\choose 2} /3 = 720$$

  • choose three nodes for the cycle, now considered marked; choose two labels for the tree on two nodes, which produces two pairs, take rotational symmetry into account, giving $$ {6\choose 3} \times 3! \times {3\choose 2} \times 2 /3 = 720$$

so that the grand total is $$2760 + 120 + 720 + 720 = 4320$$ which agrees with the value $q_{3,3}$ from the above discussion.

The generating function that I used as a guide to prepare the above listing is $$Q_{1;3}(z;u,v,w) = \frac{(z\exp(-z + u z -z^2 + v z^2 - 3/2 z^3 + 3/2 w z^3 + T(z))^3}{3}.$$ We have $$6! [z^6] Q_{1;3}(z;u,v,w) = 2160\,uv+1080\,{u}^{3}+1080\,w.$$ The same marking technique can be employed with the generating function from the original question, giving $$Q_3(z;u,v,w) = \frac{\left(z \times (1 -z + u z -z^2 + v z^2 - 3/2 z^3 + 3/2 w z^3 + T(z)) \right)^3}{3}.$$ We have $$6! [z^6] Q_{3}(z;u,v,w) = 1080\,w+1440\,uv+240\,{u}^{3}.$$ This says that e.g. enabling more than one tree per node of the cycle introduced $1080-240 = 840$ new graphs containing three singleton trees where more than one singleton is on the same node of the cycle, and that is indeed the value derived above.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.