A006116 -id:A006116 - 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

A293845 Triangle read by rows: T(n,k) is the number of chains of length k in the partially ordered (by subspace inclusion) set of all subspaces of GF(2)^n, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 2, 1, 5, 7, 3, 16, 50, 56, 21, 67, 446, 1010, 945, 315, 374, 5395, 22692, 40455, 32550, 9765, 2825, 92881, 704601, 2167179, 3193155, 2255715, 615195, 29212, 2350136, 32061404, 162602418, 394534644, 496062000, 312519060, 78129765, 417199, 89342600, 2220570872, 18194735010, 68980503390, 138302085600, 151794972000

Offset: 0

Geoffrey Critzer, Oct 17 2017

			Triangle begins:
1;
2, 1;
5, 7, 3;
16, 50, 56, 21;
67, 446, 1010, 945, 315;
374, 5395, 22692, 40455, 32550, 9765;
...

Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.

Cf. A289546, A293844 (row sums), A005329 (main diagonal), A006116 (column k = 0).

nn = 10; eq[z_] :=Sum[z^n/FunctionExpand[QFactorial[n, q]], {n, 0, nn}]; Grid[Map[Select[#, # > 0 &] &,
  Table[FunctionExpand[QFactorial[n, q]] /. q -> 2, {n, 0,
     nn}] CoefficientList[Series[ eq[z]^2/(1 - u (eq[z] - 1)) /. q -> 2, {z, 0, nn}], {z, u}]]]

T(n,k)/A005329(n) is the coefficient of y^k*x^n in eq(x)^2/(1 - y (eq(x) - 1)) where eq(x) is the q-exponential function.

A382223 Rectangular array read by antidiagonals: T(n,k) is the number of labeled digraphs on [n] along with a (coloring) function c:[n] -> [k] with the property that for all u,v in [n], u->v implies u=0, k>=0.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 1, 0, 1, 16, 12, 4, 1, 0, 1, 67, 66, 22, 5, 1, 0, 1, 374, 513, 172, 35, 6, 1, 0, 1, 2825, 5769, 1969, 355, 51, 7, 1, 0, 1, 29212, 95706, 33856, 5380, 636, 70, 8, 1, 0, 1, 417199, 2379348, 893188, 125090, 12006, 1036, 92, 9, 1

Offset: 0

Geoffrey Critzer, Mar 23 2025

			 1, 1,   1,    1,     1,      1,      1,...
 0, 1,   2,    3,     4,      5,      6,...
 0, 1,   5,   12,    22,     35,     51,...
 0, 1,  16,   66,   172,    355,    636,...
 0, 1,  67,  513,  1969,   5380,  12006,...
 0, 1, 374, 5769, 33856, 125090, 352476,...

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, Discrete Mathematics, Vol. 343, No. 11 (2020), 112041; arXiv preprint, arXiv:1909.01550 [math.CO], 2019-2020. See Table 2.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.

Cf. A006116 column k=2, A289539 column k=3, A005329, A382363.

nn = 6; B[n_] := QFactorial[n, 2];e[z_] := Sum[z^n/B[n], {n, 0, nn}]; zetapolys = Drop[Map[Expand[InterpolatingPolynomial[#, x]] &,Transpose[Table[Table[B[n], {n, 0, nn}] CoefficientList[Series[e[z]^k, {z, 0, nn}], z], {k, 1, nn}]]], -1];Table[zetapolys /. x -> i, {i, 0, nn}] // Transpose // Grid

Sum_{n>=0} T(n,k)/A005329(n) = e(x)^k, where e(x) = Sum_{n>=0}x^n/A005329(n).

A289383 Total number of nonzero vectors over all subspaces of an n-dimensional vector space over the field with two elements.

Original entry on oeis.org

0, 1, 6, 35, 240, 2077, 23562, 358775, 7449060, 213188689, 8473977534, 470309723435, 36582636406680, 3998655357260293, 615328930033081458, 133485330929459963615, 40859530900982506959180, 17659495180812130332490681, 10781678259164073608877557286, 9301770545157096607562560360595

Offset: 0

Geoffrey Critzer, Jul 04 2017

nonn

The q-analog of A001787.

Cf. A001787, A006116, A022166.

nn = 20; eq[z_] :=Sum[z^n/FunctionExpand[QFactorial[n, q]], {n, 0, nn}];Table[FunctionExpand[QFactorial[n, q]] /. q -> 2, {n, 0, nn}] CoefficientList[Series[z eq[z]^2 /. q -> 2, {z, 0, nn}], z]

a(n) = Sum_{k=1..n} A022166(n,k)*(2^k - 1).
a(n)/[n]_q! is the coefficient of x^n in the expansion of x*exp_q(x)^2 when q->2 and where exp_q(x) is the q exponential function and [n]_q! is the q-factorial of n.
a(n) = (2^n - 1)*A006116(n-1).

A329154 Coefficients of polynomials related to the sum of Gaussian binomial coefficients for q = 2. Triangle read by rows, T(n,k) for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 6, 6, 3, 1, 26, 24, 12, 4, 1, 158, 130, 60, 20, 5, 1, 1330, 948, 390, 120, 30, 6, 1, 15414, 9310, 3318, 910, 210, 42, 7, 1, 245578, 123312, 37240, 8848, 1820, 336, 56, 8, 1, 5382862, 2210202, 554904, 111720, 19908, 3276, 504, 72, 9, 1

Offset: 0

Vladimir Kruchinin and Peter Luschny, Mar 08 2020

T(n,k) is the number of n X n matrices over F_2 in reduced row echelon form having exactly k zero-columns. Equivalently, T(n,k) is the number of subspaces of F_2^n that "involve" n-k coordinates. (For the definition of "involve" see the link below: D. E. Knuth, Letter to Daniel Ullman and others). - Geoffrey Critzer, May 03 2025

			Triangle starts:
[0] [1]
[1] [1,       1]
[2] [2,       2,       1]
[3] [6,       6,       3,      1]
[4] [26,      24,      12,     4,      1]
[5] [158,     130,     60,     20,     5,     1]
[6] [1330,    948,     390,    120,    30,    6,    1]
[7] [15414,   9310,    3318,   910,    210,   42,   7,   1]
[8] [245578,  123312,  37240,  8848,   1820,  336,  56,  8,  1]
[9] [5382862, 2210202, 554904, 111720, 19908, 3276, 504, 72, 9, 1]

D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]
R. P. Stanley and S. C. Locke, Graphs without increasing paths: Solution to Problem 10572, The American Mathematical Monthly, 106(2) (1999), 168.

Row sums: A006116, first column: A135922.

Cf. A022166, A323842, A323843.

T := (n, k) -> local j, m; pochhammer(n - k + 1, k)*add((-1)^j*add(product((2^(i + m) - 1)/(2^i - 1), i = 1..n-k-m-j), m = 0..n-k-j)*binomial(n - k, j), j = 0..n-k) / k!: for n from 0 to 9 do seq(T(n,k), k=0..n) od;  # Peter Luschny, Oct 08 2023

T[n_,k_]:= (Pochhammer[n-k+1,k]/(k!)*Sum[(-1)^j*Sum[Product[(2^(i+m)-1)/(2^i-1),{i,1,n-k-m-j}],{m,0,n-k-j}]*Binomial[n-k,j],{j,0,n-k}]); Flatten[Table[T[n,k],{n,0,9},{k,0,n}]] (* Detlef Meya, Oct 07 2023 *)

R = PolynomialRing(QQ, 'x')
x = R.gen()
@cached_function
def P(n, k, x):
    if k < 0 or n < 0: return R(0)
    if k == 0: return R(1)
    return x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2)
def row(n): return sum(P(n-k, k, x) for k in range(n+1)).coefficients()
print(flatten([row(n) for n in range(10)]))

Let P(n, k, x) = x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2) and Q(n, x) = Sum_{k=0..n} P(n-k, k, x) then T(n, k) = [x^k] Q(n, x).
T(n, k) = (1/k!) * Pochhammer(n-k+1, k) * Sum_{j=0..n-k}((-1)^j*Sum_{m=0..n-k-j} (Product_{i=1..n-k-m-j} ((2^(i+m)-1)/(2^i-1))) * binomial(n-k, j)). - Detlef Meya, Oct 07 2023
T(n,k) = binomial(n,k)*A135922(n-k). (see Stanley-Locke link above) - Geoffrey Critzer, May 03 2025
E.g.f.: exp(y x)*f(x) where f(x) is the e.g.f. for A135922. - Geoffrey Critzer, May 03 2025

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

A293845 Triangle read by rows: T(n,k) is the number of chains of length k in the partially ordered (by subspace inclusion) set of all subspaces of GF(2)^n, n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A382223 Rectangular array read by antidiagonals: T(n,k) is the number of labeled digraphs on [n] along with a (coloring) function c:[n] -> [k] with the property that for all u,v in [n], u->v implies u=0, k>=0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A289383 Total number of nonzero vectors over all subspaces of an n-dimensional vector space over the field with two elements.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A329154 Coefficients of polynomials related to the sum of Gaussian binomial coefficients for q = 2. Triangle read by rows, T(n,k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

GAP

PARI

Formula