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.

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, 64, 16, 8, 2, 4, 18, 40, 112, 240, 256, 448, 438, 668, 502, 696, 480, 496, 264, 240, 88, 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

Offset

2,1

Comments

The first number in a row, T(n,n-1)=2, corresponding to the permutations having the numbers in order and reverse order.

Links

Table of n, a(n) for n=2..73.

Norman Whitehead, Log10 Graph of Several Rows

Example

Triangle begins:
  n:  row n
---------------
  2:  2;
  3:  2, 4;
  4:  2, 4, 12,  4,   2;
  5:  2, 4, 14, 32,  18,  28,  14,   8;
  6:  2, 4, 16, 36,  92,  68, 128,  92, 122,  72,  64,  16,   8;
  7:  2, 4, 18, 40, 112, 240, 256, 448, 438, 668, 502, 696, 480, 496, 264, 240, 88, 48;
  ...
First item in each row corresponds to sum at n-1, second item to sum at n, etc.
Row 4:
    |1, 2, 3, 4|=3, |1, 3, 2, 4|=5, |3, 1, 2, 4|=5, |1, 4, 2, 3|=6,
    |4, 3, 2, 1|=3, |1, 3, 4, 2|=5, |3, 2, 1, 4|=5, |2, 3, 1, 4|=6,
    |1, 2, 4, 3|=4, |1, 4, 3, 2|=5, |3, 4, 1, 2|=5, |3, 2, 4, 1|=6,
    |2, 1, 3, 4|=4, |2, 1, 4, 3|=5, |4, 1, 2, 3|=5, |4, 1, 3, 2|=6,
    |3, 4, 2, 1|=4, |2, 3, 4, 1|=5, |4, 2, 1, 3|=5, |2, 4, 1, 3|=7,
    |4, 3, 1, 2|=4, |2, 4, 3, 1|=5, |4, 2, 3, 1|=5, |3, 1, 4, 2|=7,
Thus, for example, T(4,5)=12 because there are 12 permutations with a sum of differences equal to 5.

Prog

(Python)
from itertools import permutations
def count_l1_sums(n):
    nm1     = n-1
    a000982 = (((nm1*nm1)+1)//2) # from OEIS
    tally   = a000982*[0]    # number of different totals
    perms   = permutations([i for i in range(n)]) # length is factorial(n)
    # Compute each permutation's first difference
    for perm in perms:
        l1_norm = 0
        for i in range(nm1):
            diff = perm[i+1]-perm[i]
            if diff>0: l1_norm += diff
            else:      l1_norm -= diff
        tally[l1_norm-nm1] += 1 # diff==(n-1) goes into first position
    return tally

Crossrefs

Cf. A000982 (number of possible sums for n).

Cf. A328378 (maximal sums for n).

Sequence in context: A319862 A220977 A054134 * A319822 A005127 A140773

Adjacent sequences: A381609 A381610 A381611 * A381613 A381614 A381615

Keyword

nonn,tabf

Author

Norman Whitehead, Mar 01 2025

Status

approved