A273866 -id:A273866 - cp's OEIS frontend

A290261 Write 1 - x/(1-x) as an inverse power product 1/(1 + a(1)x) 1/(1 + a(2)x^2) 1/(1 + a(3)x^3) 1/(1 + a(4)x^4) ...

1, 2, 2, 6, 6, 10, 18, 54, 54, 114, 186, 334, 630, 1314, 2106, 5910, 7710, 15642, 27594, 57798, 97902, 207762, 364722, 712990, 1340622, 2778930, 4918482, 10437702, 18512790, 37500858, 69273666, 154021590, 258155910, 535004610, 981288906

Offset: 1

Gus Wiseman, Jul 24 2017

nonn

The initial terms are given on page 1234 of Gingold, Knopfmacher, 1995.
From Petros Hadjicostas, Oct 04 2019: (Start)
In Section 3 of Gingold and Knopfmacher (1995), it is proved that, if f(z) = Product_{n >= 1} (1 + g(n))*z^n = 1/(Product_{n >= 1} (1 - h(n))*z^n), then g(2*n - 1) = h(2*n - 1) and Sum_{d|n} (1/d)*h(n/d)^d = -Sum_{d|n} (1/d)*(-g(n/d))^d. The same results were proved more than ten years later by Alkauskas (2008, 2009). [If we let a(n) = -g(n), then Alkauskas works with f(z) = Product_{n >= 1} (1 - a(n))*z^n; i.e., a(2*n - 1) = -h(2*n - 1) etc.]
The PPE of 1 - x/(1-x) is given in A220418, which is also studied in Gingold and Knopfmacher (1995) starting at p. 1223.
(End)

Seiichi Manyama, Table of n, a(n) for n = 1..3333
Giedrius Alkauskas, One curious proof of Fermat's little theorem, arXiv:0801.0805 [math.NT], 2008.
Giedrius Alkauskas, A curious proof of Fermat's little theorem, Amer. Math. Monthly 116(4) (2009), 362-364.
H. Gingold, H. W. Gould, and Michael E. Mays, Power Product Expansions, Utilitas Mathematica 34 (1988), 143-161.
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47 (1995), 1219-1239.
W. Lang, Recurrences for the general problem.

Cf. A220418, A273866, A289501, A290262.

nn=20;Solve[Table[Expand[SeriesCoefficient[Product[1/(1+a[k]x^k),{k,n}],{x,0,n}]]==-1,{n,nn}],Table[a[n],{n,nn}]][[1,All,2]]
(* Second program: *)
A[m_, n_] := A[m, n] = Which[m == 1, 2^(n-1), m > n >= 1, 0, True, A[m - 1, n] - A[m - 1, m - 1]*A[m, n - m + 1] ];
a[n_] := A[n, n];
a /@ Range[1, 55] (* Petros Hadjicostas, Oct 04 2019, courtesy of Jean-François Alcover *)

a(n) = Sum_t (-1)^v(t) where the sum is over all enriched p-trees of weight n (see A289501 for definition) and v(t) is the number of nodes (branchings and leaves) in t.
From Petros Hadjicostas, Oct 04 2019: (Start)
a(n) satisfies Sum_{d|n} (1/d)*(-a(n/d))^d = -(2^n - 1)/n. Thus, a(n) = Sum_{d|n, d>1} (1/d)*(-a(n/d))^d + (2^n - 1)/n.
a(2*n - 1) = A220418(2*n - 1) for n >= 1 because A220418 gives the PPE of 1 - x/(1-x).
Define (A(m,n): n,m >= 1) by A(m=1,n) = 2^(n-1) for n >= 1, A(m,n) = 0 for m > n >= 1 (upper triangular), and A(m,n) = A(m-1,n) - A(m-1,m-1) * A(m,n-m+1) for n >= m >= 2. Then a(n) = A(n,n). [Theorem 3 in Gingold et al. (1988).]
(End)

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)x) (1 + g(2)x^2) (1 + g(3)x^3) ... and use a(n) = - g(n).

Original entry on oeis.org

1, 1, 2, 3, 6, 8, 18, 27, 54, 84, 186, 296, 630, 1008, 2106, 3711, 7710, 12924, 27594, 48528, 97902, 173352, 364722, 647504, 1340622, 2382660, 4918482, 9052392, 18512790, 33361776, 69273666, 127198287, 258155910, 475568220, 981288906, 1814542704, 3714566310

Offset: 1

Michel Marcus, Dec 14 2012

nonn

This is the PPE (power product expansion) of A153881 (with offset 0).
When p is prime, a(p) = (2^p-2)/p (A064535).
From Petros Hadjicostas, Oct 04 2019: (Start)
This sequence appears as an example in Gingold and Knopfmacher (1995) starting at p. 1223.
In Section 3 of Gingold and Knopfmacher (1995), it is proved that, if f(z) = Product_{n >= 1} (1 + g(n))*z^n = 1/(Product_{n >= 1} (1 - h(n))*z^n), then g(2*n - 1) = h(2*n - 1) and Sum_{d|n} (1/d)*h(n/d)^d = -Sum_{d|n} (1/d)*(-g(n/d))^d. The same results were proved more than ten years later by Alkauskas (2008, 2009). [If we let a(n) = -g(n), then Alkauskas works with f(z) = Product_{n >= 1} (1 - a(n))*z^n; i.e., a(2*n - 1) = -h(2*n - 1) etc.]
The PPE of 1/(1 - x - x^2 - x^3 - x^4 - ...) is given in A290261, which is also studied in Gingold and Knopfmacher (1995, p. 1234).
(End)
The number of terms in the Zassenhaus formula exponent of order n, as computed by the algorithm by Casas, Murua & Nadinic, is equal to a(n) at least for n = 2..24. - Andrey Zabolotskiy, Apr 09 2023

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Giedrius Alkauskas, One curious proof of Fermat's little theorem, arXiv:0801.0805 [math.NT], 2008.
Giedrius Alkauskas, A curious proof of Fermat's little theorem, Amer. Math. Monthly 116(4) (2009), 362-364.
Fernando Casas, Ander Murua and Mladen Nadinic, Efficient computation of the Zassenhaus formula, Computer Physics Communications, 183 (2012), 2386-2391; arXiv:1204.0389 [math-ph], 2012.
H. Gingold, H. W. Gould, and Michael E. Mays, Power Product Expansions, Utilitas Mathematica 34 (1988), 143-161.
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47 (1995), 1219-1239.
W. Lang, Recurrences for the general problem.

Cf. A064535, A147541, A153881, A157162, A170908, A170909, A170910, A170911, A170912, A170913, A170914, A170915, A170916, A170917, A220420, A273866, A290261.

b:= proc(n, i) option remember; `if`(n=0 or i<1, 1,
      b(n, i-1)+a(i)*b(n-i, min(n-i, i)))
    end:
a:= proc(n) option remember; 2^n-b(n, n-1) end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jun 22 2018

b[n_, i_] := b[n, i] = If[n == 0 || i < 1, 1, b[n, i - 1] + a[i]*b[n - i, Min[n - i, i]]];
a[n_] := a[n] = 2^n - b[n, n - 1] ;
Array[a, 40] (* Jean-François Alcover, Jul 09 2018, after Alois P. Heinz *)

a(m) = {default(seriesprecision, m+1); gk = vector(m); pol = 1 + sum(n=1, m, -x^n); gk[1] = polcoeff( pol, 1); for (k=2, m, pol = taylor(pol/(1+gk[k-1]*x^(k-1)), x); gk[k] = polcoeff(pol, k, x);); for (k=1, m, print1(-gk[k], ", "););}

g(1) = -1 and for k > 1, g(k) satisfies Sum_{d|k} (1/d)*(-g(k/d))^d = (2^k - 1)/k, where a(k) = -g(k). - Gevorg Hmayakyan, Jun 05 2016 [Corrected by Petros Hadjicostas, Oct 04 2019. See p. 1224 in Gingold and Knopfmacher (1995).]
From Petros Hadjicostas, Oct 04 2019: (Start)
a(2*n - 1) = A290261(2*n - 1) for n >= 1 because A290261 gives the PPE of 1/(1 - x - x^2 - x^3 - ...) = (1 - x)/(1 - 2*x).
Define (A(m,n): n,m >= 1) by A(m=1,n) = -1 for n >= 1, A(m,n) = 0 for m > n >= 1 (upper triangular), and A(m,n) = A(m-1,n) - A(m-1,m-1) * A(m,n-m+1) for n >= m >= 2. Then a(n) = A(n,n). [Theorem 3 in Gingold et al. (1988).]
(End)

Name edited by Petros Hadjicostas, Oct 04 2019

A301364 Regular triangle where T(n,k) is the number of enriched p-trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 4, 5, 1, 2, 6, 11, 12, 1, 3, 10, 26, 38, 34, 1, 3, 13, 39, 87, 117, 92, 1, 4, 19, 69, 181, 339, 406, 277, 1, 4, 23, 95, 303, 707, 1198, 1311, 806, 1, 5, 30, 143, 514, 1430, 2970, 4525, 4522, 2500, 1, 5, 35, 184, 762, 2446, 6124, 11627

Offset: 1

Gus Wiseman, Mar 19 2018

An enriched p-tree of weight n > 0 is either a single node of weight n, or a finite sequence of two or more enriched p-trees with weakly decreasing weights summing to n.

			Triangle begins:
  1
  1   1
  1   1   2
  1   2   4   5
  1   2   6  11  12
  1   3  10  26  38  34
  1   3  13  39  87 117  92
  1   4  19  69 181 339 406 277
  ...
The T(5,4) = 11 enriched p-trees: (((21)1)1), ((2(11))1), (((11)2)1), ((211)1), ((21)(11)), (((11)1)2), ((111)2), ((21)11), (2(11)1), ((11)21), (2111).

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Last entries of each row give A196545. Row sums are A289501.

Cf. A008284, A055277, A063834, A220418, A273866, A273873, A281145, A290261, A299201, A299202, A299203, A300354, A300442, A300443, A301365-A301368.

eptrees[n_]:=Prepend[Join@@Table[Tuples[eptrees/@ptn],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];
Table[Length[Select[eptrees[n],Count[#,_Integer,{-1}]===k&]],{n,8},{k,n}]

A(n)={my(v=vector(n)); for(n=1, n, v[n] = y + polcoef(1/prod(k=1, n-1, 1 - v[k]*x^k + O(x*x^n)), n)); apply(p->Vecrev(p/y), v)}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Aug 26 2018

A300866 Signed recurrence over binary strict trees: a(n) = 1 - Sum_{x + y = n, 0 < x < y < n} a(x) * a(y).

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, -1, 1, 1, -2, 3, -1, -3, 8, -8, 1, 14, -26, 22, 10, -59, 90, -52, -74, 238, -291, 80, 417, -930, 915, 124, -1991, 3483, -2533, -2148, 9011, -12596, 5754, 14350, -37975, 42735, -4046, -77924, 154374, -133903, -56529, 376844, -591197, 355941, 522978, -1706239

Offset: 0

Gus Wiseman, Mar 13 2018

sign

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000992, A001190, A007317, A063834, A099323, A196545, A220418, A273866, A273873, A289501, A290261, A300442, A300443, A300862, A300863, A300864, A300865.

a[n_]:=a[n]=1-Sum[a[k]*a[n-k],{k,1,(n-1)/2}];
Array[a,40]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 - sum(k=1, (n-1)\2, v[k]*v[n-k])); concat([1], v)} \\ Andrew Howroyd, Aug 27 2018

A290262 Irregular triangle read by rows: rows give the (negated) nonzero coefficients of t in each term of the inverse power product expansion of 1 - t * x/(1-x).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 3, 4, 2, 1, 3, 5, 5, 3, 1, 1, 4, 9, 13, 13, 9, 4, 1, 1, 4, 9, 13, 13, 9, 4, 1, 1, 5, 14, 25, 30, 24, 12, 3, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 6, 21, 48, 75, 81, 60, 30, 10, 2

Offset: 1

Gus Wiseman, Jul 24 2017

Row sums are A290261(n). A regular version is A290320.

			Triangle begins:
  1;
  1,  1;
  1,  1,
  1,  2,  2,  1;
  1,  2,  2,  1;
  1,  3,  4,  2;
  1,  3,  5,  5,  3,  1;
  1,  4,  9, 13, 13,  9,  4,  1;
  1,  4,  9, 13, 13,  9,  4,  1;
  1,  5, 14, 25, 30, 24, 12,  3;
  1,  5, 15, 30, 42, 42, 30, 15,  5,  1;
  1,  6, 21, 48, 75, 81, 60, 30, 10,  2;

Cf. A220418, A273866, A289501, A290261, A290320.

eptrees[n_]:=Prepend[Join@@Table[Tuples[eptrees/@y],{y,Rest[IntegerPartitions[n]]}],n];
eptrans[a_][n_]:=Sum[(-1)^Count[tree,_List,{0,Infinity}]*Product[a[i],{i,Flatten[{tree}]}],{tree,eptrees[n]}];
Table[DeleteCases[CoefficientList[-eptrans[-t&][n],t],0],{n,12}]

A300863 Signed recurrence over enriched p-trees: a(n) = (-1)^(n - 1) + Sum_{y1 + ... + yk = n, y1 >= ... >= yk > 0, k > 1} a(y1) * ... * a(yk).

Original entry on oeis.org

1, 0, 2, 2, 6, 14, 34, 82, 214, 566, 1482, 4058, 10950, 30406, 83786, 235714, 658286, 1874254, 5293674, 15189810, 43312542, 125075238, 359185586, 1043712922, 3015569582, 8800146182, 25565402802, 74918274562, 218572345718, 642783954238, 1882606578002

Offset: 1

Gus Wiseman, Mar 13 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..500

Cf. A000992, A063834, A099323, A196545, A220418, A273866, A273873, A289501, A290261, A300862, A300864, A300865, A300866.

a[n_]:=a[n]=(-1)^(n-1)+Sum[Times@@a/@y,{y,Select[IntegerPartitions[n],Length[#]>1&]}];
Array[a,40]

O.g.f.: (-1/(1+x) + Product 1/(1-a(n)x^n))/2.

A295632 Write 1/Product_{n > 1}(1 - 1/n^s) in the form Product_{n > 1}(1 + a(n)/n^s).

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1

Offset: 2

Gus Wiseman, Nov 24 2017

sign

First negative entry is a(1024) = -4.

Cf. A001055, A045778, A050376, A220418, A220420, A273866, A273873, A289501, A290261, A290262, A290971, A290973, A295279, A295635, A295636.

nn=100;
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Solve[Table[Length[facs[n]]==Sum[Times@@a/@f,{f,Select[facs[n],UnsameQ@@#&]}],{n,2,nn}],Table[a[n],{n,2,nn}]][[1,All,2]]

A300864 Signed recurrence over strict trees: a(n) = -1 + Sum_{y1 + ... + yk = n, y1 > ... > yk > 0, k > 1} a(y1) * ... * a(yk).

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 2, -1, 0, 4, -6, 6, 6, -24, 38, -17, -64, 188, -230, -6, 662, -1432, 1286, 1210, -6362, 10692, -5530, -18274, 57022, -74364, 174, 216703, -489544, 467860, 391258, -2256430, 3948206, -2234064, -6725362, 21920402, -29716570, 2095564, 84595798, -198418242, 197499846

Offset: 1

Gus Wiseman, Mar 13 2018

sign

Cf. A000992, A018819, A063834, A099323, A196545, A220418, A273866, A273873, A289501, A290261, A300862, A300863, A300865, A300866.

a[n_]:=a[n]=-1+Sum[Times@@a/@y,{y,Select[IntegerPartitions[n],Length[#]>1&&UnsameQ@@#&]}];
-Array[a,40]

A300865 Signed recurrence over binary enriched p-trees: a(n) = (-1)^(n-1) + Sum_{x + y = n, 0 < x <= y < n} a(x) * a(y).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 2, 2, 4, 6, 10, 16, 27, 46, 77, 131, 224, 391, 672, 1180, 2050, 3626, 6344, 11276, 19863, 35479, 62828, 112685, 200462, 360627, 644199, 1162296, 2083572, 3768866, 6777314, 12289160, 22158106, 40255496, 72765144, 132453122, 239936528, 437445448

Offset: 1

Gus Wiseman, Mar 13 2018

nonn

Cf. A000992, A001190, A007317, A063834, A099323, A196545, A220418, A273866, A273873, A289501, A290261, A300352, A300442, A300443, A300862, A300863, A300864, A300866.

a[n_]:=a[n]=(-1)^(n-1)+Sum[a[k]*a[n-k],{k,1,n/2}];
Array[a,50]

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 2, 3, 5, 9, 15, 27, 47, 87, 155, 288, 524, 983, 1813, 3434, 6396, 12174, 22891, 43810, 82925, 159432, 303559, 585966, 1121446, 2171341, 4172932, 8106485, 15635332, 30445899, 58925280, 115014681, 223210718, 436603718, 849480835, 1664740873

Offset: 0

Gus Wiseman, Mar 21 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..3266

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290971, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301469.

b:= proc(n, i) option remember; `if`(n=0, 1,
     `if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> `if`(n<2, 1-n, b(n-2$2)+b(n-1, n-2)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jun 23 2018

a[n_]:=a[n]=(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
     If[i < 1, 0, b[n, i - 1] + a[i] b[n - i, Min[n - i, i]]]];
a[n_] := If[n < 2, 1 - n, b[n - 2, n - 2] + b[n - 1, n - 2]];
a /@ Range[0, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

O.g.f.: 1/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t (-1)^w(t) where the sum is over all enriched r-trees of size n and w(t) is the sum of leaves of t.

cp's OEIS Frontend

A290261 Write 1 - x/(1-x) as an inverse power product 1/(1 + a(1)*x) * 1/(1 + a(2)*x^2) * 1/(1 + a(3)*x^3) * 1/(1 + a(4)*x^4) * ...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)*x) * (1 + g(2)*x^2) *(1 + g(3)*x^3) * ... and use a(n) = - g(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A301364 Regular triangle where T(n,k) is the number of enriched p-trees of weight n with k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A300866 Signed recurrence over binary strict trees: a(n) = 1 - Sum_{x + y = n, 0 < x < y < n} a(x) * a(y).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A290262 Irregular triangle read by rows: rows give the (negated) nonzero coefficients of t in each term of the inverse power product expansion of 1 - t * x/(1-x).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A300863 Signed recurrence over enriched p-trees: a(n) = (-1)^(n - 1) + Sum_{y1 + ... + yk = n, y1 >= ... >= yk > 0, k > 1} a(y1) * ... * a(yk).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A295632 Write 1/Product_{n > 1}(1 - 1/n^s) in the form Product_{n > 1}(1 + a(n)/n^s).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A300864 Signed recurrence over strict trees: a(n) = -1 + Sum_{y1 + ... + yk = n, y1 > ... > yk > 0, k > 1} a(y1) * ... * a(yk).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A300865 Signed recurrence over binary enriched p-trees: a(n) = (-1)^(n-1) + Sum_{x + y = n, 0 < x <= y < n} a(x) * a(y).

Views

Author

A290261 Write 1 - x/(1-x) as an inverse power product 1/(1 + a(1)x) 1/(1 + a(2)x^2) 1/(1 + a(3)x^3) 1/(1 + a(4)x^4) ...

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)x) (1 + g(2)x^2) (1 + g(3)x^3) ... and use a(n) = - g(n).