A335391 -id:A335391 - cp's OEIS frontend

A102761 Same as A000179, except that a(0) = 2.

2, -1, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123

Offset: 0

N. J. A. Sloane, Apr 04 2010, following a suggestion from Vladimir Shevelev

For any integer n>=0, 2 * Integral_{t=-2..2} T_n(t/2)*exp(-t)*dt = 4 * Integral_{z=-1..1} T_n(z)*exp(-2*z)*dz = a(n)*exp(2) - A300484(n)*exp(-2). - Max Alekseyev, Mar 08 2018

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.

Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Λ_n^3 and Λ_n(α,β,γ), arXiv:1104.4051 [math.CO], 2011.

Row m=2 in A300481.
Cf. A000023, A000179, A000186, A300484.
A000179, A102761, and A335700 are all essentially the same sequence but with different conventions for the initial terms a(0) and a(1). - N. J. A. Sloane, Aug 06 2020

{ A102761(n) = subst( serlaplace( 2*polchebyshev(n, 1, (x-2)/2)), x, 1); } \\ Max Alekseyev, Mar 06 2018

a(n) = Sum_{i=0..n} A127672(n,i) * A000023(i). - Max Alekseyev, Mar 06 2018
a(n) = A300481(2,n) = A300480(-2,n). - Max Alekseyev, Mar 06 2018
a(n) = A335391(0,n) (Touchard). - William P. Orrick, Aug 29 2020

Changed a(0)=2 (making the sequence more consistent with existing formulae) by Max Alekseyev, Mar 06 2018

A000270 For n >= 2, a(n) = b(n+1)+b(n)+b(n-1), where the b(i) are the ménage numbers A000179; a(0)=a(1)=1.

Original entry on oeis.org

1, 1, 0, 3, 16, 95, 672, 5397, 48704, 487917, 5373920, 64547175, 839703696, 11762247419, 176509466560, 2825125339305, 48040633506048, 864932233294681, 16436901752820288, 328791893988472843, 6905593482159150480, 151941269284478380119, 3495011687269591273312

Offset: 0

N. J. A. Sloane

The old name (in the 1973 Handbook) was "Discordant permutations".
For n >= 2, a(n) is the number of permutations of [n+1] discordant with both the identity permutation and a permutation consisting of one 1-cycle and one n-cycle. - William P. Orrick, Aug 03 2020
The term a(0) = 1, which comes from the table on page 118 of Touchard's 1953 Scripta Math. paper is possibly in error. Equation (3) in Touchard's 1934 Comptes Rendus article produces a(0) = 0, and the formulas following equation (30) on page 117 of his 1953 paper give incorrect results unless a(0) = 0. - William P. Orrick, Aug 07 2020

			From _William P. Orrick_, Aug 07 2020: (Start)
There are no permutations of 123 discordant with both 123 and 132, so a(2) = 0; the permutations of 1234 discordant with both 1234 and 1342 are 2413, 3421, and 4123, so a(3) = 3.
Touchard (1953), p. 117, writes a(4) + a(0) for the number of permutations discordant with 12345 and 13254. There are 16 = 4*2*2 such permutations, obtained by letting (x,y) be one of (2,3), (3,2), (4,5), (5,4), then placing x in position 1, and finally, if (x,y) is (2,3) or (3,2), placing 4, 5 (in either order) in positions 2, 3 while placing 1, y (in either order) in positions 4, 5, or, if (x,y) is (4,5) or (5,4), placing 1, y (in either order) in positions 2, 3 while placing 2, 3 (in either order) in positions 4, 5. Hence Touchard's expression gives the correct result, assuming a(0) = 0.
(End)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 109-119.

Alois P. Heinz, Table of n, a(n) for n = 0..175
Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See 33.
J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.

Cf. A000179, A335391.

a:= n-> coeftayl(1+(1-x)/(1+x)*add(k*k!*(x/(1+x)^2)^k, k=0..n), x=0, n):
seq(a(n), n=0..25); # Alois P. Heinz, Sep 24 2008
# second Maple program:
A000270 := proc(n) if n <= 1 then 1 else n * add((-1)^(n-s)*s!*binomial(s+n-1, 2*s-1), s=1..n) fi end; seq(A000270(n), n=0..30);  # Mark van Hoeij, May 12 2013

max = 20; f[x_] := 1+(1-x)/(1+x)*Sum[ n*n!*(x/(1+x)^2)^n, {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Dec 09 2011, after Vladeta Jovovic *)

G.f.: 1+(1-x)/(1+x)*Sum_{n>=0} n*n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 29 2007
D-finite with recurrence: (n-3)*a(n) = (n-3)*n*a(n-1) + (n-3)*n*a(n-2) + n*a(n-3). - Vaclav Kotesovec, Mar 15 2014
a(n) ~ (n+1)! / exp(2). - Vaclav Kotesovec, Mar 15 2014
a(n) = A335391(1,n) for n >= 1. - William P. Orrick, Aug 03 2020

More terms from Alois P. Heinz, Sep 24 2008

Entry revised by N. J. A. Sloane, Jul 23 2020. Thanks to William P. Orrick for suggesting that this sequence needed a better definition. The initial terms a(0)=a(1)=1 have been preserved in order to agree with the sequence in Touchard's 1953 paper.

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

A102761 Same as A000179, except that a(0) = 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A000270 For n >= 2, a(n) = b(n+1)+b(n)+b(n-1), where the b(i) are the ménage numbers A000179; a(0)=a(1)=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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