login
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.
5

%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