cp's OEIS Frontend

A381612 Irregular triangle read by rows: T(n,k) for n-1 <= k <= A328378(n) is the number of permutations of length n having a sum of differences equal to k.

%I A381612 #22 Mar 25 2025 19:55:03
%S A381612 2,2,4,2,4,12,4,2,2,4,14,32,18,28,14,8,2,4,16,36,92,68,128,92,122,72,
%T A381612 64,16,8,2,4,18,40,112,240,256,448,438,668,502,696,480,496,264,240,88,
%U A381612 48,2,4,20,44,134,288,696,776,1566,1620,2788,2524,3914,3192,4544,3376,4056,2720,2960,1776,1712,816,576,144,72
%N A381612 Irregular triangle read by rows: T(n,k) for n-1 <= k <= A328378(n) is the number of permutations of length n having a sum of differences equal to k.
%C A381612 The first number in a row, T(n,n-1)=2, corresponding to the permutations having the numbers in order and reverse order.
%H A381612 Norman Whitehead, <a href="/A381612/a381612.png">Log10 Graph of Several Rows</a>
%e A381612 Triangle begins:
%e A381612   n:  row n
%e A381612 ---------------
%e A381612   2:  2;
%e A381612   3:  2, 4;
%e A381612   4:  2, 4, 12,  4,   2;
%e A381612   5:  2, 4, 14, 32,  18,  28,  14,   8;
%e A381612   6:  2, 4, 16, 36,  92,  68, 128,  92, 122,  72,  64,  16,   8;
%e A381612   7:  2, 4, 18, 40, 112, 240, 256, 448, 438, 668, 502, 696, 480, 496, 264, 240, 88, 48;
%e A381612   ...
%e A381612 First item in each row corresponds to sum at n-1, second item to sum at n, etc.
%e A381612 Row 4:
%e A381612     |1, 2, 3, 4|=3, |1, 3, 2, 4|=5, |3, 1, 2, 4|=5, |1, 4, 2, 3|=6,
%e A381612     |4, 3, 2, 1|=3, |1, 3, 4, 2|=5, |3, 2, 1, 4|=5, |2, 3, 1, 4|=6,
%e A381612     |1, 2, 4, 3|=4, |1, 4, 3, 2|=5, |3, 4, 1, 2|=5, |3, 2, 4, 1|=6,
%e A381612     |2, 1, 3, 4|=4, |2, 1, 4, 3|=5, |4, 1, 2, 3|=5, |4, 1, 3, 2|=6,
%e A381612     |3, 4, 2, 1|=4, |2, 3, 4, 1|=5, |4, 2, 1, 3|=5, |2, 4, 1, 3|=7,
%e A381612     |4, 3, 1, 2|=4, |2, 4, 3, 1|=5, |4, 2, 3, 1|=5, |3, 1, 4, 2|=7,
%e A381612 Thus, for example, T(4,5)=12 because there are 12 permutations with a sum of differences equal to 5.
%o A381612 (Python)
%o A381612 from itertools import permutations
%o A381612 def count_l1_sums(n):
%o A381612     nm1     = n-1
%o A381612     a000982 = (((nm1*nm1)+1)//2) # from OEIS
%o A381612     tally   = a000982*[0]    # number of different totals
%o A381612     perms   = permutations([i for i in range(n)]) # length is factorial(n)
%o A381612     # Compute each permutation's first difference
%o A381612     for perm in perms:
%o A381612         l1_norm = 0
%o A381612         for i in range(nm1):
%o A381612             diff = perm[i+1]-perm[i]
%o A381612             if diff>0: l1_norm += diff
%o A381612             else:      l1_norm -= diff
%o A381612         tally[l1_norm-nm1] += 1 # diff==(n-1) goes into first position
%o A381612     return tally
%Y A381612 Cf. A000982 (number of possible sums for n).
%Y A381612 Cf. A328378 (maximal sums for n).
%K A381612 nonn,tabf
%O A381612 2,1
%A A381612 _Norman Whitehead_, Mar 01 2025