|
%I M2547 #108 Feb 08 2023 17:47:00
%S 1,3,6,11,20,37,70,135,264,521,1034,2059,4108,8205,16398,32783,65552,
%T 131089,262162,524307,1048596,2097173,4194326,8388631,16777240,
%U 33554457,67108890,134217755,268435484,536870941,1073741854,2147483679,4294967328,8589934625
%N a(n) = 2^n + n.
%C For numbers m=n+2^n such that equation x=2^(m-x) has solution x=2^n, see A103354. - _Zak Seidov_, Mar 23 2005
%C Primes of the form x^x+1 must be of the form 2^2^(a(n))+1, that is, Fermat number F_(a(n)) (Sierpiński 1958). - _David W. Wilson_, May 08 2005
%C a(n) = n-th Mersenne number + n + 1 = A000225(n) + n + 1. Partial sums of a(n) are A132925(n+1). - _Jaroslav Krizek_, Oct 16 2009
%C Intersection of A188916 and A188917: A188915(a(n)) = (2^n)^2 = 2^(2*n) = A000302(n). - _Reinhard Zumkeller_, Apr 14 2011
%C a(n) is also the number of all connected subtrees of a star tree, having n leaves. The star tree is a tree, where all n leaves are connected to one parent P. - _Viktar Karatchenia_, Feb 29 2016
%D John H. Conway, R. K. Guy, The Book of Numbers, Copernicus Press, p. 84.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Reinhard Zumkeller, <a href="/A006127/b006127.txt">Table of n, a(n) for n = 0..100</a>
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=435">Encyclopedia of Combinatorial Structures 435</a>
%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123.pdf">Emails, May 1991</a>
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SierpinskiNumberoftheFirstKind.html">Sierpiński Number of the First Kind</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/StarGraph.html">Star Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).
%F Row sums of triangle A135227. - _Gary W. Adamson_, Nov 23 2007
%F Partial sums of A094373. G.f.: (1-x-x^2)/((1-x)^2(1-2x)). - _Paul Barry_, Aug 05 2004
%F Binomial transform of [1,2,1,1,1,1,1,...]. - _Franklin T. Adams-Watters_, Nov 29 2006
%F a(n) = 2*a(n-1) - n + 2 (with a(0)=1). - _Vincenzo Librandi_, Dec 30 2010
%F E.g.f.: exp(x)*(exp(x) + x). - _Stefano Spezia_, Dec 10 2021
%e From _Viktar Karatchenia_, Feb 29 2016: (Start)
%e a(0) = 1. There are n=0 leaves, it is a trivial tree consisting of a single parent node P.
%e a(1) = 3. There is n=1 leaf, the tree is P-A, the subtrees are: 2 singles: P, A; 1 pair: P-A; 2+1 = 3 subtrees in total.
%e a(2) = 6. When n=2, the tree is P-A P-B, the subtrees are: 3 singles: P, A, B; 2 pairs: P-A, P-B; 1 triple: A-P-B (the whole tree); 3+2+1 = 6.
%e a(3) = 11. For n=3 leaf nodes, the tree is P-A P-B P-C, the subtrees are: 4 singles: P, A, B, C; 3 pairs: P-A, P-B, P-C; 3 triples: A-P-B, A-P-C, B-P-C; 1 quad: P-A P-B P-C (the whole tree); 4+3+3+1 = 11 in total.
%e a(4) = 20. For n=4 leaves, the tree is P-A P-B P-C P-D, the subtrees are: 5 singles: P, A, B, C, D; 4 pairs: P-A, P-B, P-C, P-D; 6 triples: A-P-B, A-P-C, B-P-C, A-P-D, B-P-D, C-P-D; 4 quads: P-A P-B P-C, P-A P-B P-D, P-A P-C P-D, P-B P-C P-D; the whole tree counts as 1; 5+4+6+4+1 = 20.
%e In general, for n leaves, connected to the parent node P, there will be: (n+1) singles; (n, 1) pairs; (n, 2) triples; (n, 3) quads; ... ; (n, n-1) subtrees having (n-1) edges; 1 whole tree, having all n edges. Thus, the total number of all distinct subtrees is: (n+1) + (n, 1) + (n, 2) + (n, 3) + ... + (n, n-1) + 1 = (n + (n, 0)) + (n, 1) + (n, 2) + (n, 3) + ... + (n, n-1) + (n, n) = n + (sum of all binomial coefficients of size n) = n + (2^n). (End)
%p A006127:=(-1+z+z**2)/(2*z-1)/(z-1)**2; # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t Table[2^n + n, {n, 0, 50}] (* _Vladimir Joseph Stephan Orlovsky_, May 19 2011 *)
%t Table[BitXOr(i, 2^i), {i, 1, 100}] (* _Peter Luschny_, Jun 01 2011 *)
%t LinearRecurrence[{4,-5,2},{1,3,6},40] (* _Harvey P. Dale_, Feb 08 2023 *)
%o (Haskell)
%o a006127 n = a000079 n + n
%o a006127_list = s [1] where
%o s xs = last xs : (s $ zipWith (+) [1..] (xs ++ reverse xs))
%o _Reinhard Zumkeller_, May 19 2015, Feb 05 2011
%o (PARI) a(n)=1<<n+n \\ _Charles R Greathouse IV_, Jul 19 2011
%o (Python) print([2**n + n for n in range(34)]) # _Karl V. Keller, Jr._, Aug 18 2020
%o (Python)
%o def A006127(n): return (1<<n)+n # _Chai Wah Wu_, Jan 11 2023
%Y Cf. A135227, A000079, A052944; A000051 (first differences).
%Y Cf. A000325.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
|
