A260006 a(n) = f(1,n,n), where f is the Sudan function defined in A260002.

0, 3, 12, 35, 90, 217, 504, 1143, 2550, 5621, 12276, 26611, 57330, 122865, 262128, 557039, 1179630, 2490349, 5242860, 11010027, 23068650, 48234473, 100663272, 209715175, 436207590, 905969637, 1879048164, 3892314083, 8053063650, 16642998241, 34359738336

Offset

0,2

Comments

f(1,n,n) = 2^n*(n+2) - (n+2) = (2^n - 1)*(n+2).

To evaluate the Sudan function see A260002 and A260003.

The numbers are alternately even and odd because for even n (2^n-1)*(n+2) is even and (2^(n+1)-1)*(n+1+2) is odd.

From Enrique Navarrete, Oct 02 2021: (Start)

a(n-2) is the number of ways we can write [n] as the union of 2 sets of sizes i, j which intersect in exactly 1 element (1 < i, j < n; i = j allowed), n>=2.

For n = 4, a(n-2) = 12 since [4] can be written as the unions:

{1,2} U {1,3,4}; {2,3} U {1,2,4}; {1,2} U {2,3,4}; {2,3} U {1,3,4};

{1,3} U {1,2,4}; {2,4} U {1,2,3}; {1,3} U {2,3,4}; {2,4} U {1,3,4};

{1,4} U {1,2,3}; {3,4} U {1,2,3}; {1,4} U {2,3,4}; {3,4} U {1,2,4}. (End)

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Wikipedia, Sudan function (see diagonal of "Values of F1(x, y)" table).

Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Formula

a(n) = (2^n -1)*(n+2).

a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4) for n>3. - Colin Barker, Jul 29 2015

G.f.: x*(3 - 6*x + 2*x^2) / ((1-x)^2*(1-2*x)^2). - Colin Barker, Jul 29 2015

E.g.f.: 2*(x+1)*exp(2*x) - (x+2)*exp(x). - Robert Israel, Aug 23 2015

From Enrique Navarrete, Oct 02 2021: (Start)

a(n-2) = Sum_{j=2..n/2} binomial(n,j)*j, n even > 2.

a(n-2) = (Sum_{j=2..floor(n/2)} binomial(n,j)*j) + (1/2)*binomial(n, ceiling(n/2))*ceiling(n/2), n odd > 1. (End)

From Wolfdieter Lang, Nov 12 2021: (Start)

The previous bisection becomes for a(n):

a(2*k) = 2*(A002697(k+1) - (k+1)), and a(2*k+1) = A303602(k+1) - (2*k+3)*(2 - A000984(k+1))/2 = (2*k+3)*(4^(k+1) - 2)/2, for k >= 0. (End)

Example

a(4) = (2^4 - 1)*(4 + 2) = 90.

Mathematica

Table[(2^n -1)(n+2), {n, 0, 30}] (* Michael De Vlieger, Aug 22 2015 *)
CoefficientList[Series[x(3 -6x +2x^2)/((1-x)^2 (1-2x)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 22 2015 *)
LinearRecurrence[{6, -13, 12, -4}, {0, 3, 12, 35}, 40] (* Harvey P. Dale, Mar 04 2023 *)

Prog

(PARI) vector(40, n, n--; (2^n-1)*(n+2)) \\ Michel Marcus, Jul 29 2015
(PARI) concat(0, Vec(x*(3-6*x+2*x^2)/((1-x)^2*(1-2*x)^2) + O(x^40))) \\ Colin Barker, Jul 29 2015
(Magma) [(2^n-1)*(n+2): n in [0..30]]; // Vincenzo Librandi, Aug 22 2015
(Sage) [(n+2)*(2^n -1) for n in (0..30)] # G. C. Greubel, Dec 30 2021

Crossrefs

Cf. A000295 (f(1,0,n)), A000325 (f(1,2,n)), A005408 (f(1,n,1) = 2n+1), A001787 (n*2^(n-1)), A079583 (f(1,1,n)), A123720 (f(1,4,n)), A133124 (f(1,3,n)).

Cf. A260002, A260003, A260004, A260005.

Cf. A000984, A002697, A303602.

Sequence in context: A293267 A295363 A097339 * A303862 A320346 A305542

Adjacent sequences: A260003 A260004 A260005 * A260007 A260008 A260009

Keyword

nonn,easy,less

Author

Natan Arie Consigli, Jul 23 2015

Status

approved