cp's OEIS Frontend

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

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