login
Triangle of succession numbers for circular permutations.
13

%I #22 Aug 20 2017 11:53:37

%S 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,

%T 168,35,35,0,0,1,1625,1832,1008,448,70,56,0,0,1,13208,14625,8244,3024,

%U 1008,126,84,0,0,1,120288,132080,73125,27480,7560,2016,210,120,0,0,1

%N Triangle of succession numbers for circular permutations.

%C 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.

%C 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.

%D Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15).

%H G. C. Greubel, <a href="/A134832/b134832.txt">Table of n, a(n) for the first 50 rows</a>

%H Bhadrachalam Chitturi and Krishnaveni K S, <a href="https://arxiv.org/abs/1601.04469">Adjacencies in Permutations</a>, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.

%H Wolfdieter Lang, <a href="/A134832/a134832.pdf">First 10 rows and more.</a>

%F a(n,k) = binomial(n,k)*a(n-k,0), k>=1 with a(n-k,0):=A000757(n), n>=0.

%F E.g.f. column k: ((1-log(1-x))/e^x)*(x^k)/k!, k>=0 (from the Sheffer property).

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

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

%e Triangle begins:

%e [1];

%e [0,1];

%e [0,0,1];

%e [1,0,0,1];

%e [1,4,0,0,1];

%e ...

%e Recurrence: 15=a(6,2) = (6/2)*a(5,1)=3*5 (from Sheffer a-sequence).

%e Recurrence: 36=a(6,0)=6*(0+0+(1/3)*10+0+0+(8/3)*1) =6*6 (from Sheffer z-sequence).

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

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

%K nonn,easy,tabl

%O 0,12

%A _Wolfdieter Lang_, Jan 21 2008