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

%I #70 Mar 04 2023 11:32:16

%S 0,3,12,35,90,217,504,1143,2550,5621,12276,26611,57330,122865,262128,

%T 557039,1179630,2490349,5242860,11010027,23068650,48234473,100663272,

%U 209715175,436207590,905969637,1879048164,3892314083,8053063650,16642998241,34359738336

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

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

%C To evaluate the Sudan function see A260002 and A260003.

%C 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.

%C From _Enrique Navarrete_, Oct 02 2021: (Start)

%C 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.

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

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

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

%C {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)

%H Colin Barker, <a href="/A260006/b260006.txt">Table of n, a(n) for n = 0..1000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sudan_function">Sudan function</a> (see diagonal of "Values of F1(x, y)" table).

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-13,12,-4).

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

%F 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

%F G.f.: x*(3 - 6*x + 2*x^2) / ((1-x)^2*(1-2*x)^2). - _Colin Barker_, Jul 29 2015

%F E.g.f.: 2*(x+1)*exp(2*x) - (x+2)*exp(x). - _Robert Israel_, Aug 23 2015

%F From _Enrique Navarrete_, Oct 02 2021: (Start)

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

%F 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)

%F From _Wolfdieter Lang_, Nov 12 2021: (Start)

%F The previous bisection becomes for a(n):

%F 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)

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

%t Table[(2^n -1)(n+2), {n, 0, 30}] (* _Michael De Vlieger_, Aug 22 2015 *)

%t CoefficientList[Series[x(3 -6x +2x^2)/((1-x)^2 (1-2x)^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, Aug 22 2015 *)

%t LinearRecurrence[{6,-13,12,-4},{0,3,12,35},40] (* _Harvey P. Dale_, Mar 04 2023 *)

%o (PARI) vector(40, n, n--; (2^n-1)*(n+2)) \\ _Michel Marcus_, Jul 29 2015

%o (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

%o (Magma) [(2^n-1)*(n+2): n in [0..30]]; // _Vincenzo Librandi_, Aug 22 2015

%o (Sage) [(n+2)*(2^n -1) for n in (0..30)] # _G. C. Greubel_, Dec 30 2021

%Y 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)).

%Y Cf. A260002, A260003, A260004, A260005.

%Y Cf. A000984, A002697, A303602.

%K nonn,easy,less

%O 0,2

%A _Natan Arie Consigli_, Jul 23 2015