A056045 -id:A056045 - cp's OEIS frontend

A060173 Number of orbits of length n under a map whose periodic points are counted by A056045.

1, 1, 1, 2, 1, 6, 1, 12, 10, 30, 1, 139, 1, 252, 231, 920, 1, 3780, 1, 10250, 5601, 32076, 1, 149390, 2126, 400036, 173692, 1475642, 1, 6196651, 1, 19113136, 5864915, 68635494, 201405, 289525026, 1, 930138540, 208267554, 3469290971, 1, 14075005210, 1, 47994721225, 7683440470

Offset: 1

Thomas Ward, Mar 13 2001

The sequence A056045 records the number of points of period n under a map. The number of orbits of length n for this map gives the sequence above.

			a(7) = 1 since the map whose periodic points are counted by A056045 has 1 fixed point and 8 points of period 7, hence 1 orbits of length 7.

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.

Cf. A056045, A060164, A060165, A060166, A060167, A060168, A060169, A060170, A060171, A060172.

a056045(n) = sumdiv(n, d, binomial(n, d));
a(n) = (1/n)*sumdiv(n, d, moebius(d)*a056045(n/d)); \\ Michel Marcus, Sep 11 2017

a(n) = (1/n)* Sum_{ d divides n } mu(d)*A056045(n/d).

More terms from Michel Marcus, Sep 11 2017

A110448 G.f.: A(x) = exp( Sum_{n>=1} A056045(n)/n*x^n ), where A056045(n) = Sum_{d|n} binomial(n,d).

Original entry on oeis.org

1, 1, 2, 3, 6, 8, 18, 23, 49, 73, 145, 194, 474, 611, 1331, 2027, 4393, 5919, 14736, 19415, 46487, 68504, 156618, 212055, 560380, 739165, 1833012, 2657837, 6513367, 8743208, 23649777, 31140300, 81276046, 114962333, 293600318, 391926154

Offset: 0

Paul D. Hanna, Jul 20 2005, Nov 10 2007

nonn

			G.f.: A(x) = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 8*x^5 + 18*x^6 +...
where A(x) = exp( Sum_{n>=1} A056045(n)/n*x^n ), or
A(x) = exp(x + 3/2*x^2 + 4/3*x^3 + 11/4*x^4 + 6/5*x^5 +...).
The g.f. can also be expressed as the product:
A(x) = 1/(1-x)*G000108(x^2)*G001764(x^3)*G002293(x^4)*G002294(x^5)*...
where the functions are g.f.s of well-known sequences:
G000108(x) = 1 + x*G000108(x)^2 = g.f. of A000108 ;
G001764(x) = 1 + x*G001764(x)^3 = g.f. of A001764 ;
G002293(x) = 1 + x*G002293(x)^4 = g.f. of A002293 ;
G002294(x) = 1 + x*G002294(x)^5 = g.f. of A002294 ; etc.

Seiichi Manyama, Table of n, a(n) for n = 0..3337

Cf. A056045, A174461, A206290.

Cf. A000108, A001764, A002293, A002294, A002295.

{a(n)=polcoeff(exp(x*Ser(vector(n,m, sumdiv(m,d,binomial(m,d))/m))+x*O(x^n)),n)}

{a(n)=polcoeff(prod(m=1,n,1/x*serreverse(x/(1+x^m +x*O(x^n)))),n)}

G.f.: A(x) = Product_{n>=1} (1/x)*Series_Reversion( x/(1 + x^n) ); equivalently, G.f.: A(x) = Product_{n>=1} G(x^n,n) where G(x,n) = 1 + x*G(x,n)^n.

a(n) ~ c * 2^n / n^(3/2), where c = 2.8176325363130737043447... if n is even and c = 1.784372019603712867208... if n is odd. - Vaclav Kotesovec, Jan 15 2019

A056200 a(n) = 2^n - A056045(n).

Original entry on oeis.org

1, 1, 4, 5, 26, 22, 120, 149, 418, 716, 2036, 2378, 8178, 12846, 29294, 50709, 131054, 193972, 524268, 843260, 1979520, 3488618, 8388584, 13190042, 33501276, 56707912, 129527950, 227113934, 536870882, 887838482, 2147483616, 3683332117, 8396392382, 14846262368, 34352689180

Offset: 1

Labos Elemer, Aug 02 2000

nonn

Amiram Eldar, Table of n, a(n) for n = 1..1000

Cf. A000079, A056045.

a[n_] := 2^n - DivisorSum[n, Binomial[n, #] &]; Array[a, 40] (* Amiram Eldar, Aug 18 2024 *)

a(n) = 2^n - sumdiv(n, d, binomial(n, d)); \\ Michel Marcus, Aug 25 2019

a(p) = 2^p - p - 1 for a prime p.

More terms from Amiram Eldar, Aug 18 2024

A308037 a(n) = Sum_{d|n} Stirling2(n,d).

Original entry on oeis.org

1, 2, 2, 9, 2, 123, 2, 1830, 3027, 43038, 2, 2023728, 2, 49337473, 213142023, 2313595723, 2, 216927216877, 2, 6712023695345, 82312699558575, 366282502967439, 2, 113350450913387211, 2436684974110753, 1850568574287104493, 106563274551407600878, 231678790379913209098, 2

Offset: 1

Ilya Gutkovskiy, May 10 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..579

Cf. A000040, A008277, A056045, A096308.

a:= n-> add(Stirling2(n, d), d=numtheory[divisors](n)):
seq(a(n), n=1..30);  # Alois P. Heinz, May 10 2019

a[n_] := a[n] = Sum[StirlingS2[n, d], {d, Divisors[n]}]; Table[a[n], {n, 1, 29}]

a(n) = sumdiv(n, d, stirling(n, d, 2)); \\ Michel Marcus, May 10 2019

a(n) = 2 <=> n is prime <=> n in { A000040 }. - Alois P. Heinz, May 10 2019

A271654 a(n) = Sum_{k|n} binomial(n-1,k-1).

Original entry on oeis.org

1, 2, 2, 5, 2, 17, 2, 44, 30, 137, 2, 695, 2, 1731, 1094, 6907, 2, 30653, 2, 97244, 38952, 352739, 2, 1632933, 10628, 5200327, 1562602, 20357264, 2, 87716708, 2, 303174298, 64512738, 1166803145, 1391282, 4978661179, 2, 17672631939, 2707475853, 69150651910, 2, 286754260229, 2, 1053966829029, 115133177854, 4116715363847, 2, 16892899722499, 12271514, 63207357886437

Offset: 1

Franklin T. Adams-Watters, Apr 11 2016

nonn

Also the number of compositions of n whose length divides n, i.e., compositions with integer mean, ranked by A096199. - Gus Wiseman, Sep 28 2022

			From _Gus Wiseman_, Sep 28 2022: (Start)
The a(1) = 1 through a(6) = 17 compositions with integer mean:
  (1)  (2)    (3)      (4)        (5)          (6)
       (1,1)  (1,1,1)  (1,3)      (1,1,1,1,1)  (1,5)
                       (2,2)                   (2,4)
                       (3,1)                   (3,3)
                       (1,1,1,1)               (4,2)
                                               (5,1)
                                               (1,1,4)
                                               (1,2,3)
                                               (1,3,2)
                                               (1,4,1)
                                               (2,1,3)
                                               (2,2,2)
                                               (2,3,1)
                                               (3,1,2)
                                               (3,2,1)
                                               (4,1,1)
                                               (1,1,1,1,1,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..3329

Cf. A056045.
The version for nonempty subsets is A051293, geometric A326027.
The version for partitions is A067538, ranked by A316413, strict A102627.
These compositions are ranked by A096199.
The version for factorizations is A326622, geometric A326028.
A011782 counts compositions.
A067539 = partitions w integer geo mean, ranked by A326623, strict A326625.
A100346 counts compositions into divisors, partitions A018818.
Cf. A000041, A078174, A078175, A326567/A326568, A326624, A326641, A326836, A326837, A326843.

a:= n-> add(binomial(n-1, d-1), d=numtheory[divisors](n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Dec 03 2023

Table[Length[Join @@ Permutations/@Select[IntegerPartitions[n],IntegerQ[Mean[#]]&]],{n,15}] (* Gus Wiseman, Sep 28 2022 *)

PARI
```
a(n)=sumdiv(n,k,binomial(n-1,k-1))
```

A056188 a(1) = 1; for n>1, sum of binomial(n,k) as k runs over RRS(n), the reduced residue system of n.

Original entry on oeis.org

1, 2, 6, 8, 30, 12, 126, 128, 342, 260, 2046, 1608, 8190, 4760, 15840, 32768, 131070, 80820, 524286, 493280, 1165542, 1391720, 8388606, 5769552, 26910650, 23153832, 89478486, 131849648, 536870910, 352845960, 2147483646, 2147483648

Offset: 1

Labos Elemer, Aug 02 2000

nonn

a(n) is a multiple of n for all n.

For n > 1, a(n) is the number of binary words of length n such that the quantities of 0's and 1's are coprime. - Bartlomiej Pawlik, Sep 03 2023

			For n=10, RRS[10]={1,3,7,9}, the corresponding coefficients are {10,120,120,10}, so the sum a(10)=260.

Laszlo Toth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.

Cf. A056045, A056189.

A056188 := proc(n)
    a := 0 ;
    for k from 1 to n do
        if igcd(k,n) = 1 then
            a := a+binomial(n,k);
        end if ;
    end do:
    a ;
end proc: # R. J. Mathar, Sep 02 2017

f[n_] := Plus @@ Binomial[n, Select[ Range[n], GCD[n, # ] == 1 &]]; Table[ f[n], {n, 33}] (* Robert G. Wilson v, Nov 04 2004 *)

a(n) = if (n==1, 1, sum(k=0, n, if (gcd(n,k) == 1, binomial(n,k)))); \\ Michel Marcus, Mar 22 2020

a(n) = Sum{binomial[n, k]; GCD[n, k]=1, 0<=k<=n}.

For n=prime, a(n)=2^n-2 because all k<=n except 0 and n are used.

A327238 Expansion of Sum_{k>=1} ((1 + k * x^k)^k - 1).

Original entry on oeis.org

1, 4, 9, 20, 25, 63, 49, 160, 108, 350, 121, 940, 169, 1225, 1475, 2304, 289, 7560, 361, 8025, 12446, 7139, 529, 58192, 3750, 13858, 61965, 102655, 841, 191181, 961, 318464, 220704, 40460, 354172, 1304370, 1369, 63175, 629863, 4012608, 1681, 1916733, 1849

Offset: 1

Ilya Gutkovskiy, Sep 14 2019

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

Cf. A055225, A056045, A318636, A327124.

nmax = 43; CoefficientList[Series[Sum[((1 + k x^k)^k - 1), {k, 1, nmax}], {x, 0, nmax}], x] // Rest
Table[DivisorSum[n, (n/#)^# Binomial[n/#, #] &], {n, 1, 43}]

a(n)={sumdiv(n, d, (n/d)^d * binomial(n/d,d))} \\ Andrew Howroyd, Sep 14 2019

a(n) = Sum_{d|n} (n/d)^d * binomial(n/d,d).

a(p) = p^2, where p is prime.

A051054 a(n) = Sum_{k=1..n} C(n, floor(n/k)).

Original entry on oeis.org

0, 1, 3, 7, 15, 26, 54, 85, 159, 292, 513, 804, 1844, 2965, 5169, 10679, 20107, 34120, 72498, 126028, 245966, 498852, 913872, 1644570, 3600916, 6530881, 12280999, 25149973, 48355605, 89310576, 187976827, 348475899, 677303827

Offset: 0

N. J. A. Sloane

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A056045, A273160, A273161, A345466.

A051054 := proc(n) local k; add(binomial(n,floor(n/k)), k=1..n); end; [seq(A051054(n), n=0..40)];

Table[Sum[Binomial[n, Floor[n/i]], {i, n}], {n, 0, 40}] (* Wesley Ivan Hurt, May 16 2016 *)

a(n) = sum(k=1, n, binomial(n, n\k)); \\ Seiichi Manyama, Jan 06 2022

a(n) is asymptotic to 2^n/sqrt(n*Pi/2). - Benoit Cloitre, Jan 11 2003

A174462 a(n) = Sum_{d|n} binomial(n,d)^2.

Original entry on oeis.org

1, 5, 10, 53, 26, 662, 50, 5749, 7138, 65630, 122, 1151702, 170, 11787102, 9225260, 168963957, 290, 2709216086, 362, 34398664078, 13522807742, 497634360470, 530, 7871610432598, 2822797526, 108172480466302, 21966337136980

Offset: 1

Paul D. Hanna, Apr 04 2010

nonn

Analog to the central binomial coefficients: A000984(n) = Sum_{k=0..n} C(n,k)^2.

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

Cf. A056045, A174461.

PARI
```
{a(n)=sumdiv(n,d,binomial(n,d)^2)}
```

Logarithmic derivative of A174461.

A105862 a(n) = n * Sum_{d|n} binomial(n,d)/gcd(n,d).

Original entry on oeis.org

1, 5, 10, 29, 26, 122, 50, 317, 334, 830, 122, 4754, 170, 7698, 11510, 34237, 290, 159530, 362, 458054, 358592, 1413890, 530, 8236946, 266276, 20806102, 14087530, 85118762, 842, 404242022, 962, 1244530621, 580671266, 4667223134, 35896250

Offset: 1

Robert G. Wilson v, Apr 23 2005

nonn

			L.g.f.: A(x) = x + 5/2*x^2 + 10/3*x^3 + 29/4*x^4 + 26/5*x^5 + 61/3*x^6 +...
L.g.f.: A(x) = LOG[1/(1-x) * G(x^2,2)^2 * G(x^3,3)^3 * G(x^4,4)^4 *...]
where the functions G(x,n) are g.f.s of well-known sequences:
G(x,2) = g.f. of A000108 = 1 + x*G(x,2)^2;
G(x,3) = g.f. of A001764 = 1 + x*G(x,3)^3;
G(x,4) = g.f. of A002293 = 1 + x*G(x,4)^4 ; etc.
Exponentiation of l.g.f. A(x) is expressed by a product that begins:
exp(A(x)) = [1 + x + x^2 + x^3 +...] * [1 + 2*x^2 + 5*x^4 + 14*x^6 +...] * [1 + 3*x^3 + 12*x^6 + 55*x^9 +...] * [1 + 4*x^4 + 22*x^8 + 140*x^12 +...] * ...

Cf. A105861, A105863.

Cf. A134774 (exp(A(x))); A056045 (variant); A000108 (Catalan), A001764, A002293.

f[n_] := Block[{d = Divisors[n]}, n*Plus @@ (Binomial[n, d]/GCD[n, d])]; Table[ f[n], {n, 35}]

a(n)=n*polcoeff(sum(m=1,n,m*log(1/x*serreverse(x/(1+x^m +x*O(x^n))))),n)

a(n)=if(n<1,0,n*sumdiv(n,d,binomial(n,d)/gcd(n,d))) \\ Paul D. Hanna, Nov 11 2007

a(n) = n * Sum_{d|n} (binomial(n, d) / GCD(n, d)).

L.g.f.: A(x) = Sum_{n>=1} LOG[ G(x^n,n)^n ] where G(x,n) = 1 + x*G(x,n)^n, where exp(A(x)) = g.f. of A110448. - Paul D. Hanna, Nov 11 2007

cp's OEIS Frontend

A060173 Number of orbits of length n under a map whose periodic points are counted by A056045.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A110448 G.f.: A(x) = exp( Sum_{n>=1} A056045(n)/n*x^n ), where A056045(n) = Sum_{d|n} binomial(n,d).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A056200 a(n) = 2^n - A056045(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A308037 a(n) = Sum_{d|n} Stirling2(n,d).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A271654 a(n) = Sum_{k|n} binomial(n-1,k-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A056188 a(1) = 1; for n>1, sum of binomial(n,k) as k runs over RRS(n), the reduced residue system of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A327238 Expansion of Sum_{k>=1} ((1 + k * x^k)^k - 1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI