A064315
Triangle of number of permutations by length of shortest ascending run.
Original entry on oeis.org
1, 1, 1, 5, 0, 1, 18, 5, 0, 1, 101, 18, 0, 0, 1, 611, 89, 19, 0, 0, 1, 4452, 519, 68, 0, 0, 0, 1, 36287, 3853, 110, 69, 0, 0, 0, 1, 333395, 27555, 1679, 250, 0, 0, 0, 0, 1, 3382758, 233431, 11941, 418, 251, 0, 0, 0, 0, 1, 37688597, 2167152, 59470, 658, 922, 0, 0, 0, 0, 0, 1
Offset: 1
Sequence (1, 3, 2, 5, 4) has ascending runs (1, 3), (2, 5), (4), the shortest is length 1. Of all permutations of (1, 2, 3, 4, 5), T(5,1) = 101 have shortest ascending run of length 1.
Triangle T(n,k) begins:
1;
1, 1;
5, 0, 1;
18, 5, 0, 1;
101, 18, 0, 0, 1;
611, 89, 19, 0, 0, 1;
4452, 519, 68, 0, 0, 0, 1,
36287, 3853, 110, 69, 0, 0, 0, 1;
...
-
A:= proc(n, k) option remember; local b; b:=
proc(u, o, t) option remember; `if`(t+o<=k, (u+o)!,
add(b(u+i-1, o-i, min(k, t)+1), i=1..o)+
`if`(t<=k, u*(u+o-1)!, add(b(u-i, o+i-1, 1), i=1..u)))
end: forget(b):
add(b(j-1, n-j, 1), j=1..n)
end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Aug 29 2013
-
A[n_, k_] := A[n, k] = Module[{b}, b[u_, o_, t_] := b[u, o, t] = If[t+o <= k, (u+o)!, Sum[b[u+i-1, o-i, Min[k, t]+1], {i, 1, o}] + If[t <= k, u*(u+o-1)!, Sum[ b[u-i, o+i-1, 1], {i, 1, u}]]]; Sum[b[j-1, n-j, 1], {j, 1, n}]]; T[n_, k_] := A[n, k] - A[n, k-1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)
A097899
Number of permutations of [n] with no runs of length 1. (The permutation 3574162 has two runs of length 1: 357/4/16/2).
Original entry on oeis.org
1, 0, 1, 1, 6, 19, 109, 588, 4033, 29485, 246042, 2228203, 22162249, 237997032, 2757055393, 34191395785, 452480427678, 6360924613699, 94691284984405, 1487846074481172, 24608991911033377, 427379047337272213, 7775688853750498386, 147900024951747279643
Offset: 0
Example: a(4)=6 because 1234, 1324, 1423, 2314, 2413, 3412 are the only permutations of [4] with no runs of length 1.
- Ira. M. Gessel, Generating functions and enumeration of sequences, Ph. D. Thesis, MIT, 1977, p. 52.
-
G:=sqrt(3)*exp(-x/2)/2/cos(sqrt(3)*x/2+Pi/6): Gser:=series(G, x, 26): seq(n!*coeff(Gser, x, n), n=0..25);
-
FullSimplify[CoefficientList[Series[(Sqrt[3]/2)*E^(-x/2)/Cos[Sqrt[3]*x/2 + Pi/6], {x, 0, 20}], x]* Range[0, 20]!] (* Vaclav Kotesovec, Oct 08 2013 *)
g[u_, o_] := g[u, o] = If[u + o < 2, u,
Sum[b[u - i, o + i - 1], {i, u}] +
Sum[g[u + i - 1, o - i], {i, o}]];
b[u_, o_] := b[u, o] = If[u + o < 2, 1 - o, u*(u + o - 1)! +
Sum[g[u + i - 1, o - i], {i, o}]] ;
a[n_] := n! - Sum[b[j - 1, n - j], {j, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz in A228614 *)
A186735
Number of permutations of [n] with no ascending runs of length 1 or 2.
Original entry on oeis.org
1, 0, 0, 1, 1, 1, 20, 69, 180, 1930, 12611, 61051, 566129, 5179750, 38348469, 376547340, 4169246332, 41559058969, 465750294781, 5905176350849, 72848728572828, 946103621115633, 13501160406995728, 195518567272213262, 2918439778172724571, 46559546190633191495
Offset: 0
a(0) = 1: the empty permutation.
a(3) = 1: 123.
a(4) = 1: 1234.
a(5) = 1: 12345.
a(6) = 20: 123456, 124356, 125346, 126345, 134256, 135246, 136245, 145236, 146235, 156234, 234156, 235146, 236145, 245136, 246135, 256134, 345126, 346125, 356124, 456123.
-
A[n_, k_] := A[n, k] = Module[{b}, b[u_, o_, t_] := b[u, o, t] =
If[t + o <= k, (u + o)!,
Sum[b[u + i - 1, o - i, Min[k, t] + 1], {i, 1, o}] +
If[t <= k, u*(u + o - 1)!,
Sum[b[u - i, o + i - 1, 1], {i, 1, u}]]];
Sum[b[j - 1, n - j, 1], {j, 1, n}]];
a[n_] := n! - A[n, 2];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Sep 03 2021, after Alois P. Heinz in A064315 *)
Showing 1-3 of 3 results.