A011782 -id:A011782 - cp's OEIS frontend

A349567 Dirichlet convolution of A133494 [3^(n-1)] with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

1, 1, 5, 17, 65, 197, 665, 2017, 6285, 19025, 58025, 174565, 527345, 1584737, 4766245, 14311841, 42981185, 128995317, 387158345, 1161697825, 3485732845, 10458138977, 31376865305, 94134428213, 282412758225, 847253996225, 2541798693045, 7625460083185, 22876524019505, 68629830861205, 205890058352825, 617671220125537

Offset: 1

Antti Karttunen, Nov 22 2021

nonn

Dirichlet convolution of this sequence with A034738 produces A034754.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A133494, A349452, A349568 (Dirichlet inverse).

Cf. also A034738, A034754, A349563, A349565, A349569.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, 3^(# - 1) * s[n/#] &]; Array[a, 32] (* Amiram Eldar, Nov 22 2021 *)

A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349567(n) = sumdiv(n,d,(3^(d-1)) * A349452(n/d));

a(n) = Sum_{d|n} 3^(d-1) * A349452(n/d).

A349569 Dirichlet convolution of A000027 (identity function) with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Original entry on oeis.org

1, 0, -1, -4, -11, -24, -57, -112, -243, -480, -1013, -1964, -4083, -8064, -16309, -32496, -65519, -130440, -262125, -523156, -1048263, -2095104, -4194281, -8383760, -16777015, -33546240, -67107609, -134200860, -268435427, -536835096, -1073741793, -2147417216, -4294962187, -8589803520, -17179867533, -34359463812

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution with A034729 gives sigma, A000203, and convolution with A034738 gives A018804.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000027, A011782, A349452, A349570 (Dirichlet inverse).

Cf. also A000203, A018804, A034729, A034738, A349563, A349565, A349567.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#]*2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, # * s[n/#] &]; Array[a, 36] (* Amiram Eldar, Nov 22 2021 *)

A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349569(n) = sumdiv(n,d,d * A349452(n/d));

a(n) = Sum_{d|n} d * A349452(n/d).

A055852 Convolution of A055589 with A011782.

Original entry on oeis.org

0, 1, 7, 34, 138, 501, 1683, 5336, 16172, 47264, 134048, 370688, 1003136, 2664192, 6960384, 17922048, 45552640, 114442240, 284508160, 700579840, 1710161920, 4141416448, 9955639296, 23770693632, 56400543744, 133041225728

Offset: 0

Wolfdieter Lang May 30 2000

Seventh column of triangle A055587.

T(n,5) of array T as in A049600.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (12,-60,160,-240,192,-64).

Cf. A011782, A049600, A055587, A055589.

a:=[1,7,34,138,501,1683];; for n in [7..30] do a[n]:=12*a[n-1] -60*a[n-2] +160*a[n-3] -240*a[n-4] +192*a[n-5] -64*a[n-6]; od; Concatenation([0], a); # G. C. Greubel, Jan 16 2020

R:=PowerSeriesRing(Integers(), 30); [0] cat Coefficients(R!( x*(1-x)^5/(1-2*x)^6 )); // G. C. Greubel, Jan 16 2020

seq(coeff(series(x*(1-x)^5/(1-2*x)^6, x, n+1), x, n), n = 0..30); # G. C. Greubel, Jan 16 2020

CoefficientList[Series[x*(1-x)^5/(1-2*x)^6, {x,0,30}], x] (* G. C. Greubel, Jan 16 2020 *)

my(x='x+O('x^30)); concat([0], Vec(x*(1-x)^5/(1-2*x)^6)) \\ G. C. Greubel, Jan 16 2020

def A055852_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-x)^5/(1-2*x)^6 ).list()
A055852_list(30) # G. C. Greubel, Jan 16 2020

a(n) = T(n, 5) = A055587(n+5, 6).

G.f.: x*(1-x)^5/(1-2*x)^6.

A290222 Multiset transform of A011782, powers of 2: 1, 2, 4, 8, 16, ...

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 4, 2, 1, 0, 8, 7, 2, 1, 0, 16, 16, 7, 2, 1, 0, 32, 42, 20, 7, 2, 1, 0, 64, 96, 54, 20, 7, 2, 1, 0, 128, 228, 140, 59, 20, 7, 2, 1, 0, 256, 512, 360, 156, 59, 20, 7, 2, 1, 0, 512, 1160, 888, 422, 162, 59, 20, 7, 2, 1, 0, 1024, 2560, 2168, 1088, 442, 162, 59, 20, 7, 2, 1

Offset: 0

M. F. Hasler, Jul 24 2017

T(n,k) is the number of multisets of exactly k binary words with a total of n letters and each word beginning with 1. T(4,2) = 7: {1,100}, {1,101}, {1,110}, {1,111}, {10,10}, {10,11}, {11,11}. - Alois P. Heinz, Sep 18 2017

			The triangle starts:
1;
0    1;
0    2    1;
0    4    2    1;
0    8    7    2    1;
0   16   16    7    2   1;
0   32   42   20    7   2   1;
0   64   96   54   20   7   2  1;
0  128  228  140   59  20   7  2  1;
0  256  512  360  156  59  20  7  2  1;
0  512 1160  888  422 162  59 20  7  2  1;
0 1024 2560 2168 1088 442 162 59 20  7  2  1;
(...)

Alois P. Heinz, Rows n = 0..140, flattened
Index entries for triangles generated by the Multiset Transformation

Cf. A034691 (row sums), A000007 (column k=0), A011782 (column k=1), A178945(n-1) (column k=2).
The reverse of the n-th row converges to A034899.
Cf. A000079, A209406, A292506.

b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(binomial(2^(i-1)+j-1, j)*
         b(n-i*j, i-1, p-j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=0..n), n=0..14);  # Alois P. Heinz, Sep 12 2017

b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[Binomial[2^(i - 1) + j - 1, j] b[n - i j, i - 1, p - j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] := b[n, n, k];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)

G.f.: 1 / Product_{j>=1} (1-y*x^j)^(2^(j-1)). - Alois P. Heinz, Sep 18 2017

A349564 Dirichlet convolution of A011782 [2^(n-1)] with A349450 [Dirichlet inverse of right-shifted Catalan numbers].

Original entry on oeis.org

1, 1, 2, 2, 2, -14, -68, -308, -1178, -4366, -15772, -56780, -203916, -734772, -2658088, -9662208, -35292134, -129514026, -477376556, -1766739436, -6563071972, -24464170892, -91478369336, -343051227304, -1289887370136, -4861912851116, -18367285963792, -69533416706328, -263747683314904, -1002241679797688

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution with A034731 gives A034729.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A349450.
Cf. A000108, A011782, A349452, A349563 (Dirichlet inverse).
Cf. also A034729, A034731, A349566, A349568.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * CatalanNumber[n/# - 1] &, # < n &]; a[n_] := DivisorSum[n, 2^(# - 1) * s[n/#] &]; Array[a, 30] (* Amiram Eldar, Nov 22 2021 *)

A000108(n) = (binomial(2*n, n)/(n+1));
memoA349450 = Map();
A349450(n) = if(1==n,1,my(v); if(mapisdefined(memoA349450,n,&v), v, v = -sumdiv(n,d,if(dA000108((n/d)-1)*A349450(d),0)); mapput(memoA349450,n,v); (v)));
A349564(n) = sumdiv(n,d,2^(d-1)*A349450(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A349450(n/d).

A349568 Dirichlet convolution of A011782 [2^(n-1)] with A349453 (Dirichlet inverse of A133494, 3^(n-1)).

Original entry on oeis.org

1, -1, -5, -16, -65, -187, -665, -1984, -6260, -18895, -58025, -174016, -527345, -1583407, -4765595, -14307568, -42981185, -128980852, -387158345, -1161657760, -3485726195, -10458022927, -31376865305, -94134053296, -282412754000, -847252941535, -2541798630320, -7625456893096, -22876524019505, -68629821114805

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution of this sequence with A034754 produces A034738.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A133494, A349453, A349567 (Dirichlet inverse).

Cf. also A034738, A034754, A349564, A349566, A349570.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 3^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, 2^(# - 1) * s[n/#] &]; Array[a, 30] (* Amiram Eldar, Nov 22 2021 *)

A133494(n) = max(1, 3^(n-1));
memoA349453 = Map();
A349453(n) = if(1==n,1,my(v); if(mapisdefined(memoA349453,n,&v), v, v = -sumdiv(n,d,if(dA133494(n/d)*A349453(d),0)); mapput(memoA349453,n,v); (v)));
A349568(n) = sumdiv(n,d,(2^(d-1)) * A349453(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A349453(n/d).

A055589 Convolution of A049612 with A011782.

Original entry on oeis.org

0, 1, 6, 26, 96, 321, 1002, 2972, 8472, 23392, 62912, 165504, 427264, 1085184, 2717184, 6718464, 16427008, 39763968, 95387648, 226951168, 535953408, 1257046016, 2929852416, 6789267456, 15648423936, 35888562176, 81927340032

Offset: 0

Wolfdieter Lang May 30 2000

Sixth column of triangle A055587. T(n,4) of array T as in A049600.

Index entries for linear recurrences with constant coefficients, signature (10, -40, 80, -80, 32).

Cf. A049600, A049612, A055587, A011782.

a(n)= T(n, 4)= A055587(n+4, 5).

G.f.: x*((1-x)^4)/(1-2*x)^5.

A055853 Convolution of A055852 with A011782.

Original entry on oeis.org

0, 1, 8, 43, 190, 743, 2668, 8989, 28814, 88720, 264224, 765088, 2162624, 5986304, 16268800, 43499264, 114629120, 298147840, 766361600, 1948794880, 4907171840, 12245598208, 30305419264, 74425892864, 181481635840, 439603953664

Offset: 0

Wolfdieter Lang May 30 2000

Eighth column of triangle A055587.

T(n,6) of array T as in A049600.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (14,-84,280,-560,672,-448,128).

Cf. A011782, A049600, A055587, A055852.

R:=PowerSeriesRing(Integers(), 30); [0] cat Coefficients(R!( x*(1-x)^6/(1-2*x)^7 )); // G. C. Greubel, Jan 16 2020

seq(coeff(series(x*(1-x)^6/(1-2*x)^7, x, n+1), x, n), n = 0..30); # G. C. Greubel, Jan 16 2020

CoefficientList[Series[x*(1-x)^6/(1-2*x)^7, {x,0,30}], x] (* G. C. Greubel, Jan 16 2020 *)

my(x='x+O('x^30)); concat([0], Vec(x*(1-x)^6/(1-2*x)^7)) \\ G. C. Greubel, Jan 16 2020

def A055853_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-x)^6/(1-2*x)^7 ).list()
A055853_list(30) # G. C. Greubel, Jan 16 2020

a(n) = T(n, 6)= A055587(n+6, 7).

G.f.: x*(1-x)^6/(1-2*x)^7.

A125107 Subtract compositions (A011782) from Catalan numbers (A000108).

Original entry on oeis.org

0, 0, 0, 1, 6, 26, 100, 365, 1302, 4606, 16284, 57762, 205964, 738804, 2666248, 9678461, 35324902, 129579254, 477507628, 1767001046, 6563596132, 24465218444, 91480466488, 343055419346, 1289895758716, 4861929624236, 18367319517720, 69533483807140, 263747817532632

Offset: 0

Alford Arnold, Dec 15 2006

Apparently the number of Dyck n-paths with more than half of the path lying between the first and last peaks. - David Scambler, Sep 14 2012
From Peter Luschny, Nov 28 2024: (Start)
A Touchard walk T(n) of length n is, as defined by Dershowitz, "a sequence of n steps, each of which is one of N/S/E/W, such that at each point along the way the number of N-steps that have been taken is never less than the number of S-steps, and are in the end equal."
There are Sum_{k=0..n} binomial(n, k) Touchard walks that have no N/S-steps at all and since by Touchard's identity T(n) = Catalan(n+1), it follows that a(n) = T(n-1) - Sum_{k=0..n-1} binomial(n-1, k) = Catalan(n) - 2^(n-1) for n >= 1. Thus a(n+1) is the number of Touchard walks of length n that have at least one N-step. (End)

			A000108 begins 1 1 2 5 14 42 132 429 ...
A011782 begins 1 1 2 4  8 16  32  64 ...
so we get .... 0 0 0 1  6 26 100 365 ...
.
The 26 Touchard walks of length 4 that have at least one N-step are:
   NNSS, NSNS, NSEE, NSEW, NSWE, NSWW, NESE, NESW, NWSE,
   NWSW, NEES, NEWS, NWES, NWWS, ENSE, ENSW, WNSE, WNSW,
   ENES, ENWS, WNES, WNWS, EENS, EWNS, WENS, WWNS.

Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

Cf. A000079, A000108, A000110, A011782, A016098, A097805, A091894 (Touchard distribution), A377659 (similar with Motzkin).

# From Peter Luschny, Nov 28 2024: (Start)
a := n -> ifelse(n = 0, 0, binomial(2*n, n)/(n+1) - 2^(n-1)): seq(a(n), n = 0..28);
# Series expansion:
gf := (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x): ser := series(gf, x, 30): seq(coeff(ser, x, n), n = 0..28);
# Evaluating polynomials:
p := (n, x) -> ifelse(n = 0, 0, 2^(n-1)*(hypergeom([1 - n/2, 1/2 - n/2], [2], x) - 1)): seq(subs(x = 1, expand(simplify(p(n, x)))), n = 0..28);  # (End)

Table[CatalanNumber[n] - If[n==0, 1, 2^(n-1)], {n, 0, 30}] (* David Scambler, Sep 14 2012 *)

# Generates the walks (for illustration only).
C = str.count
def aGen(n: int) -> Generator[str, Any, list[str]]:
    a = [""]
    if n <= 0: return a
    for w in a:
        if len(w) == n - 1:
            if C(w, "N") > 0 and C(w, "N") == C(w, "S"):
                yield w
        else:
            for j in "NSEW":
                U = w + j
                if C(U, "N") >= C(U, "S"):
                    a += [U]
    return a
for n in range(6): print([w for w in aGen(n)])  # Peter Luschny, Dec 03 2024

a(n) = A000108(n) - A011782(n).
(n+1)*a(n) + 2*(1-4*n)*a(n-1) + 4*(5*n-7)*a(n-2) + 8*(5-2*n)*a(n-3) = 0. - R. J. Mathar, Aug 10 2013
From Peter Luschny, Nov 28 2024: (Start)
a(n) = [x^n] (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x).
a(n) = n! * [x^n] (exp(2*x)*(BesselI_{0}(2*x) - BesselI_{1}(2*x) - 1/2) - 1/2).
a(n) = p(n, 1) for n >= 1, where p(n, x) = 2^(n-1)*(hypergeom([1-n/2, (1-n)/2], [2], x) - 1).
a(n) = Sum_{k=0..n} (A091894(n, k) - A097805(n, n-k)). (End)

More terms from David Scambler, Sep 14 2012

A349570 Dirichlet convolution of A011782 [2^(n-1)] with A055615 (Dirichlet inverse of n).

Original entry on oeis.org

1, 0, 1, 4, 11, 24, 57, 112, 244, 480, 1013, 1972, 4083, 8064, 16331, 32512, 65519, 130488, 262125, 523244, 1048377, 2095104, 4194281, 8384176, 16777136, 33546240, 67108096, 134201316, 268435427, 536836584, 1073741793, 2147418112, 4294964213, 8589803520, 17179868787, 34359470272, 68719476699, 137438429184, 274877894643

Offset: 1

Antti Karttunen, Nov 22 2021

nonn

Dirichlet convolution of this sequence with phi (A000010) is A000740, with sigma (A000203) it is A034729, and with A018804 it is A034738.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A055615, A349569 (Dirichlet inverse).

Cf. also A000010, A000740, A000203, A018804, A034729, A034738, A349564, A349566, A349568.

a[n_] := DivisorSum[n, # * MoebiusMu[#] * 2^(n/# - 1) &]; Array[a, 40] (* Amiram Eldar, Nov 22 2021 *)

A055615(n) = (n*moebius(n));
A349570(n) = sumdiv(n,d,(2^(d-1)) * A055615(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A055615(n/d).

cp's OEIS Frontend

A349567 Dirichlet convolution of A133494 [3^(n-1)] with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349569 Dirichlet convolution of A000027 (identity function) with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055852 Convolution of A055589 with A011782.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A290222 Multiset transform of A011782, powers of 2: 1, 2, 4, 8, 16, ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A349564 Dirichlet convolution of A011782 [2^(n-1)] with A349450 [Dirichlet inverse of right-shifted Catalan numbers].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349568 Dirichlet convolution of A011782 [2^(n-1)] with A349453 (Dirichlet inverse of A133494, 3^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055589 Convolution of A049612 with A011782.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula