login
a(n) = 7^n - 3*4^n + 2*3^n.
(Formerly M5078 N2197)
17

%I M5078 N2197 #48 Oct 17 2023 01:04:27

%S 1,19,205,1795,14221,106819,778765,5581315,39606541,279447619,

%T 1965098125,13792018435,96690872461,677427332419,4744368982285,

%U 33220131761155,232579232659981,1628208214321219,11398072876175245,79788974736297475,558532690864457101

%N a(n) = 7^n - 3*4^n + 2*3^n.

%C Counts connected relations. On page 578 Kreweras (1969) says: "Le théorème s'applique notamment au dénombrement des relations binaires externes qui possèdent la propriété de connexité; cela revient à calculer le nombre a(m,n) de manières de remplir un tableau de m lignes et n colonnes avec des 0 et des 1, en respectant les deux conditions suivantes: (1): aucune rangée (ligne ni colonne) ne doit être tout entière remplie de zéros; (2): deux cases quelconques marquées 1 peuvent être jointes par une chaîne de cases marquées 1 telle que deux cases consécutives de la chaîne appartiennent à une même rangée."

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A002501/b002501.txt">Table of n, a(n) for n = 1..200</a>

%H G. Kreweras, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k480296q/f583.image">Inversion des polynomes de Bell bidimensionnels et application au dénombrement des relations binaires connexes</a>, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (14,-61,84)

%F G.f.: -x*(1+5*x) / ( (3*x-1)*(7*x-1)*(4*x-1) ). - _R. J. Mathar_, Jun 09 2013

%F a(n) = 14*a(n-1) - 61*a(n-2) + 84*a(n-3). - _Wesley Ivan Hurt_, Apr 11 2022

%t Table[7^n - 3*4^n + 2*3^n, {n, 20}] (* _T. D. Noe_, May 29 2012 *)

%o (PARI) a(n)=7^n-3*4^n+2*3^n \\ _Charles R Greathouse IV_, Sep 24 2015

%Y Cf. A005333, A001047, A002502, A093732, A093733.

%Y A diagonal of A262307.

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_

%E Better definition and more terms from Goran Kilibarda, _Vladeta Jovovic_, Apr 14 2004