

A263484


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


4



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



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 cutpoints: (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.
Math 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 (* JeanFrançois Alcover, Feb 18 2020, after Philippe Deléham *)


PROG

(Sage Math) # 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,n1) gives A003319.
A version with reflected rows is A059438, A085771.
T(2n,n) gives A308650.
Sequence in context: A011117 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



