A052186 -id:A052186 - cp's OEIS frontend

A145878 Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed points (0 <= k <= n).

1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 14, 6, 3, 0, 1, 77, 29, 9, 4, 0, 1, 497, 160, 45, 12, 5, 0, 1, 3676, 1031, 249, 62, 15, 6, 0, 1, 30677, 7590, 1603, 344, 80, 18, 7, 0, 1, 285335, 63006, 11751, 2214, 445, 99, 21, 8, 0, 1, 2928846, 583160, 97056, 16168, 2865, 552, 119, 24

Offset: 0

Emeric Deutsch, Oct 29 2008

A permutation p of {1,2,...,n} is said to have j as a strong fixed point (splitter) if p(k) < j for k < j and p(k) > j for k > j.
T(n,k) is also the number of permutation graphs on n vertices with exactly k distinct dominating sets of size one. See the link by Theresa Baren, et al. -Daniel A. McGinnis, Oct 16 2018
The values T(k+r,k) are given as a polynomial expression in k when r is fixed, and the polynomial expressions can be calculated recursively. See the link by Theresa Baren, et al. -Daniel A. McGinnis, Oct 19 2018

			T(5,3) = 4 because we have 1'2'3'54, 1'2'435', 1'324'5' and 213'4'5' (the strong fixed points are marked).
Triangle starts:
   1;
   0,  1;
   1,  0,  1;
   3,  2,  0,  1;
  14,  6,  3,  0,  1;
  77, 29,  9,  4,  0,  1;

Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49.

Nathaniel Johnston, Table of n, a(n) for n = 0..5050
Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong, On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points, arXiv:1810.03409 [math.CO], 2018.
Todd Feil, Gary Kennedy and David Callan, Problem E3467, Amer. Math. Monthly, 100 (1993), 800-801.
FindStat - Combinatorial Statistic Finder, The number of strong fixed points
V. Strehl, The average number of splitters in a random permutation [Unpublished; included here with the author's permission.]

Row sums gives A000142.

Cf. A052861, A006932, A003149.

n:=7: sfix:=proc(p) local ct,i: ct:= 0: for i to nops(p) do if p[i]=i and `subset`({seq(p[j],j=1..i-1)},{seq(k,k=1..i-1)})=true then ct:=ct+1 else end if end do: ct end proc: with(combinat): P:=permute(n): s:=[seq(sfix(P[j]),j= 1..factorial(n))]: for i from 0 to n do a[i]:=0 end do: for j to factorial(n) do if s[j]=0 then a[0]:=a[0]+1 elif s[j]=1 then a[1]:=a[1]+1 elif s[j]=2 then a[2]:=a[2]+1 elif s[j]=3 then a[3]:=a[3]+1 elif s[j]=4 then a[4]:=a[4]+1 elif s[j]=5 then a[5]:=a[5]+1 elif s[j]=6 then a[6]:=a[6]+1 elif s[j]=7 then a[7]:= a[7]+1 elif s[j]=8 then a[8]:=a[8]+1 elif s[j]=9 then a[9]:=a[9]+1 elif s[j]= 10 then a[10]:=a[10]+1 end if end do: seq(a[k],k=0..n); # yields row m of the triangle, where m is the value of n specified at the beginning of the program
n:=7: G:=1:for r from n to 2 by -1 do G:=1-(2*r-1)*z-(r^2*z^2)/G:od:G:=1/(1-t*z-z^2/G):
Gser := simplify(series(G, z = 0, n+1)): for m from 0 to n do seq(coeff(coeff(Gser, z, m), t, k), k = 0 .. m) end do; # based on P. Barry's g.f.; yields sequence in triangular form

nn=10;p=Sum[n!x^n,{n,0,nn}];i=1-1/p;CoefficientList[Series[1/(1-(i-x+y x)),{x,0,nn}],{x,y}]//Grid  (* Geoffrey Critzer, Apr 27 2012 *)

T(n,0) = A052186(n).
Sum_{k=1..n} T(n,k) = A006932(n).
Sum_{k=0..n} k*T(n,k) = A003149(n-1).
G.f.: 1/(1-xy-x^2/(1-3x-4x^2/(1-5x-9x^2/(1-7x-16x^2/(1-9x-25x^2/(1-... (continued fraction). - Paul Barry, Dec 09 2009
G.f.: 1/(1-(I(x)- x + y*x)) where I(x) is o.g.f. for A003319. - Geoffrey Critzer, Apr 27 2012
From Daniel A. McGinnis, Oct 15 2018: (Start)
T(n,k) = Sum_{i=1..n-k+1} T(n-i,k-1)*T(i-1,0).
T(3+k,k)=3k+3, T(4+k,k)=(k+1)(k+28)/2, T(5+k,k)=(k+1)(3k+77), T(6+k,k)=(k+1)(k^2+110k+2982)/6, T(7+k,k)=(k+1)(3k^2+235k+7352)/2 (previous conjectures).
See the link by Theresa Baren, et al. (End)

A259872 a(0)=-1, a(1)=1; a(n) = na(n-1) + (n-2)a(n-2) + Sum_{j=1..n-1} a(j)a(n-j) + 2Sum_{j=0..n-1} a(j)*a(n-1-j).

Original entry on oeis.org

-1, 1, -1, 2, -1, 9, 26, 201, 1407, 11714, 107983, 1102433, 12332994, 150103585, 1974901951, 27935229074, 422799610943, 6818164335881, 116717210194218, 2113959805887881, 40388891717569887, 811833598825134258, 17126091132964548335, 378335451153341591041

Offset: 0

N. J. A. Sloane, Jul 09 2015

Eric M. Schmidt, Table of n, a(n) for n = 0..300
Richard J. Martin, and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.

Cf. A259869, A259870, A259871, A260950, A052186.

nmax = 25; CoefficientList[Assuming[Element[x, Reals], Series[-1/(ExpIntegralEi[1 + 1/x]/Exp[1 + 1/x] + 1), {x, 0, nmax}]], x] (* Vaclav Kotesovec, Aug 05 2015 *)

@CachedFunction
def a(n) : return -1 if n==0 else 1 if n==1 else n*a(n-1) + (n-2)*a(n-2) + sum(a(j)*a(n-j) for j in [1..n-1]) + 2*sum(a(j)*a(n-1-j) for j in [0..n-1]) # Eric M. Schmidt, Jul 10 2015

Martin and Kearney (2015) give a g.f.

a(n) ~ (n-1)! / exp(1) * (1 - 2/n + 1/n^2 + 1/n^3 - 10/n^4 - 61/n^5 - 382/n^6 - 3489/n^7 - 39001/n^8 - 484075/n^9 - 6619449/n^10), for coefficients see A260950. - Vaclav Kotesovec, Jul 29 2015

Definition corrected by and more terms from Eric M. Schmidt, Jul 10 2015

A225960 Number of permutations of [n] having exactly one strong fixed block.

Original entry on oeis.org

0, 1, 1, 3, 9, 38, 198, 1229, 8819, 71825, 654985, 6615932, 73357572, 886078937, 11583028581, 162939646239, 2454350815033, 39415438078466, 672282146765650, 12137067564016917, 231223273420524311, 4635720862911035149, 97565878042828417209, 2150797149322137710488

Offset: 0

Alois P. Heinz, May 22 2013

nonn

See A186373 for the definition of strong fixed blocks.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..450 (first 201 and last 2 terms from Alois P. Heinz)

Column k=1 of A186373.

Cf. A052186, A260957.

b:= proc(n) b(n):= -`if`(n<0, 1, add(b(n-i-1)*i!, i=0..n)) end:
a:= n-> add(b(i)*add(b(j), j=0..n-i-1), i=0..n-1):
seq(a(n), n=0..25);

nmax = 25; A052186zero = Rest[CoefficientList[Assuming[Element[x, Reals], Series[-1/(ExpIntegralEi[1/x]/E^(1/x) + 1), {x, 0, nmax+1}]], x]]; suma = ConstantArray[0, nmax+1]; s = 0; Do[s = s + A052186zero[[j+1]]; suma[[j+1]] = s, {j, 0, nmax}]; Flatten[{0, Table[Sum[A052186zero[[i+1]]*suma[[n-i]], {i, 0, n-1}], {n, 1, nmax}]}] (* Vaclav Kotesovec, Aug 05 2015, more efficient program for big nmax *)

a(n) = Sum_{1<=i<=j<=n} A052186(i-1) * A052186(n-j).
a(n) = Sum_{i=0..n-1} A052186(i) * Sum_{j=0..n-i-1} A052186(j).
a(n) ~ 2 * (n-1)! * (1 - 1/n + 2/n^3 + 11/n^4 + 97/n^5 + 1105/n^6 + 13905/n^7 + 189633/n^8 + 2803873/n^9 + 44875599/n^10), for coefficients see A260957. - Vaclav Kotesovec, Aug 29 2014, extended Aug 05 2015

A346198 a(n) is the number of permutations on [n] with no strong fixed points but contains at least one small descent.

Original entry on oeis.org

0, 1, 1, 8, 43, 283, 2126, 17947, 168461, 1741824, 19684171, 241506539, 3198239994, 45482655683, 691471698917, 11193266251700, 192238116358427, 3491633681792507, 66875708261486766, 1347168876070616179, 28474546456352896021, 630130731702950549248, 14570725407559756078387, 351411668456841530417027

Offset: 1

Eugene Fiorini, Jared Glassband, Garrison Lee Koch, Sophia Lebiere, Xufei Liu, Evan Sabini, Nathan B. Shank, Andrew Woldar, Jul 09 2021

nonn

A small descent in a permutation p is a position i such that p(i)-p(i+1)=1.

A strong fixed point is a fixed point (or splitter) p(k)=k such that p(i) < k for i < k and p(j) > k for j > k.

			For n = 4, the a(4) = 8 permutations on [4] with no strong fixed points but has small descents: {([2, 1], [4, 3]), (2, [4, 3], 1), ([3, 2], 4, 1), (3, 4, [2, 1]), (4, 1, [3, 2]), (4, [2, 1], 3), ([4, 3], 1, 2), (<4, 3, 2, 1>)} []small descent, <>consecutive small descents.

E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways For Your Mathematical Plays, Vol. 1, CRC Press, 2001.

M. Lind, E. Fiorini, A. Woldar, and W. H. T. Wong, On Properties of Pebble Assignment Graphs, Journal of Integer Sequences, 24(6), 2020.

Cf. A000255, A000166, A000153, A000261, A001909, A001910, A055790, A346189, A346199, A346204.

Python
```
See A346204.
```

For n > 2, a(n) = b(n)-c(n) where b(n) = A052186(n-1), c(n) = A346189(n).

A355488 Expansion of g.f. f/(1+2*f) where f is the g.f. of nonempty permutations.

Original entry on oeis.org

0, 1, 0, 2, 8, 48, 328, 2560, 22368, 216224, 2291456, 26430336, 329805952, 4429255168, 63730438656, 978479250944, 15972310317056, 276292865550336, 5049672714569728, 97245533647568896, 1968395389124714496, 41783552069858877440, 928204423021249003520

Offset: 0

F. Chapoton, Jul 04 2022

nonn

This is to factorials what Fine numbers are to Catalan numbers. There is no known combinatorial interpretation.
The same construction, applied to the central binomials, leads to A126984, apart from signs and the first term. - Peter Luschny, Jul 22 2022
a(n) is the number of permutations of [n] whose number of components is odd minus the number of those permutations with an even number of components. - Peter Luschny, Sep 10 2022

			Consider the permutations of [3]: [2,3,1], [3,1,2] and [3,2,1] have 1 component,
[1,3,2] and [2,1,3] have 2 components, and [1,2,3] has three components. Thus 3 - 2 + 1 = 2 = a(3). - _Peter Luschny_, Sep 10 2022

David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.
FindStat - Combinatorial Statistic Finder, The number of connected components of a permutation.

Cf. A000108, A003319, A000957, A000142, A052186, A126984, A059438, A122827.

a:= n-> (f-> coeff(series(f/(1+2*f), x, n+1), x, n))(add(j!*x^j, j=1..n)):
seq(a(n), n=0..23);  # Alois P. Heinz, Jul 20 2022

nmax=22; f[x_]:=Sum[i! x^i,{i,nmax}]; CoefficientList[Series[f[x]/(1+2f[x]),{x,0,nmax}],x] (* Stefano Spezia, Jul 04 2022 *)

A = QQ[['t']]
f = A([0] + [factorial(n) for n in range(1,30)]).O(30)
print(list(f/(1+2*f)))

# Uses function A059438_triangle.
def A355488_list(size):
    triangle = A059438_triangle(size)
    return [0] + [sum((-1)^k*t for (k,t) in enumerate(row)) for row in triangle]
print(A355488_list(20))  # Peter Luschny, Sep 10 2022

G.f.: f/(1+2*f) where f is (the g.f. of A000142) - 1.

a(n) = -Sum_{k=1..n} (-1)^k * A059438(n, k) for n >= 1. - Peter Luschny, Sep 10 2022

A174662 Partial sums of A003149.

Original entry on oeis.org

1, 3, 8, 24, 88, 400, 2212, 14500, 110116, 951076, 9205156, 98646436, 1159016356, 14808626596, 204358994596, 3028436306596, 47955883346596, 807990334802596, 14430691329362596, 272302801683794596, 5412861968581970596

Offset: 0

Jonathan Vos Post, Nov 30 2010

Total resistance of a circuit whose n-th component is between opposite corners of an n-dimensional hypercube of unit resistors, multiplied by n!. The only prime in the sequence is 3. The subsequence of squares begins 1, 400, 9205156 = 2^2 * 37^2 * 41^2.

			a(5) = 1 + 2 + 5 + 16 + 64 + 312 = 400 = 2^4 * 5^2.

Cf. A003149, A046825, A046878, A046879, A052186, A006932, A145878.

a(n) = Sum_{i=0..n} Sum_{k=0..i} k!*(i-k)!.

Offset set to 0 by Alois P. Heinz, Jun 28 2017

cp's OEIS Frontend

A145878 Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed points (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A259872 a(0)=-1, a(1)=1; a(n) = n*a(n-1) + (n-2)*a(n-2) + Sum_{j=1..n-1} a(j)*a(n-j) + 2*Sum_{j=0..n-1} a(j)*a(n-1-j).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A225960 Number of permutations of [n] having exactly one strong fixed block.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A346198 a(n) is the number of permutations on [n] with no strong fixed points but contains at least one small descent.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Formula

A355488 Expansion of g.f. f/(1+2*f) where f is the g.f. of nonempty permutations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

Formula

A174662 Partial sums of A003149.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A259872 a(0)=-1, a(1)=1; a(n) = na(n-1) + (n-2)a(n-2) + Sum_{j=1..n-1} a(j)a(n-j) + 2Sum_{j=0..n-1} a(j)*a(n-1-j).