A182222 -id:A182222 - cp's OEIS frontend

A001189 Number of degree-n permutations of order exactly 2.

0, 1, 3, 9, 25, 75, 231, 763, 2619, 9495, 35695, 140151, 568503, 2390479, 10349535, 46206735, 211799311, 997313823, 4809701439, 23758664095, 119952692895, 618884638911, 3257843882623, 17492190577599, 95680443760575, 532985208200575, 3020676745975551

Offset: 1

N. J. A. Sloane

Number of set partitions of [n] into blocks of size 2 and 1 with at least one block of size 2. - Olivier Gérard, Oct 29 2007

For n>=2, number of standard Young tableaux with height <= n - 1. That is, all tableaux (A000085) but the one with just one column. - Joerg Arndt, Oct 24 2012

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..800
N. Chheda, M. K. Gupta, RNA as a Permutation, arXiv:1403.5477 [q-bio.BM], 2014.
R. B. Herrera, The number of elements of given period in finite symmetric group, Amer. Math. Monthly 64, 1957, 488-490.
L. Moser and M. Wyman, On solutions of x^d = 1 in symmetric groups, Canad. J. Math., 7 (1955), 159-168.
J. Rangel-Mondragon, Selected Themes in Computational Non-Euclidean Geometry: Part 1, The Mathematica Journal 15 (2013); http://www.mathematica-journal.com/data/uploads/2013/07/Rangel-Mondragon_Selected-1.pdf
Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
Thotsaporn Thanatipanonda, Inversions and major index for permutations, Math. Mag., April 2004.

Cf. A001470-A001473, A052501, A053496-A053504, A061121-A061128.
Column k=1 of A143911, column k=2 of A080510, A182222. - Alois P. Heinz, Oct 24 2012
Column k=2 of A057731. - Alois P. Heinz, Feb 14 2013

m:=30; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x + x^2/2) -Exp(x) )); [0] cat [Factorial(n+1)*b[n]: n in [1..m-2]]; // G. C. Greubel, May 14 2019

a:= proc(n) option remember; `if`(n<3, [0$2, 1][n+1],
      a(n-1) +(n-1) *(1+a(n-2)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Oct 24 2012
# alternative:
A001189 := proc(n)
    local a,prs,p,k ;
    a := 0 ;
    for prs from 1 to n/2 do
        p := product(binomial(n-2*k,2),k=0..prs-1) ;
        a := a+p/prs!;
    end do:
    a;
end proc:
seq(A001189(n),n=1..13) ; # R. J. Mathar, Jan 04 2017

RecurrenceTable[{a[1]==0,a[2]==1,a[n]==a[n-1]+(1+a[n-2])(n-1)},a[n],{n,25}] (* Harvey P. Dale, Jul 27 2011 *)

{a(n) = sum(j=1,floor(n/2), n!/(j!*(n-2*j)!*2^j))}; \\ G. C. Greubel, May 14 2019

m = 30; T = taylor(exp(x +x^2/2) - exp(x), x, 0, m); a=[factorial(n)*T.coefficient(x, n) for n in (0..m)]; a[1:] # G. C. Greubel, May 14 2019

E.g.f.: exp(x + x^2/2) - exp(x).
a(n) = A000085(n) - 1.
a(n) = b(n, 2), where b(n, d)=Sum_{k=1..n} (n-1)!/(n-k)! * Sum_{l:lcm{k, l}=d} b(n-k, l), b(0, 1)=1 is the number of degree-n permutations of order exactly d.
From Henry Bottomley, May 03 2001: (Start)
a(n) = a(n-1) + (1 + a(n-2))*(n-1).
a(n) = Sum_{j=1..floor(n/2)} n!/(j!*(n-2*j)!*(2^j)). (End)

A218262 Number of standard Young tableaux of n cells and height >= 10.

Original entry on oeis.org

1, 11, 121, 1001, 8086, 59228, 426673, 2946593, 20161558, 135303408, 904408398, 5995379358, 39727129830, 262629161094, 1739604051411, 11535387587595, 76763703224070, 512448824337780, 3436760740882050, 23151339236295810, 156789753069685500, 1067435349046248600

Offset: 10

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 10.

Alois P. Heinz, Table of n, a(n) for n = 10..300
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=10 of A182222.

Cf. A000085, A212915, A182172.

a(n) = A000085(n) - A212915(n) = A182172(n,n) - A182172(n,9).

A218263 Number of standard Young tableaux of n cells and height >= 3.

Original entry on oeis.org

1, 4, 16, 56, 197, 694, 2494, 9244, 35234, 139228, 566788, 2387048, 10343101, 46193866, 211775002, 997265204, 4809609062, 23758479340, 119952340180, 618883933480, 3257842530546, 17492187873444, 95680438560276, 532985197799976, 3020676725917252

Offset: 3

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 3. a(3)=1: 123; a(4)=4: 1234, 1243, 1324, 2134.

Alois P. Heinz, Table of n, a(n) for n = 3..800
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=3 of A182222.

b:= proc(n) b(n):= `if`(n<2, 1, b(n-1) +(n-1)*b(n-2)) end:
a:= n-> b(n) -binomial(n, iquo(n, 2)):
seq(a(n), n=3..30);

b[n_] := b[n] = If[n<2, 1, b[n-1] + (n-1)*b[n-2]];
a[n_] := b[n] - Binomial[n, Quotient[n, 2]];
Table[a[n], {n, 3, 30}] (* Jean-François Alcover, Aug 23 2021, after Alois P. Heinz *)

a(n) = A000085(n) - A001405(n) = A182172(n,n) - A182172(n,2).

Conjecture: (n-6)*(n-3)*(n+1)*a(n) +(-n^3+6*n^2+11*n-36)*a(n-1) -(n-1)*(n^3-4*n^2-21*n+76)*a(n-2) +2*(n-1)*(n-2)*(3*n-19)*a(n-3) +4*(n-5)*(n-1)*(n-2)*(n-3)*a(n-4)=0. - R. J. Mathar, Jan 04 2017

A218264 Number of standard Young tableaux of n cells and height >= 4.

Original entry on oeis.org

1, 5, 25, 105, 441, 1785, 7308, 29898, 124641, 526669, 2276846, 10038964, 45353269, 209442533, 990777442, 4791502156, 23707812077, 119810145337, 618483875689, 3256714122209, 17488997849803, 95671400358075, 532959538382100, 3020603738202750, 17411069344112895

Offset: 4

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 4. a(4)=1: 1234; a(5)=5: 12345, 12354, 12435, 13245, 21345.

Alois P. Heinz, Table of n, a(n) for n = 4..800
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=4 of A182222.

a:= proc(n) option remember;
      `if`(n<5, [0$4, 1][n+1], ((-5-7*n+3*n^2)*a(n-1)
        +(n-1)*(n^2-n-11)*a(n-2) -2*n*(n-1)*(n-2)*a(n-3)
        -3*(n-1)*(n-2)*(n-3)*a(n-4))/((n+2)*(n-4)))
    end:
seq(a(n), n=4..30);

a[n_] := a[n] = If[n<5, {0,0,0,0,1}[[n+1]], ((-5-7n+3n^2)a[n-1] + (n-1)(n^2-n-11)a[n-2] - 2n(n-1)(n-2)a[n-3] - 3(n-1)(n-2)(n-3)a[n-4])/ ((n+2)(n-4))];
Table[a[n], {n, 4, 30}] (* Jean-François Alcover, Aug 23 2021, after Alois P. Heinz *)

a(n) = A000085(n) - A001006(n) = A182172(n,n) - A182172(n,3).

A218265 Number of standard Young tableaux of n cells and height >= 5.

Original entry on oeis.org

1, 6, 36, 176, 856, 3952, 18272, 83524, 384463, 1777010, 8304636, 39254076, 188160268, 915651672, 4527595824, 22771294440, 116496899100, 606656445480, 3214574890480, 17337658462800, 95128543350576, 530998366724576, 3013524116661952, 17385349086129304

Offset: 5

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 5. a(5)=1: 12345; a(6)=6: 123456, 123465, 123546, 124356, 132456, 213456.

Alois P. Heinz, Table of n, a(n) for n = 5..800
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=5 of A182222.

a:= proc(n) option remember; `if`(n<13,
      [0$5, 1, 6, 36, 176, 856, 3952, 18272, 83524][n+1],
      ((n^4-2*n^3-179*n^2+256*n+804) *a(n-1)
      +(n-1)*(n^4+6*n^3-295*n^2+1108*n+100) *a(n-2)
      -4*(n-1)*(n-2)*(6*n^2-83*n+67) *a(n-3)
      -16*(n-11)*(n-1)*(n-3)*(n-2)^2 *a(n-4))/
      ((n-12)*(n-5)*(n+4)*(n+3)))
    end:
seq(a(n), n=5..30);

a(n) = A000085(n) - A005817(n) = A182172(n,n) - A182172(n,4).

A218266 Number of standard Young tableaux of n cells and height >= 6.

Original entry on oeis.org

1, 7, 49, 273, 1506, 7788, 40161, 202917, 1028170, 5190328, 26375635, 134565795, 692890250, 3596739368, 18877483060, 100131220940, 537718999715, 2922918175965, 16100254700137, 89857257410905, 508473405642250, 2916903963927300, 16969580464205400

Offset: 6

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 6. a(6)=1: 123456; a(7)=7: 1234567, 1234576, 1234657, 1235467, 1243567, 1324567, 2134567.

Alois P. Heinz, Table of n, a(n) for n = 6..300
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=6 of A182222.

b:= proc(n) b(n):= `if`(n<2, 1, b(n-1) +(n-1)*b(n-2)) end:
g:= proc(n) option remember; `if`(n<3, [1, 1, 2][n+1],
      ((3*n^2+17*n+15)*g(n-1) +(n-1)*(13*n+9)*g(n-2)
       -15*(n-1)*(n-2)*g(n-3)) / ((n+4)*(n+6)))
    end:
a:= n-> b(n) -g(n):
seq(a(n), n=6..30);

a(n) = A000085(n) - A049401(n) = A182172(n,n) - A182172(n,5).

A218267 Number of standard Young tableaux of n cells and height >= 7.

Original entry on oeis.org

1, 8, 64, 400, 2465, 14092, 80016, 442248, 2442351, 13375366, 73477622, 403703404, 2230591660, 12380801756, 69225756076, 389806286920, 2213844625658, 12681996193252, 73339826141716, 428242854338216, 2526129602115517, 15056977593085444, 90712249806247400

Offset: 7

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 7. a(7)=1: 1234567; a(8)=8: 12345678, 12345687, 12345768, 12346578, 12354678, 12435678, 13245678, 21345678.

Alois P. Heinz, Table of n, a(n) for n = 7..300
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=7 of A182222.

b:= proc(n) b(n):= `if`(n<2, 1, b(n-1) +(n-1)*b(n-2)) end:
g:= proc(n) option remember;
      `if`(n<4, [1, 1, 2, 4][n+1], ((20*n^2+184*n+336)*g(n-1)
       +4*(n-1)*(10*n^2+58*n+33)*g(n-2) -144*(n-1)*(n-2)*g(n-3)
       -144*(n-1)*(n-2)*(n-3)*g(n-4)) / ((n+5)*(n+8)*(n+9)))
    end:
a:= n-> b(n) -g(n):
seq(a(n), n=7..30);

a(n) = A000085(n) - A007579(n) = A182172(n,n) - A182172(n,6).

A218268 Number of standard Young tableaux of n cells and height >= 8.

Original entry on oeis.org

1, 9, 81, 561, 3817, 23881, 147862, 886028, 5288933, 31178901, 183908244, 1081452450, 6381113064, 37719710024, 224141652938, 1337958249446, 8038507929319, 48593807722975, 295913856459150, 1814986751559300, 11220842616565050, 69921225307663290

Offset: 8

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 8. a(8)=1: 12345678; a(9)=9: 123456789, 123456798, 123456879, 123457689, 123465789, 123546789, 124356789, 132456789, 213456789.

Alois P. Heinz, Table of n, a(n) for n = 8..300
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=8 of A182222.

b:= proc(n) b(n):= `if`(n<2, 1, b(n-1) +(n-1)*b(n-2)) end:
g:= proc(n) option remember; `if`(n<4, [1, 1, 2, 4][n+1],
      ((4*n^3+78*n^2+424*n+495)*g(n-1) +(n-1)*(34*n^2+280*n
      +305)*g(n-2) -2*(n-1)*(n-2)*(38*n+145)*g(n-3) -105*(n-1)
      *(n-2)*(n-3)*g(n-4)) / ((n+6)*(n+10)*(n+12)))
    end:
a:= n-> b(n) -g(n):
seq(a(n), n=8..30);

a(n) = A000085(n) - A007578(n) = A182172(n,n) - A182172(n,7).

A218269 Number of standard Young tableaux of n cells and height >= 9.

Original entry on oeis.org

1, 10, 100, 760, 5656, 38416, 257376, 1660416, 10640692, 67100072, 422374352, 2643349180, 16566306380, 103786892840, 652502735152, 4113403313016, 26057914447911, 165824119892086, 1061381766546172, 6832087071296824, 44260892997918920, 288574772339715376

Offset: 9

Alois P. Heinz, Oct 24 2012

nonn

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= 9.

Alois P. Heinz, Table of n, a(n) for n = 9..300
Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Column k=9 of A182222.

b:= proc(n) b(n):= `if`(n<2, 1, b(n-1) +(n-1)*b(n-2)) end:
g:= proc(n) option remember; `if`(n<4, [1, 1, 2, 4][n+1],
      ((40*n^3+1084*n^2+8684*n+18480)*g(n-1) +16*(n-1)
      *(5*n^3+107*n^2+610*n+600)*g(n-2) -1024*(n-1)*(n-2)
      *(n+6)*g(n-3) -1024*(n-1)*(n-2)*(n-3)*(n+4)*g(n-4))/
       ((n+7)*(n+12)*(n+15)*(n+16)))
    end:
a:= n-> b(n) -g(n):
seq(a(n), n=9..30);

a(n) = A000085(n) - A007580(n) = A182172(n,n) - A182172(n,8).

A318289 Number of standard Young tableaux of 2n cells and height >= n.

Original entry on oeis.org

1, 2, 9, 56, 441, 3952, 40161, 442248, 5288933, 67100072, 904408398, 12777826272, 189324035423, 2917525618256, 46754429476800, 774965979970096, 13279872426589125, 234395323126241080, 4258775222885983350, 79442662095373693728, 1520453631213137081776

Offset: 0

Alois P. Heinz, Nov 04 2018

nonn

Also number of self-inverse permutations of [2n] with longest increasing subsequence of length >= n.

Wikipedia, Involution (mathematics)
Wikipedia, Young tableau

Cf. A182222.

h[l_] := Module[{n = Length[l]}, Total[l]!/Product[Product[1+l[[i]]-j+Sum[ If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Array[1&, n]]], g[n, i-1, l] + If[i > n, 0, g[n-i, i, Append[l, i]]]]]];
t[n_, k_] := g[n, n, {}] - If[k == 0, 0, g[n, k-1, {}]];
a[n_] := a[n] = t[2n, n];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* Jean-François Alcover, Sep 08 2021, after Alois P. Heinz in A182222 *)

a(n) = A182222(2n,n).

cp's OEIS Frontend

A001189 Number of degree-n permutations of order exactly 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A218262 Number of standard Young tableaux of n cells and height >= 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A218263 Number of standard Young tableaux of n cells and height >= 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A218264 Number of standard Young tableaux of n cells and height >= 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A218265 Number of standard Young tableaux of n cells and height >= 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A218266 Number of standard Young tableaux of n cells and height >= 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A218267 Number of standard Young tableaux of n cells and height >= 7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A218268 Number of standard Young tableaux of n cells and height >= 8.

Views

Author

Keywords