A134832 Triangle of succession numbers for circular permutations.

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

Offset: 0

Author

Wolfdieter Lang, Jan 21 2008

Keywords

• nonn
• easy
• tabl

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 no. k given below. For Sheffer a- and z-sequences see the W. Lang link under A006232.

Examples

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

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.

Crossrefs

Cf. A000142 (row sums are factorials), A134833 (alternating row sums).

Programs

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

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