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

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, 165, 387, 387, 165, 23, 1, 1, 22, 228, 674, 1030, 674, 228, 22, 1, 1, 53, 860, 4292, 9194, 9194, 4292, 860, 53, 1, 1, 52, 1149, 7136, 20738, 28248, 20738, 7136, 1149, 52, 1

Offset: 1

Author

Jonathan Vos Post, Dec 08 2006, Dec 11 2006

Keywords

• nonn
• tabl

Comments

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.

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.

Examples

			Triangle begins:
n=1.|.1
n=2.|.1....1
n=3.|.1....0....1
n=4.|.1....3....3....1
n=5.|.1....2....6....2....1
n=6.|.1....9...26...26....9....1
n=7.|.1....8...39...48...39....8....1
n=8.|.1...23..165..387..387..165...23....1
n=9.|.1...22..228..674.1030..674..228...22....1
n=10|.1...53..860.4292.9194.9194.4292..860...53....1
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].
		

Links

• Alois P. Heinz, Rows n = 1..27, flattened
• Shinji Tanimoto, Alternate Permutations and Signed Eulerian Numbers, math.CO/0612135, Ann. Comb. 14 (2010), 355.

Crossrefs

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

Row sums give: A092186. - Alois P. Heinz, Nov 18 2013

Programs

Maple

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:
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

Mathematica

isPAP[per_] := (For[i = 2, i <= Length[per], i++, If [Mod[per[[i]], 2] == Mod[per[[i - 1]], 2], Return[False] ] ]; True);
ascents[per_] := (asc = 0; For[i = 2, i <= Length[per], i++, If[per[[i]] > per[[i - 1]],  asc ++] ]; asc);
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);
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 *)

Formula

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

Extensions

Corrected by R. J. Mathar, Dec 12 2006

Edited by N. J. A. Sloane, Dec 21 2006

Replaced arXiv URL by non-cached version - R. J. Mathar, Oct 30 2009

More terms from Alois P. Heinz, Nov 18 2013