Anthony Susevski - cp's OEIS frontend

User: Anthony Susevski

Anthony Susevski has authored 1 sequences.

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

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

User: Anthony Susevski

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