cp's OEIS Frontend

A135922 Inverse binomial transform of A006116, which is the sum of Gaussian binomial coefficients [n,k] for q=2.

%I A135922 #100 May 07 2025 11:34:44
%S A135922 1,1,2,6,26,158,1330,15414,245578,5382862,162700898,6801417318,
%T A135922 394502066810,31849226170622,3589334331706258,566102993389615254,
%U A135922 125225331231990004138,38920655753545108286254,17021548688670112527781058,10486973328106497739526535366
%N A135922 Inverse binomial transform of A006116, which is the sum of Gaussian binomial coefficients [n,k] for q=2.
%C A135922 Let B = {v_1,v_2,...,v_n} be a basis for F_2^n.  a(n) is the number of subspaces of F_2^n that do not contain any of the vectors in B.  Moreover, for 1<=k<=n, let S be a size k subset of B. a(k) is the number of subspaces of F_2^n that do not contain any of the vectors in S but do contain all the vectors in B - S. - _Geoffrey Critzer_, May 03 2025
%C A135922 Also number of Stanley graphs on n nodes. For precise definition see Knuth (1997). - _Alois P. Heinz_, Sep 24 2019
%C A135922 Also the number of naturally labeled posets on [n] with height at most two. - _David Bevan_, Jul 28 2022; Nov 16 2023
%C A135922 Also the number of sign mappings X:([n] choose 2) -> {+,-} such that for any ordered 3-tuple a<b<c we have X(ab)X(ac)X(bc) not in {+-+,+++}. - _Manfred Scheucher_, Jan 05 2024
%D A135922 Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 318.
%H A135922 Alois P. Heinz, <a href="/A135922/b135922.txt">Table of n, a(n) for n = 0..115</a>
%H A135922 David Bevan, Gi-Sang Cheon and Sergey Kitaev, <a href="https://arxiv.org/abs/2311.08023">On naturally labelled posets and permutations avoiding 12-34</a>, arXiv:2311.08023 [math.CO], 2023.
%H A135922 Lucas Gagnon, <a href="https://arxiv.org/abs/2012.00108">The combinatorics of normal subgroups in the unipotent upper triangular group</a>, arXiv:2012.00108 [math.CO], 2020.
%H A135922 D. E. Knuth, <a href="/A323841/a323841.pdf">Letter to Daniel Ullman and others</a>, Apr 29 1997 [Annotated scanned copy, with permission]
%H A135922 Zvi Rosen and Yan X. Zhang, <a href="https://arxiv.org/abs/1702.06907">Convex Neural Codes in Dimension 1</a>, arXiv:1702.06907 [math.CO], 2017. Mentions this sequence.
%H A135922 R. P. Stanley, <a href="https://www.jstor.org/stable/2974988">Problem 10572</a>, The American Mathematical Monthly, 104(2) (1997), 168.
%H A135922 R. P. Stanley and S. C. Locke, <a href="https://www.jstor.org/stable/2589063">Graphs without increasing paths: Solution to Problem 10572</a>, The American Mathematical Monthly, 106(2) (1999), 168.
%F A135922 O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - (2^k-1)*x).
%F A135922 G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-x*(2^k-1))/(1-x/(x-1/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jan 16 2013
%F A135922 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 23 2013
%F A135922 a(n) = Sum_{k=0..n} qStirling2(n,k), where qStirling2 is the triangle A139382. - _Vladimir Kruchinin_, Feb 26 2020
%F A135922 G.f.: f(1), where f(y) = 1 + x*((y-1)*f(y) + f(2*y)). - _David Bevan_, Jul 28 2022
%F A135922 E.g.f.:  exp(-x)*g(x) where g(x) is the e.g.f. for A006116. (given in D. E. Knuth link) - _Geoffrey Critzer_, May 03 2025
%e A135922 O.g.f.: A(x) = 1 + x/(1-x) + x^2/((1-x)*(1-3x)) + x^3/((1-x)*(1-3x)*(1-7x)) + x^4/((1-x)*(1-3x)*(1-7x)*(1-15x)) + ...
%p A135922 b:= proc(n) option remember; add(mul(
%p A135922       (2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)
%p A135922     end:
%p A135922 a:= proc(n) option remember;
%p A135922       add(b(n-j)*binomial(n,j)*(-1)^j, j=0..n)
%p A135922     end:
%p A135922 seq(a(n), n=0..19);  # _Alois P. Heinz_, Sep 24 2019
%t A135922 Table[SeriesCoefficient[Sum[x^n/Product[(1-(2^k-1)*x),{k,0,n}],{n,0,nn}],{x,0,nn}] ,{nn,0,20}] (* _Vaclav Kotesovec_, Aug 23 2013 *)
%t A135922 b[n_] := b[n] = Sum[Product[(2^(i+k)-1)/(2^i-1), {i, 1, n-k}], {k, 0, n}];
%t A135922 a[n_] := a[n] = Sum[(-1)^j b[n-j] Binomial[n, j], {j, 0, n}];
%t A135922 a /@ Range[0, 19] (* _Jean-François Alcover_, Mar 10 2020, after _Alois P. Heinz_ *)
%o A135922 (PARI) a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-(2^j-1)*x+x*O(x^n))), n)
%o A135922 (Sage) # After _Vladimir Kruchinin_.
%o A135922 def a(n):
%o A135922     @cached_function
%o A135922     def T(n, k):
%o A135922         if k == 1 or k == n: return 1
%o A135922         return (2^k-1)*T(n-1, k) + T(n-1, k-1)
%o A135922     return sum(T(n, k) for k in (1..n)) if n > 0 else 1
%o A135922 print([a(n) for n in (0..19)]) # _Peter Luschny_, Feb 26 2020
%Y A135922 Cf. A006116, A323841, A323842, A323843, A139382, A006455, A356111.
%K A135922 nonn
%O A135922 0,3
%A A135922 _Paul D. Hanna_, Dec 06 2007
%E A135922 References for Stanley graphs added by _David Bevan_, Jul 24 2024