login
Tanimoto triangle read by rows: T(n,k) = number of "parity-alternating permutations" (PAPS) of n symbols with k ascents.
3

%I #27 Nov 07 2017 03:04:28

%S 1,1,1,1,0,1,1,3,3,1,1,2,6,2,1,1,9,26,26,9,1,1,8,39,48,39,8,1,1,23,

%T 165,387,387,165,23,1,1,22,228,674,1030,674,228,22,1,1,53,860,4292,

%U 9194,9194,4292,860,53,1,1,52,1149,7136,20738,28248,20738,7136,1149,52,1

%N Tanimoto triangle read by rows: T(n,k) = number of "parity-alternating permutations" (PAPS) of n symbols with k ascents.

%C A permutation is a parity-alternating permutation (PAP) if its entries take even and odd integers alternately (examples: 436125, 563412 or 7216345). When n is an odd integer, odd entries must appear at both ends of PAPs. T(n,k) = the number of PAPs of {1,2,...,n} with exactly k ascents. Row sums = 2*((n/2)!)^2 if n is even and ((n+1)/2)!*((n-1)/2)! if n is odd.

%C Arises in combinatorial analysis of signed Eulerian numbers and parity-alternate permutations. This table is the first of three tables on p. 4 of the Tanimoto reference.

%H Alois P. Heinz, <a href="/A125300/b125300.txt">Rows n = 1..27, flattened</a>

%H Shinji Tanimoto, <a href="http://arXiv.org/abs/math/0612135">Alternate Permutations and Signed Eulerian Numbers</a>, math.CO/0612135, Ann. Comb. 14 (2010), 355.

%F T(n,k) = T(n,n-k-1).

%e Triangle begins:

%e n=1.|.1

%e n=2.|.1....1

%e n=3.|.1....0....1

%e n=4.|.1....3....3....1

%e n=5.|.1....2....6....2....1

%e n=6.|.1....9...26...26....9....1

%e n=7.|.1....8...39...48...39....8....1

%e n=8.|.1...23..165..387..387..165...23....1

%e n=9.|.1...22..228..674.1030..674..228...22....1

%e n=10|.1...53..860.4292.9194.9194.4292..860...53....1

%e Examples of parity-alternating permutations of n=5 and their number of rises k are [1,2,3,4,5] (k=4, only rises), [1,2,5,4,3] (k=2: 1->2 and 2->5), [1,4,3,2,5] (k=2: 1->4 and 2->5). The T(n=5,k=1)=2 parity-alternating permutations with k=1 rise are [3,2,5,4,1] and [5,2,1,4,3].

%p isPAP := proc(per) local i ; for i from 2 to nops(per) do if ( op(i,per) mod 2 ) = (op(i-1,per) mod 2 ) then RETURN(false) ; fi ; od : RETURN(true) ; end: ascents := proc(per) local i, asc ; asc :=0 ; for i from 2 to nops(per) do if op(i,per) > op (i-1,per) then asc := asc+1 : fi ; od : RETURN(asc) ; end:

%p A125300row := proc(n) local per,resul, asc,thisp,p,i,row ; row := array(0..n-1) ; for i from 0 to n-1 do row[i] := 0 : od ; per := combinat[permute](n) ; for p from 1 to nops(per) do asc := 0 ; thisp := op(p,per) ; if isPAP(thisp) then asc := ascents(thisp) ; row[asc] := row[asc]+1 ; fi ; od ; RETURN(row) : end: for n from 2 to 10 do r := A125300row(n) ; for k from 0 to n-1 do print(r[k]) ; od : od : # _R. J. Mathar_, Dec 12 2006

%t isPAP[per_] := (For[i = 2, i <= Length[per], i++, If [Mod[per[[i]], 2] == Mod[per[[i - 1]], 2], Return[False] ] ]; True);

%t ascents[per_] := (asc = 0; For[i = 2, i <= Length[per], i++, If[per[[i]] > per[[i - 1]], asc ++] ]; asc);

%t A125300row[n_] := (row = Range[0, n - 1]; For[i = 0, i <= n - 1, i++, row[[i]] = 0]; per = Permutations[Range[n]]; For[p = 1, p <= Length[per], p++, asc = 0; thisp = per[[p]]; If[isPAP[thisp], asc = ascents[thisp]; row[[asc]] += 1]]; row);

%t Join[{1}, Reap[For[n = 2, n <= 10, n++, r = A125300row[n]; For[k = 0, k <= n - 1, k++, Print[r[[k]]]; Sow[r[[k]]]]]][[2, 1]]] (* _Jean-François Alcover_, Nov 07 2017, after _R. J. Mathar_'s Maple code *)

%Y Cf. A008292 = Triangle of Eulerian numbers T(n, k) read by rows, A049061 = Triangle a(n, k) (1<=k<=n) of signed Eulerian numbers.

%Y Row sums give: A092186. - _Alois P. Heinz_, Nov 18 2013

%K nonn,tabl

%O 1,8

%A _Jonathan Vos Post_, Dec 08 2006, Dec 11 2006

%E Corrected by _R. J. Mathar_, Dec 12 2006

%E Edited by _N. J. A. Sloane_, Dec 21 2006

%E Replaced arXiv URL by non-cached version - _R. J. Mathar_, Oct 30 2009

%E More terms from _Alois P. Heinz_, Nov 18 2013