A263484 Triangle read by rows: T(n,k) (n>=1, 0<=k

1, 1, 1, 1, 2, 3, 1, 3, 7, 13, 1, 4, 12, 32, 71, 1, 5, 18, 58, 177, 461, 1, 6, 25, 92, 327, 1142, 3447, 1, 7, 33, 135, 531, 2109, 8411, 29093, 1, 8, 42, 188, 800, 3440, 15366, 69692, 273343, 1, 9, 52, 252, 1146, 5226, 24892, 125316, 642581, 2829325

Offset: 1

Author

Christian Stump, Oct 19 2015

Keywords

• nonn
• tabl

Comments

Row sums give A000142, n >= 1.

From Allan C. Wechsler, Jun 14 2019 (Start):

Suppose we are permuting the numbers from 1 through 5. For example, consider the permutation (1,2,3,4,5) -> (3,1,2,5,4). Notice that there is exactly one point where we can cut this permutation into two consecutive pieces in such a way that no item is permuted from one piece to the other, namely (3,1,2 | 5,4). This "cut" has the property that all the indices to its left are less than all the indices to its right. There are no other such cut-points: (3,1 | 2,5,4) doesn't work, for example, because 3 > 2.

Stanley defines the "connectivity set" as the set of positions at which you can make such a cut. In this case, the connectivity set is {3}.

In the present sequence, T(n,k) is the number of permutations of n elements with k cut points. (End)

Essentially the same triangle as [1, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, 4, 4, 5, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 18 2020

Examples

			Triangle begins:
  1,
  1, 1,
  1, 2,  3,
  1, 3,  7, 13,
  1, 4, 12, 32,  71,
  1, 5, 18, 58, 177, 461,
  ...
Triangle [1, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, ...]:
  1;
  1, 0;
  1, 1,  0;
  1, 2,  3,  0;
  1, 3,  7, 13,  0;
  1, 4, 12, 32, 71, 0;
... - _Philippe Deléham_, Feb 18 2020
		

Links

• Alois P. Heinz, Rows n = 0..150, flattened
• FindStat - Combinatorial Statistic Finder, The cardinality of the complement of the connectivity set.
• Mathematics Stack Exchange, Discussion of this sequence, June 2019.
• Richard P. Stanley, The Descent Set and Connectivity Set of a Permutation, arXiv:math/0507224 [math.CO], 2005.

Crossrefs

Cf. A000142.

T(n,n-1) gives A003319.

A version with reflected rows is A059438, A085771.

T(2n,n) gives A308650.

Programs

Mathematica

rows = 11;
(* DELTA is defined in A084938 *)
Most /@ DELTA[Table[Boole[n == 1], {n, rows}], Join[{0, 1}, LinearRecurrence[{1, 1, -1}, {2, 2, 3}, rows]], rows] // Flatten (* Jean-François Alcover, Feb 18 2020, after Philippe Deléham *)

SageMath

# cf. FindStat link
def statistic(x):
     return len(set(x.reduced_word()))
for n in [1..6]:
    for pi in Permutations(n):
        print(pi, "=>", statistic(pi))

Extensions

More terms from Fred Lunnon and Christian Stump

Name changed by Georg Fischer as proposed by Allan C. Wechsler, Jun 13 2019