%I #50 Nov 20 2023 00:03:03
%S 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,
%T 1142,3447,1,7,33,135,531,2109,8411,29093,1,8,42,188,800,3440,15366,
%U 69692,273343,1,9,52,252,1146,5226,24892,125316,642581,2829325
%N 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.
%C Row sums give A000142, n >= 1.
%C From _Allan C. Wechsler_, Jun 14 2019 (Start):
%C 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.
%C 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}.
%C In the present sequence, T(n,k) is the number of permutations of n elements with k cut points. (End)
%C 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
%H Alois P. Heinz, <a href="/A263484/b263484.txt">Rows n = 0..150, flattened</a>
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000019">The cardinality of the complement of the connectivity set</a>.
%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/3257689/why-does-this-appear-to-produce-oeis-sequence-a263484">Discussion of this sequence</a>, June 2019.
%H Richard P. Stanley, <a href="http://arxiv.org/abs/math/0507224">The Descent Set and Connectivity Set of a Permutation</a>, arXiv:math/0507224 [math.CO], 2005.
%e Triangle begins:
%e 1,
%e 1, 1,
%e 1, 2, 3,
%e 1, 3, 7, 13,
%e 1, 4, 12, 32, 71,
%e 1, 5, 18, 58, 177, 461,
%e ...
%e Triangle [1, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, ...]:
%e 1;
%e 1, 0;
%e 1, 1, 0;
%e 1, 2, 3, 0;
%e 1, 3, 7, 13, 0;
%e 1, 4, 12, 32, 71, 0;
%e ... - _Philippe Deléham_, Feb 18 2020
%t rows = 11;
%t (* DELTA is defined in A084938 *)
%t 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_ *)
%o (SageMath) # cf. FindStat link
%o def statistic(x):
%o return len(set(x.reduced_word()))
%o for n in [1..6]:
%o for pi in Permutations(n):
%o print(pi, "=>", statistic(pi))
%Y Cf. A000142.
%Y T(n,n-1) gives A003319.
%Y A version with reflected rows is A059438, A085771.
%Y T(2n,n) gives A308650.
%K nonn,tabl
%O 1,5
%A _Christian Stump_, Oct 19 2015
%E More terms from _Fred Lunnon_ and _Christian Stump_
%E Name changed by _Georg Fischer_ as proposed by _Allan C. Wechsler_, Jun 13 2019