[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a211606 -id:a211606
Displaying 1-6 of 6 results found.
page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
A216239
Total number of inversions in all derangement permutations of [n].
+10
6
0, 0, 1, 4, 34, 260, 2275, 21784, 228676, 2614296, 32372805, 431971100, 6182204006, 94495208444, 1536740258599, 26498747241680, 482990781797000, 9279452377499504, 187442757190618761, 3971627425918503156, 88084356619901450410, 2040857112777615061300
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
LINKS
Max Alekseyev and Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 100 terms from Max Alekseyev)
Wikipedia, Derangement
Wikipedia, Inversion
FORMULA
a(n) = SUM(k=0..n-2, (-1)^k * n!/k! * (3*n+k)*(n-k-1) )/12. - Max Alekseyev, Aug 13 2013
a(n) = ( (3*n^2-n+1)*A000166(n) + (n-1)*(-1)^n )/12. - Max Alekseyev, Aug 14 2013
a(n) = Sum_{k>=1} A228924(n,k) * k. - Alois P. Heinz, Sep 22 2013
a(n) ~ n! * n^2 / (4*exp(1)). - Vaclav Kotesovec, Sep 10 2014
EXAMPLE
a(2) = 1: (2,1) has 1 inversion.
a(3) = 4: (2,3,1), (3,1,2) have 2+2 = 4 inversions.
a(4) = 34: (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1) have 2+3+3+3+4+5+3+5+6 = 34 inversions.
MAPLE
v:= proc(l) local i; for i to nops(l) do if l[i]=i then return 0 fi od;
add(add(`if`(l[i]>l[j], 1, 0), j=i+1..nops(l)), i=1..nops(l)-1)
end:
a:= n-> add(v(d), d=combinat[permute](n)):
seq(a(n), n=0..8);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
n*((6*n^3-26*n^2+31*n-9)*a(n-1)+(n-1)*
(6*n^2-8*n+1)*a(n-2))/((n-2)*(15-20*n+6*n^2)))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Aug 13 2013
MATHEMATICA
A216239[n_] := (1/12)*n*(3*(-1)^n*n + (n*(3*n - 1) + 1)*Subfactorial[n-1]); Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Feb 05 2015, after Max Alekseyev *)
PROG
(PARI) A216239(n) = sum(k=0, n-2, (-1)^k * n!/k! * (3*n+k) * (n-k-1) )/12; /* Max Alekseyev, Aug 13 2013 */
CROSSREFS
Cf. A000166, A001809, A161124, A211606, A227404, A228924, A337193.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 15 2013
EXTENSIONS
Formula and terms a(15) onward from Max Alekseyev, Aug 13 2013
STATUS
approved
A161124
Number of inversions in all fixed-point-free involutions of {1,2,...,2n}.
+10
5
0, 1, 12, 135, 1680, 23625, 374220, 6621615, 129729600, 2791213425, 65472907500, 1663666579575, 45537716624400, 1336089255125625, 41837777148667500, 1392813754566609375, 49126088694402720000, 1830138702650463830625, 71812362934450726087500
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Also the sum of the major indices of all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=12 because the fixed-point-free involutions 2143, 3412, and 4321 have major indices 4, 2, and 6, respectively.
a(n) = Sum(k*A161123(n,k), k>=0).
For n > 0, a(n) is also the determinant absolute value of the symmetric n X n matrix M defined by M(i,j) = max(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..200
E. Pérez Herrero, Max Determinant, Psychedelic Geometry Blogspot, 15 Jan 2013
FORMULA
a(n) = n^2*(2n-1)!!.
a(n) = n^2*A001147(n). - Enrique Pérez Herrero, Jan 14 2013
a(n) = (2n)! * [x^(2n)] (x^2/2 + x^4/4)*exp(x^2/2). - Geoffrey Critzer, Mar 03 2013
D-finite with recurrence a(n) +(-2*n-7)*a(n-1) +(8*n-3)*a(n-2) +(-2*n+5)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
EXAMPLE
a(2) = 12 because the fixed-point-free involutions 2143, 3412, and 4321 have 2, 4, and 6 inversions, respectively.
MAPLE
seq(n^2*factorial(2*n)/(factorial(n)*2^n), n = 0 .. 18);
MATHEMATICA
nn=40; Prepend[Select[Range[0, nn]!CoefficientList[Series[(x^2/2+x^4/4)Exp[x^2/2], {x, 0, nn}], x], #>0&], 0] (* Geoffrey Critzer, Mar 03 2013 *)
Table[n^2 (2n-1)!!, {n, 0, 20}] (* Harvey P. Dale, Jan 05 2014 *)
CROSSREFS
Cf. A161123.
Cf. A051125, A181983, A211606.
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jun 05 2009
STATUS
approved
A264082
Total number of inversions in all set partitions of [n].
+10
4
0, 0, 0, 1, 10, 74, 504, 3383, 23004, 160444, 1154524, 8594072, 66243532, 528776232, 4369175522, 37343891839, 329883579768, 3008985817304, 28312886239136, 274561779926323, 2741471453779930, 28159405527279326, 297291626845716642, 3223299667111201702
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,5
COMMENTS
Each set partition is written as a sequence of blocks, ordered by the smallest elements in the blocks.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..210
Wikipedia, Inversion (discrete mathematics)
Wikipedia, Partition of a set
FORMULA
a(n) = Sum_{k>0} k * A125810(n,k).
EXAMPLE
a(3) = 1: one inversion in 13|2.
a(4) = 10: one inversion in each of 124|3, 13|24, 13|2|4, 1|24|3, and two inversions in each of 134|2, 14|23, 14|2|3.
CROSSREFS
Cf. A001809, A125810, A189052, A211606, A216239, A271370.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Apr 03 2016
STATUS
approved
A337193
Total number of inversions in all permutations of [n] where the descent set equals the subset of odd elements in [n-1].
+10
4
0, 0, 1, 3, 18, 80, 495, 2856, 20244, 142848, 1167885, 9729280, 90858438, 872361984, 9193900443, 99947258880, 1175452387560, 14270843322368, 185456745850329, 2487099677147136, 35413726451731770, 519907295578030080, 8052572864648861703, 128451121643116822528
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..483
Wikipedia, Inversion
Wikipedia, Permutation
FORMULA
a(n) = Sum_{k=1..ceiling((n-1)^2/2)} k * A337126(n,k).
From Vaclav Kotesovec, Aug 31 2020: (Start)
a(n) ~ n! * 2^n * n^2 / Pi^(n+1).
a(n) ~ 2^(n + 1/2) * n^(n + 5/2) / (Pi^(n + 1/2) * exp(n)). (End)
EXAMPLE
a(3) = 3, because in the A000111(3) = 2 permutations 213, 312 there are 3 inversions: (2,1), (3,1), (3,2).
a(4) = 18, because in the A000111(4) = 5 permutations 2143, 3142, 3241, 4132, 4231 there are 18 inversions: (2,1), (4,3), (3,1), (3,2), (4,2), (3,2), (3,1), (2,1), (4,1), (4,1), (4,3), (4,2), (3,2), (4,2), (4,3), (4,1), (2,1), (3,1).
MAPLE
b:= proc(u, o, t) option remember; `if`(u+o=0, [1, 0], add((p-> [0,
`if`(t=0, o-1+j, u-j)*p[1]]+p)(b(o-1+j, u-j, 1-t)), j=1..u))
end:
a:= n-> b(n, 0$2)[2]:
seq(a(n), n=0..30);
MATHEMATICA
b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1, Sum[x^If[t == 0, o - 1 + j, u - j]*b[o - 1 + j, u - j, 1 - t], {j, 1, u}]]];
a[n_] := With[{cc = CoefficientList[b[n, 0, 0], x]}, cc.Range[0, Length[cc]-1] ];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz in A337126 *)
CROSSREFS
Cf. A000111, A001809, A211606, A216239, A337126.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Aug 18 2020
STATUS
approved
A227404
Total number of inversions in all permutations of order n consisting of a single cycle.
+10
3
0, 0, 1, 4, 22, 140, 1020, 8400, 77280, 786240, 8769600, 106444800, 1397088000, 19718899200, 297859161600, 4794806016000, 81947593728000, 1482030950400000, 28277150533632000, 567677135241216000, 11961768206868480000, 263969867887165440000
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
The formula trivially follows from the observation that every pair of elements i<j forms an inversion in exactly (binomial(n,2)-n+j-i)*(n-3)! single-cycle permutations. - Max Alekseyev, Jan 05 2018
a(n) is the number of ways to partition a (n+1)X(n+1) square, with the upper left hand corner missing, into ribbons of size n, see Alexandersson, Jordan. - Per W. Alexandersson, Jun 02 2020
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..449
Per Alexandersson, Linus Jordan, Enumeration of border-strip decompositions, arXiv:1805.09778 [math.CO], 2018.
Per Alexandersson, Linus Jordan, Enumeration of border-strip decompositions, Journal of Integer Sequences, Vol. 22 (2019), Article 19.4.5.
FORMULA
For n>2, a(n) = n! * (3*n-1)/12. - Vaclav Kotesovec, Feb 14 2014
EXAMPLE
a(3) = 4 because the cyclic 3-permutations: (1,2,3), (1,3,2) written in one line (sequence) notation: {2,3,1}, {3,1,2} have 2 + 2 = 4 inversions.
MATHEMATICA
Table[Total[Map[Inversions, Map[FromCycles, Map[List, Map[Prepend[#, n]&, Permutations[n-1]]]]]], {n, 1, 8}]
CROSSREFS
Cf. A001809, A211606, A216239.
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Sep 21 2013
EXTENSIONS
a(13)-a(15) from Alois P. Heinz, Sep 26 2013
Terms a(16) and beyond from Max Alekseyev, Jan 05 2018
STATUS
approved
A213910
Irregular triangle read by rows: T(n,k) is the number of involutions of length n that have exactly k inversions; n>=0, 0<=k<=binomial(n,2).
+10
2
1, 1, 1, 1, 1, 2, 0, 1, 1, 3, 1, 2, 1, 1, 1, 1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1, 1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1, 1, 6, 10, 9, 16, 13, 19, 17, 19, 19, 17, 19, 13, 17, 7, 13, 3, 8, 1, 4, 0, 1, 1, 7, 15, 16, 26, 29, 34, 43, 39, 54, 41, 61, 40, 62, 36, 58, 28, 47, 21, 34, 15, 21, 10, 11, 6, 4, 3, 1, 1
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,6
LINKS
Alois P. Heinz, Rows n = 0..40, flattened
FORMULA
Sum_{k>=0} T(n,k)*k = A211606(n).
T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-2,k-2*(n-j)+1) for n>=0, k>0; T(n,k) = 0 for n<0 or k<0; T(n,0) = 1 for n>=0. - Alois P. Heinz, Mar 07 2013
EXAMPLE
T(4,3) = 2 because we have: (3,2,1,4), (1,4,3,2).
Triangle T(n,k) begins:
1;
1;
1, 1;
1, 2, 0, 1;
1, 3, 1, 2, 1, 1, 1;
1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1;
1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1;
...
MAPLE
T:= proc(n) option remember; local f, g, j; if n<2 then 1 else
f, g:= [T(n-1)], [T(n-2)]; for j to 2*n-3 by 2 do
f:= zip((x, y)->x+y, f, [0$j, g[]], 0) od; f[] fi
end:
seq(T(n), n=0..10); # Alois P. Heinz, Mar 05 2013
MATHEMATICA
Needs["Combinatorica`"];
Table[Distribution[Map[Inversions, Involutions[n]], Range[0, Binomial[n, 2]]], {n, 0, 9}]//Flatten
(* Second program: *)
zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
T[n_] := T[n] = Module[{f, g, j}, If[n < 2, Return@{1}, f = T[n-1]; g = T[n-2]; For[j = 1, j <= 2*n - 3, j += 2, f = zip[Plus, f, Join[Table[0, {j}], g], 0]]]; f];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 04 2023, after Alois P. Heinz *)
CROSSREFS
Cf. A008302 (permutations of [n] with k inversions).
Cf. A000085 (row sums), A211606, A214086 (diagonal).
KEYWORD
nonn,tabf
AUTHOR
Geoffrey Critzer, Mar 04 2013
STATUS
approved
page 1

Search completed in 0.006 seconds

Lookup Welcome Wiki Register Music Plot 2 Demos Index WebCam Contribute Format Style Sheet Transforms Superseeker Recents
The OEIS Community
Maintained by The OEIS Foundation Inc.
Last modified November 24 01:23 EST 2024. Contains 378052 sequences.
License Agreements, Terms of Use, Privacy Policy