OFFSET
0,3
COMMENTS
From Enrique Navarrete, Jun 13 2023: (Start)
a(n) is the number of ways to partition the set [n]={1,2,...,n} into two sets S,T and select 2 elements in total (from either S or T or both).
Example. For n=4, sample partitions are given (where S(i),T(j) means i elements are selected from S, j elements are selected from T):
S={ }, T={1,2,3,4}: partition [4] in 1 way, S(0),T(2) (6 ways);
S={1}, T={2,3,4}: partition [4] in 4 such ways, S(1),T(1) or S(0),T(2) (24 ways);
S={1,2}, T={3,4}: partition [4], in such 6 ways, S(1),T(1) or S(0),T(2) or S(2),T(0) (36 ways);
S={1,2,3}, T={4}: partition [4] in 4 such ways, S(1),T(1) or S(2),T(0) (24 ways);
S={1,2,3,4}, T={ }: partition [4] in 1 way, S(2),T(0) (6 ways). (End)
From Constantinos Kourouzides, Jun 04 2026: (Start)
Also the number of induced copies of P_3 in the n-dimensional hypercube Q_n. Equivalently, a(n) is the number of 3-vertex subsets of Q_n inducing exactly two edges. Proof: choose the middle vertex of the path in 2^n ways and then choose two distinct coordinate directions in binomial(n,2) ways. The two endpoints then differ in two coordinates, so they are not adjacent. Conversely, every induced P_3 in Q_n has a unique middle vertex and arises in this way.
This is bijective with the interpretation as labeled partitions [n]=S union T together with a chosen 2-subset {i,j} of [n]: encode S,T by the vertex v in {0,1}^n with v_k=0 for k in S and v_k=1 for k in T, and send {i,j} to the induced path v^(i)-v-v^(j), where v^(i) is obtained from v by flipping coordinate i. The inverse map takes an induced P_3 to its unique middle vertex v and the two coordinates in which the endpoints differ from v. (End)
REFERENCES
Jolley, Summation of Series, Dover (1961), eq (214) page 40.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..3000
The Ramanujan Machine, Using algorithms to discover new mathematics.
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).
FORMULA
Sum_{n>=2} 1/a(n) = 1 - log(2) = 0.3068528.... - Graeme McRae, Jul 28 2006
a(n) = Sum_{k=0..n} k*2^k = 2*A001815(n). - Zerinvary Lajos, Oct 09 2006
E.g.f.: 2*x^2*exp(2x).
a(n) = 4*A001788(n-1). - Johannes W. Meijer, Jun 27 2009
Sum_{j=1..k} (j+2)/a(j+1) = 1 - 1/((k+1)*2^k). [Jolley]
G.f.: -4*x^2 / (2*x-1)^3. - R. J. Mathar, Oct 05 2011
Sum_{n>=2} (-1)^n/a(n) = 3*log(3/2) - 1. - Amiram Eldar, Jul 20 2020
From Peter Bala Mar 04 2024: (Start)
Sum_{k = 2..n+2} 1/a(k) = 1/(4 - 4/(7 - 12/(10 - ... - 2*n*(n + 1)/(3*n + 4)))).
Sum_{k = 2..n+2} (-1)^k/a(k) = 1/(4 + 4/(5 + 12/(6 + ... + 2*n*(n + 1)/(n + 4)))).
Letting n -> oo in the above gives the continued fraction representations
1 - log(2) = Sum_{k >= 2} 1/a(k) = 1/(4 - 4/(7 - 12/(10 - ... - 2*n*(n + 1)/((3*n + 4) - ... )))) (an equivalent continued fraction for 1 - log(2) was conjectured by the Ramanujan machine) and
3*log(3/2) - 1 = Sum_{k >= 2} (-1)^k/a(k) = 1/(4 + 4/(5 + 12/(6 + ... + 2*n*(n + 1)/((n + 4) + ... )))). (End)
MAPLE
seq(2^n*binomial(n, 2), n=0..20);
MATHEMATICA
Range[0, 20]! CoefficientList[Series[2x^2 Exp[2x], {x, 0, 20}], x]
Table[2^n Binomial[n, 2], {n, 0, 30}] (* or *) LinearRecurrence[{6, -12, 8}, {0, 0, 4}, 30] (* Harvey P. Dale, Aug 15 2020 *)
PROG
(PARI) a(n)=binomial(n, 2)<<n \\ Charles R Greathouse IV, Oct 16 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jorge Coveiro, Dec 30 2004
STATUS
approved