A000255 -id:A000255 - cp's OEIS frontend

A288954 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.

1, 1, 3, 13, 79, 555, 4605, 42315, 436275, 4894155, 60125625, 794437875, 11325612375, 172141044075, 2793834368325, 48009995908875, 874143494098875, 16757439016192875, 338309837281040625, 7157757510792763875, 158706419654857449375, 3673441093896736036875

Offset: 2

Michael Wallner, Jun 20 2017

nonn

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - Michael Wallner, Apr 20 2017

a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels a maximal young leaves and non-maximal young leaves alternate except for a sequence of maximal young leaves at the begininning and at the end. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - Michael Wallner, Apr 20 2017

			See A288950 and A288953.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.

Cf. A288953 (variation without initial sequence).
Cf. A177145 (variation without initial and final sequence).
Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A000032, A000246, A001879, A051577, A213527, A288950, A288952 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).

terms = 22; egf = 1/(3(1-z))(1/Sqrt[1-z^2] + (3z^3 - z^2 - 2z + 2)/((1-z)(1-z^2))) + O[z]^terms;
CoefficientList[egf, z] Range[0, terms-1]! (* Jean-François Alcover, Dec 13 2018 *)

E.g.f.: 1/(3*(1-z))*( 1/sqrt(1-z^2) + (3*z^3-z^2-2*z+2)/((1-z)*(1-z^2)) ).

A301423 Numbers k such that !k/(k-1) is prime, where !k = A000166(k) is the subfactorial of k.

Original entry on oeis.org

4, 5, 6, 11, 15, 44, 66, 168, 575, 1713

Offset: 1

Amiram Eldar, Mar 20 2018

Also numbers k such that A000255(k-2) is prime.
The corresponding primes are 3, 11, 53, 1468457, 34361893981, 22742406079421034331584846001936724930824184898296683, ...
a(11) > 35000. - Robert Price, Apr 14 2018

Cf. A000166, A000255.

Select[Range[2,100], PrimeQ[Subfactorial[#]/(#-1)] &]

isok(n) = (n != 1) && isprime(n!*sum(k=0, n, (-1)^k/k!)/(n-1)); \\ Michel Marcus, Mar 24 2018

A346189 a(n) is the number of permutations on [n] with no strong fixed points or small descents.

Original entry on oeis.org

0, 0, 2, 6, 34, 214, 1550, 12730, 116874, 1187022, 13219550, 160233258, 2100360778, 29610224590, 446789311934, 7185155686666, 122690711149290, 2217055354281582, 42269657477711198, 847998698508705834, 17857221256001240458, 393839277313540073230, 9078806210245773668990, 218340709713567352161226

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) = 6 permutations on [4] with no strong fixed points or small descents: {(2,3,4,1),(3,4,1,2),(4,1,2,3),(3,1,4,2),(2,4,1,3),(4,2,3,1)}.

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, A346198, A346199, A346204.

Python
```
See A346204.
```

For n > 3, a(n) = b(n) - b(n-1) - Sum{i=4..n}(a(i-1)*b(n-i)) where b(n) = A000255(n-1) and b(0) = 1.

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).

A346199 a(n) is the number of permutations on [n] with at least one strong fixed point and no small descents.

Original entry on oeis.org

1, 1, 1, 5, 19, 95, 569, 3957, 31455, 281435, 2799981, 30666153, 366646995, 4751669391, 66348304849, 992975080813, 15856445382119, 269096399032035, 4836375742967861, 91766664243841393, 1833100630242606203, 38452789552631651191, 845116020421125048153

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) = 5 permutations on [4] with strong fixed points but no small descents: {(1*, 2*, 3*, 4*), (1*, 3, 4, 2), (1*, 4, 2, 3), (2, 3, 1, 4*), (3, 1, 2, 4*)} where * marks strong fixed points.

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, A346198, A346204.

Python
```
See A346204.
```

a(n) = b(n-1) + Sum_{i=4..n} A346189(i-1)*b(n-i) where b(n) = A000255(n).

A370390 Number of permutations of [n] whose longest block is of length 2. A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions.

Original entry on oeis.org

0, 0, 1, 2, 10, 53, 334, 2428, 20009, 184440, 1881050, 21034905, 255967940, 3367720736, 47641219569, 721160081974, 11631770791362, 199159952915293, 3607908007376418, 68946510671942892, 1386140583681969289, 29247292475233307612, 646231776371742321826

Offset: 0

Seiichi Manyama, Feb 17 2024

nonn

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

Column k=2 of A184182.

Cf. A000255, A002628.

my(N=30, x='x+O('x^N)); concat([0, 0], Vec(sum(k=0, N, k!*x^k*(((1-x^2)/(1-x^3))^k-((1-x)/(1-x^2))^k))))

a(n) = A002628(n) - A000255(n-1).

G.f.: Sum_{k>=0} k! * x^k * ( ((1-x^2)/(1-x^3))^k - ((1-x)/(1-x^2))^k ).

A383341 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where A(n,k) = n! * Sum_{j=0..n} (-k)^(n-j) * binomial(j+k,j)/(n-j)!.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 6, 1, 1, 4, 11, 24, 1, 1, 5, 16, 53, 120, 1, 1, 6, 21, 88, 309, 720, 1, 1, 7, 26, 129, 568, 2119, 5040, 1, 1, 8, 31, 176, 897, 4288, 16687, 40320, 1, 1, 9, 36, 229, 1296, 7317, 36832, 148329, 362880, 1, 1, 10, 41, 288, 1765, 11296, 67365, 354688, 1468457, 3628800

Offset: 0

Seiichi Manyama, Apr 24 2025

			Square array begins:
    1,    1,    1,    1,     1,     1,     1, ...
    1,    1,    1,    1,     1,     1,     1, ...
    2,    3,    4,    5,     6,     7,     8, ...
    6,   11,   16,   21,    26,    31,    36, ...
   24,   53,   88,  129,   176,   229,   288, ...
  120,  309,  568,  897,  1296,  1765,  2304, ...
  720, 2119, 4288, 7317, 11296, 16315, 22464, ...

Columns k=0..4 give A000142, A000255, A052124, A383378, A383383.
Main diagonal gives A383379.
Cf. A295181.

a(n,k) = n!*sum(j=0, n, (-k)^(n-j)*binomial(j+k, j)/(n-j)!);

E.g.f. of column k: exp(-k*x) / (1-x)^(k+1).

A(0,k) = A(1,k) = 1; A(n,k) = n*A(n-1,k) + k*(n-1)*A(n-2,k).

A384907 Number of permutations of {1..n} with all distinct lengths of maximal anti-runs (not increasing by 1).

Original entry on oeis.org

1, 1, 1, 5, 17, 97, 587, 4291, 33109, 319967, 3106433, 35554459, 419889707, 5632467097, 77342295637, 1201240551077, 18804238105133, 328322081898745, 5832312989183807, 113154541564902427, 2229027473451951265, 47899977701182298255, 1037672943682453127645

Offset: 0

Gus Wiseman, Jun 21 2025

nonn

			The permutation (1,2,4,3,5,7,8,6,9) has maximal anti-runs ((1),(2,4,3,5,7),(8,6,9)), with lengths (1,5,3), so is counted under a(9).
The a(0) = 1 through a(4) = 17 permutations:
  ()  (1)  (2,1)  (1,3,2)  (1,2,4,3)
                  (2,1,3)  (1,3,2,4)
                  (2,3,1)  (1,4,2,3)
                  (3,1,2)  (1,4,3,2)
                  (3,2,1)  (2,1,3,4)
                           (2,1,4,3)
                           (2,3,1,4)
                           (2,4,1,3)
                           (2,4,3,1)
                           (3,1,4,2)
                           (3,2,1,4)
                           (3,2,4,1)
                           (3,4,2,1)
                           (4,1,3,2)
                           (4,2,1,3)
                           (4,3,1,2)
                           (4,3,2,1)

Christian Sievers, Table of n, a(n) for n = 0..449

For subsets instead of permutations we have A384177.
For strict partitions we have A384880, for runs A384178.
For partitions we have A384885, for runs A384884.
For runs instead of anti-runs we have A384891.
A010027 counts permutations by maximal anti-runs, for runs A123513.
A034839 counts subsets by number of maximal runs, for strict partitions A116674.
A098859 counts Wilf partitions (distinct multiplicities), complement A336866.
A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.
Cf. A000255, A044813, A072574, A242882, A325325, A328592, A329739, A351202, A356606, A384886, A384892.

Table[Length[Select[Permutations[Range[n]],UnsameQ@@Length/@Split[#,#2!=#1+1&]&]],{n,0,10}]

a(n)=if(n,my(b(n)=sum(i=0,n-1,(-1)^i*(n-i)!*binomial(n-1,i)), d=floor(sqrt(2*n)), p=polcoef(prod(i=1,n,1+x*y^i,1+O(y*y^n)*((1-x^(d+1))/(1-x))),n,y)); sum(i=1,d,b(n+1-i)*i!*polcoef(p,i)),1) \\ Christian Sievers, Jun 22 2025

a(n) = Sum_{k=1..n} ( T(n,k) * A000255(n-k) ) for n>=1, where T(n,k) is the number of compositions of n into k distinct parts (cf. A072574).

a(11) and beyond from Christian Sievers, Jun 22 2025

A052655 a(2) = 6, otherwise a(n) = n*n!.

Original entry on oeis.org

0, 1, 6, 18, 96, 600, 4320, 35280, 322560, 3265920, 36288000, 439084800, 5748019200, 80951270400, 1220496076800, 19615115520000, 334764638208000, 6046686277632000, 115242726703104000, 2311256907767808000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) = number of real non-singular (0,1)-matrices of order n having maximal permanent = A000255(n). Proof: [W. Edwin Clark and Richard Brualdi] The maximum permanent is per A where A has all 1's except for n-1 0's on the main diagonal. By Corollary 4.4 in the Brualdi et al. reference for n >= 4 any n X n (0,1)-matrix B with per B = per A can be obtained from A by permuting rows and columns. Since there are n ways to place the single 1 on the main diagonal and then n! ways to permute the distinct rows, a(n) = n*n! if n >=4. Direct computation shows this also holds for n = 1 and 3. - W. Edwin Clark, Nov 15 2003

			a(2)=6 because there are 6 (0,1)-matrices with nonzero determinant having permanent=1. See example in A089482. The (0,1)-matrix with maximal permanent=2 ((1,1),(1,1)) has det=0.

Richard A. Brualdi, John L. Goldwasser, T. S. Michael, Maximum permanents of matrices of zeros and ones, J. Combin. Theory Ser. A 47 (1988), 207-245.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 602

Cf. A000255. A089480 gives occurrence counts for permanents of non-singular (0, 1)-matrices, A051752 number of (0, 1)-matrices with maximal determinant A003432.

Essentially the same as A001563.

spec := [S,{S=Prod(Z,Union(Z,Prod(Sequence(Z),Sequence(Z))))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

Join[{0,1,6},Table[n*n!,{n,3,20}]] (* Harvey P. Dale, Apr 20 2012 *)

E.g.f.: x*(-2*x^2+x^3+x+1)/(-1+x)^2.

A078509 Number of permutations p of {1,2,...,n} such that p(i)-i != 1 and p(i)-i != 2 for all i.

Original entry on oeis.org

1, 1, 1, 1, 5, 23, 131, 883, 6859, 60301, 591605, 6405317, 75843233, 974763571, 13512607303, 200949508327, 3190881283415, 53880906258521, 964039575154409, 18217997734199113, 362584510633666621, 7580578211464070863, 166099466140519353035, 3806162403831340850651

Offset: 0

Vladimir Baltic, Vladeta Jovovic, Jan 05 2003

nonn

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

Cf. A000255, A055790, A001883, A001887, A075851, A075852.

a:= proc(n) option remember; `if`(n<4, 1,
      (n-1)*a(n-1) +(n-3)*a(n-2) +a(n-3))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 10 2014

a = DifferenceRoot[Function[{y, n}, {-y[n] - n y[n+1] - (n+2) y[n+2] + y[n+3] == 0, y[0] == 1, y[1] == 1, y[2] == 1, y[3] == 1}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

From Vladeta Jovovic, Jul 16 2007: (Start)
G.f.: x/(1+x)*Sum_{n>=0} (n+1)!*(x/(1+x)^2)^n.
a(n) = Sum_{k=1..n} (-1)^(n-k)*k!*binomial(n+k-2,2*k-2). (End)
a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Aug 25 2014

More terms from Alois P. Heinz, Jan 10 2014

cp's OEIS Frontend

A288954 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A301423 Numbers k such that !k/(k-1) is prime, where !k = A000166(k) is the subfactorial of k.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A346189 a(n) is the number of permutations on [n] with no strong fixed points or small descents.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

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

A346199 a(n) is the number of permutations on [n] with at least one strong fixed point and no small descents.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Formula

A370390 Number of permutations of [n] whose longest block is of length 2. A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A383341 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where A(n,k) = n! * Sum_{j=0..n} (-k)^(n-j) * binomial(j+k,j)/(n-j)!.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A384907 Number of permutations of {1..n} with all distinct lengths of maximal anti-runs (not increasing by 1).

Views

Author

Keywords

Examples