A005329 -id:A005329 - cp's OEIS frontend

A274985 a(n) = ([n]phi! - [n]{1-phi}!)/sqrt(5), where [n]_q! is the q-factorial, phi = (1+sqrt(5))/2.

0, 0, 1, 6, 58, 948, 25992, 1179016, 87713040, 10646068080, 2101395344400, 673242645670320, 349671381118477440, 294206779308703578240, 400822226102433353285760, 883965927408694948620295680, 3155212287401150653204012531200

Offset: 0

Vladimir Reshetnikov, Sep 23 2016

nonn

			For n = 3, [3]_phi! = 1060 + 474*sqrt(5), so A274983(5) = 2*1060 = 2120 and a(5) = 2*474 = 948.

Eric Weisstein's World of Mathematics, q-Factorial, Golden Ratio.

Cf. A274983, A005329, A275706, A276474, A276688, A276987.

Round@Table[(QFactorial[n, GoldenRatio] - QFactorial[n, 1 - GoldenRatio])/Sqrt[5], {n, 0, 20}] (* Round is equivalent to FullSimplify here, but is much faster *)

[n]_phi! = (A274983(n) + a(n)*sqrt(5))/2.
[n]_{1-phi}! = (A274983(n) - a(n)*sqrt(5))/2.
a(n) ~ c * phi^(n*(n+3)/2) / sqrt(5), where c = QPochhammer(phi-1) = A276987 = 0.1208019218617061294237231569887920563043992516794... . - Vaclav Kotesovec, Sep 24 2016

A277355 a(n) = Product_{k=1..n} (2^k + k).

Original entry on oeis.org

1, 3, 18, 198, 3960, 146520, 10256400, 1384614000, 365538096000, 190445348016000, 196920489848544000, 405459288598152096000, 1665626757561208810368000, 13666467545789718289069440000, 224102734815859800504160677120000, 7346759955468331839927899478024960000

Offset: 0

Vaclav Kotesovec, Oct 10 2016

nonn

Cf. A005329, A028362.

Table[Product[2^k+k, {k, 1, n}], {n, 0, 15}]

a(n) ~ c * 2^(n*(n+1)/2), where c = Product_{k>=1} (1 + k/2^k) = 5.52995584900...

A288853 Triangle read by rows: T(n,k) is the number of surjective linear mappings from an n-dimensional vector space over F_2 onto a k-dimensional vector space, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 1, 3, 6, 1, 7, 42, 168, 1, 15, 210, 2520, 20160, 1, 31, 930, 26040, 624960, 9999360, 1, 63, 3906, 234360, 13124160, 629959680, 20158709760, 1, 127, 16002, 1984248, 238109760, 26668293120, 2560156139520, 163849992929280, 1, 255, 64770, 16322040, 4047865920, 971487820800, 217613271859200, 41781748196966400, 5348063769211699200

Offset: 0

Geoffrey Critzer, Jun 18 2017

The (q = 2) analog of A008279.
A022166(m,k)*T(n,k) is the number of m X n matrices over F_2 that have rank k.
a(n) is the number of n X n matrices over F_2 in Green's R class containing A where rank(A) = k. - Geoffrey Critzer, Oct 05 2022

			  1;
  1,  1;
  1,  3,   6;
  1,  7,  42,   168;
  1, 15, 210,  2520,  20160;
  1, 31, 930, 26040, 624960, 9999360;
  ...

Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
Jeremy L. Martin, Lecture Notes on Algebraic Combinatorics, 2010-2023, Example 2.3.6.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
Wikipedia, Green's relations.

Columns k=0-10 give: A000012, A000225, 6*A006095, 168*A006096, 20160*A006097, 9999360*A006110, 20158709760*A022189, 163849992929280*A022190, 5348063769211699200*A022191, 699612310033197642547200*A022192, 366440137299948128422802227200*A022193.
Main diagonal gives A002884.
Cf. A022166.

Table[Table[Product[q^n - q^i, {i, 0, k - 1}] /. q -> 2, {k, 0, n}], {n, 0,8}] // Grid

T(n,k) = Product_{j=0..k-1} (2^n - 2^j).
T(n,k) = A002884(k)*A022166(n,k).
Let g_m(x) = Sum_{n>=0} (2^m*x)^n/A005329(n) and e(x) = Sum_{n>=0} x^n/A005329(n).  Then Sum_{k>=0} T(n,k)*x^k/A005329(k) = g_n(x)/e(x). - Geoffrey Critzer, Jun 01 2024

A289546 Triangle read by rows. T(n,k) is the number of flags in an n dimensional vector space over GF(2) that have length exactly k, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 1, 14, 21, 0, 1, 65, 315, 315, 0, 1, 372, 4650, 13020, 9765, 0, 1, 2823, 87234, 527310, 1025325, 615195, 0, 1, 29210, 2291715, 27448764, 105413175, 156259530, 78129765, 0, 1, 417197, 88508205, 2043137265, 14019952275, 38897461575, 46487210175, 19923090075

Offset: 0

Geoffrey Critzer, Jul 28 2017

			Triangle begins:
  1;
  0, 1;
  0, 1,    3;
  0, 1,   14,    21;
  0, 1,   65,   315,    315;
  0, 1,  372,  4650,  13020,    9765;
  0, 1, 2823, 87234, 527310, 1025325, 615195;

Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A005329 (main diagonal), A289545 (row sums).

nn = 8; eq[z_] := Sum[z^n/FunctionExpand[QFactorial[n, q]], {n, 0, nn}];Table[Take[(Table[ FunctionExpand[QFactorial[n, q]] /. q -> 2, {n, 0,  nn}] CoefficientList[Series[ 1/(1 - u (eq[z] - 1)) /. q -> 2, {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid

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

A293844 Number of chains in the partially ordered (by subspace inclusion) set of all subspaces of the vector space GF(2)^n.

Original entry on oeis.org

1, 3, 15, 143, 2783, 111231, 9031551, 1478288639, 485839107071, 319967908160511, 421866566365149183, 1112976522259306192895, 5873986737617632960438271, 62010172563368117470328995839, 1309330918812255261194272293584895, 55294146267102513780208470077042393087

Offset: 0

Geoffrey Critzer, Oct 17 2017

nonn

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

Row sums of A293845.

Cf. A005329, A289545.

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

a(n)/A005329(n) is the coefficient of x^n in eq(x)^2/(2 - eq(x)) where eq(x) is the q-exponential function.

A294640 G.f. A(x) = Sum_{n>=0} x^n/a(n) satisfies: A(x) = A(x^2) + Integral A(x^2) dx.

Original entry on oeis.org

1, 1, 1, 3, 1, 5, 3, 21, 1, 9, 5, 55, 3, 39, 21, 315, 1, 17, 9, 171, 5, 105, 55, 1265, 3, 75, 39, 1053, 21, 609, 315, 9765, 1, 33, 17, 595, 9, 333, 171, 6669, 5, 205, 105, 4515, 55, 2475, 1265, 59455, 3, 147, 75, 3825, 39, 2067, 1053, 57915, 21, 1197, 609, 35931, 315, 19215, 9765, 615195, 1, 65, 33, 2211, 17, 1173, 595, 42245, 9, 657, 333, 24975, 171, 13167, 6669, 526851, 5, 405, 205, 17015, 105, 8925, 4515, 392805, 55, 4895, 2475, 225225, 1265, 117645, 59455, 5648225, 3, 291, 147, 14553, 75, 7575, 3825, 393975, 39, 4095, 2067, 221169, 1053, 114777, 57915, 6428565, 21, 2373, 1197, 137655, 609, 71253, 35931, 4275789, 315, 38115, 19215, 2363445, 9765, 1220625, 615195, 78129765, 1

Offset: 0

Paul D. Hanna, Nov 05 2017

			G.f. A(x) = Sum_{n>=0} x^n/a(n) begins:
A(x) = 1/1 + x/1 + x^2/1 + x^3/3 + x^4/1 + x^5/5 + x^6/3 + x^7/21 + x^8/1 + x^9/9 + x^10/5 + x^11/55 + x^12/3 + x^13/39 + x^14/21 + x^15/315 + x^16/1 + x^17/17 + x^18/9 + x^19/171 + x^20/5 + x^21/105 + x^22/55 + x^23/1265 + x^24/3 + x^25/75 + x^26/39 + x^27/1053 + x^28/21 + x^29/609 + x^30/315 + x^31/9765 + x^32/1 + x^33/33 + x^34/17 + x^35/595 + x^36/9 + x^37/333 + x^38/171 + x^39/6669 + x^40/5 + x^41/205 + x^42/105 + x^43/4515 + x^44/55 + x^45/2475 + x^46/1265 + x^47/59455 + x^48/3 + x^49/147 + x^50/75 + x^51/3825 + x^52/39 + x^53/2067 + x^54/1053 + x^55/57915 + x^56/21 + x^57/1197 + x^58/609 + x^59/35931 + x^60/315 + x^61/19215 + x^62/9765 + x^63/615195 + x^64/1 +...+ x^n/a(n) +...
such that A(x) = A(x^2) + Integral A(x^2) dx.
Further,
A'(x) = A(x^2) + 2*x*A(x^4) + 4*x^3*A(x^8) + 8*x^7*A(x^16) + 16*x^15*A(x^32) + 32*x^31*A(x^64) +...+ 2^n * x^(2^n-1) * A( x^(2^(n+1)) ) +...
where A'(x) = A(x^2) + 2*x*A'(x^2).
RELATED SERIES.
A'(x) = 1/1 + 2*x/1 + x^2/1 + 4*x^3/1 + x^4/1 + 2*x^5/1 + x^6/3 + 8*x^7/1 + x^8/1 + 2*x^9/1 + x^10/5 + 4*x^11/1 + x^12/3 + 2*x^13/3 + x^14/21 + 16*x^15/1 + x^16/1 + 2*x^17/1 + x^18/9 + 4*x^19 + x^20/5 + 2*x^21/5 + x^22/55 + 8*x^23/1 + x^24/3 + 2*x^25/3 + x^26/39 + 4*x^27/3 + x^28/21 + 2*x^29/21 + x^30/315 + 32*x^31/1 + x^32/1 +...
Integral A(x^2) dx = x/1 + x^3/3 + x^5/5 + x^7/21 + x^9/9 + x^11/55 + x^13/39 + x^15/315 + x^17/17 + x^19/171 + x^21/105 + x^23/1265 + x^25/75 + x^27/1053 + x^29/609 + x^31/9765 + x^33/33 + x^35/595 + x^37/333 + x^39/6669 + x^41/205 + x^43/4515 + x^45/2475 + x^47/59455 + x^49/147 + x^51/3825 + x^53/2067 + x^55/57915 + x^57/1197 + x^59/35931 + x^61/19215 + x^63/615195 + x^65/65 +...
Also, we may write the g.f. as the series
A(x) = 1 + x + 2*x^2/2! + 2*x^3/3! + 24*x^4/4! + 24*x^5/5! + 240*x^6/6! + 240*x^7/7! + 40320*x^8/8! + 40320*x^9/9! + 725760*x^10/10! + 725760*x^11/11! + 159667200*x^12/12! + 159667200*x^13/13! + 4151347200*x^14/14! + 4151347200*x^15/15! + 20922789888000*x^16/16! + 20922789888000*x^17/17! + 711374856192000*x^18/18! + 711374856192000*x^19/19! + 486580401635328000*x^20/20! + 486580401635328000*x^21/21! + 20436376868683776000*x^22/22! + 20436376868683776000*x^23/23! +...+ n!/a(n) * x^n/n! +...
The terms at positions 2^n - 1 begin:
[1, 1, 3, 21, 315, 9765, 615195, 78129765, 19923090075, ..., A005329(n), ...].
The terms at positions 3*2^n - 1 begin:
[1, 5, 55, 1265, 59455, 5648225, 1078810975, 413184603425, 316912590826975, ...].

Paul D. Hanna, Table of n, a(n) for n = 0..4100

Cf. A005329.

{a(n) = my(A=1); for(i=1,#binary(n+1), A = subst(A, x, x^2) + intformal( subst(A, x, x^2) +x*O(x^n)) ); 1/polcoeff(A, n)}
for(n=0,128,print1(a(n),", "))

G.f. A(x) = Sum_{n>=0} x^n/a(n) satisfies:
(1) A'(x) = A(x^2) + 2*x*A'(x^2).
(2) A'(x) = A(x^2) + 2*x*A(x^4) + 4*x^3*A'(x^4).
(3) A'(x) = Sum_{n>=0} 2^n * x^(2^n-1) * A( x^(2^(n+1)) ).
(4) A(x) = 1 + Integral Sum_{n>=0} 2^n * x^(2^n-1) * A( x^(2^(n+1)) ) dx.
O.g.f. G(x) = Sum_{n>=0} a(n)*x^n satisfies:
(1) G(x) = G(x^2) + x * d/dx x*G(x^2).
(2) G(x) = (1+x)*G(x^2) + 2*x^3*G'(x^2).
a(2^n) = 1 for n>=0.
a(k*2^n) = a(k) for n>=0 and k>0.
a(2^n + 1) = 2^n + 1 for n>=1.
a(2^n - 1) = Product_{k=1..n} (2^k - 1) = A005329(n) for n>0.
a(3*2^n - 1) = Product_{k=1..n} (3*2^k - 1) for n>0.
a(m*2^n - 1) = Product_{k=1..n} (m*2^k - 1) for n>0 and positive odd m.
Limit_{n->oo} Sum_{k=0..2^n} 1/(a(k) * a(2^n-k)) = 3.9409369799444642172...

A342186 Triangle read by rows, matrix inverse of A139382.

Original entry on oeis.org

1, -1, 1, 3, -4, 1, -21, 31, -11, 1, 315, -486, 196, -26, 1, -9765, 15381, -6562, 1002, -57, 1, 615195, -978768, 428787, -69688, 4593, -120, 1, -78129765, 124918731, -55434717, 9279163, -652999, 19833, -247, 1

Offset: 1

John Keith, Mar 04 2021

This triangle appears to be the q-analog of A008275 (Stirling numbers of the first kind) for q=2. However, A333142 has a similar definition.
Row sums of unsigned triangle are A006125 with offset 1.
|T(n,k)| is the number of descent free digraphs on [n] containing exactly k source nodes.  A descent in a digraph is a pair of vertices s->t such that s>t.  A descent free digraph is necessarily acyclic.  A source in an acyclic digraph is a node with indegree 0. - Geoffrey Critzer, Mar 05 2025

			The triangle begins:
           1;
          -1,         1;
           3,        -4,         1;
         -21,        31,       -11,       1;
         315,      -486,       196,     -26,       1;
       -9765,     15381,     -6562,    1002,     -57,     1;
      615195,   -978768,    428787,  -69688,    4593,  -120,    1;
   -78129765, 124918731, -55434717, 9279163, -652999, 19833, -247, 1;
  ...

John Keith, Rows n = 1..20 of triangle, flattened
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

Cf. A008275, A139382, A333142, A333143, A006125 (row sums).

Columns of unsigned triangle: A005329, A203011, A000295, A203242.

A342186 := proc(n, k) if n = 1 and k = 1 then 1 elif k > n or k < 1 then 0 else
A342186(n-1, k-1) - (2^(n-1) - 1) * A342186(n-1, k) fi end:
for n from 1 to 8 do seq(A342186(n, k), k = 1..n) od; # Peter Luschny, Jun 28 2022

T[1, 1] := 1; T[n_, k_] := T[n, k] = If[k > n || k < 1, 0, T[n - 1, k - 1] - (2^(n - 1) - 1)*T[n - 1, k]]; Table[T[n, k], {n, 1, 8}, {k, 1, n}] (* after G. C. Greubel's program for A139382 *)

mat(nn) = my(m = matrix(nn, nn)); for (n=1, nn, for(k=1, nn, m[n,k] = if (n==1, if (k==1, 1, 0), if (k==1, 1, (2^k-1)*m[n-1, k] + m[n-1, k-1])););); m; \\ A139382
tabl(nn) = 1/mat(nn); \\ Michel Marcus, Mar 18 2021

T(n,k) = T(n-1,k-1) - (2^(n-1)-1) * T(n-1,k), n, k >= 1, T(1, 1) = 1, T(n, 0) = 0.
For unsigned triangle, T(n, 1) = A005329(n-1); T(n, 2) = A203011(n-1); T(n, n-1) = A000295(n+1); T(n, n-2) = A203242(n-1).
T(n,k) = Sum_{j=k..n} (-1)^(n-j)*2^binomial(n-j,2)*qBinomial(n,j,2)*binomial(j,k), where qBinomial(n,k,2) is A022166(n,k). - Fabian Pereyra, Feb 08 2024

A342245 Number of ordered pairs (S,T) of n X n idempotent matrices over GF(2) such that ST = TS = S.

Original entry on oeis.org

1, 3, 21, 339, 12483, 1074339, 219474243, 107174166147, 126918737362179, 367662330459585027, 2614066808849501254659, 45985259502347910886975491, 2009925824909891218929491103747, 218411680908756813835229484489351171, 59296916710446845619466630380450779971587

Offset: 0

Geoffrey Critzer, Mar 07 2021

nonn

The components in the ordered pairs are not necessarily distinct.

The relation S<=T iff ST=TS=S gives a partial ordering on the idempotent matrices enumerated in A132186. Each length k chain (from bottom to top) in the poset corresponds to an ordered direct sum decomposition of GF(2)^n into exactly k subspaces.

Cf. A132186, A005329.

nn = 13; b[n_] := q^Binomial[n, 2] FunctionExpand[QFactorial[n, q]] /. q -> 2;
e[x_] := Sum[x^n/b[n], {n, 0,nn}];Table[b[n],{n,0,nn}]CoefficientList[Series[e[x]^3, {x, 0, nn}], x]

Let E(x) = Sum_{n>=0} x^n/(2^binomial(n,2) * [n]A005329(n).%20Then%20E(x)%5E3%20=%20Sum">2!) where [n]_2! = A005329(n). Then E(x)^3 = Sum{n>=0} a(n)x^n/(2^binomial(n,2) * [n]_2!)

A347485 Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 2.

Original entry on oeis.org

1, 1, 3, 1, 7, 21, 1, 15, 35, 105, 315, 1, 31, 155, 465, 1085, 3255, 9765, 1, 63, 651, 1395, 1953, 9765, 22785, 29295, 68355, 205065, 615195, 1, 127, 2667, 11811, 8001, 82677, 177165, 413385, 248031, 1240155, 2893695, 3720465, 8681085, 26043255, 78129765

Offset: 1

Álvar Ibeas, Sep 03 2021

Abuse of notation: we write T(n, L) for T(n, k), where L is the k-th partition of n in A-St order.

For any permutation (e_1,...,e_r) of the parts of L, T(n, L) is the number of chains of subspaces 0 < V_1 < ··· < V_r = (F_2)^n with dimension increments (e_1,...,e_r).

			The number of subspace chains 0 < V_1 < V_2 < (F_2)^3 is 21 = T(3, (1, 1, 1)). There are 7 = A022166(3, 1) choices for a one-dimensional subspace V_1 and, for each of them, 3 = A022166(2, 1) extensions to a two-dimensional subspace V_2.
Triangle begins:
  k:  1  2   3   4    5    6    7
      ---------------------------
n=1:  1
n=2:  1  3
n=3:  1  7  21
n=4:  1 15  35 105  315
n=5:  1 31 155 465 1085 3255 9765

R. P. Stanley, Enumerative Combinatorics (vol. 1), Cambridge University Press (1997), Section 1.3.

Álvar Ibeas, First 20 rows, flattened

Cf. A036038 (q = 1), A022166, A005329 (last entry in each row).

T(n, (n)) = 1. T(n, L) = A022166(n, e) * T(n - e, L \ {e}), if L is a partition of n and e < n is a part of L.

A381192 Irregular triangle read by rows. Properly color the vertices of a simple labeled graph on [n] using exactly n colors c_1=0, 0<=k<=binomial(n,2).

Original entry on oeis.org

1, 1, 3, 1, 21, 19, 7, 1, 315, 516, 419, 208, 65, 12, 1, 9765, 24186, 31445, 27488, 17538, 8420, 3050, 816, 153, 18, 1, 615195, 2080323, 3769767, 4754751, 4592847, 3555479, 2257723, 1188595, 519745, 187705, 55237, 12941, 2325, 301, 25, 1

Offset: 0

Geoffrey Critzer, Feb 16 2025

A descent in a labeled directed graph is an edge s->t such that s>t.
T(n,0) = A005329(n).
Sum_{k>=0} T(n,k)*k = A005329(n)*n(n-1)/8.

			     1;
     1;
     3,     1;
    21,    19,     7,     1;
   315,   516,   419,   208,    65,   12,   1;
  9765, 24186, 31445, 27488, 17538, 8420, 3050, 816, 153, 18, 1;
  ...

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

CF. A005329, A381058, A011266 (row sums), A381102.

nn = 6; B[n_] :=FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]] (1 + y)^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}];Map[CoefficientList[#, u] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[1/(1 - z), {z, 0, nn}], z] /. y -> 1] // Grid

cp's OEIS Frontend

A274985 a(n) = ([n]phi! - [n]{1-phi}!)/sqrt(5), where [n]_q! is the q-factorial, phi = (1+sqrt(5))/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A277355 a(n) = Product_{k=1..n} (2^k + k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A288853 Triangle read by rows: T(n,k) is the number of surjective linear mappings from an n-dimensional vector space over F_2 onto a k-dimensional vector space, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A289546 Triangle read by rows. T(n,k) is the number of flags in an n dimensional vector space over GF(2) that have length exactly k, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A293844 Number of chains in the partially ordered (by subspace inclusion) set of all subspaces of the vector space GF(2)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A294640 G.f. A(x) = Sum_{n>=0} x^n/a(n) satisfies: A(x) = A(x^2) + Integral A(x^2) dx.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A342186 Triangle read by rows, matrix inverse of A139382.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A342245 Number of ordered pairs (S,T) of n X n idempotent matrices over GF(2) such that ST = TS = S.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica