A001909 -id:A001909 - cp's OEIS frontend

A277563 Fifth column of Euler's difference table in A068106.

0, 0, 0, 24, 96, 504, 3216, 24024, 205056, 1965624, 20886576, 243511704, 3089233056, 42351635064, 623815221456, 9823096307544, 164655323578176, 2926840752827064, 54988308080981616, 1088680464831056664, 22653422225916839136, 494229434646381585144, 11280809162286897977616

Offset: 1

Enrique Navarrete, Dec 03 2016

nonn

This is 24 times the sequence A001909.
For n >= 5, this is the number of permutations that avoid substrings j(j+4), 1 <= j <= n-4.
For n>=5, the number of circular permutations (in cycle notation) on [n+1] that avoid substrings (j,j+5), 1<=j<=n-4.  For example, for n=5, there are 96 circular permutations in S6 that avoid the substring {16}. Note that each of these circular permutations represent 6 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 22 2017

			a(6) = 504 since there are 504 permutations in S6 that avoid the substrings {15,26}.

Indranil Ghosh, Table of n, a(n) for n = 1..400
Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.
Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.

Cf. A001909, A068106.

Array[Sum[(-1)^j*Binomial[# - 4, j] (# - j)!, {j, 0, # - 4} ] &, 23] (* Michael De Vlieger, Dec 06 2016 *)

For n>=5: a(n) = Sum_{j=0..n-4} (-1)^j*binomial(n-4,j)*(n-j)!.

a(n) ~ n!/e.

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

A090014 Permanent of (0,1)-matrix of size n X (n+d) with d=4 and n-1 zeros not on a line.

Original entry on oeis.org

5, 25, 155, 1135, 9545, 90445, 952175, 11016595, 138864365, 1893369505, 27756952355, 435287980375, 7269934161905, 128812336516885, 2413131201408695, 47652865538001595, 989254278781162325

Offset: 1

Jaap Spies, Dec 13 2003

Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.

Indranil Ghosh, Table of n, a(n) for n = 1..445
Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. Algebra and its Applic. 373 (2003), pp. 197-210.

a(n) = A001909(n-1) + A001909(n), a(1)=5

Cf. A000255, A000153, A000261, A001909, A001910, A090010, A055790, A090012-A090016.

f[x_] := x*HypergeometricPFQ[{1, 5}, {}, x/(x+1)]/(x+1); Total /@ Partition[ CoefficientList[ Series[f[x], {x, 0, 18}], x], 2, 1] // Rest (* Jean-François Alcover, Nov 12 2013, after A001909 and Mark van Hoeij *)
t={5,25};Do[AppendTo[t,(n+3)*t[[-1]]+(n-2)*t[[-2]]],{n,3,17}];t (* Indranil Ghosh, Feb 21 2017 *)

a(n) = (n+3)*a(n-1) + (n-2)*a(n-2), a(1)=5, a(2)=25.

a(n) ~ exp(-1) * n! * n^4 / 24. - Vaclav Kotesovec, Nov 30 2017

Corrected by Jaap Spies, Jan 26 2004

A247490 Square array read by antidiagonals: A(k, n) = (-1)^(n+1)* hypergeom([k, -n+1], [], 1) for n>0 and A(k,0) = 0 (n>=0, k>=1).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 2, 3, 2, 0, 1, 3, 7, 11, 9, 0, 1, 4, 13, 32, 53, 44, 0, 1, 5, 21, 71, 181, 309, 265, 0, 1, 6, 31, 134, 465, 1214, 2119, 1854, 0, 1, 7, 43, 227, 1001, 3539, 9403, 16687, 14833, 0, 1, 8, 57, 356, 1909, 8544, 30637, 82508, 148329, 133496

Offset: 0

Peter Luschny, Sep 20 2014

			k\n
[1], 0, 1, 0,  1,   2,    9,   44,    265,      1854, ...  A000166
[2], 0, 1, 1,  3,  11,   53,   309,  2119,     16687, ...  A000255
[3], 0, 1, 2,  7,  32,  181,  1214,  9403,     82508, ...  A000153
[4], 0, 1, 3, 13,  71,  465,  3539,  30637,   296967, ...  A000261
[5], 0, 1, 4, 21, 134, 1001,  8544,  81901,   870274, ...  A001909
[6], 0, 1, 5, 31, 227, 1909, 18089, 190435,  2203319, ...  A001910
[7], 0, 1, 6, 43, 356, 3333, 34754, 398959,  4996032, ...  A176732
[8], 0, 1, 7, 57, 527, 5441, 61959, 770713, 10391023, ...  A176733
The referenced sequences may have a different offset or other small deviations.

Cf. A000166, A000255, A000153, A000261, A001909, A001910, A176732 - A176736.

A := (k,n) -> `if`(n<2,n,hypergeom([k,-n+1],[],1)*(-1)^(n+1));
seq(print(seq(round(evalf(A(k,n),100)), n=0..8)), k=1..8);

from mpmath import mp, hyp2f0
mp.dps = 25; mp.pretty = True
def A247490(k, n):
    if n < 2: return n
    if k == 1 and n == 2: return 0  # (failed to converge)
    return int((-1)^(n+1)*hyp2f0(k, -n+1, 1))
for k in (1..8): print([k], [A247490(k, n) for n in (0..8)])

A336246 Array read by upwards antidiagonals: T(n,k) is the number of ways to place n persons on different seats such that each person number p, 1 <= p <= n, differs from the seat number s(p), 1 <= s(p) <= n+k, k >= 0.

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 9, 11, 7, 3, 44, 53, 32, 13, 4, 265, 309, 181, 71, 21, 5, 1854, 2119, 1214, 465, 134, 31, 6, 14833, 16687, 9403, 3539, 1001, 227, 43, 7, 133496, 148329, 82508, 30637, 8544, 1909, 356, 57, 8, 1334961, 1468457, 808393, 296967, 81901, 18089, 3333, 527, 73, 9

Offset: 1

Gerhard Kirchner, Jul 19 2020

T(n,0) = !n (subfactorial) is the number of derangements or fixed-point-free permutations, see A000166(n) below: n persons are placed on n seats such that no person sits on a seat with the same number. The generalization of a permutation is a variation (n persons and n+k seats such that k seats remain free). In this sense, T(n,k) is the number of fixed-point-free variations. I am rather sure that such variations have been examined, but I cannot find a reference.
Some subsequences T(n,k) with k=const:
T(n,0) = A000166(n);   T(n,1) = A000255(n);   T(n,2) = A000153(n-1);
T(n,3) = A000261(n-1); T(n,4) = A001909(n-3); T(n,5) = A001910(n-4);
T(n,6) = A176732(n);   T(n,7) = A176733(n);   T(n,8) = A176734(n);
T(n,9) = A176735(n);   T(n,10) = A176736(n).

			For k=1, the n-tuples of seat numbers are:
- for n=1: 2 => T(1,1) = 1.
- for n=2: 21, 23, 31 => T(2,1) = 3,
     21: person 1 sits on seat 2 and vice versa.
     A counterexample is 13 because person 1 would sit on seat 1.
- for n=3: 214,231,234,241,312,314,341,342,412,431,432 => T(3,1) = 11.
Array begins:
   0   1    2    3    4 ...
   1   3    7   13   21 ...
   2  11   32   71  134 ...
   9  53  181  465 1001 ...
  44 309 1214 3539 8544 ...
  .. ... .... .... ....

Gerhard Kirchner, Fixed-point-free variations

Cf. A000166, A000255, A000153, A000261, A001909, A001910, A176732, A176733, A176734, A176735, A176736.

block(nr: 0, k: -1,  mmax: 55,
    /*First mmax terms are returned, recurrence used*/
   a: makelist(0, n, 1, mmax),
   while nr

block(n: 1, k: 0,  mmax: 55,
    /*First mmax terms are returned, explicit formula used*/
   a: makelist(0, n, 1, mmax),
   for m from 1 thru mmax do (su: 0,
     for r from 0 thru n do su: su+(-1)^r*binomial(n,r)*(n+k-r)!/k!,
     a[m]: su, if n=1 then (n: k+2, k: 0) else (n: n-1, k: k+1)),
  return(a));

T(n,k) = (n+k-1)*T(n-1,k) + (n-1)*T(n-2,k) for n >= 2, k >= 0 with T(0,k)=1 and T(1,k)=k.
For n=0, there is one empty variation. T(0,k) is used for the recurrence only, not in the table. For n=1, the person can be placed on seat number 2..k+1 (if k > 0).
You also find the recurrence in the formula section of A000166 (k=0) and in the name section of the other sequences listed above (1 <= k <= 10). Some sequences have a different offset.
T(n,k) = Sum_{r=0..n} (-1)^r*binomial(n,r)*(n+k-r)!/k!.
Proofs see link.

cp's OEIS Frontend

A277563 Fifth column of Euler's difference table in A068106.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A090014 Permanent of (0,1)-matrix of size n X (n+d) with d=4 and n-1 zeros not on a line.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A247490 Square array read by antidiagonals: A(k, n) = (-1)^(n+1)* hypergeom([k, -n+1], [], 1) for n>0 and A(k,0) = 0 (n>=0, k>=1).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Sage

A336246 Array read by upwards antidiagonals: T(n,k) is the number of ways to place n persons on different seats such that each person number p, 1 <= p <= n, differs from the seat number s(p), 1 <= s(p) <= n+k, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maxima

Maxima

Formula