A006127 a(n) = 2^n + n.
1, 3, 6, 11, 20, 37, 70, 135, 264, 521, 1034, 2059, 4108, 8205, 16398, 32783, 65552, 131089, 262162, 524307, 1048596, 2097173, 4194326, 8388631, 16777240, 33554457, 67108890, 134217755, 268435484, 536870941, 1073741854, 2147483679, 4294967328, 8589934625
Offset: 0
Examples
From _Viktar Karatchenia_, Feb 29 2016: (Start) a(0) = 1. There are n=0 leaves, it is a trivial tree consisting of a single parent node P. 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. 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. 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. 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. 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)
References
- John H. Conway, R. K. Guy, The Book of Numbers, Copernicus Press, p. 84.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 0..100
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 435
- C. L. Mallows & N. J. A. Sloane, Emails, May 1991
- Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
- Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
- Eric Weisstein's World of Mathematics, Sierpiński Number of the First Kind
- Eric Weisstein's World of Mathematics, Star Graph
- Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
- Index entries for linear recurrences with constant coefficients, signature (4,-5,2).
Programs
-
Haskell
a006127 n = a000079 n + n a006127_list = s [1] where s xs = last xs : (s $ zipWith (+) [1..] (xs ++ reverse xs)) Reinhard Zumkeller, May 19 2015, Feb 05 2011
-
Maple
A006127:=(-1+z+z**2)/(2*z-1)/(z-1)**2; # conjectured by Simon Plouffe in his 1992 dissertation
-
Mathematica
Table[2^n + n, {n, 0, 50}] (* Vladimir Joseph Stephan Orlovsky, May 19 2011 *) Table[BitXOr(i, 2^i), {i, 1, 100}] (* Peter Luschny, Jun 01 2011 *) LinearRecurrence[{4,-5,2},{1,3,6},40] (* Harvey P. Dale, Feb 08 2023 *) -
PARI
a(n)=1<
-
Python
print([2**n + n for n in range(34)]) # Karl V. Keller, Jr., Aug 18 2020
-
Python
def A006127(n): return (1<
Formula
Row sums of triangle A135227. - Gary W. Adamson, Nov 23 2007
Partial sums of A094373. G.f.: (1-x-x^2)/((1-x)^2(1-2x)). - Paul Barry, Aug 05 2004
Binomial transform of [1,2,1,1,1,1,1,...]. - Franklin T. Adams-Watters, Nov 29 2006
a(n) = 2*a(n-1) - n + 2 (with a(0)=1). - Vincenzo Librandi, Dec 30 2010
E.g.f.: exp(x)*(exp(x) + x). - Stefano Spezia, Dec 10 2021
Comments