Search: a185651 -id:a185651
|
| |
|
|
A258170
|
|
T(n,k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i) * C(k,i) * A185651(n,i); triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
|
|
+20
4
|
|
|
|
0, 0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 8, 6, 1, 0, 5, 15, 25, 10, 1, 0, 6, 36, 91, 65, 15, 1, 0, 7, 63, 301, 350, 140, 21, 1, 0, 8, 136, 972, 1702, 1050, 266, 28, 1, 0, 9, 261, 3027, 7770, 6951, 2646, 462, 36, 1, 0, 10, 530, 9355, 34115, 42526, 22827, 5880, 750, 45, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = 1/k! * Sum_{i=0..k} (-1)^(k-i) * C(k,i) * A185651(n,i).
Conjecture 1: T(n,k) = Stirling2(n,k) for k >= 1 and k <= n <= 2*k - 1.
Conjecture 2: T(n,k) = Stirling2(n,k) for k >= 2 and n prime >= 2.
Here, Stirling2(n,k) = A008277(n,k).
(End)
|
|
|
EXAMPLE
|
Triangle T(n,k) begins:
0;
0, 1;
0, 2, 1;
0, 3, 3, 1;
0, 4, 8, 6, 1;
0, 5, 15, 25, 10, 1;
0, 6, 36, 91, 65, 15, 1;
0, 7, 63, 301, 350, 140, 21, 1;
0, 8, 136, 972, 1702, 1050, 266, 28, 1;
0, 9, 261, 3027, 7770, 6951, 2646, 462, 36, 1;
0, 10, 530, 9355, 34115, 42526, 22827, 5880, 750, 45, 1;
|
|
|
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!:
seq(seq(T(n, k), k=0..n), n=0..12);
|
|
|
MATHEMATICA
|
A[n_, k_] := A[n, k] = DivisorSum[n, EulerPhi[#]*k^(n/#)&];
T[n_, k_] := Sum[(-1)^(k-i)*Binomial[k, i]*A[n, i], {i, 0, k}]/k!; T[0, 0] = 0;
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 25 2017, translated from Maple *)
|
|
|
PROG
|
(Sage) # uses[DivisorTriangle from A327029]
DivisorTriangle(euler_phi, stirling_number2, 10) # Peter Luschny, Aug 24 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A002378
|
|
Oblong (or promic, pronic, or heteromecic) numbers: a(n) = n*(n+1).
(Formerly M1581 N0616)
|
|
+10
783
|
|
|
|
0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462, 506, 552, 600, 650, 702, 756, 812, 870, 930, 992, 1056, 1122, 1190, 1260, 1332, 1406, 1482, 1560, 1640, 1722, 1806, 1892, 1980, 2070, 2162, 2256, 2352, 2450, 2550
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
4*a(n) + 1 are the odd squares A016754(n).
The word "pronic" (used by Dickson) is incorrect. - Michael Somos
According to the 2nd edition of Webster, the correct word is "promic". - R. K. Guy
a(n) is the number of minimal vectors in the root lattice A_n (see Conway and Sloane, p. 109).
Let M_n denote the n X n matrix M_n(i, j) = (i + j); then the characteristic polynomial of M_n is x^(n-2) * (x^2 - a(n)*x - A002415(n)). - Benoit Cloitre, Nov 09 2002
The greatest LCM of all pairs (j, k) for j < k <= n for n > 1. - Robert G. Wilson v, Jun 19 2004
First differences are a(n+1) - a(n) = 2*n + 2 = 2, 4, 6, ... (while first differences of the squares are (n+1)^2 - n^2 = 2*n + 1 = 1, 3, 5, ...). - Alexandre Wajnberg, Dec 29 2005
25 appended to these numbers corresponds to squares of numbers ending in 5 (i.e., to squares of A017329). - Lekraj Beedassy, Mar 24 2006
A rapid (mental) multiplication/factorization technique -- a generalization of Lekraj Beedassy's comment: For all bases b >= 2 and positive integers n, c, d, k with c + d = b^k, we have (n*b^k + c)*(n*b^k + d) = a(n)*b^(2*k) + c*d. Thus the last 2*k base-b digits of the product are exactly those of c*d -- including leading 0(s) as necessary -- with the preceding base-b digit(s) the same as a(n)'s. Examples: In decimal, 113*117 = 13221 (as n = 11, b = 10 = 3 + 7, k = 1, 3*7 = 21, and a(11) = 132); in octal, 61*67 = 5207 (52 is a(6) in octal). In particular, for even b = 2*m (m > 0) and c = d = m, such a product is a square of this type. Decimal factoring: 5609 is immediately seen to be 71*79. Likewise, 120099 = 301*399 (k = 2 here) and 99990000001996 = 9999002*9999998 (k = 3). - Rick L. Shepherd, Jul 24 2021
Number of circular binary words of length n + 1 having exactly one occurrence of 01. Example: a(2) = 6 because we have 001, 010, 011, 100, 101 and 110. Column 1 of A119462. - Emeric Deutsch, May 21 2006
The sequence of iterated square roots sqrt(N + sqrt(N + ...)) has for N = 1, 2, ... the limit (1 + sqrt(1 + 4*N))/2. For N = a(n) this limit is n + 1, n = 1, 2, .... For all other numbers N, N >= 1, this limit is not a natural number. Examples: n = 1, a(1) = 2: sqrt(2 + sqrt(2 + ...)) = 1 + 1 = 2; n = 2, a(2) = 6: sqrt(6 + sqrt(6 + ...)) = 1 + 2 = 3. - Wolfdieter Lang, May 05 2006
Nonsquare integers m divisible by ceiling(sqrt(m)), except for m = 0. - Max Alekseyev, Nov 27 2006
The number of off-diagonal elements of an (n + 1) X (n + 1) matrix. - Artur Jasinski, Jan 11 2007
a(n) is equal to the number of functions f:{1, 2} -> {1, 2, ..., n + 1} such that for a fixed x in {1, 2} and a fixed y in {1, 2, ..., n + 1} we have f(x) <> y. - Aleksandar M. Janjic and Milan Janjic, Mar 13 2007
Numbers m >= 0 such that round(sqrt(m+1)) - round(sqrt(m)) = 1. - Hieronymus Fischer, Aug 06 2007
Numbers m >= 0 such that ceiling(2*sqrt(m+1)) - 1 = 1 + floor(2*sqrt(m)). - Hieronymus Fischer, Aug 06 2007
Numbers m >= 0 such that fract(sqrt(m+1)) > 1/2 and fract(sqrt(m)) < 1/2 where fract(x) is the fractional part (fract(x) = x - floor(x), x >= 0). - Hieronymus Fischer, Aug 06 2007
X values of solutions to the equation 4*X^3 + X^2 = Y^2. To find Y values: b(n) = n(n+1)(2n+1). - Mohamed Bouhamida, Nov 06 2007
Nonvanishing diagonal of A132792, the infinitesimal Lah matrix, so "generalized factorials" composed of a(n) are given by the elements of the Lah matrix, unsigned A111596, e.g., a(1)*a(2)*a(3) / 3! = -A111596(4,1) = 24. - Tom Copeland, Nov 20 2007
If Y is a 2-subset of an n-set X then, for n >= 2, a(n-2) is the number of 2-subsets and 3-subsets of X having exactly one element in common with Y. - Milan Janjic, Dec 28 2007
a(n) coincides with the vertex of a parabola of even width in the Redheffer matrix, directed toward zero. An integer p is prime if and only if for all integer k, the parabola y = kx - x^2 has no integer solution with 1 < x < k when y = p; a(n) corresponds to odd k. - Reikku Kulon, Nov 30 2008
The third differences of certain values of the hypergeometric function 3F2 lead to the squares of the oblong numbers i.e., 3F2([1, n + 1, n + 1], [n + 2, n + 2], z = 1) - 3*3F2([1, n + 2, n + 2], [n + 3, n + 3], z = 1) + 3*3F2([1, n + 3, n + 3], [n + 4, n + 4], z = 1) - 3F2([1, n + 4, n + 4], [n + 5, n + 5], z = 1) = (1/((n+2)*(n+3)))^2 for n = -1, 0, 1, 2, ... . See also A162990. - Johannes W. Meijer, Jul 21 2009
Generalized factorials, [a.(n!)] = a(n)*a(n-1)*...*a(0) = A010790(n), with a(0) = 1 are related to A001263. - Tom Copeland, Sep 21 2011
For n > 1, a(n) is the number of functions f:{1, 2} -> {1, ..., n + 2} where f(1) > 1 and f(2) > 2. Note that there are n + 1 possible values for f(1) and n possible values for f(2). For example, a(3) = 12 since there are 12 functions f from {1, 2} to {1, 2, 3, 4, 5} with f(1) > 1 and f(2) > 2. - Dennis P. Walsh, Dec 24 2011
a(n) gives the number of (n + 1) X (n + 1) symmetric (0, 1)-matrices containing two ones (see [Cameron]). - L. Edson Jeffery, Feb 18 2012
a(n) is the number of positions of a domino in a rectangled triangular board with both legs equal to n + 1. - César Eliud Lozada, Sep 26 2012
a(n) is the number of ordered pairs (x, y) in [n+2] X [n+2] with |x-y| > 1. - Dennis P. Walsh, Nov 27 2012
a(n) is the number of injective functions from {1, 2} into {1, 2, ..., n + 1}. - Dennis P. Walsh, Nov 27 2012
a(n) is the sum of the positive differences of the partition parts of 2n + 2 into exactly two parts (see example). - Wesley Ivan Hurt, Jun 02 2013
Number of positive roots in the root system of type D_{n + 1} (for n > 2). - Tom Edgar, Nov 05 2013
Number of roots in the root system of type A_n (for n > 0). - Tom Edgar, Nov 05 2013
a(m), for m >= 1, are the only positive integer values t for which the Binet-de Moivre formula for the recurrence b(n) = b(n-1) + t*b(n-2) with b(0) = 0 and b(1) = 1 has a root of a square. PROOF (as suggested by Wolfdieter Lang, Mar 26 2014): The sqrt(1 + 4t) appearing in the zeros r1 and r2 of the characteristic equation is (a positive) integer for positive integer t precisely if 4t + 1 = (2m + 1)^2, that is t = a(m), m >= 1. Thus, the characteristic roots are integers: r1 = m + 1 and r2 = -m.
Let m > 1 be an integer. If b(n) = b(n-1) + a(m)*b(n-2), n >= 2, b(0) = 0, b(1) = 1, then lim_{n->oo} b(n+1)/b(n) = m + 1. (End)
Cf. A130534 for relations to colored forests, disposition of flags on flagpoles, and colorings of the vertices (chromatic polynomial) of the complete graphs (here simply K_2). - Tom Copeland, Apr 05 2014
The set of integers k for which k + sqrt(k + sqrt(k + sqrt(k + sqrt(k + ...) ... is an integer. - Leslie Koller, Apr 11 2014
a(n-1) is the largest number k such that (n*k)/(n+k) is an integer. - Derek Orr, May 22 2014
Number of ways to place a domino and a singleton on a strip of length n - 2. - Ralf Stephan, Jun 09 2014
With offset 1, this appears to give the maximal number of crossings between n nonconcentric circles of equal radius. - Felix Fröhlich, Jul 14 2014
For n > 1, the harmonic mean of the n values a(1) to a(n) is n + 1. The lowest infinite sequence of increasing positive integers whose cumulative harmonic mean is integral. - Ian Duff, Feb 01 2015
a(n) is the maximum number of queens of one color that can coexist without attacking one queen of the opponent's color on an (n+2) X (n+2) chessboard. The lone queen can be placed in any position on the perimeter of the board. - Bob Selcoe, Feb 07 2015
With a(0) = 1, a(n-1) is the smallest positive number not in the sequence such that Sum_{i = 1..n} 1/a(i-1) has a denominator equal to n. - Derek Orr, Jun 17 2015
The positive members of this sequence are a proper subsequence of the so-called 1-happy couple products A007969. See the W. Lang link there, eq. (4), with Y_0 = 1, with a table at the end. - Wolfdieter Lang, Sep 19 2015
For n > 0, a(n) is the reciprocal of the area bounded above by y = x^(n-1) and below by y = x^n for x in the interval [0, 1]. Summing all such areas visually demonstrates the formula below giving Sum_{n >= 1} 1/a(n) = 1. - Rick L. Shepherd, Oct 26 2015
It appears that, except for a(0) = 0, this is the set of positive integers n such that x*floor(x) = n has no solution. (For example, to get 3, take x = -3/2.) - Melvin Peralta, Apr 14 2016
If two independent real random variables, x and y, are distributed according to the same exponential distribution: pdf(x) = lambda * exp(-lambda * x), lambda > 0, then the probability that n - 1 <= x/y < n is given by 1/a(n). - Andres Cicuttin, Dec 03 2016
a(n) is equal to the sum of all possible differences between n different pairs of consecutive odd numbers (see example). - Miquel Cerda, Dec 04 2016
a(n+1) is the dimension of the space of vector fields in the plane with polynomial coefficients up to order n. - Martin Licht, Dec 04 2016
It appears that a(n) + 3 is the area of the largest possible pond in a square (A268311). - Craig Knecht, May 04 2017
Also the number of 3-cycles in the (n+3)-triangular honeycomb acute knight graph. - Eric W. Weisstein, Jul 27 2017
The left edge of a Floyd's triangle that consists of even numbers: 0; 2, 4; 6, 8, 10; 12, 14, 16, 18; 20, 22, 24, 26, 28; ... giving 0, 2, 6, 12, 20, ... The right edge generates A028552. - Waldemar Puszkarz, Feb 02 2018
a(n+1) is the order of rowmotion on a poset obtained by adjoining a unique minimal (or maximal) element to a disjoint union of at least two chains of n elements. - Nick Mayers, Jun 01 2018
For n > 0, 1/a(n) = n/(n+1) - (n-1)/n.
For example, 1/6 = 2/3 - 1/2; 1/12 = 3/4 - 2/3.
Corollary of this:
Take 1/2 pill.
Next day, take 1/6 pill. 1/2 + 1/6 = 2/3, so your daily average is 1/3.
Next day, take 1/12 pill. 2/3 + 1/12 = 3/4, so your daily average is 1/4.
And so on. (End)
For an oblong number m >= 6 there exists a Euclidean division m = d*q + r with q < r < d which are in geometric progression, in this order, with a common integer ratio b. For b >= 2 and q >= 1, the Euclidean division is m = qb*(qb+1) = qb^2 * q + qb where (q, qb, qb^2) are in geometric progression.
Some examples with distinct ratios and quotients:
6 | 4 30 | 25 42 | 18
----- ----- -----
2 | 1 , 5 | 1 , 6 | 2 ,
and also:
42 | 12 420 | 100
----- -----
6 | 3 , 20 | 4 .
Some oblong numbers also satisfy a Euclidean division m = d*q + r with q < r < d that are in geometric progression in this order but with a common noninteger ratio b > 1 (see A335064). (End)
For n >= 1, the continued fraction expansion of sqrt(a(n)) is [n; {2, 2n}]. For n=1, this collapses to [1; {2}]. - Magus K. Chu, Sep 09 2022
a(n-2) is the maximum irregularity over all trees with n vertices. The extremal graphs are stars. (The irregularity of a graph is the sum of the differences between the degrees over all edges of the graph.) - Allan Bickle, May 29 2023
For n > 0, number of diagonals in a regular 2*(n+1)-gon that are not parallel to any edge (cf. A367204). - Paolo Xausa, Mar 30 2024
a(n-1) is the maximum Zagreb index over all trees with n vertices. The extremal graphs are stars. (The Zagreb index of a graph is the sum of the squares of the degrees over all vertices of the graph.) - Allan Bickle, Apr 11 2024
For n >= 1, a(n) is the determinant of the distance matrix of a cycle graph on 2*n + 1 vertices (if the length of the cycle is even such a determinant is zero). - Miquel A. Fiol, Aug 20 2024
|
|
|
REFERENCES
|
W. W. Berman and D. E. Smith, A Brief History of Mathematics, 1910, Open Court, page 67.
J. H. Conway and R. K. Guy, The Book of Numbers, 1996, p. 34.
J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag.
L. E. Dickson, History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, p. 357, 1952.
L. E. Dickson, History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Chelsea, pp. 6, 232-233, 350 and 407, 1952.
H. Eves, An Introduction to the History of Mathematics, revised, Holt, Rinehart and Winston, 1964, page 72.
Nicomachus of Gerasa, Introduction to Arithmetic, translation by Martin Luther D'Ooge, Ann Arbor, University of Michigan Press, 1938, p. 254.
Granino A. Korn and Theresa M. Korn, Mathematical Handbook for Scientists and Engineers, McGraw-Hill Book Company, New York (1968), pp. 980-981.
C. S. Ogilvy and J. T. Anderson, Excursions in Number Theory, Oxford University Press, 1966, pp. 61-62.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
F. J. Swetz, From Five Fingers to Infinity, Open Court, 1994, p. 219.
|
|
|
LINKS
|
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
|
|
|
FORMULA
|
a(n) = a(n-1) + 2*n, a(0) = 0.
Sum_{n >= 1} a(n) = n*(n+1)*(n+2)/3 (cf. A007290, partial sums).
Sum_{n >= 1} 1/a(n) = 1. (Cf. Tijdeman)
Sum_{n >= 1} (-1)^(n+1)/a(n) = log(4) - 1 = A016627 - 1 [Jolley eq (235)].
1 = 1/2 + Sum_{n >= 1} 1/(2*a(n)) = 1/2 + 1/4 + 1/12 + 1/24 + 1/40 + 1/60 + ... with partial sums: 1/2, 3/4, 5/6, 7/8, 9/10, 11/12, 13/14, ... - Gary W. Adamson, Jun 16 2003
a(n)*a(n+1) = a(n*(n+2)); e.g., a(3)*a(4) = 12*20 = 240 = a(3*5). - Charlie Marion, Dec 29 2003
Log 2 = Sum_{n >= 0} 1/a(2n+1) = 1/2 + 1/12 + 1/30 + 1/56 + 1/90 + ... = (1 - 1/2) + (1/3 - 1/4) + (1/5 - 1/6) + (1/7 - 1/8) + ... = Sum_{n >= 0} (-1)^n/(n+1) = A002162. - Gary W. Adamson, Jun 22 2003
(2, 6, 12, 20, 30, ...) = binomial transform of (2, 4, 2). - Gary W. Adamson, Nov 28 2007
a(0) = 0, a(n) = a(n-1) + 1 + floor(x), where x is the minimal positive solution to fract(sqrt(a(n-1) + 1 + x)) = 1/2. - Hieronymus Fischer, Dec 31 2008
E.g.f.: ((-x+1)*log(-x+1)+x)/x^2 also Integral_{x = 0..1} ((-x+1)*log(-x+1) + x)/x^2 = zeta(2) - 1. - Stephen Crowley, Jul 11 2009
a(n-1) = floor(n^5/(n^3 + n^2 + 1)). - Gary Detlefs, Feb 11 2010
For n > 0 a(n) = 1/(Integral_{x=0..Pi/2} 2*(sin(x))^(2*n-1)*(cos(x))^3). - Francesco Daddi, Aug 02 2011
Sum_{n >= 1} 1/(a(n))^(2s) = Sum_{t = 1..2*s} binomial(4*s - t - 1, 2*s - 1) * ( (1 + (-1)^t)*zeta(t) - 1). See Arxiv:1301.6293. - R. J. Mathar, Feb 03 2013
a(n) = floor(n^2 * e^(1/n)) and a(n-1) = floor(n^2 / e^(1/n)). - Richard R. Forberg, Jun 22 2013
Binomial transform of [0, 2, 2, 0, 0, 0, ...]. - Alois P. Heinz, Mar 10 2015
For n > 0, a(n) = 1/(Integral_{x=0..1} (x^(n-1) - x^n) dx). - Rick L. Shepherd, Oct 26 2015
For n > 0, a(n) = lim_{m -> oo} (1/m)*1/(Sum_{i=m*n..m*(n+1)} 1/i^2), with error of ~1/m. - Richard R. Forberg, Jul 27 2016
Dirichlet g.f.: zeta(s-2) + zeta(s-1).
Convolution of nonnegative integers (A001477) and constant sequence (A007395).
Sum_{n >= 0} a(n)/n! = 3*exp(1). (End)
a(n)*a(n+2k-1) + (n+k)^2 = ((2n+1)*k + n^2)^2.
a(n)*a(n+2k) + k^2 = ((2n+1)*k + a(n))^2. (End)
Product_{n>=1} (1 + 1/a(n)) = cosh(sqrt(3)*Pi/2)/Pi. - Amiram Eldar, Jan 20 2021
A generalization of the Dec 29 2003 formula, a(n)*a(n+1) = a(n*(n+2)), follows. a(n)*a(n+k) = a(n*(n+k+1)) + (k-1)*n*(n+k+1). - Charlie Marion, Jan 02 2023
|
|
|
EXAMPLE
|
a(3) = 12, since 2(3)+2 = 8 has 4 partitions with exactly two parts: (7,1), (6,2), (5,3), (4,4). Taking the positive differences of the parts in each partition and adding, we get: 6 + 4 + 2 + 0 = 12. - Wesley Ivan Hurt, Jun 02 2013
G.f. = 2*x + 6*x^2 + 12*x^3 + 20*x^4 + 30*x^5 + 42*x^6 + 56*x^7 + ... - Michael Somos, May 22 2014
a(1) = 2, since 45-43 = 2;
a(2) = 6, since 47-45 = 2 and 47-43 = 4, then 2+4 = 6;
a(3) = 12, since 49-47 = 2, 49-45 = 4, and 49-43 = 6, then 2+4+6 = 12. (End)
|
|
|
MAPLE
|
n*(n+1) ;
end proc:
|
|
|
MATHEMATICA
|
oblongQ[n_] := IntegerQ @ Sqrt[4 n + 1]; Select[Range[0, 2600], oblongQ] (* Robert G. Wilson v, Sep 29 2011 *)
LinearRecurrence[{3, -3, 1}, {2, 6, 12}, {0, 20}] (* Eric W. Weisstein, Jul 27 2017 *)
|
|
|
PROG
|
(PARI) {a(n) = n*(n+1)};
(PARI) concat(0, Vec(2*x/(1-x)^3 + O(x^100))) \\ Altug Alkan, Oct 26 2015
(Haskell)
a002378 n = n * (n + 1)
a002378_list = zipWith (*) [0..] [1..]
(Python)
def a(n): return n*(n+1)
|
|
|
CROSSREFS
|
Partial sums of A005843 (even numbers). Twice triangular numbers (A000217).
Cf. A035106, A087811, A119462, A127235, A049598, A124080, A033996, A028896, A046092, A000217, A005563, A046092, A001082, A059300, A059297, A059298, A166373, A002943 (bisection), A002939 (bisection), A078358 (complement).
Cf. A045943 (4-cycles in triangular honeycomb acute knight graph), A028896 (5-cycles), A152773 (6-cycles).
|
|
|
KEYWORD
|
nonn,easy,core,nice,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A075195
|
|
Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.
|
|
+10
32
|
|
|
|
1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 11, 6, 1, 6, 15, 24, 24, 8, 1, 7, 21, 45, 70, 51, 14, 1, 8, 28, 76, 165, 208, 130, 20, 1, 9, 36, 119, 336, 629, 700, 315, 36, 1, 10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1, 11, 55, 249, 1044, 3367, 7826, 11165, 8230, 2195, 108, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Here, as in A000031, turning over is not allowed.
(1/n) * Dirichlet convolution of phi(n) and k^n. (End)
|
|
|
REFERENCES
|
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 86 (2.2.23).
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 496.
Louis Comtet, Analyse combinatoire, Tome 2, p. 104 #17, P.U.F., 1970.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = (1/n)*Sum_{d | n} phi(d)*k^(n/d), where phi = Euler totient function A000010. - Philippe Deléham, Oct 08 2003
O.g.f. for column k >= 1: Sum_{n>=1} T(n,k)*x^n = -Sum_{d >= 1} (phi(d)/d) * log(1 - k*x^d).
Linear recurrence for row n >= 1: T(n,k) = Sum_{j=0..n} -binomial(j-n-1,j+1) * T(n,k-1-j) for k >= n + 2. (This recurrence is essentially due to Robert A. Russell, who contributed it in A321791.) (End)
T(n,k) = (1/n)*Sum_{i=1..n} k^gcd(n,i).
T(n,k) = (1/n)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)).
T(n,k) = (1/n)*A185651(n,k) for n >= 1, k >= 1. (End)
|
|
|
EXAMPLE
|
The array T(n,k) for n >= 1, k >= 1 begins:
1, 2, 3, 4, 5, ...
1, 3, 6, 10, 15, ...
1, 4, 11, 24, 45, ...
1, 6, 24, 70, 165, ...
1, 8, 51, 208, 629, ...
Triangle formed when the array is read by antidiagonals:
1
2, 1
3, 3, 1
4, 6, 4, 1
5, 10, 11, 6, 1
6, 15, 24, 24, 8, 1
7, 21, 45, 70, 51, 14, 1
8, 28, 76, 165, 208, 130, 20, 1
9, 36, 119, 336, 629, 700, 315, 36, 1
10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1
...
(End)
|
|
|
MATHEMATICA
|
t[n_, k_] := (1/n)*Sum[EulerPhi[d]*k^(n/d), {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 20 2014, after Philippe Deléham *)
|
|
|
PROG
|
(PARI) T(n, k) = (1/n) * sumdiv(n, d, eulerphi(d)*k^(n/d));
for(n=1, 15, for(k=1, n, print1(T(k, n - k + 1), ", "); ); print(); ) \\ Indranil Ghosh, Mar 25 2017
(Python)
from sympy.ntheory import totient, divisors
def T(n, k): return sum(totient(d)*k**(n//d) for d in divisors(n))//n
for n in range(1, 16):
print([T(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Mar 25 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A053635
|
|
a(n) = Sum_{d|n} phi(d)*2^(n/d).
|
|
+10
16
|
|
|
|
0, 2, 6, 12, 24, 40, 84, 140, 288, 540, 1080, 2068, 4224, 8216, 16548, 32880, 65856, 131104, 262836, 524324, 1049760, 2097480, 4196412, 8388652, 16782048, 33554600, 67117128, 134218836, 268452240, 536870968, 1073777040, 2147483708, 4295033472, 8589938808
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
a[0] = 0; a[n_] := Sum[EulerPhi[d] 2^(n/d), {d, Divisors[n]}];
|
|
|
PROG
|
(PARI) a(n) = if (n, sumdiv(n, d, eulerphi(d)*2^(n/d)), 0); \\ Michel Marcus, Sep 20 2017
(Magma) [0] cat [&+[EulerPhi(d)*2^(n div d): d in Divisors(n)]: n in [1..40]]; // Vincenzo Librandi, Jul 20 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A054602
|
|
a(n) = Sum_{d|3} phi(d)*n^(3/d).
|
|
+10
16
|
|
|
|
0, 3, 12, 33, 72, 135, 228, 357, 528, 747, 1020, 1353, 1752, 2223, 2772, 3405, 4128, 4947, 5868, 6897, 8040, 9303, 10692, 12213, 13872, 15675, 17628, 19737, 22008, 24447, 27060, 29853, 32832, 36003, 39372, 42945, 46728, 50727, 54948
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Continued fraction [n,n,n] = (n^2+1)/(n^3+2n) = (n^2+1)/a(n); e.g., [7,7,7] = 50/357. - Gary W. Adamson, Jul 15 2010
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MATHEMATICA
|
nterms=100; Table[n^3+2n, {n, 0, nterms}] (* Paolo Xausa, Nov 25 2021 *)
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A208535
|
|
Square array read by descending antidiagonals: T(n,k) is the number of n-bead necklaces of k colors not allowing reversal, with no adjacent beads having the same color (n, k >= 1).
|
|
+10
15
|
|
|
|
1, 2, 0, 3, 1, 0, 4, 3, 0, 0, 5, 6, 2, 1, 0, 6, 10, 8, 6, 0, 0, 7, 15, 20, 24, 6, 1, 0, 8, 21, 40, 70, 48, 14, 0, 0, 9, 28, 70, 165, 204, 130, 18, 1, 0, 10, 36, 112, 336, 624, 700, 312, 36, 0, 0, 11, 45, 168, 616, 1554, 2635, 2340, 834, 58, 1, 0, 12, 55, 240, 1044, 3360, 7826, 11160
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For prime rows, these appear to be evaluations of Moreau's necklace polynomials at the integers with several combinatorial interpretations (see Wikipedia link). - Tom Copeland, Oct 20 2014
The g.f. for column k follows easily from I. Gessel's formulas for this sequence. Since S(1,k) = k-1, we have T(1,k) = k + S(1,k) - (k - 1). Thus, Sum_{n >= 1} T(n,k)*x^n = k*x + Sum_{n >= 1} (1/n)*Sum_{d|n} (k - 1)^d*phi(n/d)*x^n - Sum_{s=0} (k-1)*x^{2*s+1}. Letting m = n/d, we get that (column k g.f.) = k*x - (k - 1)*x/(1 -x^2) + Sum_{m >= 1} (phi(m)/m)*Sum_{d >= 1}((k - 1)*x^m)^d/d. But Sum_{d>=1} z^d/d = -log(1 - z), and so (column k g.f.) = k*x - (k - 1)*x/(1 - x^2) - Sum_{m >= 1} (phi(m)/m)*log(1 - (k - 1)*x^m).
The other formula for the g.f. of column k of this sequence follows from the formula Sum_{n >= 1} (phi(n)/n)*log(1 + t^n) = t/(1 - t^2), which in turn follows from the well-known series Sum_{n >= 1} phi(n)*t^n/(1 + t^n) = t*(1 + t^2)/(1 - t^2)^2.
The extra term k*x in the g.f. for column k is due to the fact that we conventionally assume that a necklace with only one bead, colored with one of the k colors available, is such that there are "no adjacent beads having the same color" (even though, strictly speaking, a single bead is adjacent to itself when we go around the circle of the necklace).
One can use the g.f. for column k to derive the so-called "Empirical for row n" formulae that are denoted by a(k) and given in the formula section below (from n = 1 to n = 7). For example, for n = 3, a(k) = a(k, x=0), where a(k, x) = (1/3!)*d^3/dx^3 (column k g.f.). Here, d^3/dx^3 stands for "third derivative w.r.t. x". If we let f(x) = x/(1 - x^2) and g(x, m) = -log(1 - (k - 1)*x^m), then f^{(3)}(0) = 6, while g^{(3)}(0,m) = 2*(k - 1)^3 for m = 1, 0 for m=2, 6*(k - 1) for m = 3, and 0 for m >= 4. Then, a(k) = (1/6)*(-6*(k - 1) + 2*(k - 1)^3 + (2/3)*6*(k - 1)) = (1/3)*k^3 - k^2 + (2/3)*k. Using this method, one can derive an "Empirical for row n" formula for a(k) for any positive integer n. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let S(n,k) = (1/n) Sum_{d|n} (k-1)^d phi(n/d), where phi is Euler's function.
Then for n even, T(n,k) = S(n,k) and for n > 1 and odd, T(n,k) = S(n,k) - (k-1), and T(1,k) = k. - Ira M. Gessel, Oct 21 2014, Sep 25 2017
Empirical for row n:
n=1: a(k) = k
n=2: a(k) = (1/2)*k^2 - (1/2)*k
n=3: a(k) = (1/3)*k^3 - k^2 + (2/3)*k
n=4: a(k) = (1/4)*k^4 - k^3 + (7/4)*k^2 - k
n=5: a(k) = (1/5)*k^5 - k^4 + 2*k^3 - 2*k^2 + (4/5)*k
n=6: a(k) = (1/6)*k^6 - k^5 + (5/2)*k^4 - (19/6)*k^3 + (7/3)*k^2 - (5/6)*k
n=7: a(k) = (1/7)*k^7 - k^6 + 3*k^5 - 5*k^4 + 5*k^3 - 3*k^2 + (6/7)*k
-----------
The first three numbers in each row of the triangular array are given by T(n,k) = (1/k)*(n-k+1)! / (n-2*k+1)!.
For the table here, the first three rows, aside from initial zeros, are given by a(n,k) = (1/n)*(k + 1 - n)! / (k + 1 - 2*n)! or, with no leading zeros, by a(n,k) = (1/n)*(n+k-1)! / (k-1)!. The first three elements of each column correspond to the last three elements of a row in A238363 and the first three of A111492.
Prime rows (> 1) appear to be a(m,n) = (n^m - n)/m. See Wikipedia link. (End)
G.f. for column k: Sum_{n >= 1} T(n,k)*x^n = k*x - Sum_{n >= 1} (phi(n)/n)*((k - 1)*log(1 + x^n) + log(1 - (k - 1)*x^n)) = k*x - (k - 1)*x/(1 - x^2) - Sum_{n >= 1} (phi(n)/n)*log(1 - (k - 1)*x^n). - Petros Hadjicostas, Nov 05 2017
|
|
|
EXAMPLE
|
Table T(n,k) (with rows n >= 1 and columns k >= 1) starts:
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
0 1 3 6 10 15 21 28 36 45 55 66 78 ...
0 0 2 8 20 40 70 112 168 240 330 440 572 ...
0 1 6 24 70 165 336 616 1044 1665 2530 3696 5226 ...
0 0 6 48 204 624 1554 3360 6552 11808 19998 32208 49764 ...
0 1 14 130 700 2635 7826 19684 43800 88725 166870 295526 498004 ...
0 0 18 312 2340 11160 39990 117648 299592 683280 1428570 2783880 5118828 ...
0 1 36 834 8230 48915 210126 720916 2097684 5381685 12501280 26796726 53750346 ...
...
All solutions for n = 4 and k = 3:
1 2 1 1 1 1
3 3 2 2 3 2
2 2 3 1 1 1
3 3 2 2 3 3
|
|
|
MATHEMATICA
|
T[n_, k_] := If[n == 1, k, Sum[ EulerPhi[n/d]*(k-1)^d, {d, Divisors[n]}]/n - If[OddQ[n], k-1, 0]]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)
|
|
|
PROG
|
(PARI)
T(n, k) = if(n==1, k, sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1));
for(n=1, 10, for(k=1, 10, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 14 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A228640
|
|
a(n) = Sum_{d|n} phi(d)*n^(n/d).
|
|
+10
11
|
|
|
|
0, 1, 6, 33, 280, 3145, 46956, 823585, 16781472, 387422001, 10000100440, 285311670721, 8916103479504, 302875106592409, 11112006930972780, 437893890382391745, 18446744078004651136, 827240261886336764449, 39346408075494964903956, 1978419655660313589124321
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
|
|
|
MAPLE
|
with(numtheory):
a:= n-> add(phi(d)*n^(n/d), d=divisors(n)):
seq(a(n), n=0..20);
|
|
|
MATHEMATICA
|
a[0] = 0; a[n_] := DivisorSum[n, EulerPhi[#]*n^(n/#)&]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 21 2017 *)
|
|
|
PROG
|
(Python)
from sympy import totient, divisors
return sum(totient(d)*n**(n//d) for d in divisors(n, generator=True)) # Chai Wah Wu, Feb 15 2020
(PARI) a(n) = if (n, sumdiv(n, d, eulerphi(d)*n^(n/d)), 0); \\ Michel Marcus, Feb 15 2020; corrected Jun 13 2022
(Magma) [0] cat [&+[EulerPhi(d)*n^(n div d): d in Divisors(n)]:n in [1..20]]; // Marius A. Burtea, Feb 15 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A054610
|
|
a(n) = Sum_{d|n} phi(d)*3^(n/d).
|
|
+10
7
|
|
|
|
0, 3, 12, 33, 96, 255, 780, 2205, 6672, 19755, 59340, 177177, 532416, 1594359, 4785228, 14349525, 43053504, 129140211, 387441756, 1162261521, 3486844320, 10460357775, 31381236876, 94143178893, 282430082832, 847288610475
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} 3^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
|
|
|
PROG
|
(PARI) a(n) = sum(k=1, n, 3^gcd(n, k)); \\ Michel Marcus, Apr 16 2021
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A054611
|
|
a(n) = Sum_{d|n} phi(d)*4^(n/d).
|
|
+10
6
|
|
|
|
0, 4, 20, 72, 280, 1040, 4200, 16408, 65840, 262296, 1049680, 4194344, 16782000, 67108912, 268451960, 1073744160, 4295033440, 17179869248, 68719747320, 274877907016, 1099512679520, 4398046544304, 17592190238920, 70368744177752
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MAPLE
|
A054611:=proc(n) local k, t1; t1:=0; for k in divisors(n) do t1 := t1+phi(k)*4^(n/k); od: t1; end;
|
|
|
PROG
|
(PARI) a(n) = if(n==0, 0, sumdiv(n, d, eulerphi(d)*4^(n/d))); \\ Michel Marcus, Sep 19 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A054619
|
|
Triangle T(n,k) = Sum_{d|k} phi(d)*n^(k/d).
|
|
+10
6
|
|
|
|
1, 2, 6, 3, 12, 33, 4, 20, 72, 280, 5, 30, 135, 660, 3145, 6, 42, 228, 1344, 7800, 46956, 7, 56, 357, 2464, 16835, 118104, 823585, 8, 72, 528, 4176, 32800, 262800, 2097200, 16781472, 9, 90, 747, 6660, 59085, 532350, 4783023, 43053480, 387422001
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
1;
2, 6;
3, 12, 33;
4, 20, 72, 280;
5, 30, 135, 660, 3145;
6, 42, 228, 1344, 7800, 46956;
...
|
|
|
MAPLE
|
with(numtheory):
T:= (n, k)-> add(phi(d)*n^(k/d), d=divisors(k)):
|
|
|
MATHEMATICA
|
T[n_, k_] := Sum[EulerPhi[d]*n^(k/d), {d, Divisors[k]}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 25 2015 *)
|
|
|
PROG
|
(PARI) T(n, k) = sumdiv(k, d, eulerphi(d)*n^(k/d)); \\ Michel Marcus, Feb 25 2015
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.097 seconds
|
