|
|
A214152
|
|
Number of permutations T(n,k) in S_n containing an increasing subsequence of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.
|
|
15
|
|
|
1, 2, 1, 6, 5, 1, 24, 23, 10, 1, 120, 119, 78, 17, 1, 720, 719, 588, 207, 26, 1, 5040, 5039, 4611, 2279, 458, 37, 1, 40320, 40319, 38890, 24553, 6996, 891, 50, 1, 362880, 362879, 358018, 268521, 101072, 18043, 1578, 65, 1, 3628800, 3628799, 3612004, 3042210, 1438112, 337210, 40884, 2603, 82, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{i=k..n} A047874(n,i).
|
|
EXAMPLE
|
T(3,2) = 5. All 3! = 6 permutations of {1,2,3} contain an increasing subsequence of length 2 with the exception of 321.
Triangle T(n,k) begins:
: 1;
: 2, 1;
: 6, 5, 1;
: 24, 23, 10, 1;
: 120, 119, 78, 17, 1;
: 720, 719, 588, 207, 26, 1;
: 5040, 5039, 4611, 2279, 458, 37, 1;
|
|
MAPLE
|
h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
+add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
T:= (n, k)-> n! -g(n, k-1, []):
seq(seq(T(n, k), k=1..n), n=1..12);
|
|
MATHEMATICA
|
h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]! / Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}] ]; g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1&, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; t[n_, k_] := n! - g[n, k-1, {}]; Table[Table[t[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|