A135799 Second column (k=1) of triangle A134832 (circular succession numbers).

1, 0, 0, 4, 5, 48, 252, 1832, 14625, 132080, 1323168, 14576076, 175108661, 2278429216, 31920719820, 479088848976, 7669098865441, 130426934203296, 2348478878321248, 44633950190867220, 892899715052136645

Offset: 0

Author

Wolfdieter Lang, Jan 21 2008, Feb 22 2008

Keywords

• nonn
• easy

Comments

a(n) enumerates circular permutations of {1,2,...,n+1} with exactly one successor pair (i,i+1). Due to cyclicity also (n+1,1) is a successor pair.

The o.g.f. of this sequence seems to be the product of the o.g.f. for A000166 (derangements) by the fraction (1+2*x)/(1+x)^2 = 1 - x^2+ 2*x^3 - 3*x^4 + ... = 1 + sum( (-1)^i i x^(i+1), i=0..infinity) - Thomas Baruchel, Jan 08 2016

This correspond to the following transform: a(n) = b(n) - sum((-1)^(n + i) (n - i - 1)*b(i), (i=0..n-2)) - Olivier Gérard, Mar 05 2016

Examples

			a(3)=4 because the 4!/4 = 6 circular permutations of n=4 elements (1,2,3,4), (1,4, 3,2), (1,3,4,2),(1,2,4,3), (1,4,2,3) and (1,3,2,4) have 4,0,1,1, 1 and 1 successor pair(s), respectively.
		

References

• Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15), for k=1.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..448
• Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.

Crossrefs

Cf. A000757 (k=0 column), A134515 (k=2 column).

Programs

Mathematica

f[n_] := (-1)^n + Sum[(-1)^k*n!/((n - k)*k!), {k, 0, n - 1}]; a[n_, n_] = 1; a[n_, 0] := f[n]; a[n_, k_] := a[n, k] = n/k*a[n - 1, k - 1]; Table[a[n, 1], {n, 21}] (* Michael De Vlieger, Jan 09 2016, after Jean-François Alcover at A134832 *)

Formula

a(n) = (n+1)*A000757(n), n>=0.

E.g.f.: (d/dx) x*(1-log(1-x))/e^x.

O.g.f.: see comment section.