A263484 Triangle read by rows: T(n,k) (n>=1, 0<=k<n) is the number of permutations of n elements with n-k elements in its connectivity set.

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,5

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

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.

Example

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

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 *)

Prog

(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))

Crossrefs

Cf. A000142.

T(n,n-1) gives A003319.

A version with reflected rows is A059438, A085771.

T(2n,n) gives A308650.

Sequence in context: A368401 A069269 A193092 * A293985 A100324 A121424

Adjacent sequences: A263481 A263482 A263483 * A263485 A263486 A263487

Keyword

nonn,tabl

Author

Christian Stump, Oct 19 2015

Extensions

More terms from Fred Lunnon and Christian Stump

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

Status

approved