Paolo Bonzini - cp's OEIS frontend

A274775 Indices in A006928 where the imbalance between 1's and 2's sets a new record.

1, 2, 4, 11, 31, 92, 256, 377, 470, 797, 824, 857, 1126, 1397, 1496, 1523, 1532, 6351, 6968, 7175, 7268, 7565, 7970, 20337, 20370, 21981, 22008, 25637, 25664, 25691, 27968, 39183, 39210, 42397, 43128, 43149, 48636, 48729, 48756, 49013, 49040, 49067, 49094, 49863

Offset: 1

Paolo Bonzini, Jul 06 2016

nonn

Indices in A088568 where new values appear.

Sorted union of A025507 and A025506.

Paolo Bonzini, Table of n, a(n) for n = 1..151

Cf. A006928, A025507, A088568, A025506

A274448 Denominators in expansion of W(exp(x)) about x=1, where W is the Lambert function.

Original entry on oeis.org

1, 2, 16, 192, 3072, 61440, 1474560, 41287680, 1321205760, 47563407360, 1902536294400, 83711596953600, 4018156653772800, 208944145996185600, 11700872175786393600, 702052330547183616000, 44931349155019751424000, 235025518657026392064000, 219983885462976702971904000, 16718775295186229425864704000, 1337502023614898354069176320000

Offset: 0

Paolo Bonzini, Jun 23 2016

a(17) is the first term that differs from A051711.

			W(exp(x)) = 1 +(x-1)/2+(x-1)^2/16-(x-1)^3/192-...

R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, On the Lambert W Function, Advances in Computational Mathematics, (5), 1996, pp. 329-359.
R. M. Corless, D. J. Jeffrey and D. E. Knuth, A sequence of series for the Lambert W Function (section 2.2).

Cf. A274447.

a:= n-> denom(coeftayl(LambertW(exp(x)), x=1, n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 08 2012

CoefficientList[ Series[ ProductLog[ Exp[1+x] ], {x, 0, 22}], x] // Denominator (* Jean-François Alcover, Oct 15 2012 *)

a(n) = A051711(n)/gcd(A001662(n),A051711(n))

A274447 Numerators in expansion of W(exp(x)) about x=1, where W is the Lambert function.

Original entry on oeis.org

1, 1, 1, -1, -1, 13, -47, -73, 2447, -16811, -15551, 1726511, -18994849, 10979677, 2983409137, -48421103257, 135002366063, 778870772857, -232033147779359, 1305952009204319, 58740282660173759, -1862057132555380307, 16905219421196907793, 527257187244811805207

Offset: 0

Paolo Bonzini, Jun 23 2016

a(17) is the first term that differs from A001662.

			W(exp(x)) = 1 + (x-1)/2 + (x-1)^2/16 - (x-1)^3/192 - ...

Alois P. Heinz, Table of n, a(n) for n = 0..446 (first 151 terms from G. C. Greubel)
R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, On the Lambert W Function, Advances in Computational Mathematics, (5), 1996, pp. 329-359.
R. M. Corless, D. J. Jeffrey and D. E. Knuth, A sequence of series for the Lambert W Function (section 2.2).

Cf. A001662, A051711, A274448.

a:= n-> numer(coeftayl(LambertW(exp(x)), x=1, n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 08 2012
# For large n much faster is:
q := proc(n) if n=0 then 1 else add((-1)^k*combinat[eulerian2](n-1, k), k=0..n-1) fi end: A001662 := n -> numer(q(n)/n!):
seq(A001662(n), n=0..100):  # Peter Luschny, Nov 13 2012

CoefficientList[ Series[ ProductLog[ Exp[1+x] ], {x, 0, 22}], x] // Numerator (* Jean-François Alcover, Oct 15 2012 *)
a[0] = 1; a[n_] := 1/n!*Sum[(n+k-1)!*Sum[(-1)^(j)/(k-j)!*Sum[1/i!* StirlingS1[n-i+j-1, j-i]/(n-i+j-1)!, {i, 0, j}]*2^(n-j-1), {j, 0, k}], {k, 0, n-1}] // Numerator; Array[a, 30, 0] (* Jean-François Alcover, Feb 13 2016, after Vladimir Kruchinin *)

a(n):=num(if n=0 then 1 else 1/n!*(sum((n+k-1)!*sum(((-1)^(j)/(k-j)!*sum((1/i!*stirling1(n-i+j-1, j-i))/(n-i+j-1)!, i, 0, j))*2^(n-j-1), j, 0, k), k, 0, n-1))); /* Vladimir Kruchinin, Nov 11 2012 */

@CachedFunction
def eulerian2(n, k):
    if k==0: return 1
    if k==n: return 0
    return eulerian2(n-1, k)*(k+1)+eulerian2(n-1, k-1)*(2*n-k-1)
def q(n):
    return add((-1)^k*eulerian2(n-1, k) for k in (0..n-1)) if n>0 else 1
A001662 = lambda n: (q(n)/factorial(n)).numerator()
[A001662(n) for n in (0..22)]  # Peter Luschny, Nov 13 2012

a(n) = A001662(n)/gcd(A001662(n),A051711(n)).
From Vladimir Kruchinin, Nov 11 2012: (Start)
a(n) = numerator(1/n!*(Sum_{u=2..n} stirling2(n,u)*(Sum_{k=1..u-1} ((u+k-1)!*Sum_{j=1..k} 2^(-u-j)/(k-j)!*Sum_{l=1..j} (-1)^(l)/((j-l)!)*Sum_{i=0..l} (l^(u+j-i-1))/((l-i)!*i!*(u+j-i-1)!)))+1/2)).
a(n) = numerator((1/n!)*Sum_{k=0..n-1} (n+k-1)!*Sum_{j=0..k} ((-1)^j/(k-j)!)*2^(n-j-1)*Sum_{i=0..j} (1/i!)*Stirling1(n-i+j-1,j-i)/(n-i+j-1)!), n>0, a(0)=1. (End)
a(n) = numerator(q(n)/n!) where q(n) = add_{k=0..n-1}(-1)^k*E2(n-1,k) if n>0 and 1 otherwise, E2 the second-order Eulerian numbers. - Peter Luschny, Nov 13 2012
a(n) := numerator(1/n!*Sum_{i=1..n} Stirling2(n,i)*A013703(i)/2^(2*i+1)). - Paolo Bonzini, Jun 23 2016

A157679 Number of subtrees of a complete binary tree.

Original entry on oeis.org

0, 1, 2, 4, 6, 9, 15, 25, 35, 49, 70, 100, 160, 256, 416, 676, 936, 1296, 1800, 2500, 3550, 5041, 7171, 10201, 16261, 25921, 41377, 66049, 107169, 173889, 282309, 458329, 634349, 877969, 1215289, 1682209, 2335897, 3243601, 4504301, 6255001, 8881051, 12609601

Offset: 0

Paolo Bonzini, Mar 04 2009

Take the complete binary tree with n labeled nodes. Here is a poor picture of the tree with 6 nodes:
        R
       / \
      /   \
     /     \
    o       o
   / \     /
  o   o   o
Then the number of rooted subtrees of the graph is a(n).

			For n = 3, the a(3) = 4 subtrees are:
  R   R   R      R
     /     \    / \
    o       o  o   o

Alois P. Heinz, Table of n, a(n) for n = 0..5971
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
Index entries for sequences related to rooted trees

Cf. A004019, A005468.

a:= proc(n) option remember; `if`(n<2, n,
     (h-> (1+a(h))*(1+a(n-1-h)))(iquo(n, 2)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 02 2022

a[0] = 0; a[1] = 1; a[n_?EvenQ] := a[n] = (1 + a[n/2 - 1])*(1 + a[n/2]); a[n_?OddQ] := a[n] = (1 + a[(n-1)/2])^2; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Oct 19 2011 *)

a(0) = 0, a(1) = 1.
a(n) = 1 + a(floor((n-1)/2)) + a(ceiling((n-1)/2)) + a(floor((n-1)/2)) * a(ceiling((n-1)/2)) = (1+a(floor((n-1)/2))) * (1+a(ceiling((n-1)/2))).
If b(n) is sequence A005468, then a(n)=b(n+1)-1. From the definition of A005468, a(n) = b(floor((n+1)/2))*b(ceiling((n+1)/2)). So for every odd n a(n) is a square: a(2*n-1)=b(n)^2.
If c(n) is sequence A004019, then c(n)=a(2^n-1).
A004019 (and Aho and Sloane) give a closed formula for c(n) that translates to a(n) = nearest integer to b^((n+1)/2) - 1" where b = 2.25851...; the formula gives the asymptotic behavior of this sequence, however it does not compute the correct values for a(n) unless n+1 is a power of two.

A144945 Number of ways to place 2 queens on an n X n chessboard so that they attack each other.

Original entry on oeis.org

0, 6, 28, 76, 160, 290, 476, 728, 1056, 1470, 1980, 2596, 3328, 4186, 5180, 6320, 7616, 9078, 10716, 12540, 14560, 16786, 19228, 21896, 24800, 27950, 31356, 35028, 38976, 43210, 47740, 52576, 57728, 63206, 69020, 75180, 81696, 88578, 95836, 103480, 111520

Offset: 1

Paolo Bonzini, Sep 26 2008

a(n) gives the number of edges on a graph with n X n nodes where each node corresponds to a square on an n X n chessboard and there is an edge between two nodes if two queens placed on the corresponding squares attack each other.
In other words, number of edges in the n X n queen graph. - Eric W. Weisstein, Jun 19 2017
Number of ways to place two queens on the same row or column = A006002: b(n) = n*C(n,2) = n^2*(n-1)/2; number of ways to place two queens on the same diagonal (either SW-NE or NE-SW) = A000330 shifted by one: c(n) = n(n-1)*(2*n-1)/6; total: a(n) = 2*b(n)+2*c(n) = n*(5*n-1)*(n-1)/3.
Starting with "6" = binomial transform of [6, 22, 26, 10, 0, 0, 0, ...]. - Gary W. Adamson, Aug 12 2009
Also the Harary index of the n X n king graph. - Eric W. Weisstein, Jun 20 2017

			Example: For n=2 there are two rows, two columns and two diagonals. Each of these can be filled with two queens, giving a(2)=6.
For n=3 there are C(3,2) = 3 ways to place two queens on the same rows or column, giving C(3,2)*3 = 9 ways to place two queens on the same rows and 9 ways to place two queens on the same column. There are three nontrivial SW-NE diagonals, two of length two (each giving 1 way to place two attacking queens) and one of length three (giving 3 ways to place two attacking queens): total 3+1+1=5. There are also 5 ways to place two queens on the same NW-SE diagonal, giving a total of 9+9+5+5 = 28.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Harary Index
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Queen Graph
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A000330, A006002.

[(n-1)*n*(5*n-1)/3: n in [1..40]]; // Vincenzo Librandi, Sep 28 2011

A144945:=n->(n-1)*n*(5*n-1)/3: seq(A144945(n), n=1..50); # Wesley Ivan Hurt, Nov 02 2014

Table[n (5 n - 1) (n - 1)/3, {n, 50}] (* Harvey P. Dale, Oct 15 2011 *)
LinearRecurrence[{4, -6, 4, -1}, {0, 6, 28, 76}, 50] (* Harvey P. Dale, Oct 15 2011 *)
CoefficientList[Series[2 x (3 + 2 x)/(-1 + x)^4, {x, 0, 20}], x] (* Eric W. Weisstein, Dec 07 2017 *)

a(n) = (n-1)*n*(5*n-1)/3 \\ Charles R Greathouse IV, Jun 19 2017

first(n) = Vec(2*x^2*(3+2*x)/(1-x)^4 + O(x^(n+1)), -n) \\ Iain Fox, Dec 07 2017

a(n) = (n-1)*n*(5*n-1)/3.
From Bruno Berselli, Sep 27 2011: (Start)
G.f.: 2*x^2*(3+2*x)/(1-x)^4.
a(-n) = -A174814(n).
a(n) = a(n-1) + 2*A005475(n-1).
Sum_{i=1..n} a(i) = (n-1)*n*(n+1)*(5*n+2)/12. (End)
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n>4; a(1)=0, a(2)=6, a(3)=28, a(4)=76. - Harvey P. Dale, Oct 15 2011
a(n) = Sum_{i=1..n-1} i*(5*i+1), with a(0)=0, a(1)=6. - Bruno Berselli, Feb 10 2014
E.g.f.: x^2*(9+5*x)*exp(x)/3. - Robert Israel, Nov 02 2014

More terms from Harvey P. Dale, Oct 15 2011

A146303 Number of distinct ways to place queens (even fewer than n) on an n X n chessboard so that no queen is attacking another and that it is not possible to add another queen.

Original entry on oeis.org

1, 4, 9, 18, 58, 348, 1862, 10188, 57600, 376692, 2640422, 19469324, 151978440, 1258451524, 10963084588, 100087600184

Offset: 1

Paolo Bonzini, Oct 29 2008

In other words, number of maximal independent vertex sets (and minimal vertex covers) in the n X n queen graph. - Eric W. Weisstein, Jun 20 2017

			The a(2) = 4 solutions are to place a single queen in each of the squares of the chessboard. For n=3, there is a single one-queen solution (placing the queen in b2) and eight two-queen solutions, but no three-queen solution (see A000170).

S. W. Golomb and L. D. Baumert, Backtrack Programming, Journal of the ACM, 4 (2001), 516-524.
Stefan Kral, C++11 code using OpenMP
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Eric Weisstein's World of Mathematics, Queen Graph

Cf. A000170, A146304.

a(12)-a(16) from Stefan Kral, Aug 10 2016

A146304 Number of distinct ways to place bishops (up to 2n-2) on an n X n chessboard so that no bishop is attacking another and that it is not possible to add another bishop.

Original entry on oeis.org

1, 4, 10, 64, 660, 7744, 111888, 1960000, 40829184, 989479936, 27559645440, 870414361600, 30942459270912, 1225022400102400, 53716785891102720, 2589137004664520704, 136573353235553058816, 7838079929528363843584, 487668908919708442951680, 32741107405951528945844224

Offset: 1

Paolo Bonzini, Oct 29 2008

nonn

Number of maximal independent vertex sets (and minimal vertex covers) in the n X n bishop graph. - Eric W. Weisstein, Jun 04 2017

			For n=2, the a(2) = 4 solutions are to place two bishops on the same row (two solutions) or column (two solutions).

Andrew Howroyd, Table of n, a(n) for n = 1..200
Andrew Howroyd, Algorithm and explanation of PARI code
Eric Weisstein's World of Mathematics, Bishop Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Cf. A146303, A122749, A201862, A288182, A288183, A290594, A290613.

M[sig_List, n_, k_, d_, x_] := M[sig, n, k, d, x] = If[n == 0, Boole[k == 0], If[k > 0, k*x*M[sig, n - 1, k - 1, d, x], 0] + If[k < n && sig[[n]] > d, (sig[[n]] - d)*x*M[sig, n - 1, k, d + 1, x], 0] + If[k + sig[[n]] - d < n, M[sig, n - 1, k + sig[[n]] - d, sig[[n]], x], 0]];
Q[sig_List, x_] := M[sig, Length[sig], 0, 0, x];
Bishop[n_, white_] := Table[n - i + If[white == 1, 1 - Mod[i, 2], Mod[i, 2]], {i, 1, n - If[white == 1, Mod[n, 2], 1 - Mod[n, 2]]}]
a[n_] := Q[Bishop[n, 0], 1]*Q[Bishop[n, 1], 1];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jun 15 2017, translated from Andrew Howroyd's PARI code *)

\\ Needs memoization - see note on algorithm for a faster version.
M(sig,n,k,d,x)={if(n==0,k==0, if(k>0,k*x*M(sig,n-1,k-1,d,x),0) + if(kd,(sig[n]-d)*x*M(sig,n-1,k,d+1,x),0) + if(k+sig[n]-dAndrew Howroyd, Jun 05 2017

Conjectured to be a(n) = O(n^(n-1)).

a(n) = A290594(n) * A290613(n) for n > 1. - Andrew Howroyd, Aug 09 2017

a(10)-a(11) from Andrew Howroyd, May 21 2017

Terms a(12) and beyond from Andrew Howroyd, Jun 05 2017

A132343 Output of Knuth's "man or boy" test for varying k.

Original entry on oeis.org

1, 0, -2, 0, 1, 0, 1, -1, -10, -30, -67, -138, -291, -642, -1446, -3250, -7244, -16065, -35601, -78985, -175416, -389695, -865609, -1922362, -4268854, -9479595, -21051458, -46750171, -103821058, -230560902, -512016658, -1137056340, -2525108865, -5607619809

Offset: 0

Paolo Bonzini, Nov 08 2007

The man or boy test was proposed by computer scientist D. E. Knuth as a means of evaluating implementations of the ALGOL 60 programming language. The aim of the test was to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. E. Knuth (Jul 1964). Man or boy?.
Charles H. Lindsey (Dec 1988). Block Structure and Environments.
A. G. Price, et al. (Jan 1965). Men only.
Rosetta Code, Man or boy test.
Eric M. Schmidt, Recurrences for the man or boy sequence.
Index entries for linear recurrences with constant coefficients, signature (5,-10,11,-6,1).

CoefficientList[Series[(2 x^9 - 11 x^8 + 15 x^7 + x^6 - 16 x^5 + 13 x^4 + x^3 - 8 x^2 + 5 x - 1) / ((x - 1) (x^4 - 5 x^3 + 6 x^2 - 4 x + 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Jul 21 2013 *)
Join[{1,0,-2,0,1},LinearRecurrence[{5,-10,11,-6,1},{0,1,-1,-10,-30},29]] (* Ray Chandler, Jul 15 2015 *)

Vec(O(x^66)+(2*x^9-11*x^8+15*x^7+x^6-16*x^5+13*x^4+x^3-8*x^2+5*x-1)/((x-1)*(x^4-5*x^3+6*x^2-4*x+1))) \\ Joerg Arndt, Jul 21 2013

a(5)=0, a(6)=1, a(7)=-1, a(8)=-10, a(9)=-30, a(n)=a(n-5)-6*a(n-4)+11*a(n-3)-10*a(n-2)+5*a(n-1) for n >= 10. - Markus Jarderot (mizardx(AT)gmail.com), Jun 05 2010

G.f.: (2*x^9-11*x^8+15*x^7+x^6-16*x^5+13*x^4+x^3-8*x^2+5*x-1) / ((x-1)*(x^4-5*x^3+6*x^2-4*x+1)). - Joerg Arndt, Jul 21 2013

More terms from Eric M. Schmidt, Jul 20 2013

A115590 a(0) = 0; a(n) = (1+a(n-1))^3 for n > 0.

Original entry on oeis.org

0, 1, 8, 729, 389017000, 58871587162270593034051001, 204040901322752673844230437877671861543858084850895762746141813554591014612008

Offset: 0

Paolo Bonzini, Mar 15 2006; corrected Apr 06 2006 and Jan 19 2007

Take the rooted ternary tree of depth n, with (3^(n+1) - 1) / 2 labeled nodes. Let the number of rooted subtrees be a(n). For example, for n = 1 the a(2) = 8 subtrees are:
 R...R...R...R......R.......R...R.......R
 .../....|....\..../.\...../|...|\...../|\
 ..o.....o.....o..o...o...o.o...o.o...o.o.o
Then a(n+1) = (1+a(n))^3.

Geir Agnarsson, Elie Alhajjar, and Aleyah Dawkins, On locally finite ordered rooted trees and their rooted subtrees, arXiv:2312.11379 [math.CO], 2023.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
Index entries for sequences related to rooted trees

Cf. A000578, A004019, A368326, A368327.

{0}~Join~RecurrenceTable[{a[n]==(a[n-1]+1)^3, a[0]==1},a,{n,0,8}] (* Vaclav Kotesovec, May 21 2015 *)

As for A004019, it follows from Aho and Sloane that there is a constant c such that a(n) is the nearest integer to c^(3^n). In fact a(n) = nearest integer to b^(3^n) - 1 where b = 2.0804006677503193521177452323719035237099784935372250879749088464344434056773788...

Name edited by Michael De Vlieger, Dec 21 2023

cp's OEIS Frontend

User: Paolo Bonzini

A274775 Indices in A006928 where the imbalance between 1's and 2's sets a new record.

Views

Author

Keywords

Comments

Links

Crossrefs

A274448 Denominators in expansion of W(exp(x)) about x=1, where W is the Lambert function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A274447 Numerators in expansion of W(exp(x)) about x=1, where W is the Lambert function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Sage

Formula

A157679 Number of subtrees of a complete binary tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A144945 Number of ways to place 2 queens on an n X n chessboard so that they attack each other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A146303 Number of distinct ways to place queens (even fewer than n) on an n X n chessboard so that no queen is attacking another and that it is not possible to add another queen.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A146304 Number of distinct ways to place bishops (up to 2n-2) on an n X n chessboard so that no bishop is attacking another and that it is not possible to add another bishop.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs