A131520 -id:A131520 - cp's OEIS frontend

A131518 Number of partitions of the graph G_n (defined below) into "strokes".

2, 6, 14, 122, 362, 5282, 20582, 397154, 2027090, 46177922, 303147902, 7699478162, 63517159994, 1745540360930, 17676592058582, 517137940132802, 6290714838241442, 194139271606482434, 2782486941099788270, 90105513853333901042, 1495993248737211995402, 50671468195931300884322

Offset: 1

Yasutoshi Kohmoto, Aug 15 2007, Oct 03 2007

nonn

Here G_n = {V_n, E_n}, V_n = {v_1, v_2}, E_n = {e_1, e_2, ..., e_n}; for all i, e_i = v_1v_2.

Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii) union of corresponding undirected paths is E.

			G_2 : o=o, two edges exist between v_1 and v_2.

G. C. Greubel, Table of n, a(n) for n = 1..440
R. J. Mathar, Explanation of the Alekseyev formula

Cf. A131520, A354228.

f[n_, k_]:= If[EvenQ[n-k], Binomial[(n+k)/2, k], 0];
A088009[n_]:= n!*Sum[f[n-1, k-1]/k!, {k, 0, n}];
A131518[n_]:= If[EvenQ[n], 2*A088009[n] + n!*(n/2 +1), 2*A088009[n]];
Table[A131518[n], {n,1,30}] (* G. C. Greubel, Feb 14 2021 *)

def f(n, k): return binomial((n+k)/2, k) if (n-k)%2==0 else 0
def A088009(n): return factorial(n)*sum(f(n-1, k-1)/factorial(k) for k in (0..n))
def A131518(n): return 2*A088009(n) + (n/2 +1)*factorial(n) if (n%2==0) else 2*A088009(n)
[A131518(n) for n in (1..30)] # G. C. Greubel, Feb 14 2021

For odd n, a(n)=2*A088009(n); for even n, a(n)=2*A088009(n)+n!*(n/2+1). The first term stands for partitions with paths starting and ending in different vertices. The second term (that exists only for even n) stands for partitions with paths starting and ending at the same vertex (there are at most 2 such paths starting and ending in v_1 and v_2 respectively, each path consists of even number of edges). - Max Alekseyev, Sep 29 2007

More terms from Max Alekseyev, Sep 29 2007

A173740 Triangle T(n,k) = binomial(n,k) + 2 for 1 <= k <= n - 1, n >= 2, and T(n,0) = T(n,n) = 1 for n >= 0, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 5, 5, 1, 1, 6, 8, 6, 1, 1, 7, 12, 12, 7, 1, 1, 8, 17, 22, 17, 8, 1, 1, 9, 23, 37, 37, 23, 9, 1, 1, 10, 30, 58, 72, 58, 30, 10, 1, 1, 11, 38, 86, 128, 128, 86, 38, 11, 1, 1, 12, 47, 122, 212, 254, 212, 122, 47, 12, 1, 1, 13, 57, 167, 332, 464, 464, 332, 167, 57, 13, 1

Offset: 0

Roger L. Bagula, Feb 23 2010

For n >= 1, row n sums to A131520(n).

			Triangle begins:
  1;
  1,  1;
  1,  4,  1;
  1,  5,  5,   1;
  1,  6,  8,   6,   1;
  1,  7, 12,  12,   7,   1;
  1,  8, 17,  22,  17,   8,   1;
  1,  9, 23,  37,  37,  23,   9,   1;
  1, 10, 30,  58,  72,  58,  30,  10,  1;
  1, 11, 38,  86, 128, 128,  86,  38, 11,  1;
  1, 12, 47, 122, 212, 254, 212, 122, 47, 12, 1;
  ...

G. C. Greubel, Rows n = 0..100 of the triangle, flattened

Cf. A100314, A103451, A131520, A156050.

Sequences of the form binomial(n, k) + q: A132823 (q=-2), A132044 (q=-1), A007318 (q=0), A132735 (q=1), this sequence (q=2), A173741 (q=4), A173742 (q=6).

T:= func< n,k | k eq 0 or k eq n select 1 else Binomial(n,k) + 2 >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Feb 13 2021

T[n_, m_] = Binomial[n, m] + 2*If[m*(n - m) > 0, 1, 0];
Flatten[Table[T[n, m], {n, 0, 10}, {m, 0, n}]]

T(n,k) := if k = 0 or k = n then 1 else binomial(n, k) + 2$
create_list(T(n, k), n, 0, 12, k, 0, n); /* Franck Maminirina Ramaharo, Dec 08 2018 */

def T(n, k): return 1 if (k==0 or k==n) else binomial(n, k) + 2
flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Feb 13 2021

From Franck Maminirina Ramaharo, Dec 08 2018:(Start)
T(n,k) = A007318(n,k) + 2*(1 - A103451(n,k)).
T(n,k) = 3*A007318(n,k) - 2*A132044(n,k).
n-th row polynomial is 1 - (-1)^(2^n) + (1 + x)^n + 2*(x - x^n)/(1 - x).
G.f.: (1 - (1 + x)*y + 3*x*y^2 - 2*(x + x^2)*y^3)/((1 - y)*(1 - x*y)*(1 - y - x*y)).
E.g.f.: (2 - 2*x + 2*x*exp(y) - 2*exp(x*y) + (1 - x)*exp((1 + x)*y))/(1 - x). (End)
Sum_{k=0..n} T(n, k) = 2^n + 2*(n - 1 + [n=0]) = 2*A100314(n). - G. C. Greubel, Feb 13 2021

Edited and name clarified by Franck Maminirina Ramaharo, Dec 08 2018

A354228 Number of partitions of the multigraph G_n (defined below) into "strokes".

Original entry on oeis.org

1, 6, 58, 578, 5766, 57810, 580310, 5829538, 58575686, 588641522, 5915670070, 59451845314, 597489270438, 6004768803090, 60348023150742, 606498938168290, 6095328830488582, 61258206225329970, 615646518692614390, 6187263150038580994

Offset: 1

Yasutoshi Kohmoto and Max Alekseyev, Jul 18 2022

nonn

Here G_n = {V_n, E_n}, V_n = {v_1, v_2, ..., v_n}, E_n = {e_1, e_2, ..., e_{n-1}, f_1, f_2, ..., f_{n-1}}. For all i, e_i = f_i = v_iv_{i+1} although e_i and f_i are considered distinct.

Given an undirected multigraph G = (V,E) with labeled edges, its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii) union of corresponding undirected paths is E.

Index entries for linear recurrences with constant coefficients, signature (13,-22,-88,112).

Previously A131519 was thought to be this sequence.

Cf. A131518, A131520.

CoefficientList[Series[x (1-2x)^2(1-3x-14x^2)/(1-13x+22x^2+88x^3-112x^4),{x,0,20}],x] (* or *) LinearRecurrence[{13,-22,-88,112},{0,1,6,58,578,5766},30] (* Harvey P. Dale, Oct 31 2024 *)

For n >= 6, a(n) = 13*a(n-1) - 22*a(n-2) - 88*a(n-3) + 112*a(n-4).

O.g.f.: x * (1-2*x)^2 * (1 - 3*x - 14*x^2) / (1 - 13*x + 22*x^2 + 88*x^3 - 112*x^4).

A089243 Number of partitions into strokes of the star graph with n edges on the plane, up to rotations and reflections around the center node.

Original entry on oeis.org

1, 2, 3, 4, 9, 22, 61, 200, 689, 3054, 12110, 61132, 274264, 1515134, 7498195, 44301928, 238206692, 1490114770, 8605537805, 56612534420, 348083793872, 2396294898646, 15577794980189, 111781094032984, 763986810923430, 5695585712379834

Offset: 0

Yasutoshi Kohmoto

A "stroke" is defined as follows. If the following conditions are satisfied then the partition to directed paths on a directed graph is called "a partition to strokes on a directed graph", and all directed paths in the partition are called "strokes". C.1. Two different directed paths in a partition do not have the same edges. C.2. A union of two different paths in a partition does not become a directed path. In other words, a "stroke" is a locally maximal path on a directed graph.
This sequence has its origin in the strokes made when writing Japanese Kanji.
The value a(1) is ambiguous as it depends on the definition of the star graph with n = 1 edge. If one of the edge endpoints is labeled as the star center, then we have the current value a(1) = 2. However, if the center is not distinguished, then a(1) would be 1. - Max Alekseyev, May 04 2023

			For n = 3, call the center node "0" and the terminal nodes "1", "2", "3".
Four partitions exist as follows:
  {1->0->2, 0->3}
  {1->0->2, 3->0}
  {1->0, 2->0, 3->0}
  {0->1, 0->2, 0->3}.
So a(3) = 4.

Christian Sievers, Table of n, a(n) for n = 0..728

Cf. A131518, A131520, A354228, A131709, A357857, A357895.

p(n,t,o)=o*sum(k=0,(n-1)/2,n!/(k!*(n-2*k)!)*t^k)+if(n%2==0, n!/(n/2)!*t^(n/2));
a(n)=if(n==0,1,(sumdiv(n,d,eulerphi(n/d)*p(d,n/d,2)) + if(n%2,2*n*p((n-1)/2,2,1),n/2*p(n/2,2,2)+n*p(n/2-1,2,2)+n*p(n/2-1,2,1)))/(2*n)) \\ Christian Sievers, May 14 2023

Edited, terms a(0)-a(1) and a(6) corrected, a(7)-a(13) added by Max Alekseyev, Oct 20 2022

More terms from Christian Sievers, May 14 2023

A173742 Triangle T(n,k) = binomial(n,k) + 6 with T(n,0) = T(n,n) = 1 for n >= 0, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 8, 1, 1, 9, 9, 1, 1, 10, 12, 10, 1, 1, 11, 16, 16, 11, 1, 1, 12, 21, 26, 21, 12, 1, 1, 13, 27, 41, 41, 27, 13, 1, 1, 14, 34, 62, 76, 62, 34, 14, 1, 1, 15, 42, 90, 132, 132, 90, 42, 15, 1, 1, 16, 51, 126, 216, 258, 216, 126, 51, 16, 1, 1, 17, 61, 171, 336, 468, 468, 336, 171, 61, 17, 1

Offset: 0

Roger L. Bagula, Feb 23 2010

For n >= 1, row n sums to A131520(n) + A008586(n).

			Triangle begins:
  1;
  1,  1;
  1,  8,  1;
  1,  9,  9,   1;
  1, 10, 12,  10,   1;
  1, 11, 16,  16,  11,   1;
  1, 12, 21,  26,  21,  12,   1;
  1, 13, 27,  41,  41,  27,  13,   1;
  1, 14, 34,  62,  76,  62,  34,  14,  1;
  1, 15, 42,  90, 132, 132,  90,  42, 15,  1;
  1, 16, 51, 126, 216, 258, 216, 126, 51, 16, 1;
  ...

G. C. Greubel, Rows n = 0..100 of the triangle, flattened

Cf. A007318, A103451, A132044, A156050, A173740, A173741.

T:= func< n,k | k eq 0 or k eq n select 1 else Binomial(n,k) +6 >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Feb 13 2021

T[n_, m_] = Binomial[n, m] + 6*If[m*(n - m) > 0, 1, 0];
Flatten[Table[T[n, m], {n, 0, 10}, {m, 0, n}]]

T(n,k) := if k = 0 or k = n then 1 else binomial(n, k) + 6$
create_list(T(n, k), n, 0, 12, k, 0, n); /* Franck Maminirina Ramaharo, Dec 09 2018 */

def T(n, k): return 1 if (k==0 or k==n) else binomial(n, k) + 6
flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Feb 13 2021

From Franck Maminirina Ramaharo, Dec 09 2018: (Start)
T(n,k) = A007318(n,k) + 6*(1 - A103451(n,k)).
T(n,k) = 7*A007318(n,k) - 6*A132044(n,k).
n-th row polynomial is 3*(1 - (-1)^(2^n)) + (1 + x)^n + 6*(x - x^n)/(1 - x).
G.f.: (1 - (1 + x)*y + 7*x*y^2 - 6*(x + x^2)*y^3)/((1 - y)*(1 - x*y)*(1 - y - x*y)).
E.g.f.: (6 - 6*x + 6*x*exp(y) - 6*exp(x*y) + (1 - x)*exp((1 + x)*y))/(1 - x). (End)
Sum_{k=0..n} T(n, k) = 2^n + 6*n - 6 + 6*[n=0]. - G. C. Greubel, Feb 13 2021

Edited and name clarified by Franck Maminirina Ramaharo, Dec 09 2018

A303273 Array T(n,k) = binomial(n, 2) + k*n + 1 read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 4, 4, 1, 4, 6, 7, 7, 1, 5, 8, 10, 11, 11, 1, 6, 10, 13, 15, 16, 16, 1, 7, 12, 16, 19, 21, 22, 22, 1, 8, 14, 19, 23, 26, 28, 29, 29, 1, 9, 16, 22, 27, 31, 34, 36, 37, 37, 1, 10, 18, 25, 31, 36, 40, 43, 45, 46, 46, 1, 11, 20, 28, 35, 41

Offset: 0

Franck Maminirina Ramaharo, Apr 20 2018

Columns are linear recurrence sequences with signature (3,-3,1).
8*T(n,k) + A166147(k-1) are squares.
Columns k are binomial transforms of [1, k, 1, 0, 0, 0, ...].
Antidiagonals sums yield A116731.

			The array T(n,k) begins
1    1    1    1    1    1    1    1    1    1    1    1    1  ...  A000012
1    2    3    4    5    6    7    8    9   10   11   12   13  ...  A000027
2    4    6    8   10   12   14   16   18   20   22   24   26  ...  A005843
4    7   10   13   16   19   22   25   28   31   34   37   40  ...  A016777
7   11   15   19   23   27   31   35   39   43   47   51   55  ...  A004767
11  16   21   26   31   36   41   46   51   56   61   66   71  ...  A016861
16  22   28   34   40   46   52   58   64   70   76   82   88  ...  A016957
22  29   36   43   50   57   64   71   78   85   92   99  106  ...  A016993
29  37   45   53   61   69   77   85   93  101  109  117  125  ...  A004770
37  46   55   64   73   82   91  100  109  118  127  136  145  ...  A017173
46  56   66   76   86   96  106  116  126  136  146  156  166  ...  A017341
56  67   78   89  100  111  122  133  144  155  166  177  188  ...  A017401
67  79   91  103  115  127  139  151  163  175  187  199  211  ...  A017605
79  92  105  118  131  144  157  170  183  196  209  222  235  ...  A190991
...
The inverse binomial transforms of the columns are
1    1    1    1    1    1    1    1    1    1    1    1    1  ...
0    1    2    3    4    5    6    7    8    9   10   11   12  ...
1    1    1    1    1    1    1    1    1    1    1    1    1  ...
0    0    0    0    0    0    0    0    0    0    0    0    0  ...
0    0    0    0    0    0    0    0    0    0    0    0    0  ...
0    0    0    0    0    0    0    0    0    0    0    0    0  ...
...
T(k,n-k) = A087401(n,k) + 1 as triangle
1
1   1
1   2   2
1   3   4   4
1   4   6   7   7
1   5   8  10  11  11
1   6  10  13  15  16  16
1   7  12  16  19  21  22  22
1   8  14  19  23  26  28  29  29
1   9  16  22  27  31  34  36  37  37
1  10  18  25  31  36  40  43  45  46  46
...

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994.

Cf. A085475, A086270, A086271, A086272, A086273, A130154, A159798, A162609, A162610, A300401.

T := (n, k) -> binomial(n, 2) + k*n + 1;
for n from 0 to 20 do seq(T(n, k), k = 0 .. 20) od;

Table[With[{n = m - k}, Binomial[n, 2] + k n + 1], {m, 0, 11}, {k, m, 0, -1}] // Flatten (* Michael De Vlieger, Apr 21 2018 *)

T(n, k) := binomial(n, 2)+ k*n + 1$
for n:0 thru 20 do
    print(makelist(T(n, k), k, 0, 20));

T(n,k) = binomial(n, 2) + k*n + 1;
tabl(nn) = for (n=0, nn, for (k=0, nn, print1(T(n, k), ", ")); print); \\ Michel Marcus, May 17 2018

G.f.: (3*x^2*y - 3*x*y + y - 2*x^2 + 2*x - 1)/((x - 1)^3*(y - 1)^2).
E.g.f.: (1/2)*(2*x*y + x^2 + 2)*exp(y + x).
T(n,k) = 3*T(n-1,k) - 3*T(n-2,k) + T(n-3,k), with T(0,k) = 1, T(1,k) = k + 1 and T(2,k) = 2*k + 2.
T(n,k) = T(n-1,k) + n + k - 1.
T(n,k) = T(n,k-1) + n, with T(n,0) = 1.
T(n,0) = A152947(n+1).
T(n,1) = A000124(n).
T(n,2) = A000217(n).
T(n,3) = A034856(n+1).
T(n,4) = A052905(n).
T(n,5) = A051936(n+4).
T(n,6) = A246172(n+1).
T(n,7) = A302537(n).
T(n,8) = A056121(n+1) + 1.
T(n,9) = A056126(n+1) + 1.
T(n,10) = A051942(n+10) + 1, n > 0.
T(n,11) = A101859(n) + 1.
T(n,12) = A132754(n+1) + 1.
T(n,13) = A132755(n+1) + 1.
T(n,14) = A132756(n+1) + 1.
T(n,15) = A132757(n+1) + 1.
T(n,16) = A132758(n+1) + 1.
T(n,17) = A212427(n+1) + 1.
T(n,18) = A212428(n+1) + 1.
T(n,n) = A143689(n) = A300192(n,2).
T(n,n+1) = A104249(n).
T(n,n+2) = T(n+1,n) = A005448(n+1).
T(n,n+3) = A000326(n+1).
T(n,n+4) = A095794(n+1).
T(n,n+5) = A133694(n+1).
T(n+2,n) = A005449(n+1).
T(n+3,n) = A115067(n+2).
T(n+4,n) = A133694(n+2).
T(2*n,n) = A054556(n+1).
T(2*n,n+1) = A054567(n+1).
T(2*n,n+2) = A033951(n).
T(2*n,n+3) = A001107(n+1).
T(2*n,n+4) = A186353(4*n+1) (conjectured).
T(2*n,n+5) = A184103(8*n+1) (conjectured).
T(2*n,n+6) = A250657(n-1) = A250656(3,n-1), n > 1.
T(n,2*n) = A140066(n+1).
T(n+1,2*n) = A005891(n).
T(n+2,2*n) = A249013(5*n+4) (conjectured).
T(n+3,2*n) = A186384(5*n+3) = A186386(5*n+3) (conjectured).
T(2*n,2*n) = A143689(2*n).
T(2*n+1,2*n+1) = A143689(2*n+1) (= A030503(3*n+3) (conjectured)).
T(2*n,2*n+1) = A104249(2*n) = A093918(2*n+2) = A131355(4*n+1) (= A030503(3*n+5) (conjectured)).
T(2*n+1,2*n) = A085473(n).
a(n+1,5*n+1)=A051865(n+1) + 1.
a(n,2*n+1) = A116668(n).
a(2*n+1,n) = A054569(n+1).
T(3*n,n) = A025742(3*n-1), n > 1 (conjectured).
T(n,3*n) = A140063(n+1).
T(n+1,3*n) = A069099(n+1).
T(n,4*n) = A276819(n).
T(4*n,n) = A154106(n-1), n > 0.
T(2^n,2) = A028401(n+2).
T(1,n)*T(n,1) = A006000(n).
T(n*(n+1),n) = A211905(n+1), n > 0 (conjectured).
T(n*(n+1)+1,n) = A294259(n+1).
T(n,n^2+1) = A081423(n).
T(n,A000217(n)) = A158842(n), n > 0.
T(n,A152947(n+1)) = A060354(n+1).
floor(T(n,n/2)) = A267682(n) (conjectured).
floor(T(n,n/3)) = A025742(n-1), n > 0 (conjectured).
floor(T(n,n/4)) = A263807(n-1), n > 0 (conjectured).
ceiling(T(n,2^n)/n) = A134522(n), n > 0 (conjectured).
ceiling(T(n,n/2+n)/n) = A051755(n+1) (conjectured).
floor(T(n,n)/n) = A133223(n), n > 0 (conjectured).
ceiling(T(n,n)/n) = A007494(n), n > 0.
ceiling(T(n,n^2)/n) = A171769(n), n > 0.
ceiling(T(2*n,n^2)/n) = A046092(n), n > 0.
ceiling(T(2*n,2^n)/n) = A131520(n+2), n > 0.

cp's OEIS Frontend

A131518 Number of partitions of the graph G_n (defined below) into "strokes".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A173740 Triangle T(n,k) = binomial(n,k) + 2 for 1 <= k <= n - 1, n >= 2, and T(n,0) = T(n,n) = 1 for n >= 0, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

Sage

Formula

Extensions

A354228 Number of partitions of the multigraph G_n (defined below) into "strokes".

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A089243 Number of partitions into strokes of the star graph with n edges on the plane, up to rotations and reflections around the center node.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A173742 Triangle T(n,k) = binomial(n,k) + 6 with T(n,0) = T(n,n) = 1 for n >= 0, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

Sage

Formula

Extensions

A303273 Array T(n,k) = binomial(n, 2) + k*n + 1 read by antidiagonals.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A357895 Number of partitions of the complete graph on n vertices into strokes.