OFFSET
0,12
COMMENTS
Imagine seating n people numbered 1,2,...n around a circular table. There are only n!/n=(n-1)! inequivalent permutations due to the action of the cyclic group Z_n. a(n,k) enumerates such circular permutations which have precisely k successor pairs (i,i+1). Due to cyclicity (n,1) is also counted as successor pair. See the Charalambides reference.
This is an example of a Sheffer triangle of the Appell type denoted by (((1-log(1-x))/e^x,x). This explains the e.g.f. for column nr. k given below. For Sheffer a- and z-sequences see the W. Lang link under A006232.
REFERENCES
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15).
LINKS
G. C. Greubel, Table of n, a(n) for the first 50 rows
Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.
Wolfdieter Lang, First 10 rows and more.
FORMULA
a(n,k) = binomial(n,k)*a(n-k,0), k>=1 with a(n-k,0):=A000757(n), n>=0.
E.g.f. column k: ((1-log(1-x))/e^x)*(x^k)/k!, k>=0 (from the Sheffer property).
Recurrence a(n,k) = (n/k)*a(n-1,k-1), n >= k >= 1, (from the Sheffer a-sequences [1,0,0,...] due to the Appell type).
Recurrence a(n,0) = n*sum(z(j)*a(n-1,j),j=0..n-1), n>=1; a(0,0):=1, with the Sheffer z-sequence z(j):= A135808(j).
EXAMPLE
Triangle begins:
[1];
[0,1];
[0,0,1];
[1,0,0,1];
[1,4,0,0,1];
...
Recurrence: 15=a(6,2) = (6/2)*a(5,1)=3*5 (from Sheffer a-sequence).
Recurrence: 36=a(6,0)=6*(0+0+(1/3)*10+0+0+(8/3)*1) =6*6 (from Sheffer z-sequence).
MATHEMATICA
A000757[n_] := (-1)^n + Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]; a[n_, n_] = 1; a[n_, 0] := A000757[n]; a[n_, k_] := a[n, k] = n/k*a[n-1, k-1]; Table[a[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 02 2013 *)
CROSSREFS
KEYWORD
AUTHOR
Wolfdieter Lang, Jan 21 2008
STATUS
approved