A006095 -id:A006095 - cp's OEIS frontend

A369802 Inversion count of the Eytzinger array layout of n elements.

0, 0, 1, 1, 4, 6, 7, 7, 14, 20, 25, 29, 32, 34, 35, 35, 50, 64, 77, 89, 100, 110, 119, 127, 134, 140, 145, 149, 152, 154, 155, 155, 186, 216, 245, 273, 300, 326, 351, 375, 398, 420, 441, 461, 480, 498, 515, 531, 546, 560, 573, 585, 596, 606, 615, 623, 630

Offset: 0

Darío Clavijo, Feb 01 2024

nonn

The Eytzinger array layout (A375825) arranges elements so that a binary search can be performed starting at element k=1 and at a given k step to 2*k or 2*k+1 according as the target is smaller or larger than the element at k.

This layout is a permutation of the elements and its inversion count (number of swaps needed to sort by the bubble sort algorithm) is a measure of how much it differs from an ordinary sorted array.

			For n=5, the Eytzinger array layout is {4, 2, 5, 1, 3} and it contains a(5) = 6 element pairs which are not in ascending order (out of 10 element pairs altogether).

Sergey Slotin, Eytzinger binary search

Cf. A006095, A261692, A375825.

from sympy.combinatorics.permutations import Permutation
def a(n):
  def eytzinger(t, k=1, i=0):
    if (k < len(t)):
      i = eytzinger(t, k * 2, i)
      t[k] = i
      i += 1
      i = eytzinger(t, k * 2 + 1, i)
    return i
  t = [0] * (n+1)
  eytzinger(t)
  return Permutation(t[1:]).inversions()
print([a(n) for n in range(0, 58)])

a(2^n-1) = A006095(n).

Conjecture: a(n) = (A261692(n)-n)/2.

A006103 Gaussian binomial coefficient [ 2n,n ] for q=3.

Original entry on oeis.org

1, 4, 130, 33880, 75913222, 1506472167928, 267598665689058580, 427028776969176679964080, 6129263888495201102915629695046, 791614563787525746761491781638123230424, 920094266641283414155073889843358388073398779900

Offset: 0

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

T. D. Noe, Table of n, a(n) for n = 0..25
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

Cf. A022167.

q:=3; [n le 0 select 1 else (&*[(1-q^(2*n-j))/(1-q^(j+1)): j in [0..n-1]]): n in [0..15]]; // G. C. Greubel, Mar 09 2019

Table[QBinomial[2n, n, 3], {n, 0, 10}] (* Vladimir Reshetnikov, Sep 12 2016 *)

q=3; {a(n) = prod(j=0, n-1, (1-q^(2*n-j))/(1-q^(j+1))) };
vector(15, n, n--; a(n)) \\ G. C. Greubel, Mar 09 2019

[gaussian_binomial(2*n,n,3) for n in (0..15)] # G. C. Greubel, Mar 09 2019

a(n) = Sum_{k=0..n} 3^(k^2)*(A022167(n,k))^2. - Werner Schulte, Mar 09 2019

A006104 Gaussian binomial coefficient [ n,n/2 ] for q=3.

Original entry on oeis.org

1, 1, 4, 13, 130, 1210, 33880, 925771, 75913222, 6174066262, 1506472167928, 366573514642546, 267598665689058580, 195168545232713290660, 427028776969176679964080, 934054234760012359481199283, 6129263888495201102915629695046

Offset: 0

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

T. D. Noe, Table of n, a(n) for n=0..50
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

Table[QBinomial[n,Floor[n/2],3],{n,0,20}] (* Harvey P. Dale, Nov 11 2011 *)

More terms from Harvey P. Dale, Nov 11 2011

A006107 Gaussian binomial coefficient [ n,4 ] for q = 4.

Original entry on oeis.org

1, 341, 93093, 24208613, 6221613541, 1594283908581, 408235958349285, 104514759495347685, 26756185103024942565, 6849609413493939400165, 1753501675591663698472421, 448896535558672700374937061, 114917519925881846404167134693

Offset: 4

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 4..200
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

r:=4; q:=4; [&*[(1-q^(n-i+1))/(1-q^i): i in [1..r]]: n in [r..20]]; // Vincenzo Librandi, Aug 07 2016

seq((4^n-64)*(4^n-16)*(4^n-4)*(4^n-1)/2961100800, n=4..30); # Robert Israel, Feb 01 2018

Table[QBinomial[n, 4, 4], {n, 4, 20}] (* Vincenzo Librandi, Aug 07 2016 *)

[gaussian_binomial(n,4,4) for n in range(4,14)] # Zerinvary Lajos, May 27 2009

G.f.: x^4/((1-x)*(1-4*x)*(1-16*x)*(1-64*x)*(1-256*x)). - Vincenzo Librandi, Aug 07 2016
a(n) = Product_{i=1..4} (4^(n-i+1)-1)/(4^i-1), by definition. - Vincenzo Librandi, Aug 07 2016
a(n) = (4^n-64)*(4^n-16)*(4^n-4)*(4^n-1)/2961100800. - Robert Israel, Feb 01 2018

A006109 Gaussian binomial coefficient [ n,n/2 ] for q=4.

Original entry on oeis.org

1, 1, 5, 21, 357, 5797, 376805, 24208613, 6221613541, 1594283908581, 1634141006295525, 1673768626404966885, 6857430062381149327845, 28089747579101385828291045, 460250514083576206796548772325, 7540859480106603961931048583270885

Offset: 0

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 0..80
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

Table[QBinomial[n, Floor[n/2], 4], {n, 0, 20}] (* Vincenzo Librandi, Aug 13 2016 *)

A006113 Gaussian binomial coefficient [ n,4 ] for q = 5.

Original entry on oeis.org

1, 781, 508431, 320327931, 200525284806, 125368356709806, 78360229974772306, 48975769621072897306, 30609934249224268600431, 19131218685276848401412931, 11957012900737114492991256681, 7473133215765585192791624069181, 4670708278954101902438990598678556

Offset: 4

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 4..200
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

r:=4; q:=5; [&*[(1-q^(n-i+1))/(1-q^i): i in [1..r]]: n in [r..20]]; // Vincenzo Librandi, Aug 07 2016

qBinom := proc(n,m,q)
        mul( (1-q^(n-i))/(1-q^(i+1)),i=0..m-1) ;
end proc:
A006113 := proc(n)
        qBinom(n,4,5) ;
end proc:
seq(A006113(n),n=4..16) ; # R. J. Mathar, Sep 28 2011

Table[QBinomial[n, 4, 5], {n, 4, 20}] (* Vincenzo Librandi, Aug 07 2016 *)

[gaussian_binomial(n,4,5) for n in range(4,14)] # Zerinvary Lajos, May 27 2009

G.f.: x^4/((1-x)*(1-5*x)*(1-25*x)*(1-125*x)*(1-625*x)). - Vincenzo Librandi, Aug 07 2016

a(n) = Product_{i=1..4} (5^(n-i+1)-1)/(5^i-1), by definition. - Vincenzo Librandi, Aug 06 2016

A006114 Gaussian binomial coefficient [ 2n,n ] for q=5.

Original entry on oeis.org

1, 6, 806, 2558556, 200525284806, 391901483074853556, 19138263752352528498478556, 23362736428829868448189697999416056, 712977784594148279816735342927316866304884806, 543959438081999965602054955428186322207689611643379103556

Offset: 0

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Robert Israel, Table of n, a(n) for n = 0..36
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)
Index entries related to Gaussian binomial coefficients

with(QDifferenceEquations):
seq(eval(QSimpComb(QBinomial(2*n,n,q)),q=5), n=0..12); # Robert Israel, Feb 01 2018

Table[QBinomial[2n,n,5],{n,0,10}] (* Harvey P. Dale, Jun 10 2018 *)

A006115 Gaussian binomial coefficient [ n,n/2 ] for q=5.

Original entry on oeis.org

1, 1, 6, 31, 806, 20306, 2558556, 320327931, 200525284806, 125368356709806, 391901483074853556, 1224770494838892134806, 19138263752352528498478556

Offset: 0

N. J. A. Sloane

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Vincenzo Librandi, Table of n, a(n) for n = 0..75
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)

Table[QBinomial[n, Floor[n/2], 5], {n, 0, 20}] (* Vincenzo Librandi, Aug 13 2016 *)

A130324 A059268^2.

Original entry on oeis.org

1, 3, 4, 7, 12, 16, 15, 28, 48, 64, 31, 60, 112, 192, 256, 63, 124, 240, 448, 768, 1024, 127, 252, 496, 960, 1792, 3072, 4096, 255, 508, 1008, 1984, 3840, 7168, 12288, 16384, 511, 1020, 2032, 4032, 7936, 15360, 28672, 49152, 65536

Offset: 0

Gary W. Adamson, May 24 2007

Row sums = A006095: (1, 7, 35, 155, 651, 2667, ...).

			First few rows of the triangle:
   1;
   3,   4;
   7,  12,  16;
  15,  28,  48,  64;
  31,  60, 112, 192, 256;
  63, 124, 240, 448, 768, 1024;
  ...

Cf. A059268, A006095.

A059268^2 as an infinite lower triangular matrix, where A059268 = (1; 1,2; 1,2,4; ...).

A130329 A059268 * A130321.

Original entry on oeis.org

1, 5, 2, 21, 10, 4, 85, 42, 20, 8, 341, 170, 84, 40, 16, 1365, 682, 340, 168, 80, 32, 5461, 2730, 1364, 680, 336, 160, 64, 21845, 10922, 5460, 2728, 1360, 672, 320, 128, 87381, 43690, 21844, 10920, 5456, 2720, 1344, 640, 256

Offset: 0

Gary W. Adamson, May 24 2007

Row sums = A006095: (1, 7, 35, 155, 651, 2667, ...).
Left border = A002450: (1, 5, 21, 85, 341, 1365, ...).
A130328 = A130321 * A059268.

			First few rows of the triangle:
    1;
    5,   2;
   21,  10,  4;
   85,  42, 20,  8;
  341, 170, 84, 40, 16;
  ...

Cf. A059268, A130321, A006095, A002450, A130328.

A059268 * A130321 as infinite lower triangular matrices.

cp's OEIS Frontend

A369802 Inversion count of the Eytzinger array layout of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A006103 Gaussian binomial coefficient [ 2n,n ] for q=3.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A006104 Gaussian binomial coefficient [ n,n/2 ] for q=3.

Views

Author

Keywords

References

Links

Programs

Mathematica

Extensions

A006107 Gaussian binomial coefficient [ n,4 ] for q = 4.

Views

Author

Keywords

References

Links

Programs

Magma

Maple

Mathematica

Sage

Formula

A006109 Gaussian binomial coefficient [ n,n/2 ] for q=4.

Views

Author

Keywords

References

Links

Programs

Mathematica

A006113 Gaussian binomial coefficient [ n,4 ] for q = 5.

Views

Author

Keywords

References

Links

Programs

Magma

Maple

Mathematica

Sage

Formula

A006114 Gaussian binomial coefficient [ 2n,n ] for q=5.

Views

Author

Keywords

References

Links

Programs

Maple

Mathematica

A006115 Gaussian binomial coefficient [ n,n/2 ] for q=5.

Views

Author

Keywords

References