A003949 Expansion of g.f. (1+x)/(1-6*x).

1, 7, 42, 252, 1512, 9072, 54432, 326592, 1959552, 11757312, 70543872, 423263232, 2539579392, 15237476352, 91424858112, 548549148672, 3291294892032, 19747769352192, 118486616113152, 710919696678912, 4265518180073472, 25593109080440832, 153558654482644992

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Coordination sequence for infinite tree with valency 7.

For n >= 1, a(n+1) is equal to the number of functions f:{1,2,...,n+1}->{1,2,3,4,5,6,7} such that for fixed, different x_1, x_2,...,x_n in {1,2,...,n+1} and fixed y_1, y_2,...,y_n in {1,2,3,4,5,6,7} we have f(x_i)<>y_i, (i=1,2,...,n). - Milan Janjic, May 10 2007

For n >= 1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,2,3,5,6} with no two adjacent letters identical. - Milan Janjic, Jan 31 2015

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 308
• Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
• Index to divisibility sequences
• Index entries for linear recurrences with constant coefficients, signature (6).
• Index entries for sequences related to trees

Crossrefs

Cf. A003947, A003948, A003950, A003951.

Programs

GAP

k:=7;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Sep 24 2019

Magma

k:=7; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Sep 24 2019

Magma

R:=PowerSeriesRing(Rationals(), 25); Coefficients(R!( (1+x)/(1-6*x))); // Marius A. Burtea, Jan 20 2020

Maple

k:=7; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # modified by G. C. Greubel, Sep 24 2019

Mathematica

q = 7; Join[{a = 1}, Table[If[n != 0, a = q*a - a, a = q*a], {n, 0, 25}]] (* or *) Join[{1}, 7*6^Range[0, 25]] (* Vladimir Joseph Stephan Orlovsky, Jul 11 2011 *)
CoefficientList[Series[(1+x)/(1-6*x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 10 2012 *)
LinearRecurrence[{6},{1,7},30] (* or *) Join[{1},NestList[6#&,7,30]] (* Harvey P. Dale, May 03 2025 *)

PARI

a(n)=if(n,7*6^(n-1),1) \\ Charles R Greathouse IV, Mar 22 2016

Sage

k=7; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Sep 24 2019

Formula

G.f.: (1+x)/(1-6*x).

a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 5. - Philippe Deléham, Jul 10 2005

a(0)=1; for n > 0, a(n) = 7*6^(n-1). - Vincenzo Librandi, Nov 18 2010

a(0)=1, a(1)=7, a(n) = 6*a(n-1). - Vincenzo Librandi, Dec 10 2012

E.g.f.: (7*exp(6*x) - 1)/6. - G. C. Greubel, Sep 24 2019

Extensions

Edited by N. J. A. Sloane, Dec 04 2009