Displaying 1-10 of 12 results found.
a(n) = Sum_{d|n} p(d), where p(d) = A000041 = number of partitions of d.
+10
57
1, 3, 4, 8, 8, 17, 16, 30, 34, 52, 57, 99, 102, 153, 187, 261, 298, 432, 491, 684, 811, 1061, 1256, 1696, 1966, 2540, 3044, 3876, 4566, 5846, 6843, 8610, 10203, 12610, 14906, 18491, 21638, 26508, 31290, 38044, 44584, 54133, 63262, 76241
COMMENTS
Inverse Moebius transform of A000041. Sum of the partition numbers of the divisors of n. - Omar E. Pol, Feb 25 2014 Number of constant multiset partitions of multisets spanning an initial interval of positive integers with multiplicities an integer partition of n. - Gus Wiseman, Sep 16 2018
FORMULA
G.f.: Sum_{k>0} (-1+1/Product_{i>0} (1-z^(k*i))). - Vladeta Jovovic, Jun 22 2003
EXAMPLE
For n = 10 the divisors of 10 are 1, 2, 5, 10, hence the partition numbers of the divisors of 10 are 1, 2, 7, 42, so a(10) = 1 + 2 + 7 + 42 = 52. - Omar E. Pol, Feb 26 2014 The a(6) = 17 constant multiset partitions:
(111111) (111)(111) (11)(11)(11) (1)(1)(1)(1)(1)(1)
(111222) (12)(12)(12)
(111122) (112)(112)
(112233) (123)(123)
(111112)
(111123)
(111223)
(111234)
(112234)
(112345)
(123456)
(End)
MAPLE
with(combinat): with(numtheory): a := proc(n) c := 0: l := sort(convert(divisors(n), list)): for i from 1 to nops(l) do c := c+numbpart(l[i]) od: RETURN(c): end: for j from 1 to 60 do printf(`%d, `, a(j)) od: # Zerinvary Lajos, Apr 14 2007
MATHEMATICA
a[n_] := Sum[ PartitionsP[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 44}] (* Jean-François Alcover, Oct 03 2013 *)
a(n) = Sum_{ k, k|n } 2^(k-1).
+10
44
1, 3, 5, 11, 17, 39, 65, 139, 261, 531, 1025, 2095, 4097, 8259, 16405, 32907, 65537, 131367, 262145, 524827, 1048645, 2098179, 4194305, 8390831, 16777233, 33558531, 67109125, 134225995, 268435457, 536887863, 1073741825, 2147516555, 4294968325, 8590000131
COMMENTS
Dirichlet convolution of b_n=1 with c_n = 2^(n-1).
Number of constant multiset partitions of normal multisets of size n, where a multiset is normal if it spans an initial interval of positive integers. - Gus Wiseman, Sep 16 2018
FORMULA
G.f.: Sum_{n>=1} 2^(n-1) * x^n / (1 - x^n). - Paul D. Hanna, Aug 21 2014 G.f.: Sum_{n>=1} x^n * Sum_{d|n} 1/(1 - x^d)^(n/d). - Paul D. Hanna, Aug 21 2014
EXAMPLE
The a(4) = 11 constant multiset partitions:
(1)(1)(1)(1)
(11)(11)
(12)(12)
(1111)
(1222)
(1122)
(1112)
(1233)
(1223)
(1123)
(1234)
(End)
MAPLE
seq(add(2^(k-1), k=numtheory:-divisors(n)), n = 1 .. 100); # Robert Israel, Aug 22 2014
MATHEMATICA
Rest[CoefficientList[Series[Sum[x^k/(1-2*x^k), {k, 1, 30}], {x, 0, 30}], x]] (* Vaclav Kotesovec, Sep 08 2014 *)
PROG
(PARI) {a(n)=polcoeff(sum(m=1, n, 2^(m-1)*x^m/(1-x^m +x*O(x^n))), n)}
(PARI) {a(n)=local(A=x+x^2); A=sum(m=1, n, x^m*sumdiv(m, d, 1/(1 - x^(m/d) +x*O(x^n))^d) ); polcoeff(A, n)}
(Python)
from sympy import divisors
def A034729(n): return sum(1<<(d-1) for d in divisors(n, generator=True)) # Chai Wah Wu, Jul 15 2022 (Magma)
A034729:= func< n | (&+[2^(d-1): d in Divisors(n)]) >;
(SageMath)
def A034729(n): return sum(2^(k-1) for k in (1..n) if (k).divides(n))
Dirichlet convolution of b_n = 2^(n-1) with phi(n).
+10
19
1, 3, 6, 12, 20, 42, 70, 144, 270, 540, 1034, 2112, 4108, 8274, 16440, 32928, 65552, 131418, 262162, 524880, 1048740, 2098206, 4194326, 8391024, 16777300, 33558564, 67109418, 134226120, 268435484, 536888520, 1073741854, 2147516736
COMMENTS
Sum of GCD's of parts in all compositions of n. - Vladeta Jovovic, Aug 13 2003 It also equals the sum of all lengths of all cyclic compositions of n. This was proved in Perez (2008).
The bivariate g.f. for the number b(n,k) of all cyclic of compositions of n with k parts is Sum_{n,k>=1} b(n,k)*x^n*y^k = -Sum_{s>=1} (phi(s)/s)*log(1 - y^s*Sum_{t>=1} x^{s*t}) = -Sum_{s>=1} (phi(s)/s)*log(1 - y^s*x^s/(1-x^s)). See, for example, Hadjicostas (2016). Differentiating w.r.t. y and setting y = 1, we get Sum_{n>=1} a(n)*x^n = Sum_{n>=1} (Sum_{k=1..n} b(n,k)*k)*x^n = Sum_{s>=1} phi(s)*x^s/(1-2*x^s).
(End)
FORMULA
a(n) = (1/2)* Sum_{d|n} phi(d)*2^(n/d), n >= 1.
a(n) = Sum_{k=1..n} 2^(n/gcd(n,k) - 1)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021
EXAMPLE
For the compositions of n=4 we have a(4) = gcd(4) + gcd(1,3) + gcd(3,1) + gcd(2,2) + gcd(2,1,1) + gcd(1,2,1) + gcd(1,1,2) + gcd(1,1,1,1) = 4 + 1 + 1 + 2 + 1 + 1 + 1 + 1 = 12. Also, for cyclic compositions of n=4, we have length(4) + length(1,3) + length(2,2) + length(1,1,2) + length(1,1,1,1) = 1 + 2 + 2 + 3 + 4 = 12.
MATHEMATICA
Table[Sum[EulerPhi[d]*2^(n/d-1), {d, Divisors[n]}], {n, 1, 40}] (* Vaclav Kotesovec, Feb 07 2019 *)
PROG
(PARI) a(n) = sum(k=1, n, 2^(gcd(k, n)-1)); \\ Seiichi Manyama, Apr 17 2021 (PARI) a(n) = sumdiv(n, d, eulerphi(n/d)*2^(d-1)); \\ Seiichi Manyama, Apr 17 2021 (PARI) my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k/(1-2*x^k))) \\ Seiichi Manyama, Apr 17 2021
Sum over all partitions of n of the LCM of the parts.
+10
9
1, 1, 3, 6, 12, 23, 38, 73, 118, 198, 318, 530, 819, 1298, 1974, 2975, 4516, 6698, 9980, 14550, 21186, 30304, 43503, 62030, 87908, 123292, 172543, 239720, 331688, 458198, 629376, 860332, 1168172, 1583176, 2138438, 2876283, 3859770, 5159886, 6863702, 9112356
MAPLE
with(combstruct):
a181844 := proc(n) local k, L, l, R, part;
R := NULL; L := 0;
for k from 1 to n do
part := iterstructs(Partition(n), size=k):
while not finished(part) do
l := nextstruct(part);
L := L + ilcm(op(l));
od;
od;
L end:
# second Maple program:
b:= proc(n, i, r) option remember; `if`(n=0, r, `if`(i<1, 0,
b(n, i-1, r)+b(n-i, min(i, n-i), ilcm(i, r))))
end:
a:= n-> b(n$2, 1):
MATHEMATICA
t[n_, k_] := LCM @@@ IntegerPartitions[n, {n - k + 1}] // Total; a[n_] := Sum[t[n, k], {k, 1, n}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Jul 26 2013 *)
T(n, k) = Sum_{d|n} phi(d) * A008284(n/d, k) for n >= 1, T(0, 0) = 1. Triangle read by rows for 0 <= k <= n.
+10
9
1, 0, 1, 0, 2, 1, 0, 3, 1, 1, 0, 4, 3, 1, 1, 0, 5, 2, 2, 1, 1, 0, 6, 6, 4, 2, 1, 1, 0, 7, 3, 4, 3, 2, 1, 1, 0, 8, 8, 6, 6, 3, 2, 1, 1, 0, 9, 6, 9, 6, 5, 3, 2, 1, 1, 0, 10, 11, 10, 10, 8, 5, 3, 2, 1, 1, 0, 11, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1, 0, 12, 17, 19, 19, 14, 12, 7, 5, 3, 2, 1, 1
FORMULA
For n >= 1, T(n,k) = Sum_{i=1..n} A008284(gcd(n,i),k). For n >= 1, T(n,k) = Sum_{i=1..n} A008284(n/gcd(n,i),k)*phi(gcd(n,i))/phi(n/gcd(n,i)). (End)
EXAMPLE
Triangle starts:
[0] [1]
[1] [0, 1]
[2] [0, 2, 1]
[3] [0, 3, 1, 1]
[4] [0, 4, 3, 1, 1]
[5] [0, 5, 2, 2, 1, 1]
[6] [0, 6, 6, 4, 2, 1, 1]
[7] [0, 7, 3, 4, 3, 2, 1, 1]
[8] [0, 8, 8, 6, 6, 3, 2, 1, 1]
[9] [0, 9, 6, 9, 6, 5, 3, 2, 1, 1]
PROG
(SageMath)
def DivisorTriangle(f, T, Len, w = None):
D = [[1]]
for n in (1..Len-1):
r = lambda k: [f(d)*T(n//d, k) for d in divisors(n)]
L = [sum(r(k)) for k in (0..n)]
if w != None: L = [*map(lambda v: v * w(n), L)]
D.append(L)
return D
DivisorTriangle(euler_phi, A008284, 10)
CROSSREFS
Cf. A000041 (where reversed rows converge to).
Sum of GCDs of strict integer partitions of n.
+10
4
1, 2, 4, 5, 7, 10, 11, 14, 18, 21, 22, 33, 30, 39, 49, 54, 54, 78, 72, 100, 110, 121, 126, 181, 174, 207, 238, 284, 284, 389, 370, 466, 512, 582, 647, 806, 796, 954, 1066, 1265, 1300, 1616, 1652, 1979, 2192, 2452, 2636, 3202, 3336, 3892, 4237, 4843, 5172, 6090
FORMULA
a(n) = Sum_{k=1..n} A000009(gcd(n,k)).
MAPLE
b:= proc(n, i, r) option remember; `if`(i*(i+1)/2<n, 0,
(t-> `if`(i<n, b(n-i, min(i-1, n-i), t), 0)
+`if`(i=n, t, 0)+b(n, i-1, r))(igcd(i, r)))
end:
a:= n-> b(n$2, 0):
MATHEMATICA
Table[Sum[GCD@@ptn, {ptn, Select[IntegerPartitions[n], UnsameQ@@#&]}], {n, 30}]
(* Second program: *)
b[n_, i_, r_] := b[n, i, r] = If[i(i+1)/2 < n, 0,
With[{t = GCD[i, r]}, If[i < n, b[n - i, Min[i - 1, n - i], t], 0] +
If[i == n, t, 0] + b[n, i - 1, r]]];
a[n_] := b[n, n, 0];
a(n) = Sum_{d|n} phi(d)*Bell(n/d) for n>0, a(0) = 0.
+10
3
0, 1, 3, 7, 19, 56, 214, 883, 4163, 21163, 116039, 678580, 4213848, 27644449, 190900217, 1382958677, 10480146333, 82864869820, 682076827740, 5832742205075, 51724158351527, 474869816158547, 4506715739125923, 44152005855084368, 445958869299027638
MAPLE
with(numtheory):
A:= proc(n, k) option remember;
add(phi(d)*k^(n/d), d=divisors(n))
end:
T:= (n, k)-> add((-1)^(k-i)*binomial(k, i)*A(n, i), i=0..k)/k!:
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..30);
MATHEMATICA
a[n_] := If[n == 0, 0, DivisorSum[n, EulerPhi[#] BellB[n/#] &]];
Triangle read by rows, A168532 * A000012; as infinite lower triangular matrices.
+10
2
1, 2, 1, 3, 1, 1, 5, 2, 1, 1, 7, 1, 1, 1, 1, 11, 4, 2, 1, 1, 1, 15, 1, 1, 1, 1, 1, 1, 22, 5, 2, 2, 1, 1, 1, 1, 30, 3, 3, 1, 1, 1, 1, 1, 1, 42, 8, 2, 2, 2, 1, 1, 1, 1, 1, 56, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 77, 14, 7, 4, 2, 2, 1, 1, 1, 1, 1, 1
COMMENTS
Row sums = A078392: (1, 3, 5, 9, 11, 20, 21,...). Left border = the partition numbers, A000041 starting with offset 1.
FORMULA
triangular matrix with all 1's. The operation takes partial row sums
starting from the right of each row.
EXAMPLE
First few rows of the triangle =
1;
2, 1;
3, 1, 1;
5, 2, 1, 1;
7, 1, 1, 1, 1;
11, 4, 2, 1, 1, 1;
15, 1, 1, 1, 1, 1, 1;
22, 5, 2, 2, 1, 1, 1, 1;
30, 3, 3, 1, 1, 1, 1, 1, 1;
42, 8, 2, 2, 2, 1, 1, 1, 1, 1;
56, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
77, 14, 7, 4, 2, 2, 1, 1, 1, 1, 1, 1;
101, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
135, 16, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1;
176, 9, 9, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
231, 22, 5, 5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1;
...
Irregular triangle where T(n,k) is the number of integer partitions of n with GCD equal to the k-th divisor of n.
+10
2
1, 1, 1, 2, 1, 3, 1, 1, 6, 1, 7, 2, 1, 1, 14, 1, 17, 3, 1, 1, 27, 2, 1, 34, 6, 1, 1, 55, 1, 63, 7, 3, 2, 1, 1, 100, 1, 119, 14, 1, 1, 167, 6, 2, 1, 209, 17, 3, 1, 1, 296, 1, 347, 27, 7, 2, 1, 1, 489, 1, 582, 34, 6, 3, 1, 1, 775, 14, 2, 1, 945, 55, 1, 1, 1254
EXAMPLE
Triangle begins:
1
1 1
2 1
3 1 1
6 1
7 2 1 1
14 1
17 3 1 1
27 2 1
34 6 1 1
55 1
63 7 3 2 1 1
100 1
119 14 1 1
167 6 2 1
209 17 3 1 1
296 1
347 27 7 2 1 1
489 1
582 34 6 3 1 1
MAPLE
# with table A000837 obtained from that sequence f:= proc(n) local D, d;
D:= sort(convert(numtheory:-divisors(n), list), `>`);
end proc:
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], GCD@@#==k&]], {n, 20}, {k, Divisors[n]}]
a(n) = Sum_{d|n} phi(d)*(n/d)! for n > 0, a(0) = 0.
+10
2
0, 1, 3, 8, 28, 124, 732, 5046, 40352, 362898, 3628932, 39916810, 479002388, 6227020812, 87178296258, 1307674368272, 20922789928384, 355687428096016, 6402373706092350, 121645100408832018, 2432902008180269152, 51090942171709450128, 1124000727777647596830
MAPLE
with(numtheory); A327030 := n -> add(phi(d)*(n/d)!, d = divisors(n)):
MATHEMATICA
a[0] = 0; a[n_] := DivisorSum[n, EulerPhi[#] * (n/#)! &]; Array[a, 23, 0] (* Amiram Eldar, May 24 2021 *)
PROG
(PARI) a(n) = if (n>0, sumdiv(n, d, eulerphi(d)*(n/d)!), 0); \\ Michel Marcus, Aug 28 2019 (Magma) [0] cat [&+[EulerPhi(d)*Factorial(n div d):d in Divisors(n)]:n in [1..22]]; // Marius A. Burtea, Nov 13 2019 (Magma) [0] cat [&+[Factorial(Gcd(n, i)):i in [1..n]]:n in [1..22]]; // Marius A. Burtea, Nov 13 2019
Search completed in 0.011 seconds
|