|
|
A134832
|
|
Triangle of succession numbers for circular permutations.
|
|
13
|
|
|
1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 4, 0, 0, 1, 8, 5, 10, 0, 0, 1, 36, 48, 15, 20, 0, 0, 1, 229, 252, 168, 35, 35, 0, 0, 1, 1625, 1832, 1008, 448, 70, 56, 0, 0, 1, 13208, 14625, 8244, 3024, 1008, 126, 84, 0, 0, 1, 120288, 132080, 73125, 27480, 7560, 2016, 210, 120, 0, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
Cf. A000142 (row sums are factorials), A134833 (alternating row sums).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|