login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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 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.

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 (* Jean-Franç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,n-1) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 20:10 EDT 2021. Contains 347598 sequences. (Running on oeis4.)