login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144209 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph consists of a single node or has a unique cycle of length 4. 4
1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 0, 15, 60, 1, 0, 0, 0, 45, 360, 1080, 1, 0, 0, 0, 105, 1260, 7560, 20580, 1, 0, 0, 0, 210, 3360, 30240, 164640, 430080, 1, 0, 0, 0, 378, 7560, 90720, 740880, 3873240, 9920232, 1, 0, 0, 0, 630, 15120, 226800, 2469600, 19367460, 99406440, 252000000 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,15

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

FORMULA

T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = 3*C(n-1,3)*n^(n-4) if k=n, else T(n,k) = T(n-1,k) + Sum_{j=3..k-1} C(n-1,j) T(j+1,j+1) T(n-1-j,k-j-1).

EXAMPLE

T(5,4) = 15 = 5*3, because there are 5 possibilities for a single node and T(4,4) = 3:

.1-2. .1-2. .1.2.

.|.|. ..X.. .|X|.

.3-4. .3-4. .3.4.

Triangle begins:

1;

1, 0;

1, 0, 0;

1, 0, 0, 0;

1, 0, 0, 0,  3;

1, 0, 0, 0, 15, 60;

MAPLE

T:= proc(n, k) option remember; if k=0 then 1 elif k<0 or n<k then 0 elif k=n then 3*binomial(n-1, 3)*n^(n-4) else T(n-1, k) +add(binomial(n-1, j) * T(j+1, j+1) *T(n-1-j, k-j-1), j=3..k-1) fi end: seq(seq(T(n, k), k=0..n), n=0..11);

MATHEMATICA

T[n_, k_] := T[n, k] = Which[k == 0, 1, k < 0 || n < k, 0, k == n, 3*Binomial[n-1, 3]*n^(n-4), True, T[n-1, k] + Sum[Binomial[n-1, j]*T[j+1, j+1]*T[n-1-j, k-j-1], {j, 3, k-1}]]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Aug 29 2014, translated from Maple *)

CROSSREFS

Columns 0, 1+2+3, 4 give: A000012, A000004, A050534.

Main diagonal gives A065889.

Row sums give A144210.

Cf. A007318.

Sequence in context: A154721 A185664 A300812 * A094544 A062734 A205531

Adjacent sequences:  A144206 A144207 A144208 * A144210 A144211 A144212

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 14 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 25 15:04 EDT 2019. Contains 326324 sequences. (Running on oeis4.)