|
|
A359413
|
|
Triangle read by rows: T(n, k) is the number of permutations of size n that require exactly k iterations of the pop-stack sorting map to reach the identity, for n >= 1, 0 <= k <= n-1.
|
|
1
|
|
|
1, 1, 1, 1, 3, 2, 1, 7, 8, 8, 1, 15, 26, 46, 32, 1, 31, 80, 191, 262, 155, 1, 63, 234, 735, 1440, 1737, 830, 1, 127, 664, 2752, 6924, 12314, 12432, 5106, 1, 255, 1850, 10114, 31928, 73122, 112108, 98156, 35346, 1, 511, 5088, 36564, 145199, 404758, 816401, 1104042, 844038, 272198
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
When k is fixed, T(n, k) has a rational g.f. (see A. Claesson and B. A. Guðmundsson).
|
|
LINKS
|
|
|
FORMULA
|
T(n, 0) = 1.
T(n, 1) = 2^(n-1)-1 for n >= 2 (see L. Pudwell and R. Smith).
T(n, k) = 0 when k >= n (see M. Albert and V. Vatter).
|
|
EXAMPLE
|
The pop-stack sorting map acts by reversing the descending runs of a permutation. For example, it sends 3412 to 3142, it sends 3142 to 1324, and it sends 1324 to 1234. This shows that if we start with the permutation 3412, then we require 4-1=3 iterations to reach the identity permutation. There are T(4,3) = 8 permutations of size 4 that require 3 iterations, namely 2341, 3241, 3412, 3421, 4123, 4132, 4231, 4312.
Triangle T(n,k) begins:
[1] 1;
[2] 1, 1;
[3] 1, 3, 2;
[4] 1, 7, 8, 8;
[5] 1, 15, 26, 46, 32;
[6] 1, 31, 80, 191, 262, 155;
...
|
|
PROG
|
(Python)
from itertools import permutations
def ps(lst): # pop-stack sorting operator [cf. Claesson, Guðmundsson]
out, stack = [], []
for i in range(len(lst)):
if len(stack) == 0 or stack[-1] < lst[i]:
out.extend(stack[::-1])
stack = []
stack.append(lst[i])
return out + stack[::-1]
def psops(t):
c, lst, srtdlst = 0, list(t), sorted(t)
if lst == srtdlst: return 0
while lst != srtdlst:
lst = ps(lst)
c += 1
return c
def T(n, k):
return sum(1 for p in permutations(range(n), n) if psops(p) == k)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|