A006117 -id:A006117 - cp's OEIS frontend

A228365 Inverse binomial transform of the Galois numbers G_(n)^{(3)} (A006117).

1, 1, 3, 15, 129, 1833, 43347, 1705623, 112931553, 12639552945, 2413134909507, 788041911546303, 442817851480763169, 428369525248261655193, 716160018275094098267859, 2067365673240491189928496263, 10333740296321620864171488891201, 89302459853776656431139970491341025

Offset: 0

R. J. Mathar, Aug 21 2013

nonn

Analog of the inverse binomial transform of G_(n)^{(q)} with q=2, A135922.

A 2-multigraph is a labeled graph with no loops but with up to 2 edges joining any pair of vertices. a(n) is the number of 2-multigraphs on [n] such that no path of length two has vertices i,j,k (in that order) with iGeoffrey Critzer, May 05 2025

Alois P. Heinz, Table of n, a(n) for n = 0..91
R. P. Stanley and S. C. Locke, Graphs without increasing paths: Solution to Problem 10572, The American Mathematical Monthly, 106(2) (1999), 168.

Cf. A135922, A006117, A006116.

b:= proc(n) option remember; add(mul(
      (3^(i+k)-1)/(3^i-1), i=1..n-k), k=0..n)
    end:
a:= proc(n) option remember;
      add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
seq(a(n), n=0..19);  # Alois P. Heinz, Sep 24 2019

Table[SeriesCoefficient[Sum[x^n/Product[(1-(3^k-1)*x),{k,0,n}],{n,0,nn}],{x,0,nn}] ,{nn,0,20}] (* Vaclav Kotesovec, Aug 23 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.01826904637117... if n is odd. - Vaclav Kotesovec, Aug 23 2013

A022167 Triangle of Gaussian binomial coefficients [ n,k ] for q = 3.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 13, 13, 1, 1, 40, 130, 40, 1, 1, 121, 1210, 1210, 121, 1, 1, 364, 11011, 33880, 11011, 364, 1, 1, 1093, 99463, 925771, 925771, 99463, 1093, 1, 1, 3280, 896260, 25095280, 75913222, 25095280, 896260, 3280, 1

Offset: 0

N. J. A. Sloane

The coefficients of the matrix inverse are apparently given by T^(-1)(n,k) = (-1)^n*A157783(n,k). - R. J. Mathar, Mar 12 2013

			Triangle begins:
  1;
  1,    1;
  1,    4,      1;
  1,   13,     13,        1;
  1,   40,    130,       40,        1;
  1,  121,   1210,     1210,      121,        1;
  1,  364,  11011,    33880,    11011,      364,      1;
  1, 1093,  99463,   925771,   925771,    99463,   1093,    1;
  1, 3280, 896260, 25095280, 75913222, 25095280, 896260, 3280, 1;

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.

T. D. Noe, Rows n = 0..50 of triangle, flattened
R. Mestrovic, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)
Index entries for sequences related to Gaussian binomial coefficients

Columns k=0..3 give A000012, A003462, A006100, A006101.

Cf. A006117 (row sums).

A022167 := proc(n,m)
        A027871(n)/A027871(n-m)/A027871(m) ;
end proc:
seq(seq(A022167(n,m),m=0..n),n=0..10) ; # R. J. Mathar, Nov 14 2011

p[n_] := Product[3^k-1, {k, 1, n}]; t[n_, m_] := p[n]/(p[n-m]*p[m]); Table[t[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jan 10 2014, after R. J. Mathar *)
Table[QBinomial[n, k, 3], {n, 0, 10}, {k, 0, n}] // Flatten
(* or, after Vladimir Kruchinin, using S 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 -> 3, {j, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 08 2020 *)

T(n,k) = T(n-1,k-1) + q^k * T(n-1,k). - Peter A. Lawrence, Jul 13 2017
T(n,k) = Sum_{j=0..k} C(n,j)*qStirling2(n-j,n-k,3)*(2)^(k-j),j,0,k), n >= k, where qStirling2(n,k,3) is triangle A333143. - Vladimir Kruchinin, Mar 07 2020
G.f. of column k: x^k * exp( Sum_{j>=1} f((k+1)*j)/f(j) * x^j/j ), where f(j) = 3^j - 1. - Seiichi Manyama, May 09 2025

A015195 Sum of Gaussian binomial coefficients for q=9.

Original entry on oeis.org

1, 2, 12, 184, 9104, 1225248, 540023488, 652225844096, 2584219514040576, 28081351726592246272, 1001235747932175990213632, 97915621602690773814148184064, 31420034518763282871588038742544384, 27654326463468067495668136467306727743488

Offset: 0

N. J. A. Sloane, Olivier Gérard

nonn

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.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 0..60
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A006116, A006117, A006118, A006119, A006120, A006121, A006122.

Row sums of triangle A022173.

Total/@Table[QBinomial[n, m, 9], {n, 0, 20}, {m, 0, n}] (* Vincenzo Librandi, Nov 01 2012 *)
Flatten[{1,RecurrenceTable[{a[n]==2*a[n-1]+(9^(n-1)-1)*a[n-2],a[0]==1,a[1]==2},a,{n,1,15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)

a(n) = 2*a(n-1)+(9^(n-1)-1)*a(n-2), (Goldman + Rota, 1969). - Vaclav Kotesovec, Aug 21 2013

a(n) ~ c * 9^(n^2/4), where c = EllipticTheta[3,0,1/9]/QPochhammer[1/9,1/9] = 1.3946866902389... if n is even and c = EllipticTheta[2,0,1/9]/QPochhammer[1/9,1/9] = 1.333574200539... if n is odd. - Vaclav Kotesovec, Aug 21 2013

A015196 Sum of Gaussian binomial coefficients for q=10.

Original entry on oeis.org

1, 2, 13, 224, 13435, 2266646, 1348019857, 2269339773068, 13484735901526279, 226960944509263279490, 13485189809930561625032701, 2269636415245291711513986785912, 1348523520252401463276762566348539123

Offset: 0

N. J. A. Sloane, Olivier Gérard

nonn

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.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 0..60
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A006116, A006117, A006118, A006119, A006120, A006121, A006122, A015195.

Row sums of triangle A022174.

Total/@Table[QBinomial[n, m, 10], {n, 0, 20}, {m, 0, n}] (* Vincenzo Librandi, Nov 01 2012 *)
Flatten[{1,RecurrenceTable[{a[n]==2*a[n-1]+(10^(n-1)-1)*a[n-2],a[0]==1,a[1]==2},a,{n,1,15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)

a(n) = 2*a(n-1)+(10^(n-1)-1)*a(n-2), (Goldman + Rota, 1969). - Vaclav Kotesovec, Aug 21 2013

a(n) ~ c * 10^(n^2/4), where c = EllipticTheta[3,0,1/10]/QPochhammer[1/10,1/10] = 1.348524024616... if n is even and c = EllipticTheta[2,0,1/10]/QPochhammer[1/10,1/10] = 1.2763120346269... if n is odd. - Vaclav Kotesovec, Aug 21 2013

A228465 Recurrence a(n) = a(n-1) + 2^n*a(n-2) with a(0)=0, a(1)=1.

Original entry on oeis.org

0, 1, 1, 9, 25, 313, 1913, 41977, 531705, 22023929, 566489849, 45671496441, 2366013917945, 376506912762617, 39141278944373497, 12376519796349807353, 2577539376694811306745, 1624792742123856760679161, 677311275106408471956040441, 852536648457739021814912002809

Offset: 0

Vaclav Kotesovec, Aug 22 2013

nonn

Generally (if p>0, q>1), recurrence a(n) = b*a(n-1) + (p*q^n+d)*a(n-2), a(n) is asymptotic to c*q^(n^2/4)*(p*q)^(n/2), where c is for fixed parameters b, p, d, q, a(0), a(1) constant, independent on n.

Vincenzo Librandi, Table of n, a(n) for n = 0..100

Cf. A006116, A006117, A006118, A006119, A006120, A006121, A006122.

[n le 2 select (n-1) else Self(n-1)+Self(n-2)*2^(n-1): n in [1..20]]; // Vincenzo Librandi, Aug 23 2013

RecurrenceTable[{a[n]==a[n-1]+2^n*a[n-2],a[0]==0,a[1]==1},a,{n,0,20}]
(* Alternative: *)
a[n_] := Sum[2^(k^2-1) QBinomial[n - k , k - 1, 2], {k, 1, n}];
Table[a[n], {n, 0, 19}] (* After Vladimir Kruchinin. Peter Luschny, Jan 20 2020 *)

def a(n):
    return sum(2^(k^2 - 1)*q_binomial(n-k , k-1, 2) for k in (1..n))
print([a(n) for n in range(20)]) # Peter Luschny, Jan 20 2020

a(n) ~ c * 2^(n^2/4 + n/2), where c = 0.548441579870783378573455400152590154... if n is even and c = 0.800417244834941368929416800341853541... if n is odd.

a(n) = Sum_{k=1..floor(n/2+1/2)} qbinomial(n-k,k-1)*2^(k^2-1), where q-binomial is triangle A022166, that is, with q=2. - Vladimir Kruchinin, Jan 20 2020

A015197 Sum of Gaussian binomial coefficients for q=11.

Original entry on oeis.org

1, 2, 14, 268, 19156, 3961832, 3092997464, 7024809092848, 60287817008722576, 1505950784990730735392, 142158530752430089391520224, 39060769254069395008311334483648, 40559566021977397260316290099710383936

Offset: 0

N. J. A. Sloane, Olivier Gérard

nonn

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.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 0..60
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A006116, A006117, A006118, A006119, A006120, A006121, A006122, A015195, A015196.

Row sums of triangle A022175.

Total/@Table[QBinomial[n, m, 11], {n, 0, 20}, {m, 0, n}] (* Vincenzo Librandi, Nov 02 2012 *)
Flatten[{1,RecurrenceTable[{a[n]==2*a[n-1]+(11^(n-1)-1)*a[n-2],a[0]==1,a[1]==2},a,{n,1,15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)

a(n) = 2*a(n-1)+(11^(n-1)-1)*a(n-2), (Goldman + Rota, 1969). - Vaclav Kotesovec, Aug 21 2013

a(n) ~ c * 11^(n^2/4), where c = EllipticTheta[3,0,1/11]/QPochhammer[1/11,1/11] = 1.312069129398... if n is even and c = EllipticTheta[2,0,1/11]/QPochhammer[1/11,1/11] = 1.2291712170215... if n is odd. - Vaclav Kotesovec, Aug 21 2013

A174527 Triangle T(n,m) = 2*A022167(n,m) - binomial(n, m), 0 <= m <= n, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 23, 23, 1, 1, 76, 254, 76, 1, 1, 237, 2410, 2410, 237, 1, 1, 722, 22007, 67740, 22007, 722, 1, 1, 2179, 198905, 1851507, 1851507, 198905, 2179, 1, 1, 6552, 1792492, 50190504, 151826374, 50190504, 1792492, 6552, 1, 1, 19673, 16139204

Offset: 0

Roger L. Bagula and Gary W. Adamson, Mar 21 2010

Row sums are 1, 2, 8, 48, 408, 5296, 113200, 4105184, 255805472, 27442457664, 5089653253824, ... = 2*A006117(n)-2^n.

			Triangle begins
  1;
  1,    1;
  1,    6,       1;
  1,   23,      23,        1;
  1,   76,     254,       76,         1;
  1,  237,    2410,     2410,       237,        1;
  1,  722,   22007,    67740,     22007,      722,       1;
  1, 2179,  198905,  1851507,   1851507,   198905,    2179,    1;
  1, 6552, 1792492, 50190504, 151826374, 50190504, 1792492, 6552, 1;

Cf. A060187.

A174527 := proc(n,k)
        2*A022167(n,k)-binomial(n,k) ;
end proc:
seq(seq(A174527(n,m),m=0..n),n=0..10) ; # R. J. Mathar, Nov 14 2011

c[n_, q_] = Product[1 - q^i, {i, 1, n}];
t[n_, m_, q_] = 2*c[n, q]/(c[m, q]*c[n - m, q]) - Binomial[n, m];
Table[Flatten[Table[Table[t[n, m, q], {m, 0, n}], {n, 0, 10}]], {q, 2, 12}]

A348102 a(n) is the number of vector subspaces in (F_3)^n, counted up to coordinate permutation.

Original entry on oeis.org

1, 2, 5, 12, 34, 102, 374, 1680, 10271, 91878, 1308856, 31048616, 1243411976, 83446254312, 9312844044030, 1715236203607456

Offset: 0

Álvar Ibeas, Sep 30 2021

nonn

Row sums of A347970. Cf. A006117, A076766.

A370887 Square array read by descending antidiagonals: T(n,k) is the number of subgroups of the elementary abelian group of order A000040(k)^n for n >= 0 and k >= 1.

Original entry on oeis.org

1, 1, 2, 1, 2, 5, 1, 2, 6, 16, 1, 2, 8, 28, 67, 1, 2, 10, 64, 212, 374, 1, 2, 14, 116, 1120, 2664, 2825, 1, 2, 16, 268, 3652, 42176, 56632, 29212, 1, 2, 20, 368, 19156, 285704, 3583232, 2052656, 417199, 1, 2, 22, 616, 35872, 3961832, 61946920, 666124288

Offset: 0

Miles Englezou, Mar 05 2024

As an elementary abelian group G of order p^n is isomorphic to an n-dimensional vector space V over the finite field of characteristic p, T(n,k) is also the number of subspaces of V.

V defined as above, T(n,k) is also the sum of the Gaussian binomial coefficients (n,r), 0 <= r < n, for a prime q number, since (n,r) counts the number of r-dimensional subspaces of V. The sequences of these sums for a fixed prime q number correspond to the columns of T(n,k).

			T(1,1) = 2 since the elementary abelian of order A000040(1)^1 = 2^1 has 2 subgroups.
T(3,5) = 2*T(2,5) + (A000040(5)^(3-1)-1)*T(1,5) = 2*14 + ((11^2)-1)*2 = 268.
First 6 rows and 8 columns:
n\k|   1     2       3        4          5           6            7            8
----+---------------------------------------------------------------------------
 0 |   1     1       1        1          1           1            1            1
 1 |   2     2       2        2          2           2            2            2
 2 |   5     6       8       10         14          16           20           22
 3 |  16    28      64      116        268         368          616          764
 4 |  67   212    1120     3652      19156       35872        99472       152404
 5 | 374  2664   42176   285704    3961832    10581824     51647264     99869288
 6 |2825 56632 3583232 61946920 3092997464 13340150272 141339210560 377566978168

Cf. A000040, A113935, A006116, A006117, A006119, A006121, A015197.

# produces an array A of the first (7(7+1))/2 terms. However computation quickly becomes expensive for values > 7.
LoadPackage("sonata");    # sonata package needs to be loaded to call function Subgroups. Sonata is included in latest versions of GAP.
N:=[1..7];; R:=[];; S:=[];;
for i in N do
    for j in N do
        if j>i then
            break;
        fi;
        Add(R,j);
    od;
    Add(S,R);
    R:=[];;
od;
A:=[];;
for n in N do
    L:=List([1..Length(S[n])],m->Size(Subgroups(ElementaryAbelianGroup( Primes[Reversed(S[n])[m]]^(S[n][m]-1)))));
    Add(A,L);
od;
A:=Flat(A);

T(n,k)=polcoeff(sum(i=0,n,x^i/prod(j=0,i,1-primes(k)[k]^j*x+x*O(x^n))),n)

T(n,k) = 2*T(n-1,k) + (A000040(k)^(n-1)-1)*T(n-2,k).
T(0,k) = 1.
T(1,k) = 2.
T(2,k) = A000040(k) + 3 = A113935(k).
T(3,k) = 2*(A000040(k)^3 + (A000040(k)-2))/(A000040(k)-1).

cp's OEIS Frontend

A228365 Inverse binomial transform of the Galois numbers G_(n)^{(3)} (A006117).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A022167 Triangle of Gaussian binomial coefficients [ n,k ] for q = 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A015195 Sum of Gaussian binomial coefficients for q=9.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A015196 Sum of Gaussian binomial coefficients for q=10.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A228465 Recurrence a(n) = a(n-1) + 2^n*a(n-2) with a(0)=0, a(1)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A015197 Sum of Gaussian binomial coefficients for q=11.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A174527 Triangle T(n,m) = 2*A022167(n,m) - binomial(n, m), 0 <= m <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

A348102 a(n) is the number of vector subspaces in (F_3)^n, counted up to coordinate permutation.

Views

Author