A022166 -id:A022166 - cp's OEIS frontend

A385435 Row sums of A385434.

1, 2, 2, 4, 4, 8, 2, 4, 4, 8, 8, 16, 4, 8, 8, 16, 13, 26, 2, 4, 4, 8, 8, 16, 4, 8, 8, 16, 16, 32, 8, 16, 16, 32, 26, 52, 4, 8, 8, 16, 13, 26, 8, 16, 16, 32, 26, 52, 13, 26, 26, 52, 40, 80, 2, 4, 4, 8, 8, 16, 4, 8, 8, 16, 16, 32, 8, 16, 16, 32, 26, 52, 4, 8, 8

Offset: 0

David Radcliffe, Jun 28 2025

Donald E. Knuth and Herbert S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math., 396:212-219, 1989.
Romeo Meštrović, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014. (See Equation (80) on p. 31.)

Cf. A007318, A051638, A022166, A385434.

Total/@Table[Mod[QBinomial[n, k, 2], 3], {n, 0,74}, {k, 0, n}]  (* James C. McMahon, Jun 29 2025 *)

from gmpy2 import digits
def A385435(n): return 3*3**(s:=digits(n>>1,3)).count('2')-1<>1,3)).count('2')-1<>1 # Chai Wah Wu, Jul 10 2025

a(2n) = A051638(n), a(2n+1) = 2*A051638(n).

A136097 a(n) = A135951(n) /[(2^(n+1)-1) * 2^(n*(n-1)/2)].

Original entry on oeis.org

1, -1, 5, -93, 6477, -1733677, 1816333805, -7526310334829, 124031223014725741, -8152285307423733458541, 2140200604371078953284092525, -2245805993494514875022552272042605, 9423041917569791458584837551185555483245

Offset: 0

Paul D. Hanna, Dec 13 2007

sign

A135951 is the central terms of A135950; A135950 is the matrix inverse of A022166; A022166 is the triangle of Gaussian binomial coefficients [n,k] for q = 2.

Cf. A135951, A135950, A022166.

Table[(-1)^n QBinomial[2n, n, 2]/(2^(n+1) - 1), {n, 0, 20}] (* Vladimir Reshetnikov, Sep 16 2016 *)

a(n)=local(q=2,A=matrix(2*n+1,2*n+1,n,k,if(n>=k,if(n==1 || k==1, 1, prod(j=n-k+1, n-1, 1-q^j)/prod(j=1, k-1, 1-q^j))))^-1); A[2*n+1,n+1]/( (q^(n+1)-1)/(q-1) * q^(n*(n-1)/2) )

Conjecture: the n-th central term of the matrix inverse of the triangle of Gaussian binomial coefficients in q is divisible by [(q^(n+1)-1)/(q-1) * q^(n*(n-1)/2)] for n>=0 and integer q > 1.

a(n) = (-1)^n * A015030(n) where A015030 is 2-Catalan numbers. - Michael Somos, Jan 10 2023

A156914 Square array T(n, k) = q-binomial(2*n, n, k+1), read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 3, 6, 1, 4, 35, 20, 1, 5, 130, 1395, 70, 1, 6, 357, 33880, 200787, 252, 1, 7, 806, 376805, 75913222, 109221651, 924, 1, 8, 1591, 2558556, 6221613541, 1506472167928, 230674393235, 3432, 1, 9, 2850, 12485095, 200525284806, 1634141006295525, 267598665689058580, 1919209135381395, 12870

Offset: 0

Roger L. Bagula, Feb 18 2009

			Square array begins as:
    1,         1,             1,                1, ...;
    2,         3,             4,                5, ...;
    6,        35,           130,              357, ...;
   20,      1395,         33880,           376805, ...;
   70,    200787,      75913222,       6221613541, ...;
  252, 109221651, 1506472167928, 1634141006295525, ...;
Antidiagonal triangle begins as:
  1;
  1, 2;
  1, 3,    6;
  1, 4,   35,      20;
  1, 5,  130,    1395,         70;
  1, 6,  357,   33880,     200787,           252;
  1, 7,  806,  376805,   75913222,     109221651,          924;
  1, 8, 1591, 2558556, 6221613541, 1506472167928, 230674393235, 3432;

G. C. Greubel, Antidiagonal rows n = 0..25, flattened

Cf. A000984, A022166, A022167, A022168, A022169, A022170, A022171, A022175.

QBinomial:= func< n,k,q | q eq 1 select Binomial(n, k) else k eq 0 select 1 else (&*[ (1-q^(n-j+1))/(1-q^j): j in [1..k] ]) >;
T:= func< n,k | QBinomial(2*n, n, k+1) >;
[T(k, n-k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jun 14 2021

T[n_, k_]:= QBinomial[2*n, n, k+1];
Table[T[k, n-k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jun 14 2021 *)

def A156914(n, k): return q_binomial(2*n, n, k+1)
flatten([[A156914(k,n-k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Jun 14 2021

T(n, k) = q-binomial(2*n, n, k+1), where q-binomial(n, k, q) = Product_{j=0..k-1} ( (1-q^(n-j))/(1-q^(j+1)) ), read by antidiagonals. - G. C. Greubel, Jun 14 2021

Edited by G. C. Greubel, Jun 14 2021

A270883 Row sums of triangle A270882. Number of direct-sum decompositions of an n-dimensional vector space over GF(2) with any given nonzero vector in a block.

Original entry on oeis.org

1, 1, 3, 29, 961, 110657, 45148929, 66294748161, 355213310611457, 7025248750804353025, 517789725632146766102529, 143350189472963401121415823361, 150053549525040193876302690826321921, 597137918840965720442548744290289324130305, 9075744511279922489436849557317778793074029232129

Offset: 0

Michel Marcus, Mar 25 2016

nonn

David Ellerman, The number of direct-sum decompositions of a finite vector space, arXiv:1603.07619 [math.CO], 2016.
David Ellerman, The Quantum Logic of Direct-Sum Decompositions, arXiv preprint arXiv:1604.01087 [quant-ph], 2016. See Section 7.5.

Cf. A270881, A270882.

Recurrence: a(n) = Sum_{k=0,...,n-1} q-binomial(n-1,k)*q^(n*(n-k))*D_q(k) where D_q(k) is given by A270881 for q = 2 and where the q-binomial for q = 2 is given by A022166. This summation formula is the q-analog of the summation formula for the Bell numbers A000110 when q = 1. - David P. Ellerman, Mar 26 2016

Name edited by David P. Ellerman, Mar 26 2016

a(8)-a(14) from Geoffrey Critzer, May 21 2017

A277346 Maximal coefficient among squares of the polynomials in row n of the triangle of q-binomial coefficients.

Original entry on oeis.org

1, 1, 2, 3, 8, 16, 48, 119, 390, 1070, 3656, 10762, 37834, 116546, 417540, 1330923, 4836452, 15823388, 58130756, 194168612, 719541996, 2444224858, 9121965276, 31422225930, 117959864244, 411141476444, 1551101290792, 5460849893348, 20689450250926, 73474839110524

Offset: 0

Vladimir Reshetnikov, Oct 09 2016

nonn

q-binomial coefficients (a.k.a. Gaussian binomial coefficients) are polynomials in q with integer coefficients.

Vaclav Kotesovec, Table of n, a(n) for n = 0..100
Eric W. Weisstein, q-Binomial Coefficient.
Wikipedia, q-binomial.

Cf. A277218, A022166.

Table[Max[Table[Max[CoefficientList[FunctionExpand[QBinomial[n, k, q]^2], q]], {k, 0, n}]], {n, 0, 30}]

Conjecture: a(n) ~ sqrt(3) * 2^(2*n+2) / (Pi^(3/2) * n^(5/2)). - Vaclav Kotesovec, Jan 07 2023

A280752 Numerators of triangle related to enumeration of minimal 2-covers of a labeled n-set.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 10, 1, 1, 2, 865, 71, 1, 1, 5, 2630, 1427, 181, 1, 1, 3, 163133, 306553, 36667, 145, 1, 1, 7, 3368938, 129115655, 46958822, 43662, 4036, 1

Offset: 1

N. J. A. Sloane, Jan 15 2017

			Triangle begins:
1,
1/3,   1/3,
1/7,   1/2,      1/7,
1/15,  3/5,     10/21,         1/15,
1/31,  2/3,    865/651,       71/186,       1/31,
1/63,  5/7,   2630/651,     1427/651,     181/651,     1/63,
1/127, 3/4, 163133/11811, 306553/15748, 36667/11811, 145/762, 1/127,
...

Octavio A. Agustín-Aquino, Archimedes' quadrature of the parabola and minimal covers, arXiv:1602.05279 [math.CO], 2016.

Cf. A022166, A057963, A280753.

A280753 Denominators of triangle related to enumeration of minimal 2-covers of a labeled n-set.

Original entry on oeis.org

1, 3, 3, 7, 2, 7, 15, 5, 21, 15, 31, 3, 651, 186, 31, 63, 7, 651, 651, 651, 63, 127, 4, 11811, 15748, 11811, 762, 127, 255, 9, 66929, 602361, 602361, 10795, 32385, 255

Offset: 1

N. J. A. Sloane, Jan 15 2017

			Triangle begins:
1,
1/3,   1/3,
1/7,   1/2,      1/7,
1/15,  3/5,     10/21,         1/15,
1/31,  2/3,    865/651,       71/186,       1/31,
1/63,  5/7,   2630/651,     1427/651,     181/651,     1/63,
1/127, 3/4, 163133/11811, 306553/15748, 36667/11811, 145/762, 1/127,
...

Octavio A. Agustín-Aquino, Archimedes' quadrature of the parabola and minimal covers, arXiv:1602.05279 [math.CO], 2016.

Cf. A022166, A057963, A280752.

A308326 The q-analog T(q; n,k) of the triangle A163626 for 0 <= k <= n, for q = 2.

Original entry on oeis.org

1, 1, -1, 1, -4, 3, 1, -13, 33, -21, 1, -40, 270, -546, 315, 1, -121, 2010, -10080, 17955, -9765, 1, -364, 14433, -165270, 707805, -1171800, 615195, 1, -1093, 102123, -2580081, 24421005, -95765355, 151953165, -78129765, 1, -3280, 718140, -39416076, 795752370, -6790268520, 25331269320, -39221142030, 19923090075

Offset: 0

Werner Schulte, May 23 2019

The formulas are given for the general case depending on some fixed integer q. The terms are valid if q = 2.

Special cases: T(0; n,k) = (-1)^k * binomial(n,k) for 0 <= k <= n and T(1; n,k) = A163626(n,k) for 0 <= k <= n.

			If q = 2 the triangle T(2; n,k) starts:
n\k:  0     1      2        3        4         5         6         7
====================================================================
  0:  1
  1:  1    -1
  2:  1    -4      3
  3:  1   -13     33      -21
  4:  1   -40    270     -546      315
  5:  1  -121   2010   -10080    17955     -9765
  6:  1  -364  14433  -165270   707805  -1171800    615195
  7:  1 -1093 102123 -2580081 24421005 -95765355 151953165 -78129765
etc.

Cf. A000007, A007318, A022166, A022167, A139382, A163626.

q = 2; {T(n,k) = if(k<0 || k>n, 0, if(k==0, 1, if(q==1, (k+1) * T(n-1,k) - k * T(n-1,k-1), ((q^(k+1) - 1)/(q - 1)) * T(n-1,k) - ((q^k - 1)/(q - 1)) * T(n-1,k-1))))};
for(n=0, 9, for(k=0, n, print1(T(n,k), ", "))) \\ Werner Schulte, May 26 2019

T(q; n,k) = [k+1]_q * T(q; n-1,k) - [k]_q * T(q; n-1,k-1) for 1 <= k <= n with initial values T(q; n,0) = 1 for n >= 0 and T(q; i,j) = 0 if i < j or j < 0 where [i]_q = (q^i - 1)/(q - 1) for i >= 0.
T(q; n,k) = (1/q^binomial(k+1,2)) * (Sum_{j=0..k} (-1)^j * [k,j]_q * q^binomial(k-j,2) * ([j+1]_q)^n) for 0 <= k <= n and q not equal zero where [m,i]_q are the q-binomials (here A022166 for q = 2) and [i]_q = (q^i - 1)/(q - 1) for i >= 0.
Sum_{k=0..n} T(q; n,k) = A000007(n) for n >= 0.
T(q; n,k)/T(q; k,k) give the q-analogs of the Stirling numbers of the second kind (for q = 2 see A139382, but offset 1).
T(q; n,n) = (-1)^n * Product_{j=1..n} [j]_q for n>=0 with empty product 1 (case n = 0) where [i]_q = (q^i - 1)/(q - 1) for i >= 0.
T(q; n,1) = -[n,1]_(q+1) for n >= 1 where [m,i]_q are the q-binomials (here A022166 for q = 2 and A022167 for q = 3).
G.f. of column k: col(q; t,k) = Sum_{n>=k} T(q; n,k)*t^n = ((-t)^k/(1-t)) * Product_{j=1..k} ([i]_q/(1-[i+1]_q*t)) for k>=0 with empty product 1 (case k=0) and [i]_q = i if q = 1 otherwise (q^i-1)/(q-1) for i>=0.

A316554 Triangle read by rows: number of Boolean functions in n variables, of algebraic degree d, with the property that at least one of their discrete derivatives has degree strictly smaller than d-1 (d-1 is maximum possible degree).

Original entry on oeis.org

0, 3, 0, 7, 7, 0, 15, 35, 15, 0, 31, 1023, 155, 31, 0, 63, 18879, 56079, 651, 63, 0, 127, 2097151, 128373759, 4090543, 2667, 127, 0, 255, 155553791, 8739796397055, 8761037088127, 534190575, 10795, 255, 0, 511, 68719476735, 36818452141739261951, 603282315201970099093503, 36821430371387013247, 137165789295, 43435, 511, 0

Offset: 1

Ana Salagean, Jul 06 2018

Boolean functions in n variables (n bits input, one bit output) are viewed in their algebraic normal form (ANF), i.e., as polynomial functions over F_2 (the finite field of integers modulo 2), of degree at most one in each variable.
The functions are counted up to equivalence: two functions are defined as equivalent if they both have the same degree d and their difference is a polynomial function of degree d-1.
The discrete derivative of f in direction (a_1,...,a_n) is defined as f(x_1+a_1,...,x_n+a_n) - f(x_1,...,x_n); if f has degree d, its derivatives have degree d-1 or less.
We count the functions which have at least one derivative of degree strictly less than d-1.
This is a triangular array, indexed by (n,d), with d=1..n. It is written row by row, starting with n=1.
Note that in the Formula section we denoted by qbinomial(n,k,q) the Gaussian binomial coefficients, or q-binomial coefficients; we use the values for q=2, which are sequence A022166. Both formulae were proven in the reference.

			Table begins:
   0,
   3,     0,
   7,     7,     0,
  15,    35,    15,   0,
  31,  1023,   155,  31,  0,
  63, 18879, 56079, 651, 63, 0,
  ...

Michael De Vlieger, Table of n, a(n) for n = 1..105 (rows 1 <= n <= 14, flattened).
A. Salagean and M. Mandache-Salagean, Counting and characterising functions with "fast points" for differential attacks, Cryptography and Communications 9 (2017), 217-239.
Ana Sălăgean, Ferruh Özbudak, Counting Boolean functions with faster points, Designs, Codes and Cryptography (2020).

Cf. A022166.

Block[{f}, f[n_, k_, m_] := Product[(1 - m^(n - i))/(1 - m^(i + 1)), {i, 0, k - 1}]; Table[Sum[(-1)^(i - 1)*2^(i (i - 1)/2)*f[n, i, 2] (2^Binomial[n - i, k] - 1), {i, n - k}], {n, 9}, {k, n}]] // Flatten (* Michael De Vlieger, Jun 16 2020 *)

qb(n, k, m) = prod(i=0, k-1, (1 - m^(n-i))/(1-m^(i+1)));
T(n, k) = sum(i=1, n-k, (-1)^(i-1)*2^(i*(i-1)/2)*qb(n,i,2)*(2^binomial(n-i,k)-1)); \\ Michel Marcus, Jul 22 2018

T(n,d) = Sum_{i=1..n-d} (-1)^(i-1) 2^(i(i-1)/2) qbinomial(n,i,2) (2^binomial(n-i,d)-1).

Recurrence relation on n, for each fixed d: T(n,d) = Sum_{i=1..(n-d)} qbinomial(n,i,2) (2^binomial(n-i,d) - 1 - T(n-i,d)); T(d,d) = 0.

A338621 Triangle read by rows: A(n, k) is the number of partitions of n with "aft" value k (see comments).

Original entry on oeis.org

1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 3, 2, 2, 4, 3, 2, 2, 4, 5, 2, 2, 2, 4, 6, 7, 1, 2, 2, 4, 6, 9, 6, 1, 2, 2, 4, 6, 10, 11, 7, 2, 2, 4, 6, 10, 13, 14, 5, 2, 2, 4, 6, 10, 14, 19, 15, 5, 2, 2, 4, 6, 10, 14, 21, 22, 17, 3, 2, 2, 4, 6, 10, 14, 22, 27, 29, 17, 2, 2, 2, 4, 6, 10, 14, 22, 29, 36, 33, 17

Offset: 0

Joshua Swanson, Nov 04 2020

The "aft" of an integer partition is the number of cells minus the larger of the number of parts or the largest part. For example, aft(4, 2, 2) = 8-4 = 4 = aft(3, 3, 1, 1).
Columns stabilize to twice the partition numbers: A(n, k) = 2p(n) = A139582(n) if n > 2k.
Row sums are partition numbers A000041.
Maximum value of k in row n is n - ceiling(sqrt(n)) = (n-1) - floor(sqrt(n-1)) = A028391(n-1).

			A(6, 2) = 4 since there are four partitions with 6 cells and aft 2, namely (4, 2), (2, 2, 1, 1), (4, 1, 1), (3, 1, 1, 1).
Triangle starts:
  1;
  1;
  2;
  2, 1;
  2, 2, 1;
  2, 2, 3;
  2, 2, 4, 3;
  2, 2, 4, 5,  2;
  2, 2, 4, 6,  7,  1;
  2, 2, 4, 6,  9,  6,  1;
  2, 2, 4, 6, 10, 11,  7;
  2, 2, 4, 6, 10, 13, 14,  5;
  2, 2, 4, 6, 10, 14, 19, 15,  5;
  2, 2, 4, 6, 10, 14, 21, 22, 17,  3;
  2, 2, 4, 6, 10, 14, 22, 27, 29, 17,  2;
  2, 2, 4, 6, 10, 14, 22, 29, 36, 33, 17,  1;
  2, 2, 4, 6, 10, 14, 22, 30, 41, 45, 39, 15,  1;
  2, 2, 4, 6, 10, 14, 22, 30, 43, 52, 57, 41, 14;
  2, 2, 4, 6, 10, 14, 22, 30, 44, 57, 69, 67, 47, 11;
  2, 2, 4, 6, 10, 14, 22, 30, 44, 59, 76, 85, 81, 46, 9; ...

S. C. Billey, M. Konvalinka, and J. P. Swanson, Asymptotic normality of the major index on standard tableaux, Adv. in Appl. Math. 113 (2020).

S. C. Billey, M. Konvalinka, and J. P. Swanson, Asymptotic normality of the major index on standard tableaux, arXiv:1905.00975 [math.CO], 2019.
FindStat - Combinatorial Statistic Finder, The aft of an integer partition

Cf. A000041, A139582.

CoefficientList[
SeriesCoefficient[
  1 + Sum[If[r == 0, 1, 2] q^(r + 1) Sum[
      q^(2 s) t^s QBinomial[2 s + r, s, q t], {s, 0, 30}], {r, 0,
     30}], {q, 0, 20}], t]

Row(n)={if(n==0, [1], my(v=vector(n)); forpart(p=n, v[1+n-max(#p, p[#p])]++); Vecrev(Polrev(v)))}
{ for(n=1, 15, print(Row(n))) } \\ Andrew Howroyd, Nov 04 2020

G.f.: Sum_{lambda} t^aft(lambda) * q^|lambda| = 1 + Sum_{r >= 0} c_r * q^(r+1) * Sum_{s >= 0} q^(2*s) * t^s * [2*s + r, s]_(q*t) where c_0 = 1, c_r = 2 for r >= 1, and [a, b]_q is a Gaussian binomial coefficient (see A022166).

cp's OEIS Frontend

A385435 Row sums of A385434.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A136097 a(n) = A135951(n) /[(2^(n+1)-1) * 2^(n*(n-1)/2)].

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A156914 Square array T(n, k) = q-binomial(2*n, n, k+1), read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A270883 Row sums of triangle A270882. Number of direct-sum decompositions of an n-dimensional vector space over GF(2) with any given nonzero vector in a block.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A277346 Maximal coefficient among squares of the polynomials in row n of the triangle of q-binomial coefficients.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A280752 Numerators of triangle related to enumeration of minimal 2-covers of a labeled n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

A280753 Denominators of triangle related to enumeration of minimal 2-covers of a labeled n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

A308326 The q-analog T(q; n,k) of the triangle A163626 for 0 <= k <= n, for q = 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A316554 Triangle read by rows: number of Boolean functions in n variables, of algebraic degree d, with the property that at least one of their discrete derivatives has degree strictly smaller than d-1 (d-1 is maximum possible degree).

Views

Author

Keywords