A220420 -id:A220420 - cp's OEIS frontend

A273873 Number of strict trees of weight n.

1, 1, 2, 3, 6, 12, 28, 65, 166, 412, 1076, 2806, 7524, 20020, 54744, 148417, 410078, 1126732, 3144500, 8728570, 24555900, 68713420, 194469616, 548088278, 1559301428, 4418131108, 12628267512, 35957541462, 103150588492, 294924202032, 848878072440, 2435729999665

Offset: 1

Gus Wiseman, Jun 01 2016

nonn

A strict tree t is either (case 1) a positive integer t = n, or (case 2) a set t = {t1, t2, ..., tk} of two or more strict trees (i.e. branches) with distinct weights, where the weight of a strict tree in the second case is the sum of the weights of its branches; hence the multiset of weights is a strict integer partition of n. For example, {{{{{2,1},1},2},3},{4,{2,1}},{2,1},1} is a strict tree of weight 20.

			a(6) = 12: {6, (51), (42), ((41)1), (321), ((31)2), ((32)1), (((31)1)1), ((21)21), (((21)1)2), (((21)2)1), ((((21)1)1)1)}.

Alois P. Heinz, Table of n, a(n) for n = 1..2000
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47(1995), 1219-1239
Gus Wiseman, Comcategories and Multiorders, (pdf version)
Gus Wiseman, All strict trees n=1..6.

Cf. A196545 (weakly ordered plane trees); A220418, A220420 (power product expansions); A271619, A063834 (twice partitioned numbers), A289501.

b:= proc(n, i) option remember; `if`(i*(i+1)/2 1+b(n, n-1):
seq(a(n), n=1..35);  # Alois P. Heinz, Jun 02 2016

STE[n_Integer?Positive]:=STE[n]=1+Plus@@Map[Function[ptn,Times@@STE/@ptn],Select[IntegerPartitions[n],And[Length[#]>1,UnsameQ@@#]&]];
Array[STE,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[i(i + 1)/2 < n, 0,
     If[n == 0, 1, b[n, i - 1] + b[n - i, Min[n - i, i - 1]] a[i]]];
a[n_] := If[n == 0, 1, 1 + b[n, n - 1]];
a /@ Range[35] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, 1 + v[k]*x^k + O(x*x^n)), n)); v} \\ Andrew Howroyd, Aug 26 2018

Sum_{g(t)=y} (-1)^{d(t)} = mu(|y|<={y_1,...,y_k}), where mu is the Mobius function of the multiorder of integer partitions, g(t) is the multiset of leaves of a strict tree t, and d(t) is the number of branchings.

Strict trees are closely related to the coefficients appearing in a(i) = Sum_y c(y_1)*...*c(y_k) where Sum_i c(i)*x^i = Prod_i (1 + a(i)*x^i). The latter identity is the formal power product expansion (PPE) of an (ordinary) generating function.

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

A273866 Coefficients a(k,m) of polynomials a{k}(h) appearing in the product Product_{k >= 1} (1 - a{k}(h)x^k) = 1 - hx/(1-x).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 6, 7, 6, 3, 1, 1, 4, 9, 13, 13, 9, 4, 1, 1, 4, 10, 17, 20, 17, 10, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 16, 36, 57, 66, 57, 36, 16, 5, 1

Offset: 1

Gevorg Hmayakyan, Jun 01 2016

The a(k,m) form a table where each row has k-1 elements starting from 2 and the a(1,1) = 1.

			a{1}(h) = h,
a{2}(h) = h,
a{3}(h) = h^2 + h,
a{4}(h) = h^3 + h^2 + h,
a{5}(h) = h^4 + 2*h^3 + 2*h^2 + h,
a{6}(h) = h^5 + 2*h^4 + 2*h^3 + 2*h^2 + h,
a{7}(h) = h^6 + 3*h^5 + 5*h^4 + 5*h^3 + 3*h^2 + h,
a{8}(h) = h^7 + 3*h^6 + 6*h^5 + 7*h^4 + 6*h^3 + 3*h^2 + h,
a{9}(h) = h^8 + 4*h^7 + 9*h^6 + 13*h^5 + 13*h^4 + 9*h^3 + 4*h^2 + h
...
and the corresponding a(k,m) table is:
  1,
  1,
  1,  1,
  1,  1,  1,
  1,  2,  2,  1,
  1,  2,  2,  2,  1,
  1,  3,  5,  5,  3,  1,
  1,  3,  6,  7,  6,  3,  1,
  1,  4,  9, 13, 13,  9,  4,  1,
  ...
a(7,3) = 5 because there are six strict trees contributing positive one {{5,1},1}, {{4,2},1}, {{4,1},2}, {{3,2},2}, {4,{2,1}}, {{3,1},3} and there is one strict tree contributing negative one {4,2,1}. - _Gus Wiseman_, Nov 14 2016

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. A196545, A220418, A220420, A273866, A273873, A279785, A290261, A290262, A290971, A295632.

with(ListTools), with(numtheory), with(combinat);
L := product(1-a[k]*x^k, k = 1 .. 600);
S := Flatten([seq(-h, i = 1 .. 100)]);
Sabs := Flatten([seq(i, i = 1 .. 100)]);
seq(assign(a[i] = solve(coeff(L, x^i) = `if`(is(i in Sabs), S[Search(i, Sabs)], 0), a[i])), i = 1 .. 20);
map(coeffs, [seq(simplify(a[i]), i = 1 .. 20)]);

strictrees[n_Integer?Positive]:=Prepend[Join@@Function[ptn,Tuples[strictrees/@ptn]]/@Select[IntegerPartitions[n],And[Length[#]>1,UnsameQ@@#]&],n];
Table[Sum[(-1)^(Count[tree,,{0,Infinity}]-1),{tree,Select[strictrees[n],Length[Flatten[{#}]]===m&]}],{n,1,9},{m,1,n-1/.(0->1)}] (* _Gus Wiseman, Nov 14 2016 *)
(* second program *)
A[m_, n_] :=
  A[m, n] =
   Which[m == 1, -h, m > n >= 1, 0, True,
    A[m - 1, n] - A[m - 1, m - 1]*A[m, n - m + 1]];
a[n_] := Expand[-A[n, n]];
a /@ Range[1, 25] (* Petros Hadjicostas, Oct 04 2019, courtesy of Jean-François Alcover *)

a(k,m) = a(k, k-m).
For prime p: Sum_{m = 1..p-1} a(p, m) = (2^p - 2)/p.
a{k}(h) satisfies Sum_{d|k} (1/d)*(a{k/d}(h))^d = ((h+1)^k - 1)/k. [Corrected by Petros Hadjicostas, Oct 04 2019]
For prime p: a{p}(h) = ((h+1)^p - h^p - 1)/p.
See A273873 for the definition of strict tree. Then a(n,m) = Sum_t (-1)^{v(t)-1} where the sum is over all strict trees of weight n with m leaves, and v(t) is the number of nodes in t (including the leaves, which are positive integers). See example 2 and the first Mathematica program. - Gus Wiseman, Nov 14 2016

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]]

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

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 6, 1, 4, 1, 4, 2, 2, 1, 8, 2, 2, 2, 4, 1, 6, 1, 6, 2, 2, 2, 12, 1, 2, 2, 8, 1, 6, 1, 4, 4, 2, 1, 16, 2, 4, 2, 4, 1, 8, 2, 8, 2, 2, 1, 16, 1, 2, 4, 10, 2, 6, 1, 4, 2, 6, 1, 24, 1, 2, 4, 4, 2, 6, 1, 16, 6, 2, 1, 16, 2, 2

Offset: 2

Gus Wiseman, Nov 24 2017

nonn

Cf. A001055, A045778, A050376, A220418, A220420, A273866, A273873, A289501, A290261, A290262, A290971, A290973, A295279, A295632, 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[-1==Sum[Times@@a/@f,{f,facs[n]}],{n,2,nn}],Table[a[n],{n,2,nn}]][[1,All,2]]

A295636 Write 2 - Zeta(s) in the form Product_{n > 1}(1 - a(n)/n^s).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 8, 1, 2, 2, 4, 1, 6, 1, 6, 2, 2, 2, 8, 1, 2, 2, 8, 1, 6, 1, 4, 4, 2, 1, 16, 1, 4, 2, 4, 1, 8, 2, 8, 2, 2, 1, 16, 1, 2, 4, 8, 2, 6, 1, 4, 2, 6, 1, 24, 1, 2, 4, 4, 2, 6, 1, 16, 3, 2, 1, 16, 2, 2, 2

Offset: 2

Gus Wiseman, Nov 24 2017

nonn

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

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

a(n) = Sum_t (-1)^(v(t)-1) where the sum is over all strict tree-factorizations of n (see A295279 for definition) and v(t) is the number of nodes (branchings and leaves) in t.

cp's OEIS Frontend

A273873 Number of strict trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

A273866 Coefficients a(k,m) of polynomials a{k}(h) appearing in the product Product_{k >= 1} (1 - a{k}(h)*x^k) = 1 - h*x/(1-x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A295636 Write 2 - Zeta(s) in the form Product_{n > 1}(1 - a(n)/n^s).

Views

Author

Keywords

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).

A273866 Coefficients a(k,m) of polynomials a{k}(h) appearing in the product Product_{k >= 1} (1 - a{k}(h)x^k) = 1 - hx/(1-x).