Displaying 1-10 of 73 results found.
1, 5, 43, 709, 23003, 1481957, 190305691, 48796386661, 25003673060507, 25613941912987493, 52467767892904362139, 214929296497738201165669, 1760788099067877263041671323, 28849467307107603960961499533157
COMMENTS
To win a game, you must flip n+1 heads in a row, where n is the total number of tails flipped so far. The probability of having won before n+1 tails (that is, winning by flipping n+1 or fewer heads in a row) is a(n)/ A006125(n). The probability of winning for the first time after n tails (that is, by flipping n+1 heads in a row) is A005329(n)/ A006125(n).
FORMULA
a(n) = a(n-1) * 2^(n+1) + A005329(n).
EXAMPLE
a(3) = 43 because 1/2 + 1/8 + 3/64 = 43/64, or because a(2) * 2^(2+1) + A005329(2) = 5 * 8 + 3 = 43.
MATHEMATICA
Nest[Append[#1, #1[[-1]]*2^(#2 + 1) + Product[2^i - 1, {i, #2}]] & @@ {#, Length[#]} &, {1}, 13] (* Michael De Vlieger, Jul 15 2024 *)
Inverse binomial transform of A005329.
+20
2
1, 0, 2, 14, 246, 8374, 560950, 74018118, 19314751526, 10004153405174, 10313935405968726, 21205201672407811750, 87047013055579706265862, 713958711370466820900197334, 11705348549229324549016264190006
MATHEMATICA
Table[Sum[(-1)^(n+k) Binomial[n, k] QFactorial[k, 2], {k, 0, n}], {n, 0, 15}] (* Vladimir Reshetnikov, Nov 20 2015 *)
Normalized values of the Fabius function: 2^binomial(n-1, 2) * (2*n)! * A005329(n) * F(1/2^n).
+20
0
2, 1, 5, 105, 7007, 1298745, 619247475, 723733375365, 2006532782969715, 12889909959143502285, 188494585656727188486375, 6188497678605937441851529425, 451101946262511157576785806552415, 72341127537387548941434093006996374625, 25326487488712595887856341442148826764706875
COMMENTS
The Fabius function F(x) is the smooth monotone increasing function on [0, 1] satisfying F(0) = 0, F(1) = 1, F'(x) = 2*F(2*x) for 0 < x < 1/2, F'(x) = 2*F(2*(1-x)) for 1/2 < x < 1. It is infinitely differentiable at every point in the interval, but is nowhere analytic. It assumes rational values at dyadic rationals.
Comment from Vladimir Reshetnikov, Jan 25 2017: I just realized that I do not have a rigorous proof that all terms are integers. Could somebody suggest a proof? I would also be very interested to learn the asymptotics of this sequence.
REFERENCES
Rvachev V. L., Rvachev V. A., Non-classical methods of the approximation theory in boundary value problems, Naukova Dumka, Kiev (1979) (in Russian), pages 117-125.
MATHEMATICA
c[0] = 1; c[n_] := c[n] = Sum[(-1)^k c[n - k]/(2 k + 1)!, {k, 1, n}] / (4^n - 1); Table[2^(1 - 2 n) (2 n)! QFactorial[n, 2] Sum[c[k] (-1)^k/(n - 2 k)!, {k, 0, n/2}], {n, 0, 15}]
a(n) = 2^(n*(n-1)/2).
(Formerly M1897)
+10
354
1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736, 35184372088832, 36028797018963968, 73786976294838206464, 302231454903657293676544, 2475880078570760549798248448, 40564819207303340847894502572032, 1329227995784915872903807060280344576
COMMENTS
Number of graphs on n labeled nodes; also number of outcomes of labeled n-team round-robin tournaments.
Number of perfect matchings of order n Aztec diamond. [see Speyer]
Number of Gelfand-Zeitlin patterns with bottom row [1,2,3,...,n]. [Zeilberger]
For n >= 1 a(n) is the size of the Sylow 2-subgroup of the Chevalley group A_n(2) (sequence A002884). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 30 2001 a(n) is the number of ways to tile the region
o-----o
|.....|
o--o.....o--o
|...........|
o--o...........o--o
|.................|
o--o.................o--o
|.......................|
|.......................|
|.......................|
o--o.................o--o
|.................|
o--o...........o--o
|...........|
o--o.....o--o
|.....|
o-----o
(top-to-bottom distance = 2n) with dominoes like either of
o--o o-----o
|..| or |.....|
|..| o-----o
|..|
o--o
(End)
The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001 Let M_n denotes the n X n matrix with M_n(i,j)=binomial(2i,j); then det(M_n)=a(n+1). - Benoit Cloitre, Apr 21 2002 Smallest power of 2 which can be expressed as the product of n distinct numbers (powers of 2), e.g., a(4) = 1024 = 2*4*8*16. Also smallest number which can be expressed as the product of n distinct powers. - Amarnath Murthy, Nov 10 2002 The number of binary relations that are both reflexive and symmetric on an n-element set. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
The number of symmetric binary relations on an (n-1)-element set. - Peter Kagey, Feb 13 2021 To win a game, you must flip n+1 heads in a row, where n is the total number of tails flipped so far. Then the probability of winning for the first time after n tails is A005329 / A006125. The probability of having won before n+1 tails is A114604 / A006125. - Joshua Zucker, Dec 14 2005 a(n-1) is the number of simple labeled graphs on n nodes such that every node has even degree. - Geoffrey Critzer, Oct 21 2011 a(n+1) is the number of symmetric binary matrices of size n X n. - Nathan J. Russell, Aug 30 2014 Let T_n be the n X n matrix with T_n(i,j) = binomial(2i + j - 3, j-1); then det(T_n) = a(n). - Tony Foster III, Aug 30 2018 k^(n*(n-1)/2) is the determinant of n X n matrix T_(i,j) = binomial(k*i + j - 3, j-1), in this case k=2. - Tony Foster III, May 12 2019 Let B_n be the n+1 X n+1 matrix with B_n(i, j) = Sum_{m=max(0, j-i)..min(j, n-i)} (binomial(i, j-m) * binomial(n-i, m) * (-1)^m), 0<=i,j<=n. Then det B_n = a(n+1). Also, deleting the first row and any column from B_n results in a matrix with determinant a(n). The matrices B_n have the following property: B_n * [x^n, x^(n-1) * y, x^(n-2) * y^2, ..., y^n]^T = [(x-y)^n, (x-y)^(n-1) * (x+y), (x-y)^(n-2) * (x+y)^2, ..., (x+y)^n]^T. - Nicolas Nagel, Jul 02 2019 a(n) is the number of positive definite (-1,1)-matrices of size n X n. - Eric W. Weisstein, Jan 03 2021 a(n) is the number of binary relations on a labeled n-set that are both total and antisymmetric. - José E. Solsona, Feb 05 2023
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 547 (Fig. 9.7), 573.
G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 178.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 178.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 3, Eq. (1.1.2).
J. Propp, Enumeration of matchings: problems and progress, in: New perspectives in geometric combinatorics, L. Billera et al., eds., Mathematical Sciences Research Institute series, vol. 38, Cambridge University Press, 1999.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
FORMULA
Sequence is given by the Hankel transform of A001003 (Schroeder's numbers) = 1, 1, 3, 11, 45, 197, 903, ...; example: det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197; 11, 45, 197, 903]) = 2^6 = 64. - Philippe Deléham, Mar 02 2004 a(n) = 2^floor(n^2/2)/2^floor(n/2). - Paul Barry, Oct 04 2004 G.f.: G(0)/x - 1/x, where G(k) = 1 + 2^(k-1)*x/(1 - 1/(1 + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 26 2013 a(n) = s_lambda(1,1,...,1) where s is the Schur polynomial in n variables and lambda is the partition (n,n-1,n-2,...,1). - Leonid Bedratyuk, Feb 06 2022 a(n) = Product_{1 <= j <= i <= n-1} (i + j)/(2*i - 2*j + 1). Cf. A007685. - Peter Bala, Oct 25 2024
EXAMPLE
This sequence counts labeled graphs on n vertices. For example, the a(0) = 1 through a(2) = 8 graph edge sets are:
{} {} {} {}
{12} {12}
{13}
{23}
{12,13}
{12,23}
{13,23}
{12,13,23}
This sequence also counts labeled graphs with loops on n - 1 vertices. For example, the a(1) = 1 through a(3) = 8 edge sets are the following. A loop is represented as an edge with two equal vertices.
{} {} {}
{11} {11}
{12}
{22}
{11,12}
{11,22}
{12,22}
{11,12,22}
(End)
MATHEMATICA
Join[{1}, 2^Accumulate[Range[0, 20]]] (* Harvey P. Dale, May 09 2013 *) Prepend[Table[Count[Tuples[{0, 1}, {n, n}], _?SymmetricMatrixQ], {n, 5}], 1] (* Eric W. Weisstein, Jan 03 2021 *) Prepend[Table[Count[Tuples[{-1, 1}, {n, n}], _?PositiveDefiniteMatrixQ], 1], {n, 4}] (* Eric W. Weisstein, Jan 03 2021 *)
PROG
(Haskell) [2^(n*(n-1) `div` 2) | n <- [0..20]] -- José E. Solsona, Feb 05 2023 (Python)
CROSSREFS
Cf. A001187 (connected labeled graphs). The unlabeled version is A000088, or A002494 without isolated vertices. The version for hypergraphs is A058891, or A016031 without singletons. The case of connected edge set is A287689.
Decimal expansion of Product_{k >= 1} (1 - 1/2^k).
+10
99
2, 8, 8, 7, 8, 8, 0, 9, 5, 0, 8, 6, 6, 0, 2, 4, 2, 1, 2, 7, 8, 8, 9, 9, 7, 2, 1, 9, 2, 9, 2, 3, 0, 7, 8, 0, 0, 8, 8, 9, 1, 1, 9, 0, 4, 8, 4, 0, 6, 8, 5, 7, 8, 4, 1, 1, 4, 7, 4, 1, 0, 6, 6, 1, 8, 4, 9, 0, 2, 2, 4, 0, 9, 0, 6, 8, 4, 7, 0, 1, 2, 5, 7, 0, 2, 4, 2, 8, 4, 3, 1, 9, 3, 3, 4, 8, 0, 7, 8, 2
COMMENTS
This is the limiting probability that a large random binary matrix is nonsingular (cf. A002884). This constant is very close to 2^(13/24) * sqrt(Pi/log(2)) / exp(Pi^2/(6*log(2))) = 0.288788095086602421278899775042039398383022429351580356839... - Vaclav Kotesovec, Aug 21 2018
REFERENCES
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 354-361.
FORMULA
Lim inf Product_{k=0..floor(log_2(n))} floor(n/2^k)*2^k/n for n->oo. - Hieronymus Fischer, Aug 13 2007 Lim inf A098844(n)/n^(1+floor(log_2(n)))*2^(1/2*(1+floor(log_2(n)))*floor(log_2(n))) for n->oo. - Hieronymus Fischer, Aug 13 2007 Product_{k >= 1} (1-1/2^k) = (1/2; 1/2)_{infinity}, where (a;q)_{infinity} is the q-Pochhammer symbol. - G. C. Greubel, Nov 27 2015 exp(Sum_{n>=1}(1/n/(1 - 2^n))) (according to Mathematica). - Mats Granvik, Sep 07 2016 (Sum_{k>0} (4^k-1)/(Product_{i=1..k} ((4^i-1)*(2*4^i-1))))*2 = 2/7 + 2/(3*7*31) + 2/(3*7*15*31*127)+2/(3*7*15*31*63*127*511) + ... (conjecture). - Werner Schulte, Dec 22 2016 Equals Sum_{k=-oo..oo} (-1)^k/2^((3*k+1)*k/2) (by Euler's pentagonal number theorem). - Amiram Eldar, Aug 13 2020 Constant C = Sum_{n >= 0} (-1)^n/( Product_{k = 1..n} (2^k - 1) ). The above conjectural result by Schulte follows by adding terms of this series in pairs.
C = (1/2)*Sum_{n >= 0} (-1/2)^n/( Product_{k = 1..n} (2^k - 1) ).
C = (3/8)*Sum_{n >= 0} (-1/4)^n/( Product_{k = 1..n} (2^k - 1) ).
1/C = Sum_{n >= 0} 2^(n*(n-1)/2)/( Product_{k = 1..n} (2^k - 1) ).
C = 1 - Sum_{n >= 0} (1/2)^(n+1)*Product_{k = 1..n} (1 - 1/2^k).
This latter identity generalizes as:
C = Sum_{n >= 0} (1/4)^(n+1)*Product_{k = 1..n} (1 - 1/2^k),
3*C = 1 - Sum_{n >= 0} (1/8)^(n+1)*Product_{k = 1..n} (1 - 1/2^k),
3*7*C = 6 + Sum_{n >= 0} (1/16)^(n+1)*Product_{k = 1..n} (1 - 1/2^k),
3*7*15*C = 91 - Sum_{n >= 0} (1/32)^(n+1)*Product_{k = 1..n} (1 - 1/2^k),
and so on, where the sequence [1, 0, 1, 6, 91, ...] is A005327. (End)
Equals sqrt(2*Pi/log(2)) * exp(log(2)/24 - Pi^2/(6*log(2))) * Product_{k>=1} (1 - exp(-4*k*Pi^2/log(2))) (McIntosh, 1995).
Equals Sum_{n>=0} (-1)^n/ A005329(n).
EXAMPLE
(1/2)*(3/4)*(7/8)*(15/16)*... = 0.288788095086602421278899721929230780088911904840685784114741...
MATHEMATICA
RealDigits[ Product[1 - 1/2^i, {i, 100}], 10, 111][[1]] (* Robert G. Wilson v, May 25 2011 *)
PROG
(PARI) default(realprecision, 20080); x=prodinf(k=1, -1/2^k, 1); x*=10; for (n=0, 20000, d=floor(x); x=(x-d)*10; write("b048651.txt", n, " ", d)); \\ Harry J. Smith, May 07 2009
CROSSREFS
Cf. A002884, A001318, A005327, A005329, A048652, A065446, A079555, A098844, A067080, A100220, A132019, A132020, A132026, A132038, A070933, A261584, A335764.
Number of nonsingular n X n matrices over GF(2) (order of the group GL(n,2)); order of Chevalley group A_n (2); order of projective special linear group PSL_n(2).
(Formerly M4302 N1798)
+10
89
1, 1, 6, 168, 20160, 9999360, 20158709760, 163849992929280, 5348063769211699200, 699612310033197642547200, 366440137299948128422802227200, 768105432118265670534631586896281600, 6441762292785762141878919881400879415296000
COMMENTS
Also number of bases for GF(2^n) over GF(2).
Also (apparently) number of n X n matrices over GF(2) having permanent = 1. - Hugo Pfoertner, Nov 14 2003 The previous comment is true because over GF(2) permanents and determinants are the same. - Joerg Arndt, Mar 07 2008 The number of automorphisms of (Z_2)^n (the direct product of n copies of Z_2). - Peter Eastwood, Apr 06 2015 Note that n! divides a(n) since the subgroup of GL(n,2) consisting of all permutation matrices is isomorphic to S_n (the n-th symmetric group). - Jianing Song, Oct 29 2022
REFERENCES
Carter, Roger W. Simple groups of Lie type. Pure and Applied Mathematics, Vol. 28. John Wiley & Sons, London-New York-Sydney, 1972. viii+331pp. MR0407163 (53 #10946). See page 2.
J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker and R. A. Wilson, ATLAS of Finite Groups. Oxford Univ. Press, 1985 [for best online version see https://oeis.org/wiki/Welcome#Links_to_Other_Sites], p. xvi.
H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, 4th ed., Springer-Verlag, NY, reprinted 1984, p. 131.
Horadam, K. J., Hadamard matrices and their applications. Princeton University Press, Princeton, NJ, 2007. xiv+263 pp. See p. 132.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
a(n) = Product_{i=0..n-1} (2^n-2^i).
a(n) = 2^(n*(n-1)/2) * Product_{i=1..n} (2^i - 1).
a(n) = (6*a(n-1)^2*a(n-3) - 8*a(n-1)*a(n-2)^2) / (a(n-2)*a(n-3)) for n > 2. - Seiichi Manyama, Oct 20 2016
EXAMPLE
PSL_2(2) is isomorphic to the symmetric group S_3 of order 6.
MAPLE
# First program
A002884:= n-> product(2^n - 2^i, i=0..n-1);
# Second program
A002884:= n-> 2^(n*(n-1)/2) * product( 2^i - 1, i=1..n);
MATHEMATICA
Table[Product[2^n-2^i, {i, 0, n-1}], {n, 0, 13}] (* Harvey P. Dale, Aug 07 2011 *)
PROG
(Magma) [1] cat [(&*[2^n -2^k: k in [0..n-1]]): n in [1..15]]; // G. C. Greubel, Aug 31 2023 (SageMath) [product(2^n -2^j for j in range(n)) for n in range(16)] # G. C. Greubel, Aug 31 2023
Triangle of Gaussian binomial coefficients (or q-binomial coefficients) [n,k] for q = 2.
+10
80
1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 35, 15, 1, 1, 31, 155, 155, 31, 1, 1, 63, 651, 1395, 651, 63, 1, 1, 127, 2667, 11811, 11811, 2667, 127, 1, 1, 255, 10795, 97155, 200787, 97155, 10795, 255, 1, 1, 511, 43435, 788035, 3309747, 3309747, 788035, 43435, 511, 1
COMMENTS
Also number of distinct binary linear [n,k] codes.
T(n,k) is the number of subgroups of the Abelian group (C_2)^n that have order 2^k. - Geoffrey Critzer, Mar 28 2016 T(n,k) is the number of k-subspaces of the finite vector space GF(2)^n. - Jianing Song, Jan 31 2020
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.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 698.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.
FORMULA
G.f.: A(x,y) = Sum_{k>=0} y^k/Product_{j=0..k} (1 - 2^j*x). - Paul D. Hanna, Oct 28 2006 For k = 1,2,3,... the expansion of exp( Sum_{n >= 1} (2^(k*n) - 1)/(2^n - 1)*x^n/n ) gives the o.g.f. for the k-th diagonal of the triangle (k = 1 corresponds to the main diagonal). - Peter Bala, Apr 07 2015 T(m+n,k) = Sum_{i=0..k} q^((k-i)*(m-i)) * T(m,i) * T(n,k-i), q=2 (see the Sved link, page 337). - Werner Schulte, Apr 09 2019
EXAMPLE
Triangle begins:
1;
1, 1;
1, 3, 1;
1, 7, 7, 1;
1, 15, 35, 15, 1;
1, 31, 155, 155, 31, 1;
1, 63, 651, 1395, 651, 63, 1;
1, 127, 2667, 11811, 11811, 2667, 127, 1;
MAPLE
mul( 2^i-1, i=1..n) ;
end proc:
MATHEMATICA
(* S stands for qStirling2 *) S[n_, k_, q_] /; 1 <= k <= n := S[n - 1, k - 1, q] + Sum[q^j, {j, 0, k - 1}]*S[n - 1, k, q]; S[n_, 0, _] := KroneckerDelta[n, 0]; S[0, k_, _] := KroneckerDelta[0, k]; S[_, _, _] = 0;
T[n_, k_] /; n >= k := Sum[Binomial[n, j]*S[n - j, n - k, q]*(q - 1)^(k - j) /. q -> 2, {j, 0, k}];
PROG
(PARI) T(n, k)=polcoeff(x^k/prod(j=0, k, 1-2^j*x+x*O(x^n)), n) \\ Paul D. Hanna, Oct 28 2006 (PARI) qp = matpascal(9, 2);
for(n=1, #qp, for(k=1, n, print1(qp[n, k], ", "))) \\ Gerald McGarvey, Dec 05 2009 (PARI) {q=2; T(n, k) = if(k==0, 1, if (k==n, 1, if (k<0 || n<k, 0, T(n-1, k-1) + q^k*T(n-1, k))))};
for(n=0, 10, for(k=0, n, print1(T(n, k), ", "))) \\ G. C. Greubel, May 27 2018 (Sage) def T(n, k): return gaussian_binomial(n, k).subs(q=2) # Ralf Stephan, Mar 02 2014 (Magma) q:=2; [[k le 0 select 1 else (&*[(1-q^(n-j))/(1-q^(j+1)): j in [0..(k-1)]]): k in [0..n]]: n in [0..20]]; // G. C. Greubel, Nov 17 2018
Total number of self-dual binary codes of length 2n. Totally isotropic spaces of index n in symplectic geometry of dimension 2n.
+10
33
1, 3, 15, 135, 2295, 75735, 4922775, 635037975, 163204759575, 83724041661975, 85817142703524375, 175839325399521444375, 720413716161839357604375, 5902349576513949856852644375, 96709997811181068404530578084375
COMMENTS
a(n) = n terms in the sequence (1, 2, 4, 8, 16, ...) dot n terms in the sequence (1, 1, 3, 15, 135). Example: a(5) = 2295 = (1, 2, 4, 8, 16) dot (1, 1, 3, 15, 135) = (1 + 2 + 12 + 120 + 2160). - Gary W. Adamson, Aug 02 2010
REFERENCES
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 630.
FORMULA
a(n) = Product_{i=1..n-1} (2^i+1).
Letting a(0)=1, we have a(n) = Sum_{k=0..n-1} 2^k*a(k) for n>0. a(n) is asymptotic to c*sqrt(2)^(n^2-n) where c=2.384231029031371724149899288.... = A079555 = Product_{k>=1} (1 + 1/2^k). - Benoit Cloitre, Jan 25 2003 G.f.: Sum_{n>=1} 2^(n*(n-1)/2) * x^n/(Product_{k=0..n-1} (1-2^k*x)). - Paul D. Hanna, Sep 16 2009 a(n) = 2^(binomial(n,2) - 1)*(-1; 1/2)_{n}, where (a;q)_{n} is the q-Pochhammer symbol. - G. C. Greubel, Dec 23 2015 a(n) = b(n-1), where b(0) = 1, and for n > 0, b(n) = b(n-1) + (2^n)*b(n-1).
a(n) = Sum_{i=1.. A000124(n-1)} A053632(n-1,i-1)*(2^(i-1)) [where the indexing of both rows and columns of irregular table A053632(row,col) is considered to start from zero]. (End)
G.f. A(x) satisfies: A(x) = x * (1 + A(2*x)) / (1 - x). - Ilya Gutkovskiy, Jun 06 2020 Conjectural o.g.f. as a continued fraction of Stieltjes type (S-fraction):
1/(1 - 3*x/(1 - 2*x/(1 - 10*x/(1 - 12*x/(1 - 36*x/(1 - 56*x/(1 - 136*x/(1 - 240*x/(1 - ... - 2^(n-1)*(2^n + 1)*x/(1 - 2^n*(2^n - 1)*x/(1 - ... ))))))))))). - Peter Bala, Sep 27 2023
EXAMPLE
G.f. = x + 3*x^2 + 15*x^3 + 135*x^4 + 2295*x^5 + 75735*x^6 + 4922775*x^7 + ...
MAPLE
seq(mul(1 + 2^j, j = 1..n-1), n = 1..20); # G. C. Greubel, Jun 06 2020
MATHEMATICA
Table[Product[2^i+1, {i, n-1}], {n, 15}] (* or *) FoldList[Times, 1, 2^Range[15]+1] (* Harvey P. Dale, Nov 21 2011 *)
PROG
(PARI) {a(n)=polcoeff(sum(m=0, n, 2^(m*(m-1)/2)*x^m/prod(k=0, m-1, 1-2^k*x+x*O(x^n))), n)} \\ Paul D. Hanna, Sep 16 2009 (PARI) {a(n) = if( n<1, 0 , prod(k=1, n-1, 2^k + 1))}; /* Michael Somos, Jan 28 2018 */ (PARI) {a(n) = sum(k=0, n-1, 2^(k*(k+1)/2) * prod(j=1, k, (2^(n-j) - 1) / (2^j - 1)))}; /* Michael Somos, Jan 28 2018 */ (Sage)
from ore_algebra import *
R.<x> = QQ['x']
A.<Qx> = OreAlgebra(R, 'Qx', q=2)
print((Qx - x - 1).to_list([0, 1], 10)) # Ralf Stephan, Apr 24 2014 (Sage)
from sage.combinat.q_analogues import q_pochhammer
[q_pochhammer(n-1, -2, 2) for n in (1..20)] # G. C. Greubel, Jun 06 2020 (Magma) [1] cat [&*[ 2^k+1: k in [1..n] ]: n in [1..16]]; // Vincenzo Librandi, Dec 24 2015 (Python)
for n in range(2, 40, 2):
product = 1
for i in range(1, n//2-1 + 1):
product *= (2**i+1)
print(product)
(Python)
from math import prod
(Scheme, with memoization-macro definec)
(define ( A028362 n) (A028362off0 (- n 1))) (definec (A028362off0 n) (if (zero? n) 1 (+ (A028362off0 (- n 1)) (* (expt 2 n) (A028362off0 (- n 1))))))
Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n.
(Formerly M1501)
+10
25
1, 2, 5, 16, 67, 374, 2825, 29212, 417199, 8283458, 229755605, 8933488744, 488176700923, 37558989808526, 4073773336877345, 623476476706836148, 134732283882873635911, 41128995468748254231002, 17741753171749626840952685, 10817161765507572862559462656
COMMENTS
Also number of distinct binary linear codes of length n and any dimension.
Equivalently, number of subgroups of the Abelian group (C_2)^n.
Let V_n be an n-dimensional vector space over a field with 2 elements. Let P(V_n) be the collection of all subspaces of V_n. Then a(n-1) is the number of times any given nonzero vector of V_n appears in P(V_n). - Geoffrey Critzer, Jun 05 2017 With V_n and P(V_n) as above, a(n) is also the cardinality of P(V_n). - Vaia Patta, Jun 25 2019
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.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 698.
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.
FORMULA
O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - 2^k*x). - Paul D. Hanna, Dec 06 2007 Coefficients of the square of the q-exponential of x evaluated at q=2, where the q-exponential of x = Sum_{n>=0} x^n/F(n) and F(n) = Product{i=1..n} (q^i-1)/(q-1) is the q-factorial of n.
G.f.: (Sum_{k=0..n} x^n/F(n))^2 = Sum_{k=0..n} a(n)*x^n/F(n) where F(n) = A005329(n) = Product{i=1..n} (2^i - 1). a(n) = Sum_{k=0..n} F(n)/(F(k)*F(n-k)) where F(n)= A005329(n) is the 2-factorial of n. a(n) = Sum_{k=0..n} Product_{i=1..n-k} (2^(i+k) - 1)/(2^i - 1).
G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2^k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 16 2013 a(n) = 2*a(n-1) + (2^(n-1)-1)*a(n-2). [Hitzemann and Hochstattler]. - R. J. Mathar, Aug 21 2013 a(n) ~ c * 2^(n^2/4), where c = EllipticTheta[3,0,1/2] / QPochhammer[1/2,1/2] = 7.3719688014613... if n is even and c = EllipticTheta[2,0,1/2] / QPochhammer[1/2,1/2] = 7.3719494907662... if n is odd. - Vaclav Kotesovec, Aug 21 2013
EXAMPLE
O.g.f.: A(x) = 1/(1-x) + x/((1-x)*(1-2x)) + x^2/((1-x)*(1-2x)*(1-4x)) + x^3/((1-x)*(1-2x)*(1-4x)*(1-8x)) + ...
Also generated by iterated binomial transforms in the following way:
[1,2,5,16,67,374,2825,29212,...] = BINOMIAL([1,1,2,6,26,158,1330,...]); see A135922; [1,2,6,26,158,1330,15414,245578,...] = BINOMIAL([1,1,3,13,83,749,...]);
[1,3,13,83,749,9363,160877,...] = BINOMIAL^2([1,1,5,33,317,4361,...]);
[1,5,33,317,4361,82789,2148561,...] = BINOMIAL^4([1,1,9,97,1433,...]);
[1,9,97,1433,30545,902601,...] = BINOMIAL^8([1,1,17,321,7601,252833,...]);
etc.
MAPLE
gf:= m-> add(x^n/mul(1-2^k*x, k=0..n), n=0..m):
a:= n-> coeff(series(gf(n), x, n+1), x, n):
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
2^m*b(n-1, m)+b(n-1, m+1))
end:
a:= n-> b(n, 0):
MATHEMATICA
faq[n_, q_] = Product[(1-q^(1+k))/(1-q), {k, 0, n-1}]; qbin[n_, m_, q_] = faq[n, q]/(faq[m, q]*faq[n-m, q]); a[n_] := Sum[qbin[n, k, 2], {k, 0, n}]; a /@ Range[0, 19] (* Jean-François Alcover, Jul 21 2011 *) Flatten[{1, RecurrenceTable[{a[n]==2*a[n-1]+(2^(n-1)-1)*a[n-2], a[0]==1, a[1]==2}, a, {n, 1, 15}]}] (* Vaclav Kotesovec, Aug 21 2013 *) QP = QPochhammer; a[n_] := Sum[QP[2, 2, n]/(QP[2, 2, k]*QP[2, 2, n-k]), {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 23 2015 *) Table[Sum[QBinomial[n, k, 2], {k, 0, n}], {n, 0, 19}] (* Ivan Neretin, Mar 28 2016 *)
PROG
(PARI) a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-2^j*x+x*O(x^n))), n) \\ Paul D. Hanna, Dec 06 2007 (PARI) a(n, q=2)=sum(k=0, n, prod(i=1, n-k, (q^(i+k)-1)/(q^i-1))) \\ Paul D. Hanna, Nov 29 2008 (Magma) I:=[1, 2]; [n le 2 select I[n] else 2*Self(n-1)+(2^(n-2)-1)*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Aug 12 2014
a(n) = Product_{i=1..n} (3^i - 1).
+10
22
1, 2, 16, 416, 33280, 8053760, 5863137280, 12816818094080, 84078326697164800, 1654829626053597593600, 97714379759212830706892800, 17309711516825516108403231948800
COMMENTS
2*(10)^m|a(n) where 4*m <= n <= 4*m+3 for m >= 1. - G. C. Greubel, Nov 20 2015 Given probability p = 1/3^n that an outcome will occur at the n-th stage of an infinite process, then starting at n=1, 1-a(n)/ A047656(n+1) is the probability that the outcome has occurred at or before the n-th iteration. The limiting ratio is 1- A100220 ~ 0.4398739. - Bob Selcoe, Mar 01 2016
FORMULA
a(n) ~ c * 3^(n*(n+1)/2), where c = A100220 = Product_{k>=1} (1-1/3^k) = 0.560126077927948944969792243314140014379736333798... . - Vaclav Kotesovec, Nov 21 2015 a(n) = 3^(binomial(n+1,2))*(1/3;1/3)_{n}, where (a;q)_{n} is the q-Pochhammer symbol. - G. C. Greubel, Dec 24 2015 G.f.: Sum_{n>=0} 3^(n*(n+1)/2)*x^n / Product_{k=0..n} (1 + 3^k*x). - Ilya Gutkovskiy, May 22 2017 Sum_{n>=0} (-1)^n/a(n) = A100220. (End)
MAPLE
mul( 3^i-1, i=1..n) ;
end proc:
MATHEMATICA
Table[Product[(3^k-1), {k, 1, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jul 17 2015 *)
PROG
(Magma) [1] cat [&*[ 3^k-1: k in [1..n] ]: n in [1..11]]; // Vincenzo Librandi, Dec 24 2015
Search completed in 0.036 seconds
|