A055790 -id:A055790 - cp's OEIS frontend

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

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

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

A105927 Let d(n) = A000166(n); then a(n) = ( (n^2+n-1)d(n) + (-1)^(n-1)(n-1) )/2.

Original entry on oeis.org

0, 0, 2, 12, 84, 640, 5430, 50988, 526568, 5940576, 72755370, 961839340, 13656650172, 207316760352, 3351430059614, 57487448630220, 1042952206111440, 19954639072648768, 401578933206288978, 8480263630552747596, 187505565234912994340, 4332318322289242716480

Offset: 0

N. J. A. Sloane, Apr 27 2005

nonn

Wang, Miska, & Mező call these 2-derangement numbers.
Number of permutations p of [n] such that p(k) = k+2 for exactly two k in the range 0Vladeta Jovovic, Dec 14 2007
Number of derangements of the multiset {0,0,1,2,...,n}.  For example a(3)=12 because we have: {1,2,0,3,0}, {1,2,3,0,0}, {1,3,0,0,2}, {1,3,2,0,0}, {2,1,0,3,0}, {2,1,3,0,0}, {2,3,0,0,1}, {2,3,0,1,0}, {3,1,0,0,2}, {3,1,2,0,0}, {3,2,0,0,1}, {3,2,0,1,0}. - Geoffrey Critzer, Jun 02 2014
Number of derangements of a set of n + 2 elements such that the first two elements belong to distinct cycles. - Istvan Mezo, Apr 05 2017

P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 108.

Alois P. Heinz, Table of n, a(n) for n = 0..300
C.-Y. Wang, P. Miska, I. Mező, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.

Cf. A000153, A018934, A055790.

a:= proc(n) option remember; `if`(n<3, n*(n-1),
       n*(n-1)*(a(n-1)+a(n-2))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 03 2014

Table[(Subfactorial[n+2]-2Subfactorial[n+1]-Subfactorial[n])/2,{n,0,21}] (* Geoffrey Critzer, Jun 02 2014 *)

s(n) = if( n<1, 1, n * s(n-1) + (-1)^n);
a(n) = (s(n + 2) - 2*s(n + 1) - s(n))/2; \\ Indranil Ghosh, Apr 06 2017

a(n) = n*(n-1)*(a(n-1) + a(n-2))/(n-2) for n >= 3, a(n) = n*(n-1) for n < 3. - Alois P. Heinz, Jun 03 2014
a(n) ~ sqrt(Pi/2) * n^(n+5/2) / exp(n+1). - Vaclav Kotesovec, Sep 05 2014
a(n) = (n^2 + n + 1) * n!/e + O(1). - Charles R Greathouse IV, Apr 07 2017

A116854 First differences of the rows in the triangle of A116853, starting with 0.

Original entry on oeis.org

1, 1, 1, 3, 1, 2, 11, 3, 4, 6, 53, 11, 14, 18, 24, 309, 53, 64, 78, 96, 120, 2119, 309, 362, 426, 504, 600, 720, 16687, 2119, 2428, 2790, 3216, 3720, 4320, 5040, 148329, 16687, 18806, 21234, 24024, 27240, 30960, 35280, 40320, 1468457, 148329, 165016, 183822, 205056, 229080, 256320, 287280, 322560, 362880

Offset: 1

Gary W. Adamson, Feb 24 2006

Row n contains the first differences of row n of A116853, starting with T(n,1) = A116853(n,1) - 0.

As in A116853, 0! = 1 is omitted here. - Georg Fischer, Mar 23 2019

			First few rows of the triangle are:
[1]    1;
[2]    1,   1;
[3]    3,   1,   2;
[4]   11,   3,   4,   6;
[5]   53,  11,  14,  18,  24;
[6]  309,  53,  64,  78,  96, 120;
[7] 2119, 309, 362, 426, 504, 600, 720;
...
For example, row 4 (11, 3, 4, 6) are first differences along row 4 of A116853: ((0), 11, 14, 18, 24).

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened

Cf. A000255, A116853.

Cf. A000142 (row sums), A033815 (central terms), A047920, A068106 (with 0!), A055790 (column k=3), A277609 (k=4), A277563 (k=5), A280425 (k=6).

a116854 n k = a116854_tabl !! (n-1) !! (k-1)
a116854_row n = a116854_tabl !! (n-1)
a116854_tabl = [1] : zipWith (:) (tail $ map head tss) tss
               where tss = a116853_tabl
-- Reinhard Zumkeller, Aug 31 2014

A116853 := proc(n,k) option remember ; if n = k then n! ; else procname(n,k+1)-procname(n-1,k) ; end if; end proc:
A116854 := proc(n,k) if k = 1 then A116853(n,1) ; else A116853(n,k) -A116853(n,k-1) ; end if; end proc:
seq(seq(A116854(n,k),k=1..n),n=1..15) ; # R. J. Mathar, Mar 27 2010

rows = 10;
rr = Range[rows]!;
dd = Table[Differences[rr, n], {n, 0, rows - 1}];
T = Array[t, {rows, rows}];
Do[Thread[Evaluate[Diagonal[T, -k+1]] = dd[[k, ;; rows-k+1]]], {k, rows}];
Table[({0}~Join~Table[t[n, k], {k, 1, n}]) // Differences, {n, 1, rows}] // Flatten (* Jean-François Alcover, Dec 21 2019 *)

T(n,k) = A116853(n,k) - A116853(n,k-1) if k>1.
T(n,1) = A116853(n,1) = A000255(n-1).
Sum_{k=1..n} T(n,1) = n! = A000142(n).

Definition made concrete and sequence extended by R. J. Mathar, Mar 27 2010

A284844 Number of permutations on [n+3] with no circular 3-successions.

Original entry on oeis.org

16, 70, 384, 2534, 19424, 169254, 1650160, 17784646, 209855856, 2689946246, 37210700576, 552433526310, 8759992172224, 147751562532454, 2641055171379984, 49869279287055494, 991843699479853520, 20724299315437752006, 453861919477920665536, 10395594941305558134886

Offset: 1

Enrique Navarrete, Apr 03 2017

nonn

Define a circular k-succession in a permutation p on [n] as either a pair p(i),p(i+1) if p(i+1)=p(i)+k, or as the pair p(n),p(1) if p(1)=p(n)+k. If we let d*(n,k) be the number of permutations on [n] that avoid substrings (j,j+k), 1 <= j <= n, k=3, i.e., permutations with no circular 3-succession, then a(n) counts d*(n+3,3).

For example, for n=1, the permutations in S4 that contain the substring {14} in circular 3-succession are 1423, 1432, 2143, 2314, 3142, 3214, 4231, 4321, therefore d*(4,3) consists of the complementary permutations in S4, and a(1)=16.

			a(2)=70 since there are 70 permutations in S5 with no circular 3-succession, i.e., permutations that avoid substrings {14,25} such as 25134 or 51342.

Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.

A284844 := proc(n)
    local j;
    add( (-1)^j*binomial(n,j)*(n-j+2)!,j=0..n) ;
    %*(n+3) ;
end proc:
seq(A284844(n),n=1..20) ; # R. J. Mathar, Jul 15 2017

a[n_] := ((n+3)*((n*(n+5)+5)*Subfactorial[n+2]+(-1)^(n+1)*(n+1)))/((n+2)*(n+1));
Array[a, 20] (* Jean-François Alcover, Dec 09 2017 *)

a(n) = (n+3)* Sum_{j=0..n} (-1)^j*binomial(n,j)*(n-j+2)!.

Conjecture: a(n) = (n+3)*A055790(n+1). - R. J. Mathar, Jul 15 2017

A331007 Number of derangements of a set of n elements where 2 specific elements cannot appear in each other's positions.

Original entry on oeis.org

1, 0, 0, 0, 4, 24, 168, 1280, 10860, 101976, 1053136, 11881152, 145510740, 1923678680, 27313300344, 414633520704, 6702860119228, 114974897260440, 2085904412222880, 39909278145297536, 803157866412577956, 16960527261105495192, 375011130469825988680, 8664636644578485432960

Offset: 0

Anthony Susevski, Jan 06 2020

nonn

The sequence was originally generated using Python to exhaustively enumerate permutations describing the secret Santa setup for n people where 2 specific people cannot receive each other's names. Derangements, A000166, describe a restriction-free secret Santa setup and are related to this sequence.
If a derangement is not included, then both of the two friends must be in the same permutation cycle and must be adjacent in this cycle. The second friend can be either immediately before or immediately after the first giving two possibilities (except when the cycle contains only the two friends). These considerations lead to a formula for a(n). - Andrew Howroyd, Jan 07 2020
There are three distinct types of derangement that must be excluded, (1) friend 1 and friend 2 receive each other's names, (2) friend 2 receives friend 1's name but friend 1 does not receive friend 2's name, and (3) friend 1 receives friend 2's name but friend 2 does not receive friend 1's name. - William P. Orrick, Jul 25 2020

			For a group of 4 friends, the number of possible permutations of their names in a secret Santa draw in which neither friend number 1 nor friend number 2 can draw the other one's name is 4. The permutations are 3412, 3421, 4312, 4321.
For a group of 6 friends, the number of possible permutations of their names in a secret Santa draw in which neither friend number 1 nor friend number 2 can draw the other one's name is 168.

J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.

Cf. A000166 (number of derangements), A055790, A335391.

f:=gfun:-rectoproc({(n-4)*a(n) = (n-2)*(n-3)*(a(n-1) + a(n-2)), a(0)=1, a(1)=0, a(2)=0, a(3)=0, a(4)=4}, a(n), remember): map(f,[$0..23]); # Georg Fischer, Jun 12 2021

f[n_] := If[n < 0, 0, Subfactorial[n]];
a[n_] := f[n] + f[n-2] - 2 Sum[Binomial[n-2, k]*f[k]*(n-k-2)!, {k, 0, n-2}];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Sep 27 2022, after Andrew Howroyd *)

a(n) = {if(n<=1, n==0, b(n) + b(n-2) - 2*sum(k=0, n-2, binomial(n-2,k)*b(k)*(n-k-2)!))} \\ Andrew Howroyd, Jan 07 2020

def permutation(n):
    permutations = [[]]
    for i in range(1,n + 1):
        new_permutations = []
        for p in permutations:
            for j in range(0, len(p) + 1):
                n = p.copy()
                n.insert(j, i)
                new_permutations.append(n)
        permutations = new_permutations
    return permutations
def check_secret_santa(permutations):
    num_valid = 0
    for perm in permutations:
        valid = True
        for i, p in enumerate(perm):
            if i == p - 1 or (i == 0 and p == 2) or (i == 1 and p == 1):
                valid = False
                break
        if valid:
            num_valid += 1
    return num_valid

a(n) = A000166(n) + A000166(n-2) - 2*Sum_{k=0, n-2} binomial(n-2,k)*A000166(k)*(n-k-2)! for n >= 2. - Andrew Howroyd, Jan 07 2020
a(n) = (n-3)*(n-2)*A055790(n-3) for n > 2. - Jon E. Schoenfield, Jan 07 2020
a(n) = !n - 2 * !(n-1) - !(n-2) for n >= 2, where !n = A000166(n). - William P. Orrick, Jul 25 2020
a(n) = A335391(n-2, 2) for n >= 2 (Touchard). - William P. Orrick, Jul 25 2020
D-finite with recurrence: (n-4)*a(n) = (n-2)*(n-3)*(a(n-1) + a(n-2)), a(0)=1, a(1)=0, a(2)=0, a(3)=0, a(4)=4. - Georg Fischer, Jun 12 2021

Terms a(11) and beyond from Andrew Howroyd, Jan 07 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A105927 Let d(n) = A000166(n); then a(n) = ( (n^2+n-1)*d(n) + (-1)^(n-1)*(n-1) )/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A116854 First differences of the rows in the triangle of A116853, starting with 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A284844 Number of permutations on [n+3] with no circular 3-successions.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

Formula

A331007 Number of derangements of a set of n elements where 2 specific elements cannot appear in each other's positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A105927 Let d(n) = A000166(n); then a(n) = ( (n^2+n-1)d(n) + (-1)^(n-1)(n-1) )/2.