A125811 -id:A125811 - cp's OEIS frontend

A260670 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the generalized pattern 23-1; triangle T(n,k), n>=0, 0<=k<=A125811(n)-1, read by rows.

1, 1, 2, 5, 1, 15, 6, 3, 52, 32, 23, 10, 3, 203, 171, 152, 98, 62, 22, 11, 1, 877, 944, 984, 791, 624, 392, 240, 111, 55, 18, 4, 4140, 5444, 6460, 6082, 5513, 4302, 3328, 2141, 1393, 780, 432, 187, 88, 24, 6, 21147, 32919, 43626, 46508, 46880, 41979, 36774

Offset: 0

Alois P. Heinz, Nov 14 2015

Patterns 1-32, 3-12, 21-3 give the same sequence.

			T(3,1) = 1: 231.
T(4,1) = 6: 1342, 2314, 2413, 2431, 3241, 4231.
T(4,2) = 3: 2341, 3412, 3421.
T(5,2) = 23: 13452, 14523, 14532, 23415, 23514, 23541, 24351, 25341, 32451, 34125, 34152, 34215, 35124, 35142, 35214, 35412, 35421, 42351, 43512, 43521, 52341, 53412, 53421.
T(5,3) = 10: 23451, 24513, 24531, 34251, 35241, 45123, 45132, 45213, 45312, 45321.
T(5,4) = 3: 34512, 34521, 45231.
Triangle T(n,k) begins:
0 :   1;
1 :   1;
2 :   2;
3 :   5,   1;
4 :  15,   6,   3;
5 :  52,  32,  23,  10,   3;
6 : 203, 171, 152,  98,  62,  22,  11,   1;
7 : 877, 944, 984, 791, 624, 392, 240, 111, 55, 18, 4;

Alois P. Heinz, Rows n = 0..50, flattened
A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, arXiv:math/0110036 [math.CO], 2001

Columns k=0-10 give: A000110, A264460, A264461, A264462, A264463, A264464, A264465, A264466, A264467, A264468, A264469.
Row sums give A000142.
Cf. A001754, A125811, A260665, A263776.

b:= proc(u, o) option remember;
     `if`(u+o=0, 1, add(b(u-j, o+j-1), j=1..u)+
       add(expand(b(u+j-1, o-j)*x^u), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n,0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[u-j, o+j-1], {j, 1, u}] + Sum[Expand[b[u+j-1, o-j]*x^u], {j, 1, o}]]; T[n_] := Function[p, Table[ Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 16 2017, after Alois P. Heinz *)

Sum_{k>0} k * T(n,k) = A001754(n).

A381529 T(n,k) is the number of permutations of [n] having exactly k pairs of integers i=0, 0<=k<=A125811(n)-1, read by rows.

Original entry on oeis.org

1, 1, 2, 5, 1, 15, 5, 4, 54, 21, 24, 16, 5, 235, 89, 118, 112, 101, 35, 28, 2, 1237, 408, 577, 633, 719, 585, 402, 239, 167, 59, 14, 7790, 2106, 3023, 3529, 4410, 4463, 4600, 3012, 2789, 1933, 1438, 629, 442, 122, 34, 57581, 12529, 17693, 20980, 27208, 30064, 35359, 33332, 28137, 24970, 22850, 17148, 14272, 8645, 5639, 3684, 1809, 664, 282, 34

Offset: 0

Alois P. Heinz, Feb 26 2025

			T(4,0) = 15: (1)(2)(3)(4), (1,2)(3)(4), (1)(2,3)(4), (1)(2)(3,4), (1,2)(3,4), (1,2,3)(4), (1,3,2)(4), (1)(2,3,4), (1)(2,4,3), (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2).
T(4,1) = 5: (1)(2,4)(3), (1,2,4)(3), (1,4,2)(3), (1,3)(2)(4), (1,3)(2,4).
T(4,2) = 4: (1,4)(2)(3), (1,4)(2,3), (1,3,4)(2), (1,4,3)(2).
Triangle T(n,k) begins:
     1;
     1;
     2;
     5,   1;
    15,   5,   4;
    54,  21,  24,  16,   5;
   235,  89, 118, 112, 101,  35,  28,   2;
  1237, 408, 577, 633, 719, 585, 402, 239, 167, 59, 14;
  ...

Alois P. Heinz, Rows n = 0..55, flattened
Wikipedia, Inversion
Wikipedia, Permutation

Columns k=0-1 give: A051295, A381539.
Row sums give A000142.
Row lengths give A125811.
Last elements of rows give A381531.
Main diagonal gives A381545.
Cf. A008302, A125810 (similar for set partitions), A126673, A381299 (similar for ordered set partitions).

b:= proc(o, u, t) option remember; expand(`if`(u+o=0, max(0, t-1)!,
     `if`(t>0, b(u+o, 0$2)*(t-1)!, 0)+add(x^(u+j-1)*
        b(o-j, u+j-1, 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);

Sum_{k>=1} k * T(n,k) = A126673(n)/2.

A080107 Number of fixed points of permutation of SetPartitions under {1,2,...,n}->{n,n-1,...,1}. Number of symmetric arrangements of non-attacking rooks on upper half of n X n chessboard.

Original entry on oeis.org

1, 1, 2, 3, 7, 12, 31, 59, 164, 339, 999, 2210, 6841, 16033, 51790, 127643, 428131, 1103372, 3827967, 10269643, 36738144, 102225363, 376118747, 1082190554, 4086419601, 12126858113, 46910207114, 143268057587, 566845074703, 1778283994284, 7186474088735

Offset: 0

Wouter Meeussen, Mar 15 2003

nonn

Even-numbered terms a(2k) are A002872: 2,7,31,164,999 ("Sorting numbers"); odd-numbered terms are its binomial transform, A080337. The symmetrical set partitions of {-n,...,-1,0,1,...,n} can be classified by the partition containing 0. Thus we get the sum over k of {n choose k} times the number of symmetrical set partitions of 2n-2k elements. - Don Knuth, Nov 23 2003
Number of partitions of n numbers that are symmetrical and cannot be nested (i.e., include a pattern of the form abab). - Douglas Boffey, May 21 2015
Number of achiral color patterns in a row or loop of length n. Two color patterns are equivalent if the colors are permuted. - Robert A. Russell, Apr 23 2018
Also the number of self-complementary set partitions of {1, ..., n}. The complement of a set partition pi of {1, ..., n} is defined as n + 1 - pi (elementwise) on page 3 of Callan. For example, the complement of {{1,5},{2},{3,6},{4}} is {{1,4},{2,6},{3},{5}}. - Gus Wiseman, Feb 13 2019

			Of the set partitions of 4, the following 7 are invariant under 1->4, 2->3, 3->2, 4->1: {{1,2,3,4}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,3},{2,4}}, {{1},{2,3},{4}}, {{1,4},{2},{3}}, {{1},{2},{3},{4}}, so a(4)=7.
For a(4)=7, the row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD (same as previous example).  The loop patterns are AAAA, AAAB, AABB, AABC, ABAB, ABAC, and ABCD. - _Robert A. Russell_, Apr 23 2018
From _Gus Wiseman_, Feb 13 2019: (Start)
The a(1) = 1 through a(5) = 12 self-complementary set partitions:
  {{1}}  {{12}}    {{123}}      {{1234}}        {{12345}}
         {{1}{2}}  {{13}{2}}    {{12}{34}}      {{1245}{3}}
                   {{1}{2}{3}}  {{13}{24}}      {{135}{24}}
                                {{14}{23}}      {{15}{234}}
                                {{1}{23}{4}}    {{1}{234}{5}}
                                {{14}{2}{3}}    {{12}{3}{45}}
                                {{1}{2}{3}{4}}  {{135}{2}{4}}
                                                {{14}{25}{3}}
                                                {{15}{24}{3}}
                                                {{1}{24}{3}{5}}
                                                {{15}{2}{3}{4}}
                                                {{1}{2}{3}{4}{5}}
(End)

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See p. 18.
David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.
S. V. Pemmaraju and S. S. Skiena, The New Combinatorica, 2001.
Frank Ruskey, Set Partitions

Cf. A002872, A080337.
Cf. A125810. - Paul D. Hanna, Jan 19 2009
Cf. A000126, A000296, A124323, A169985, A324012, A324013, A324014.

< Range[n, 1, -1]]; t= 1 + RankSetPartition /@ t; t= ToCycles[t]; t= Cases[t, {_Integer}]; Length[t], {n, 7}]
(* second program: *)
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[cc = CoefficientList[QB[n, q], q]; cc.Table[(-1)^(k+1), {k, 1, Length[cc]}], {n, 0, 30}] (* Jean-François Alcover, Feb 29 2016, after Paul D. Hanna *)
(* Ach[n, k] is the number of achiral color patterns for a row or loop of n
  colors containing exactly k different colors *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],
  k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]]
Table[Sum[Ach[n, k], {k, 0, n}], {n, 0, 30}] (* Robert A. Russell, Apr 23 2018 *)
x[n_] := x[n] = If[n < 2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
Table[Sum[StirlingS2[Ceiling[n/2], k] x[k-Mod[n, 2]], {k, 0, Ceiling[n/2]}],
  {n, 0, 30}] (* Robert A. Russell, Apr 27 2018, after Knuth reference *)

Knuth gives recurrences and generating functions.
a(n) = Sum_{k=0..t(n)} (-1)^k*A125810(n,k) where A125810 is a triangle of coefficients for a q-analog of the Bell numbers and t(n)=A125811(n)-1. - Paul D. Hanna, Jan 19 2009
From Robert A. Russell, Apr 23 2018: (Start)
a(n) = Sum_{k=0..n} Ach(n,k) where
  Ach(n,k) = [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)) + [n<2]*[n==k]*[n>=0].
a(n) = 2*A103293(n+1) - A000110(n). (End)
a(n) = [n==0 mod 2]*Sum_{k=0..n/2} Stirling2(n/2, k)*A005425(k) + [n==1 mod 2] * Sum_{k=1..(n+1)/2} Stirling2((n+1)/2, k) * A005425(k-1). (from Knuth reference)
a(n) = 2*A084708(n) - A084423(n). - Robert A. Russell, Apr 27 2018

Offset set to 0 by Alois P. Heinz, May 23 2015

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.

Original entry on oeis.org

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

A125812 q-Bell numbers for q=2; eigensequence of A022166, which is the triangle of Gaussian binomial coefficients [n,k] for q=2.

Original entry on oeis.org

1, 1, 2, 6, 28, 204, 2344, 43160, 1291952, 63647664, 5218320672, 719221578080, 168115994031040, 67159892835119296, 46166133463916209792, 54941957091151982047616, 113826217192695041078973184, 412563248965919999955196308224, 2627807814905396804499456018866688

Offset: 0

Paul D. Hanna, Dec 10 2006

nonn

			The recurrence a(n) = Sum_{k=0..n-1} A022166(n-1,k) * a(k) is illustrated by:
a(2) = 1*(1) + 3*(1) + 1*(2) = 6;
a(3) = 1*(1) + 7*(1) + 7*(2) + 1*(6) = 28;
a(4) = 1*(1) + 15*(1) + 35*(2) + 15*(6) + 1*(28) = 204.
Triangle A022166 begins:
1;
1, 1;
1, 3, 1;
1, 7, 7, 1;
1, 15, 35, 15, 1;
1, 31, 155, 155, 31, 1;
1, 63, 651, 1395, 651, 63, 1; ...

Alois P. Heinz, Table of n, a(n) for n = 0..90

Cf. A022166, A125810, A125811, A125813, A125814, A125815.

Column k=2 of A381369.

b:= proc(o, u, t) option remember;
     `if`(u+o=0, 1, `if`(t>0, b(u+o, 0$2), 0)+add(2^(u+j-1)*
        b(o-j, u+j-1, min(2, t+1)), j=`if`(t=0, 1, 1..o)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 21 2025

a[0] = 1; a[n_] := a[n] = Sum[QBinomial[n-1, k, 2] a[k], {k, 0, n-1}]; Table[a[n], {n, 0, 16}] (* Jean-François Alcover, Apr 09 2016 *)

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

a(n) = Sum_{k=0..n-1} A022166(n-1,k) * a(k) for n>0, with a(0)=1.

a(n) = Sum_{k>=0} 2^k * A125810(n,k). - Alois P. Heinz, Feb 21 2025

A125813 q-Bell numbers for q=3; eigensequence of A022167, which is the triangle of Gaussian binomial coefficients [n,k] for q=3.

Original entry on oeis.org

1, 1, 2, 7, 47, 628, 17327, 1022983, 132615812, 38522717107, 25526768401271, 39190247441314450, 141213238745969102393, 1207367655155905204747681, 24733467452839301566047854678, 1224709126636123500201799360630423, 147747406166666863538672620806542995763

Offset: 0

Paul D. Hanna, Dec 10 2006

nonn

			The recurrence: a(n) = Sum_{k=0..n-1} A022167(n-1,k) * a(k) is illustrated by:
  a(2) = 1*(1) + 4*(1) + 1*(2) = 7;
  a(3) = 1*(1) + 13*(1) + 13*(2) + 1*(7) = 47;
  a(4) = 1*(1) + 40*(1) + 130*(2) + 40*(7) + 1*(47) = 628.
Triangle A022167 begins:
  1;
  1, 1;
  1, 4, 1;
  1, 13, 13, 1;
  1, 40, 130, 40, 1;
  1, 121, 1210, 1210, 121, 1;
  1, 364, 11011, 33880, 11011, 364, 1;
  ...

Alois P. Heinz, Table of n, a(n) for n = 0..72

Cf. A022167, A125810, A125811, A125812, A125814, A125815.

Column k=3 of A381369.

b:= proc(o, u, t) option remember;
     `if`(u+o=0, 1, `if`(t>0, b(u+o, 0$2), 0)+add(3^(u+j-1)*
        b(o-j, u+j-1, min(2, t+1)), j=`if`(t=0, 1, 1..o)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 21 2025

b[o_, u_, t_] := b[o, u, t] =
   If[u + o == 0, 1, If[t > 0, b[u + o, 0, 0], 0] + Sum[3^(u + j - 1)*
   b[o - j, u + j - 1, Min[2, t + 1]], {j, If[t == 0, {1}, Range[o]]}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Mar 15 2025, after Alois P. Heinz *)

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

a(n) = Sum_{k=0..n-1} A022167(n-1,k) * a(k) for n>0, with a(0)=1.

a(n) = Sum_{k>=0} 3^k * A125810(n,k). - Alois P. Heinz, Feb 21 2025

A125815 q-Bell numbers for q=5; eigensequence of A022169, which is the triangle of Gaussian binomial coefficients [n,k] for q=5.

Original entry on oeis.org

1, 1, 2, 9, 103, 3276, 307867, 89520089, 83657942588, 258923776689771, 2717711483011792407, 98702105953049319472394, 12629828399521800714941435773, 5784963467206342855747483263957541, 9613516698678314330032600987632336641122, 58637855728567773833514895771659795097103477549

Offset: 0

Paul D. Hanna, Dec 10 2006

nonn

			The recurrence: a(n) = Sum_{k=0..n-1} A022169(n-1,k) * a(k)
is illustrated by:
a(2) = 1*(1) + 6*(1) + 1*(2) = 9;
a(3) = 1*(1) + 31*(1) + 31*(2) + 1*(9) = 103;
a(4) = 1*(1) + 156*(1) + 806*(2) + 156*(9) + 1*(103) = 3276.
Triangle A022169 begins:
  1;
  1,    1;
  1,    6,      1;
  1,   31,     31,       1;
  1,  156,    806,     156,      1;
  1,  781,  20306,   20306,    781,    1;
  1, 3906, 508431, 2558556, 508431, 3906, 1;
  ...

Alois P. Heinz, Table of n, a(n) for n = 0..60

Cf. A022169, A125810, A125811, A125812, A125813, A125814.

Column k=5 of A381369.

b:= proc(o, u, t) option remember;
     `if`(u+o=0, 1, `if`(t>0, b(u+o, 0$2), 0)+add(5^(u+j-1)*
        b(o-j, u+j-1, min(2, t+1)), j=`if`(t=0, 1, 1..o)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 21 2025

b[o_, u_, t_] := b[o, u, t] =
   If[u + o == 0, 1, If[t > 0, b[u + o, 0, 0], 0] + Sum[5^(u + j - 1)*
   b[o - j, u + j - 1, Min[2, t + 1]], {j, If[t == 0, {1}, Range[o]]}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Mar 15 2025, after Alois P. Heinz *)

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

a(n) = Sum_{k=0..n-1} A022169(n-1,k) * a(k) for n>0, with a(0)=1.

a(n) = Sum_{k>=0} 5^k * A125810(n,k). - Alois P. Heinz, Feb 21 2025

A125814 q-Bell numbers for q=4; eigensequence of A022168, which is the triangle of Gaussian binomial coefficients [n,k] for q=4.

Original entry on oeis.org

1, 1, 2, 8, 72, 1552, 84416, 12107584, 4726583424, 5150624868864, 16010990175691264, 144648776120641766400, 3857411545088966609514496, 307705704204270334224705015808, 74294186209325019487040708053442560, 54874536782175258883045772243829235417088

Offset: 0

Paul D. Hanna, Dec 10 2006

nonn

			The recurrence: a(n) = Sum_{k=0..n-1} A022168(n-1,k) * a(k) is illustrated by:
  a(2) = 1*(1) + 5*(1) + 1*(2) = 8;
  a(3) = 1*(1) + 21*(1) + 21*(2) + 1*(8) = 72;
  a(4) = 1*(1) + 85*(1) + 357*(2) + 85*(8) + 1*(72) = 1552.
Triangle A022168 begins:
  1;
  1,    1;
  1,    5,     1;
  1,   21,    21,      1;
  1,   85,   357,     85,     1;
  1,  341,  5797,   5797,   341,    1;
  1, 1365, 93093, 376805, 93093, 1365, 1;
  ...

Alois P. Heinz, Table of n, a(n) for n = 0..65

Cf. A022168, A125810, A125811, A125812, A125813, A125815.

Column k=4 of A381369.

b:= proc(o, u, t) option remember;
     `if`(u+o=0, 1, `if`(t>0, b(u+o, 0$2), 0)+add(4^(u+j-1)*
        b(o-j, u+j-1, min(2, t+1)), j=`if`(t=0, 1, 1..o)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 21 2025

b[o_, u_, t_] := b[o, u, t] =
   If[u + o == 0, 1, If[t > 0, b[u + o, 0, 0], 0] + Sum[4^(u + j - 1)*
   b[o - j, u + j - 1, Min[2, t + 1]], {j, If[t == 0, {1}, Range[o]]}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Mar 15 2025, after Alois P. Heinz *)

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

a(n) = Sum_{k=0..n-1} A022168(n-1,k) * a(k) for n>0, with a(0)=1.

a(n) = Sum_{k>=0} 4^k * A125810(n,k). - Alois P. Heinz, Feb 21 2025

A381531 Number of permutations of [n] having the maximal possible number of pairs of integers i

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 2, 14, 34, 34, 12, 132, 540, 1020, 888, 288, 4608, 28800, 89280, 143712, 113472, 34560, 760320, 6773760, 31449600, 81527040, 117089280, 85847040, 24883200, 721612800, 8709120000, 56783462400, 217205452800, 495200563200, 651939840000, 450584985600, 125411328000

Offset: 0

Alois P. Heinz, Feb 26 2025

nonn

The sequence has local minima at positions n in { A000217 }. The values at these positions are superfactorials (A000178).

			a(4) = 4: (1,4)(2)(3), (1,4)(2,3), (1,3,4)(2), (1,4,3)(2) with 2 pairs each.
a(6) = 2: (1,5,6)(2,4)(3), (1,6,5)(2,4)(3) with 7 pairs each.

Alois P. Heinz, Table of n, a(n) for n = 0..406
Wikipedia, Inversion
Wikipedia, Permutation

Cf. A000178, A000217, A125811, A381529.

b:= proc(o, u, t) option remember; (p-> (d-> coeff(p, x, d)
      *x^d)(degree(p)))(expand(`if`(u+o=0, max(0, t-1)!,
      `if`(t>0, b(u+o, 0$2)*(t-1)!, 0)+add(x^(u+j-1)*
        b(o-j, u+j-1, t+1), j=`if`(t=0, 1, 1..o)))))
    end:
a:= n-> coeffs(b(n, 0$2)):
seq(a(n), n=0..36);

a(n) = A381529(n,A125811(n)-1).

a(A000217(n)) = A000178(n-1) for n>=1.

cp's OEIS Frontend

A260670 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the generalized pattern 23-1; triangle T(n,k), n>=0, 0<=k<=A125811(n)-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A381529 T(n,k) is the number of permutations of [n] having exactly k pairs of integers i=0, 0<=k<=A125811(n)-1, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A080107 Number of fixed points of permutation of SetPartitions under {1,2,...,n}->{n,n-1,...,1}. Number of symmetric arrangements of non-attacking rooks on upper half of n X n chessboard.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A125812 q-Bell numbers for q=2; eigensequence of A022166, which is the triangle of Gaussian binomial coefficients [n,k] for q=2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A125813 q-Bell numbers for q=3; eigensequence of A022167, which is the triangle of Gaussian binomial coefficients [n,k] for q=3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A125815 q-Bell numbers for q=5; eigensequence of A022169, which is the triangle of Gaussian binomial coefficients [n,k] for q=5.

Views

Author

Keywords

Examples

Links

Crossrefs