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,4

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

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.

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.

Example

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.

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

Crossrefs

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

Sequence in context: A239860 A151486 A042383 * A226648 A335797 A041941

Adjacent sequences: A135796 A135797 A135798 * A135800 A135801 A135802

Keyword

nonn,easy

Author

Wolfdieter Lang, Jan 21 2008, Feb 22 2008

Status

approved