A002467 -id:A002467 - cp's OEIS frontend

A352875 Number of integer compositions y of n with a fixed point y(i) = i.

0, 1, 1, 2, 5, 10, 21, 42, 86, 174, 351, 708, 1424, 2861, 5743, 11520, 23092, 46269, 92673, 185562, 371469, 743491, 1487870, 2977164, 5956616, 11916910, 23839736, 47688994, 95393322, 190811346, 381662507, 763389209, 1526881959, 3053930971, 6108131542, 12216698288

Offset: 0

Gus Wiseman, May 15 2022

nonn

			The a(0) = 0 through a(5) = 10 compositions (empty column indicated by dot):
  .  (1)  (11)  (12)   (13)    (14)
                (111)  (22)    (32)
                       (112)   (113)
                       (121)   (122)
                       (1111)  (131)
                               (221)
                               (1112)
                               (1121)
                               (1211)
                               (11111)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The version for partitions is A001522, ranked by A352827 (unproved).
The version for permutations is A002467, complement A000166.
The complement for partitions is A064428, ranked by A352826 (unproved).
This is the sum of latter columns of A238349, nonfixed A352523.
The complement is counted by A238351.
The complement for reversed partitions is A238394, ranked by A352830.
The version for reversed partitions is A238395, ranked by A352872.
The case of just one fixed point is A240736.
A008290 counts permutations by fixed points, nonfixed A098825.
A011782 counts compositions.
A115720 and A115994 count partitions by Durfee square.
A238352 counts reversed partitions by fixed points, rank statistic A352822.
A352512 counts fixed points in standard compositions, nonfixed A352513.
A352521 = comps by subdiags, first col A219282, rank stat A352514.
A352522 = comps by weak subdiags, first col A238874, rank stat A352515.
A352524 = comps by superdiags, first col A008930, rank stat A352516.
A352525 = comps by weak superdiags, col k=1 A177510, rank stat A352517.
A352833 counts partitions by fixed points.
Cf. A006918, A008292, A088218, A114088, A123125, A188674, A257990.

pq[y_]:=Length[Select[Range[Length[y]],#==y[[#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],pq[#]>0&]],{n,0,15}]

S(v,u,c)={vector(#v, k, c + sum(i=1, k-1, v[k-i]*u[i]))}
seq(n)={my(v=vector(1+n), s=vector(#v, i, 2^(i-2))); v[1]=1; s[1]=0; for(i=1, n, v=S(v, vector(n, j, if(j==i,'x,1)), O(x)); s-=apply(p->polcoef(p,0), v)); s} \\ Andrew Howroyd, Jan 02 2023

a(n) = 2^(n-1) - A238351(n) for n >= 1. - Andrew Howroyd, Jan 02 2023

Terms a(21) and beyond from Andrew Howroyd, Jan 02 2023

A162971 Triangle read by rows: T(n,k) is number of non-derangement permutations of {1,2,...,n} having k cycles (1 <= k <= n).

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 8, 6, 1, 0, 30, 35, 10, 1, 0, 144, 210, 85, 15, 1, 0, 840, 1414, 735, 175, 21, 1, 0, 5760, 10752, 6664, 1960, 322, 28, 1, 0, 45360, 91692, 64764, 22449, 4536, 546, 36, 1, 0, 403200, 869040, 679580, 268380, 63273, 9450, 870, 45, 1, 0, 3991680, 9074736, 7704180, 3382280, 902055, 157773, 18150, 1320, 55, 1

Offset: 1

Emeric Deutsch, Jul 22 2009

Sum of entries in row n = A002467(n) (the number of non-derangement permutations of {1,2,...,n}).
T(n,2) = n*(n-2)! = A001048(n-1) for n>=3.
Sum_{k=1..n} k*T(n,k) = A162972(n).

			T(4,2) = 8 because we have (1)(234), (1)(243), (134)(2), (143)(2), (124)(3), (142)(3), (123)(4), and (132)(4).
Triangle starts:
  1;
  0,   1;
  0,   3,   1;
  0,   8,   6,   1;
  0,  30,  35,  10,   1;
  0, 144, 210,  85,  15,   1;
  ...

Alois P. Heinz, Rows n = 1..150, flattened

Cf. A001048, A002467, A162972.

G := (1-exp(-t*z))/(1-z)^t: Gser := simplify(series(G, z = 0, 15)): for n to 11 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n to 11 do seq(coeff(P[n], t, j), j = 1 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, t) option remember; `if`(n=0, t, add(expand((j-1)!*
      b(n-j, `if`(j=1, 1, t))*x)*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)):
seq(T(n), n=1..12);  # Alois P. Heinz, Aug 15 2023

b[n_, t_] := b[n, t] = If[n == 0, t, Sum[Expand[(j - 1)!*b[n - j, If[j == 1, 1, t]]*x]*Binomial[n - 1, j - 1], {j, 1, n}]];
T[n_] := CoefficientList[b[n, 0]/x, x];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Apr 04 2024, after Alois P. Heinz *)

E.g.f.: G(t,z) = (1-exp(-tz))/(1-z)^t.

A193465 Row sums of triangle A061312.

Original entry on oeis.org

0, 2, 9, 52, 335, 2466, 20447, 189064, 1930959, 21603430, 262869959, 3457226268, 48880169351, 739429561066, 11918051268255, 203914545928336, 3691384616598047, 70491995143458894, 1416242276574905879, 29862732908481855460, 659413025994777460119

Offset: 0

Johannes W. Meijer, Jul 27 2011

a(n) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = A001563(k) for k = 0, 1, ..., n. - Michael Somos, Jun 06 2012

			2*x + 9*x^2 + 52*x^3 + 335*x^4 + 2466*x^5 + 20447*x^6 + 189064*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..445

Cf. A000166, A001563, A002467, A047920, A061312, A180191, A074909.

A193465 := proc(n): add(A061312(n,k), k=0..n) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: seq(A193465(n), n=0..20);

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 + x - (1 + x^2) / Exp[ x ]) / (1 - x)^3, {x, 0, n}]] (* Michael Somos, Jun 06 2012 *)

{a(n) = if( n<0, 0, n! * polcoeff( (1 + x - (1 + x^2) / exp(x + x * O(x^n))) / (1 - x)^3, n))} /* Michael Somos, Jun 06 2012 */

a(n) = Sum_{k=0..n} A061312(n,k).
a(n) = (n+1)*A180191(n+1).
a(n) = A002467(n+2) - (n+1)! (the game of mousetrap with n cards).
a(n) = (n+1)*(n+1)! - A000166(n+2) (rencontres numbers).
a(n) = ((n-n^3)*a(n-3) + (2*n+n^2-n^3)*a(n-2) - (1-n-2*n^2)*a(n-1))/n with a(0) = 0, a(1) = 2 and a(2) = 9.
E.g.f: (1 + x - (1 + x^2) / exp(x)) / (1 - x)^3. - Michael Somos, Jun 06 2012
a(n) = Sum_{k=0..n} C(n+1,k)*A000166(k+1) = Sum_{k=0..n} A074909(n,k)*A000166(k+1). - Anton Zakharov, Sep 26 2016
a(n) = Sum_{k=1..n+1} A047920(n+1,k). - Alois P. Heinz, Sep 01 2021

A208956 Triangular array read by rows. T(n,k) is the number of n-permutations that have at least k fixed points with n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 1, 1, 15, 7, 1, 1, 76, 31, 11, 1, 1, 455, 191, 56, 16, 1, 1, 3186, 1331, 407, 92, 22, 1, 1, 25487, 10655, 3235, 771, 141, 29, 1, 1, 229384, 95887, 29143, 6883, 1339, 205, 37, 1, 1, 2293839, 958879, 291394, 68914, 13264, 2176, 286, 46, 1, 1

Offset: 1

Geoffrey Critzer, Mar 03 2012

Row sums = n!

			Triangle begins:
     1;
     1,    1;
     4,    1,   1;
    15,    7,   1,  1;
    76,   31,  11,  1,  1;
   455,  191,  56, 16,  1, 1;
  3186, 1331, 407, 92, 22, 1, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A002467 (column 1), A155521 (column 2).

b:= proc(n) b(n):= `if`(n<2, 1-n, (n-1)*(b(n-1)+b(n-2))) end:
T:= (n, k)-> add(binomial(n, i)*b(n-i), i=k..n):
seq(seq(T(n,k), k=1..n), n=1..12);  # Alois P. Heinz, Apr 22 2013

f[list_] := Select[list,#>0&]; Map[f,Transpose[Table[nn=10; d=Exp[-x]/(1-x); p=1/(1-x); s=Sum[x^i/i!,{i,0,n}]; Drop[Range[0,nn]! CoefficientList[Series[p-s d, {x,0,nn}], x], 1], {n,0,9}]]]//Flatten

E.g.f. for column k: 1/(1-x) - D(x)*Sum_{i=0..k-1} x^i/i! where D(x) is the e.g.f. for A000166.

T(n,k) = Sum_{i=k..n} C(n,i)*A000166(n-i). - Alois P. Heinz, Apr 22 2013

A236438 a(n) = n*a(n-1) + (-1)^n for n>0, a(0)=2.

Original entry on oeis.org

2, 1, 3, 8, 33, 164, 985, 6894, 55153, 496376, 4963761, 54601370, 655216441, 8517813732, 119249392249, 1788740883734, 28619854139745, 486537520375664, 8757675366761953, 166395831968477106, 3327916639369542121, 69886249426760384540, 1537497487388728459881

Offset: 0

Michael Somos, Jan 25 2014

nonn

			G.f. = 2 + x + 3*x^2 + 8*x^3 + 33*x^4 + 164*x^5 + 985*x^6 + 6894*x^7 + ...

Indranil Ghosh, Table of n, a(n) for n = 0..449

Cf. A000166, A001120, A002467.

m:=50; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!((1+Exp(-x))/(1-x))); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Aug 07 2018

a := n -> GAMMA(n+1) + GAMMA(n+1,-1)*exp(-1):
seq(simplify(a(n)), n=0..22); # Peter Luschny, Feb 28 2017

a[ n_] := If[ n < 0, 0, n! + Subfactorial[n]]
a[ n_] := If[ n < 1, 2 Boole[n == 0], n! + Round[ n! / E]]
a[ n_] := If[ n < 0, 0, n! + (-1)^n HypergeometricPFQ[ { -n, 1}, {}, 1]]
a[ n_] := If[ n<0, 0, n! SeriesCoefficient[ (1 + Exp[ -x]) / (1 - x), {x, 0, n}]]

{a(n) = if( n<1, 2 * (n==0), n * a(n-1) + (-1)^n)}

{a(n) = if( n<0, 0, n! * polcoeff( (1 + exp(-x + x * O(x^n))) / (1 - x), n))}

E.g.f.: (1 + exp(-x)) / (1 - x).
a(n) = A001120(n) unless n=0.
a(n) = A000166(n) + n!.
0 = a(n) * (a(n+1) + a(n+2) - a(n+3)) + a(n+1) * (a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2) * (a(n+2)) if n>=0.
a(n) = Gamma(n+1) + Gamma(n+1, -1)*exp(-1). - Peter Luschny, Feb 28 2017
D-finite with recurrence a(n) +(-n+1)*a(n-1) +(-n+1)*a(n-2)=0. - R. J. Mathar, Sep 24 2021

A277032 Number of permutations of [n] such that the minimal cyclic distance between elements of the same cycle equals one, a(1)=1 by convention.

Original entry on oeis.org

1, 1, 5, 20, 109, 668, 4801, 38894, 353811, 3561512, 39374609, 474132730, 6179650125, 86676293916, 1301952953989, 20852719565694, 354771488612075, 6389625786835184, 121456993304945749, 2429966790591643402, 51042656559451380013, 1123165278137918510772

Offset: 1

Alois P. Heinz, Sep 25 2016

nonn

			a(2) = 1: (1,2).
a(3) = 5: (1,2,3), (1,3,2), (1)(2,3), (1,2)(3), (1,3)(2).

Per Alexandersson et al., d-regular partitions and permutations, MathOverflow, 2014

Column k=1 of A277031.

Cf. A002467, A180191, A276975.

b:= proc(n, i, l) option remember; `if`(n=0, mul(j!, j=l),
      (m-> add(`if`(i=j or n*j=1, 0, b(n-1, j, `if`(j>m,
      [l[], 0], subsop(j=l[j]+1, l)))), j=1..m+1))(nops(l)))
    end:
a:= n-> `if`(n=1, 1, n!-b(n-1, 1, [0])):
seq(a(n), n=1..15);

b[n_, i_, l_] := b[n, i, l] = If[n == 0, Product[j!, {j, l}], With[{m = Length[l]}, Sum[If[i == j || n*j == 1, 0, b[n-1, j, If[j>m, Append[l, 0], ReplacePart[l, j -> l[[j]]+1]]]], {j, 1, m+1}]]];
a[n_] := If[n == 1, 1, n! - b[n-1, 1, {0}]];
Array[a, 15] (* Jean-François Alcover, Mar 13 2021, after Alois P. Heinz *)

A306015 Exponential series expansion of (exp(x*y) + sinh(x) - cosh(x))/(1 - x).

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 4, 6, 3, 1, 15, 24, 12, 4, 1, 76, 120, 60, 20, 5, 1, 455, 720, 360, 120, 30, 6, 1, 3186, 5040, 2520, 840, 210, 42, 7, 1, 25487, 40320, 20160, 6720, 1680, 336, 56, 8, 1, 229384, 362880, 181440, 60480, 15120, 3024, 504, 72, 9, 1

Offset: 0

Peter Luschny, Jun 23 2018

From David Callan, Dec 18 2021: (Start)
For 0 <= k <= n, T(n,k) is the number of nonderangements of size n in which k of the fixed points are colored red. In particular, with D_n the derangement number A000166(n), T(n,0) = n! - D_n. For a general example, T(3,1) = 6 counts the colored permutations R23, R32, 1R3, 3R1, 12R, 21R where the red fixed points are indicated by "R".
For n >= k >= 1, T(n,k) = n!/k!. Proof. In a colored permutation, such as 3R7R516 counted by T(n,k) with n = 7 and k = 2, the R's indicate (red) fixed points and so no information is lost by rank ordering the remaining entries while retaining the placement of the R's: 2R5R314. The result is a permutation of the set consisting of 1,2,...,n-k and k R's; there are n!/k! such permutations and the process is reversible. QED. (End)

			  n |  k = 0       1       2      3      4     5    6   7  8  9
  --+----------------------------------------------------------
  0 |      0
  1 |      1,      1
  2 |      1,      2,      1
  3 |      4,      6,      3,     1
  4 |     15,     24,     12,     4,     1
  5 |     76,    120,     60,    20,     5,    1
  6 |    455,    720,    360,   120,    30,    6,   1
  7 |   3186,   5040,   2520,   840,   210,   42,   7,  1
  8 |  25487,  40320,  20160,  6720,  1680,  336,  56,  8, 1
  9 | 229384, 362880, 181440, 60480, 15120, 3024, 504, 72, 9, 1

G. C. Greubel, Rows n=0..99 of triangle, flattened

A094587 with an extra first column A002467.

Row sums are A306150.

gf := (exp(x*y) + sinh(x) - cosh(x))/(1 - x):
ser := series(gf, x, 16): L := [seq(n!*coeff(ser, x, n), n=0..14)]:
seq(seq(coeff(L[k+1], y, n), n=0..k), k=0..12);

Join[{0}, With[{nmax = 15}, CoefficientList[CoefficientList[Series[ (Exp[x*y] + Sinh[x] - Cosh[x])/(1 - x), {x, 0, nmax}, {y, 0, nmax}], x], y ]*Range[0, nmax]!] // Flatten ] (* G. C. Greubel, Jul 18 2018 *)

A353317 Heinz numbers of integer partitions that have a fixed point and a conjugate fixed point (counted by A188674).

Original entry on oeis.org

2, 9, 15, 18, 21, 30, 33, 36, 39, 42, 51, 57, 60, 66, 69, 72, 78, 84, 87, 93, 102, 111, 114, 120, 123, 125, 129, 132, 138, 141, 144, 156, 159, 168, 174, 175, 177, 183, 186, 201, 204, 213, 219, 222, 228, 237, 240, 245, 246, 249, 250, 258, 264, 267, 275, 276

Offset: 1

Gus Wiseman, May 15 2022

nonn

A fixed point of a sequence y is an index y(i) = i. A fixed point of a partition is unique if it exists.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The terms and their prime indices begin:
    2: (1)
    9: (2,2)
   15: (3,2)
   18: (2,2,1)
   21: (4,2)
   30: (3,2,1)
   33: (5,2)
   36: (2,2,1,1)
   39: (6,2)
   42: (4,2,1)
   51: (7,2)
   57: (8,2)
   60: (3,2,1,1)
   66: (5,2,1)
   69: (9,2)
   72: (2,2,1,1,1)
   78: (6,2,1)
   84: (4,2,1,1)
For example, the partition (2,2,1,1) with Heinz number 36 has a fixed point at the second position, as does its conjugate (4,2), so 36 is in the sequence.

These partitions are counted by A188674.
Crank: A342192, A352873, A352874; counted by A064410, A064428, A001522.
The strict case is A352829.
Fixed point but no conjugate fixed point: A353316, counted by A118199.
A000700 counts self-conjugate partitions, ranked by A088902.
A002467 counts permutations with a fixed point, complement A000166.
A056239 adds up prime indices, row sums of A112798 and A296150.
A115720/A115994 count partitions by their Durfee square, rank stat A257990.
A122111 represents partition conjugation using Heinz numbers.
A238352 counts reversed partitions by fixed points, rank statistic A352822.
A238394 counts reversed partitions without a fixed point, ranked by A352830.
A238395 counts reversed partitions with a fixed point, ranked by A352872.
A352826 ranks partitions w/o a fixed point, counted by A064428 (unproved).
A352827 ranks partitions with a fixed point, counted by A001522 (unproved).
Cf. A001222, A065770, A093641, A252464, A325039, A325163, A325169, A352828, A352831, A352832, A352833.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
pq[y_]:=Length[Select[Range[Length[y]],#==y[[#]]&]];
conj[y_]:=If[Length[y]==0,y,Table[Length[Select[y,#>=k&]],{k,1,Max[y]}]];
Select[Range[100],pq[Reverse[primeMS[#]]]>0&& pq[conj[Reverse[primeMS[#]]]]>0&]

A003048 a(n+1) = n*a(n) - (-1)^n.

Original entry on oeis.org

1, 2, 3, 10, 39, 196, 1175, 8226, 65807, 592264, 5922639, 65149030, 781788359, 10163248668, 142285481351, 2134282220266, 34148515524255, 580524763912336, 10449445750422047, 198539469258018894

Offset: 1

N. J. A. Sloane

nonn

Cf. A002467.

a:= proc(p) option remember; p*a(p-1)-(-1)^p end proc: a(0):= 1: seq(a(p),p=0..19); # Robert Israel, Jan 05 2008

a[0] = 1; a[p_] := p*a[p - 1] -(-1)^p; a /@ Range[0, 19] (* Zerinvary Lajos, Mar 29 2007 *)
FoldList[#1*#2 - (-1)^#2 &, 1, Range[19]] (* Robert G. Wilson v, Jul 07 2012 *)
RecurrenceTable[{a[n + 1] == n a[n] - (-1)^n, a[1] == 1}, a[n], {n, 21}] (* Ray Chandler, Jul 30 2015 *)

PARI
```
a(n)=if(n<2,n>0,(n-1)*a(n-1)+(-1)^n)
```

a(n)=if(n<1,0,(n-1)!*polcoeff((2-exp(-x+O(x^n)))/(1-x),n-1))

E.g.f.: (2-exp(-x))/(1-x) (if offset 0).
a(n) = (n-1)! + A002467(n-1), n > 0. (index corrected Mar 07 2022)
D-finite with recurrence a(n+2) = n(a(n) + a(n+1)) for n > 0. - Amarnath Murthy, Oct 05 2002
a(n) = 2*(n-1)! - floor(((n-1)! + 1)/e), n > 1. - Gary Detlefs, Apr 11 2010

A095237 a(1)=1; then for n even, a(n)=(sum of previous terms times n) plus 1, for n odd, a(n)=(sum of previous terms times n) minus 1.

Original entry on oeis.org

1, 3, 11, 61, 379, 2731, 22301, 203897, 2064455, 22938391, 277554529, 3633441109, 51170962283, 771500662115, 12399117783989, 211611610180081, 3822234708877711, 72847296804492847, 1460993008134550985

Offset: 1

Amarnath Murthy, Jun 13 2004

nonn

Conjecture: There are infinitely many primes in this sequence.
The sequence would have been a little nicer if the even terms had a minus one and the odd a plus one, so the first term would not have to be an exception.
Except for the first two terms, it appears that a(n) are the first differences of A002467. - Carl Najafi, Sep 27 2018

Muniru A Asiru, Table of n, a(n) for n = 1..100

Cf. A095236.

Digits:=100: a:=n->factorial(n+1)-floor((factorial(n+1)+1)/exp(1))-factorial(n)+floor((factorial(n)+1)/exp(1)): 1,seq(a(n),n=2..20); # Muniru A Asiru, Sep 28 2018

a=vector(100); s=1; for(i=2,100,if(Mod(i,2)==0,a[i]=s*i+1,a[i]=s*i-1);s+=a[i])

a(n) = (n+1)! - floor(((n+1)!+1)/e) - n! + floor((n!+1)/e), n > 1. - Gary Detlefs, Nov 07 2010

Edited by Johan Claes, Jun 16 2004

cp's OEIS Frontend

A352875 Number of integer compositions y of n with a fixed point y(i) = i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A162971 Triangle read by rows: T(n,k) is number of non-derangement permutations of {1,2,...,n} having k cycles (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A193465 Row sums of triangle A061312.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A208956 Triangular array read by rows. T(n,k) is the number of n-permutations that have at least k fixed points with n >= 1 and 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A236438 a(n) = n*a(n-1) + (-1)^n for n>0, a(0)=2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A277032 Number of permutations of [n] such that the minimal cyclic distance between elements of the same cycle equals one, a(1)=1 by convention.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A306015 Exponential series expansion of (exp(x*y) + sinh(x) - cosh(x))/(1 - x).

Views

Author

Keywords

Comments

Examples