|
|
A006117
|
|
Sum of Gaussian binomial coefficients [ n,k ] for q=3.
(Formerly M1687)
|
|
9
|
|
|
1, 2, 6, 28, 212, 2664, 56632, 2052656, 127902864, 13721229088, 2544826627424, 815300788443072, 452436459318538048, 434188323928823259776, 722197777341507864283008, 2078153254879878944892861184, 10366904326991986000747424911616, 89478415088556766546699920236339712, 1338962661056423158371347974009398601216
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
REFERENCES
|
J. Goldman and G.-C. Rota, The number of subspaces of a vector space, pp. 75-83 of W. T. Tutte, editor, Recent Progress in Combinatorics. Academic Press, NY, 1969.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley, NY, 1983, p. 99.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.
|
|
LINKS
|
|
|
FORMULA
|
O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - 3^k*x). - Paul D. Hanna, Dec 06 2007
a(n) = 2*a(n-1)+(3^(n-1)-1)*a(n-2), n>1. [Hitzemann and Hochstattler] - R. J. Mathar, Aug 21 2013
a(n) ~ c * 3^(n^2/4), where c = EllipticTheta[3,0,1/3] / QPochhammer[1/3,1/3] = 3.019783845699... if n is even and c = EllipticTheta[2,0,1/3]/QPochhammer[1/3,1/3] = 3.018269046371... if n is odd. - Vaclav Kotesovec, Aug 21 2013
0 = a(n)*(2*a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(-6*a(n+1) + 3*a(n+2)) for all n in Z. - Michael Somos, Jan 25 2014
|
|
EXAMPLE
|
O.g.f.: A(x) = 1/(1-x) + x/((1-x)*(1-3x)) + x^2/((1-x)*(1-3x)*(1-9x)) + x^3/((1-x)*(1-3x)*(1-9x)*(1-27x)) + ...
Also generated by iterated binomial transforms in the following way:
[1,2,6,28,212,2664,56632,...] = BINOMIAL([1,1,3,15,129,1833,43347,..]);
[1,3,15,129,1833,43347,1705623,...] = BINOMIAL^2([1,1,7,67,1081,...]);
[1,7,67,1081,29185,1277887,...] = BINOMIAL^6([1,1,19,415,12961,...]);
[1,19,415,12961,684361,58352707,...] = BINOMIAL^18([1,1,55,3187,...]);
[1,55,3187,219673,22634209,...] = BINOMIAL^54([1,1,163,27055,4805569,...]);
etc.
G.f. = 1 + 2*x + 6*x^2 + 28*x^3 + 212*x^4 + 2664*x^5 + 56632*x^6 + 2052656*x^7 + ...
|
|
MAPLE
|
f:=n-> 1+ add( mul((3^(n-i)-1)/(3^(i+1)-1), i=0..k-1), k=1..n);
|
|
MATHEMATICA
|
Flatten[{1, RecurrenceTable[{a[n]==2*a[n-1]+(3^(n-1)-1)*a[n-2], a[0]==1, a[1]==2}, a, {n, 1, 15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)
Table[Sum[QBinomial[n, k, 3], {k, 0, n}], {n, 0, 20}] (* Vincenzo Librandi, Aug 13 2016 *)
|
|
PROG
|
(PARI) a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-3^j*x+x*O(x^n))), n) \\ Paul D. Hanna, Dec 06 2007
(Magma) [n le 2 select n else 2*Self(n-1)+(3^(n-2)-1)*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Aug 13 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|