cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A136444 a(n) = Sum_{k=0..n} k*binomial(n-k, 2*k).

Original entry on oeis.org

0, 0, 0, 1, 3, 6, 12, 25, 51, 101, 197, 381, 731, 1392, 2634, 4958, 9290, 17337, 32239, 59760, 110460, 203651, 374593, 687567, 1259597, 2303449, 4205493, 7666560, 13956532, 25374108, 46076436, 83575025, 151431099, 274108826, 495708364, 895670733, 1617003823, 2916984121
Offset: 0

Views

Author

Don Knuth, Apr 04 2008

Keywords

Comments

Consider four related sequences: A_n = sum C(n-k, 2*k), B_n = sum C(n-k, 2*k+1), A^*_n = sum k*C(n-k, 2*k), B^*_n = sum k*C(n-k, 2*k+1).
Sequence A_n, with generating function (1-z)/p(z) where p(z) = 1 - 2*z + z^2 - z^3, is A005251.
Sequence B_n, with generating function z/p(z), is A005314.
Sequence A^*_n is the present sequence.
Sequence B^*_n is A118430, but shifted one place so that the generating function is z^4/p(z)^2 instead of z^3/p(z)^2.
These sequences have many interrelations; for example,
B_{n+1} - B_n = A_n; B^*_{n+1} - B^*_n = A^*_n;
A_{n+1} - A_n = B_{n-1}; A^*{n+1} - A^*_n = B^*{n-1} + B_{n-1}.

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Links

Crossrefs

Cf. A005251, A005314, A118430, A136445, A137356-A137361.

Programs

  • Magma
    [&+[k*Binomial(n-k, 2*k): k in [0..n]]: n in [0..40]]; // Bruno Berselli, Feb 13 2015
  • Maple
    a:= n-> (Matrix([[0,0,1,1,-3,-5]]). Matrix(6, (i,j)-> if (i=j-1) then 1 elif j=1 then [4,-6,6,-5,2,-1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..37);  # Alois P. Heinz, Aug 13 2008
  • Mathematica
    a[n_] := ({0, 0, 1, 1, -3, -5} . MatrixPower[ Table[If[i == j-1, 1, If[j == 1, {4, -6, 6, -5, 2, -1}[[i]], 0]], {i, 6}, {j, 6}], n])[[1]]; Table[a[n], {n, 0, 37}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)
CoefficientList[Series[x^3 (1 - x)/(1 - 2 x + x^2 - x^3)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Aug 15 2015 *)

Formula

G.f.: x^3*(1-x)/(1-2*x+x^2-x^3)^2.
a(n) ~ c * d^n * n, where d = A109134 = 1.75487766624669276... is the root of the equation d*(d-1)^2 = 1, c = 0.072838349685011... is the root of the equation 529*c^3 - 207*c^2 + 26*c = 1. - Vaclav Kotesovec, May 25 2015

A137202 Number of nodes in the BDD for the hidden weighted bit function h_n under the best possible ordering of variables.

Original entry on oeis.org

3, 3, 5, 9, 16, 23, 33, 46, 63, 82, 109, 139, 178, 224, 282, 348, 434, 531, 653, 796, 973, 1176, 1433, 1725, 2090
Offset: 1

Views

Author

Don Knuth, Apr 23 2008

Keywords

Comments

In this problem we don't consider "complement bits" to shorten the BDD.
The best method presently known to find a(n) takes something like 2.5^n steps.

Examples

			For example, when n=8 the smallest BDD is obtained when one tests first x8 (1 node), then x7 (2 nodes), then x1 (4), then x6 (6), then x2 (9), then x5 (12), then x4 (8), then x3 (2). The total number of nodes is 46, including the two sink nodes.

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Links

Crossrefs

Cf. A136445.
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.