A346462 Triangle read by rows: T(n,k) gives the number of permutations of length n containing exactly k instances of the 1-box pattern; 0 <= k <= n.

1, 1, 0, 0, 0, 2, 0, 0, 4, 2, 2, 0, 10, 4, 8, 14, 0, 40, 10, 42, 14, 90, 0, 230, 40, 226, 80, 54, 646, 0, 1580, 230, 1480, 442, 534, 128, 5242, 0, 12434, 1580, 11496, 2920, 4746, 1404, 498, 47622, 0, 110320, 12434, 101966, 22762, 45216, 13138, 7996, 1426

Offset: 0

Author

Peter Kagey, Jul 19 2021

Keywords

• nonn
• tabl

Comments

An instance of the 1-box pattern in a permutation pi is a letter pi_i such that pi_{i-1} or pi_{i+1} differs from pi_i by exactly 1.

Column k=0 is A002464. Columns k=2 and k=3 are given by A086852.

Main diagonal begins: 1,0,2,2,8,14,54,128,498,1426,5736,... A363181.

Examples

			The permutation 14327568 has 5 instances of the 1-box pattern:
- position 2 differs from position 3 by one,
- position 3 differs from positions 2 and 4 by one,
- position 4 differs from position 3 by one,
- position 6 differs from position 7 by one,
- position 7 differs from position 6 by one, and
positions 1, 5, and 8 differ from all of their neighbors by more than 1.
Table begins:
  n\k|  0  1    2   3    4   5   6
-----+-----------------------------
   0 |  1
   1 |  1  0
   2 |  0  0    2
   3 |  0  0    4   2
   4 |  2  0   10   4    8
   5 | 14  0   40  10   42  14
   6 | 90  0  230  40  226  80  54
		

Links

• Alois P. Heinz, Rows n = 0..20, flattened
• FindStat, St000064: The number of one-box pattern of a permutation.
• S. Kitaev, J. Remmel, The 1-box pattern on pattern avoiding permutations, arXiv:1305.6970 [math.CO], 2013.

Crossrefs

Cf. A002464, A086852, A229729, A229730, A363181.

Row sums give A000142.