A264082 -id:A264082 - cp's OEIS frontend

A125810 Triangle of q-Bell number coefficients, read by rows that form polynomials in q, giving the eigensequence for the triangle of q-binomial coefficients.

1, 1, 2, 4, 1, 8, 4, 3, 16, 12, 13, 8, 3, 32, 32, 42, 38, 33, 15, 10, 1, 64, 80, 120, 133, 145, 121, 98, 60, 37, 15, 4, 128, 192, 320, 408, 507, 526, 544, 457, 391, 281, 195, 104, 61, 20, 6, 256, 448, 816, 1160, 1585, 1875, 2189, 2259, 2256, 2066, 1819, 1450, 1133, 777, 506, 300, 158, 65, 25, 4

Offset: 0

Paul D. Hanna, Dec 10 2006

Row n evaluated at sample values of q are as follows:
R_n(q=1) = A000110(n) (Bell numbers);
R_n(q=-1) = A080107(n) (fixed points of permutation of SetPartitions);
R_n(q=2) = A125812; R_n(q=3) = A125813; R_n(q=4) = A125814; R_n(q=5) = A125815.
T(n,k) is the number of set partitions of [n] having exactly k inversions. T(5,4)=3: 145|23, 145|2|3, 15|24|3; T(6,6) = 10: 1456|23, 156|234, 156|23|4, 1456|2|3, 146|25|3, 16|245|3, 156|2|34, 16|25|34, 156|2|3|4, 16|25|3|4. - Alois P. Heinz, Apr 03 2016

			Row g.f.s B_q(n) are polynomials in q generated by:
B_q(n) = Sum_{j=0..n-1} B_q(j) * C_q(n-1,j) for n>0 with B_q(0)=1
where the triangle of q-binomial coefficients C_q(n,k) begins:
1;
1, 1;
1, 1 + q, 1;
1, 1 + q + q^2, 1 + q + q^2, 1;
1, 1 + q + q^2 + q^3, 1 + q + 2*q^2 + q^3 + q^4, 1 + q + q^2 + q^3, 1;
The initial q-Bell coefficients in B_q(n) are:
B_q(0) = 1; B_q(1) = 1; B_q(2) = 2;
B_q(3) = 4 + q;
B_q(4) = 8 + 4*q + 3*q^2;
B_q(5) = 16 + 12*q + 13*q^2 + 8*q^3 + 3*q^4;
B_q(6) = 32 + 32*q + 42*q^2 + 38*q^3 + 33*q^4 + 15*q^5 + 10*q^6 + q^7.
Number of terms in row n is given by A125811, which starts:
1,1,1,2,3,5,8,11,15,20,26,32,39,47,56,66,76,87,99,112,126,141,156,...
Triangle begins:
    1;
    1;
    2;
    4,   1;
    8,   4,   3;
   16,  12,  13,    8,    3;
   32,  32,  42,   38,   33,   15,   10,    1;
   64,  80, 120,  133,  145,  121,   98,   60,   37,   15,    4;
  128, 192, 320,  408,  507,  526,  544,  457,  391,  281,  195,  104,   61,  20, 6;
  256, 448, 816, 1160, 1585, 1875, 2189, 2259, 2256, 2066, 1819, 1450, 1133, 777, 506, 300, 158, 65, 25, 4;
  ...

Alois P. Heinz, Rows n = 0..50, flattened
Arvind Ayyer and Naren Sundaravaradan, An area-bounce exchanging bijection on a large subset of Dyck paths, arXiv:2401.14668 [math.CO], 2024. See p. 20.

Cf. A000110 (row sums), A080107, A125811, A125812, A125813, A125814, A125815.

Cf. A264082, A381299.

b:= proc(o, u, t) option remember; expand(
     `if`(u+o=0, 1, `if`(t>0, b(u+o, 0$2), 0)+add(x^(u+j-1)*
        b(o-j, u+j-1, min(2, t+1)), j=`if`(t=0, 1, 1..o))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, Feb 21 2025

QB[n_, q_] := QB[n, q] = Sum[QB[j, q] QBinomial[n-1, j, q], {j, 0, n-1}] // FunctionExpand // Simplify; QB[0, q_]=1; QB[1, q_]=1; Table[ CoefficientList[QB[n, q], q], {n, 0, 9}] // Flatten (* Jean-François Alcover, Feb 29 2016 *)

/* q-Binomial coefficients: */
{C_q(n, k) = if(n

T(n,0) = 2^(n-1) for n>0. G.f. of row n is a polynomial in q, B_q(n), that is generated by the recurrence: B_q(n) = Sum_{j=0..n-1} B_q(j) * C_q(n-1,j) for n>0, with B_q(0)=1. The q-binomial coefficient (also called Gaussian binomial coefficient) is given by: C_q(n,k) = [Product_{i=n-k+1..n} (1-q^i)]/[Product_{j=1..k} (1-q^j)].

Sum_{k>0} k * T(n,k) = A264082(n). - Alois P. Heinz, Apr 03 2016

A240796 Total number of occurrences of the pattern 1<2 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 1, 15, 186, 2330, 31065, 447405, 6979588, 117745668, 2141106795, 41810587775, 873474855726, 19451904450654, 460209050303821, 11531197020389025, 305122289460210120, 8503747639606509128, 249020038061419770783, 7645072502094118876755, 245564189847880300238290

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.
The number that avoid the pattern 1<2  is 2^(n-1).
The total number of occurrences of the pattern 1<2 in all permutations on n elements is (n-1)*(n-1)! (cf. A010027, A001563).

			The 13 preferential arrangements on 3 points and the number of times the pattern 1<2 occurs are:
1<2<3, 3
1<3<2, 2
2<1<3, 2
2<3<1, 1
3<1<2, 1
3<2<1, 0
1=2<3, 2
1=3<2, 1
2=3<1, 0
1<2=3, 2
2<1=3, 1
3<1=2, 0
1=2=3, 0,
for a total of a(3) = 15.

Alois P. Heinz, Table of n, a(n) for n = 1..420

Cf. A000670, A240763, A240796-A240800, A010027, A001563, A264082, A381299.

b:= proc(n, t) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*j*t/2])(b(n-j, t+j))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_, t_] := b[n, t] = If[n == 0, {1, 0}, Sum[Function[{p}, p + {0, p[[1]]*j*t/2}][b[n - j, t + j]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n, 0][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Jun 08 2015, after Alois P. Heinz *)

a(n) ~ n! * n^2 / (8 * (log(2))^(n+1)). - Vaclav Kotesovec, May 03 2015

a(n) = Sum_{k=0..binomial(n,2)} k * A381299(n,k). - Alois P. Heinz, Feb 22 2025

a(8)-a(20) from Alois P. Heinz, Dec 08 2014

A189052 a(n) is the number of inversions in all compositions of n.

Original entry on oeis.org

0, 0, 0, 1, 4, 14, 42, 118, 314, 806, 2010, 4902, 11738, 27686, 64474, 148518, 338906, 767014, 1723354, 3847206, 8539098, 18854950, 41438170, 90682406, 197675994, 429372454, 929582042, 2006430758, 4318579674, 9270965286, 19854281690, 42422744102, 90452806618, 192478164006

Offset: 0

N. J. A. Sloane, Apr 16 2011

Row sums of triangle in A189073.

			a(4)=4. There are eight compositions of 4.  Five of these (the partitions of 4) have no inversions.  The remaining three: 3+1, 2+1+1, 1+2+1 have 1,2,1 inversions respectively. - _Geoffrey Critzer_, Mar 19 2014

Nathaniel Johnston, Table of n, a(n) for n = 0..1000
M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, Inversions in Compositions of Integers, Quaest. Math. 34 (2011), no. 2, 187-202.
Index entries for linear recurrences with constant coefficients, signature (5,-6,-4,8)

Cf. A264082, A271370, A271372.

Cf. A189073.

with(PolynomialTools):n:=33:taypoly:=taylor(x^3*(1-x)/((1+x)*(1-2*x)^3),x=0,n+1):seq(coeff(taypoly,x,m),m=0..n); # Nathaniel Johnston, Apr 17 2011
# second Maple program:
a:= n-> `if`(n=0, 0, (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>,
             <8|-4|-6|5>>^n. <<-1/8, 0, 0, 1>>)[1, 1]):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 04 2016

nn=30;CoefficientList[Series[(1-x)*x^3/((1+x)*(1-x-x)^3),{x,0,nn}],x] (* Geoffrey Critzer, Mar 19 2014 *)
LinearRecurrence[{5,-6,-4,8},{0,0,0,1,4},40] (* Harvey P. Dale, May 25 2016 *)

A189052(n)=2^(n-1)*(1/24*(n+2)*(n+1)-5/36*(n+1)-5/108)-2/27*(-1)^n;
vector(33,n,A189052(n)) /* show terms */ /* Joerg Arndt, Apr 16 2011 */

a(n) = 2^(n-1)*(1/24*(n+2)*(n+1)-5/36*(n+1)-5/108)-2/27*(-1)^n for n>0.
a(n) = +5*a(n-1) -6*a(n-2) -4*a(n-3) +8*a(n-4).
G.f.: x^3*(1-x)/((1+x)*(1-2*x)^3).

A271370 Total number of inversions in all partitions of n.

Original entry on oeis.org

0, 0, 0, 1, 3, 9, 18, 38, 68, 120, 200, 326, 508, 785, 1179, 1741, 2532, 3633, 5141, 7199, 9972, 13680, 18618, 25116, 33642, 44738, 59139, 77653, 101444, 131751, 170320, 219049, 280553, 357652, 454254, 574507, 724135, 909265, 1138169, 1419737, 1765884, 2189441

Offset: 0

Alois P. Heinz, Apr 05 2016

nonn

			a(3) = 1: one inversion in 21.
a(4) = 3: one inversion in 31, and two inversions in 211.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Inversion (discrete mathematics)
Wikipedia, Partition (number theory)

Cf. A000041, A189052, A264033, A264082, A271371.

b:= proc(n, i, t) option remember; `if`(n=0, [1, 0], `if`(i<1, 0,
      add((p-> p+[0, p[1]*j*t])(b(n-i*j, i-1, t+j)), j=0..n/i)))
    end:
a:= n-> b(n$2, 0)[2]:
seq(a(n), n=0..60);

b[n_, i_, t_] := b[n, i, t] = If[n==0, {1, 0}, If[i<1, 0, Sum[Function[p, If[p === 0, 0, p+{0, p[[1]]*j*t}]][b[n-i*j, i-1, t+j]], {j, 0, n/i}]]];
a[n_] := b[n, n, 0][[2]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Feb 03 2017, translated from Maple *)

a(n) = Sum_{k>0} k * A264033(n,k).

cp's OEIS Frontend

A125810 Triangle of q-Bell number coefficients, read by rows that form polynomials in q, giving the eigensequence for the triangle of q-binomial coefficients.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A240796 Total number of occurrences of the pattern 1<2 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A189052 a(n) is the number of inversions in all compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A271370 Total number of inversions in all partitions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula