|
Search: id:A131520
|
|
|
| A131520 |
|
Number of partitions of the graph G_n (defined below) into "strokes". |
|
+0
3
|
|
| 2, 6, 12, 22, 40, 74, 140, 270, 528, 1042, 2068, 4118, 8216, 16410, 32796, 65566, 131104, 262178, 524324, 1048614, 2097192, 4194346, 8388652, 16777262, 33554480, 67108914, 134217780, 268435510, 536870968, 1073741882, 2147483708
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
G_n = {V_n, E_n}, V_n = {v_1, v_2, ..., v_n}, E_n = {v_1v_2, v2_v_3, ..., v_{n-1}v_n, v_nv_1}
See the definition of "stroke" in A089243.
A partition of a graph G into strokes S_i must satisfy the following conditions, where H is a digraph on G:
o Union_{i} S_i = H
o i != j => S_i and S_j do not have a common edge
o i != j => S_i U S_j is not a directed path
o For all i, S_i is a dipath
|
|
FORMULA
|
a(n) = 2*(n-1) + 2^n.
G.f.: 2*x*(-1+x+x^2)/(-1+x)^2/(-1+2*x). - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 14 2007
|
|
EXAMPLE
|
Figure for G_4 : o-o-o-o-o Two vertices on both sides are the same.
|
|
MATHEMATICA
|
s=1; lst={}; Do[s+=(n+=s++)-6; AppendTo[lst, Abs[s]], {n, 1, 5!, 2}]; lst [From Vladimir Orlovsky (4vladimir(AT)gmail.com), Nov 15 2008]
|
|
CROSSREFS
|
Cf. A131518, A131519.
Sequence in context: A045964 A005819 A168193 this_sequence A086953 A101953 A084570
Adjacent sequences: A131517 A131518 A131519 this_sequence A131521 A131522 A131523
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Yasutoshi Kohmoto zbi74583(AT)boat.zero.ad.jp, Aug 15 2007
|
|
EXTENSIONS
|
More terms from Max Alekseyev (maxale(AT)gmail.com), Sep 29 2007
|
|
|
Search completed in 0.002 seconds
|
