A182172 -id:A182172 - cp's OEIS frontend

A293114 Number of sets of nonempty words with a total of n letters over n-ary alphabet such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

1, 1, 2, 6, 15, 45, 136, 430, 1415, 4845, 17235, 63509, 242854, 959904, 3926209, 16564083, 72097127, 322898943, 1487602607, 7034420691, 34122991199, 169499127425, 861596397518, 4475340840980, 23738200183570, 128427236055296, 708248486616539, 3977551340260517

Offset: 0

Alois P. Heinz, Sep 30 2017

nonn

			a(0) = 1: {}.
a(1) = 1: {a}.
a(2) = 2: {aa}, {ab}.
a(3) = 6: {a,aa}, {a,ab}, {aaa}, {aab}, {aba}, {abc}.

Alois P. Heinz, Table of n, a(n) for n = 0..800

Main diagonal of A293112.
Row sums of A293113 and of A293815.
Cf. A000085, A182172, A293110, A306009.

g:= proc(n) option remember;
      `if`(n<2, 1, g(n-1)+(n-1)*g(n-2))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*binomial(g(i), j), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..35);

g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1]* Binomial[g[i], j], {j, 0, n/i}]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 06 2018, from Maple *)

G.f.: Product_{j>=1} (1+x^j)^A000085(j).

Weigh transform of A000085.

A293128 Number of standard Young tableaux of 2n cells and height <= n.

Original entry on oeis.org

1, 1, 6, 51, 588, 7990, 126060, 2242618, 44546320, 977152266, 23500234512, 615372604033, 17442275104496, 532242021137346, 17399782340548920, 606732491690590816, 22477989291826848000, 881635273413199806994, 36493478646922003374096, 1589642562747880936613248

Offset: 0

Alois P. Heinz, Sep 30 2017

nonn

Also the number of standard Young tableaux of 2n cells and <= n columns.

Also the number of 2n-length words w over n-ary alphabet {a1,a2,...,an} such that for every prefix z of w we have #(z,a1) >= #(z,a2) >= ... >= #(z,an), where #(z,x) counts the letters x in word z. The a(2) = 6 words of length 4 over alphabet {a,b} are: aaaa, aaab, aaba, abaa, aabb, abab.

Vaclav Kotesovec, Table of n, a(n) for n = 0..41 (terms 0..32 from Alois P. Heinz)
Wikipedia, Young tableau

Cf. A182172, A267436.

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(l[k]
      `if`(n=0 or i=1, h([l[], 1$n]), add(
               g(n-i*j, i-1, [l[], i$j]), j=0..n/i)):
a:= n-> g(2*n, n, []):
seq(a(n), n=0..15);

h[l_] := With[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] < j, 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]], Sum[g[n - i*j, i - 1, Join[l, Table[i, {j}]]], {j, 0, n/i}]];
a[n_] := g[2n, n, {}];
a /@ Range[0, 15] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

a(n) = A182172(2n,n).

A217323 Number of self-inverse permutations in S_n with longest increasing subsequence of length 3.

Original entry on oeis.org

1, 3, 11, 31, 92, 253, 709, 1936, 5336, 14587, 40119, 110202, 304137, 840597, 2332469, 6487762, 18106906, 50667263, 142194843, 400057791, 1128408337, 3190023641, 9038202201, 25659417876, 72987714502, 207983161609, 593665226069, 1697230353691, 4859461136196

Offset: 3

Alois P. Heinz, Sep 30 2012

Also the number of Young tableaux with n cells and 3 rows.

			a(3) = 1: 123.
a(4) = 3: 1243, 1324, 2134.
a(5) = 11: 12543, 13254, 14325, 14523, 15342, 21354, 21435, 32145, 34125, 42315, 52341.

Alois P. Heinz, Table of n, a(n) for n = 3..1000

Column k=3 of A047884.

Cf. A001006, A001405, A182172.

a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,
      ((n+1)*(6*n^3-5*n^2-7*n-24)*a(n-1)
       +n*(n-1)*(21*n^2-28*n-109)*a(n-2)
       -2*(n-1)*(n-2)*(12*n^2+11*n-3)*a(n-3)
       -12*(3*n+5)*(n-1)*(n-2)*(n-3)*a(n-4))/
      ((n-3)*(3*n+2)*(n+2)*(n+1))))
    end:
seq(a(n), n=3..40);

MotzkinNumber = DifferenceRoot[Function[{y, n}, {(-3n-3)*y[n] + (-2n-5)*y[n+1] + (n+4)*y[n+2] == 0, y[0] == 1, y[1] == 1}]];
a[n_] := MotzkinNumber[n] - Binomial[n, Quotient[n, 2]];
Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Oct 27 2021, from 2nd formula *)

a(n) = A182172(n,3) - A182172(n,2) = A001006(n) - A001405(n).

A229053 Number of standard Young tableaux of n cells and height <= 11.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140151, 568491, 2390311, 10347911, 46191551, 211671999, 996269310, 4801547628, 23695885170, 119481280210, 615372604033, 3232009497979, 17302866542177, 94301143232321, 522945331559246, 2947729723188352

Offset: 0

Vaclav Kotesovec, Sep 12 2013

nonn

Vaclav Kotesovec and Alois P. Heinz, Table of n, a(n) for n = 0..400
Index entries for sequences related to Young tableaux.

Cf. A182172, A001405 (k=2), A001006 (k=3), A005817 (k=4), A049401 (k=5), A007579 (k=6), A007578 (k=7), A007580 (k=8), A212915 (k=9), A212916 (k=10).
Column k=11 of A182172.
Cf. A000085.

RecurrenceTable[{-10395 (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) a[-6+n]-3 (-4+n) (-3+n) (-2+n) (-1+n) (28701+2578 n) a[-5+n]+(-3+n) (-2+n) (-1+n) (331317+74458 n+3319 n^2) a[-4+n]+2 (-2+n) (-1+n) (546120+154023 n+11843 n^2+270 n^3) a[-3+n]-(-1+n) (1857231+1090536 n+149299 n^2+7472 n^3+125 n^4) a[-2+n]+(-2755377-1658520 n-265085 n^2-17752 n^3-535 n^4-6 n^5) a[-1+n]+(10+n) (18+n) (24+n) (28+n) (30+n) a[n]==0,a[1]==1,a[2]==2,a[3]==4,a[4]==10,a[5]==26,a[6]==76}, a, {n, 20}]

Recurrence: (n+10)*(n+18)*(n+24)*(n+28)*(n+30)*a(n) = (6*n^5 + 535*n^4 + 17752*n^3 + 265085*n^2 + 1658520*n + 2755377)*a(n-1) + (n-1)*(125*n^4 + 7472*n^3 + 149299*n^2 + 1090536*n + 1857231)*a(n-2) - 2*(n-2)*(n-1)*(270*n^3 + 11843*n^2 + 154023*n + 546120)*a(n-3) - (n-3)*(n-2)*(n-1)*(3319*n^2 + 74458*n + 331317)*a(n-4) + 3*(n-4)*(n-3)*(n-2)*(n-1)*(2578*n + 28701)*a(n-5) + 10395*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*a(n-6).
a(n) ~ 40186125/1024 * 11^(n+55/2)/(Pi^(5/2)*n^(55/2)).
Conjecture: a(n) ~ k^n/Pi^(k/2)*(k/n)^(k*(k-1)/4) * prod(j=1,k,Gamma(j/2)).

A293111 Number of multisets of nonempty words with a total of 2n letters over n-ary alphabet containing the n-th letter such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Original entry on oeis.org

1, 2, 10, 58, 439, 3767, 37481, 405672, 4816390, 60748286, 817467196, 11533898929, 170979909037, 2635984019533, 42297026556483, 701880878089205, 12045976560853148, 212911592290588547, 3874514946593004395, 72378921228197309169, 1387364840045160600103

Offset: 0

Alois P. Heinz, Sep 30 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..26

Cf. A182172, A293109, A293115.

a(n) = A293109(2n,n).

A293115 Number of sets of nonempty words with a total of 2n letters over n-ary alphabet containing the n-th letter such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Original entry on oeis.org

1, 1, 8, 53, 410, 3576, 35878, 391136, 4666521, 59096165, 797628339, 11282268353, 167582833398, 2587994886476, 41585338511800, 690912445945576, 11870082701946292, 209995330141487944, 3824511903396303251, 71496027436457015058, 1371314535020854180410

Offset: 0

Alois P. Heinz, Sep 30 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..26

Cf. A182172, A293111, A293113.

a(n) = A293113(2n,n).

A213290 Number of n-length words w over binary alphabet such that for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 2, 4, 5, 9, 14, 27, 46, 91, 162, 323, 589, 1177, 2179, 4357, 8152, 16303, 30746, 61491, 116689, 233377, 445095, 890189, 1704795, 3409589, 6552379, 13104757, 25258601, 50517201, 97617061, 195234121, 378098956, 756197911, 1467343306, 2934686611, 5704370761

Offset: 0

Alois P. Heinz, Jun 08 2012

nonn

			a(0) = 1: the empty word.
a(1) = 2: a, b for alphabet {a,b}.
a(2) = 4: aa, ab, ba, bb.
a(3) = 5: aaa, aab, aba, baa, bbb.
a(4) = 9: aaaa, aaab, aaba, aabb, abaa, abab, baaa, baab, bbbb.
a(5) = 14: aaaaa, aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba, bbbbb.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=2 of A213276.

Cf. A001405, A057427, A182172.

b:= n-> `if`(n<0, 0, binomial(n, ceil(n/2))):
a:= n-> b(n) +b(n-2) +`if`(n>0, 1, 0):
seq(a(n), n=0..40);

a(n) = A001405(n) + A001405(n-2) + A057427(n).

a(n) = A182172(n,2) + A182172(n-2,2) + A057427(n).

A217321 Number of self-inverse permutations in S_n with longest increasing subsequence of length 9.

Original entry on oeis.org

1, 9, 89, 639, 4655, 30330, 198148, 1233743, 7694099, 46938514, 287070944, 1738940782, 10570927022, 64059763010, 389873574058, 2373799261605, 14522526860316, 89060416668016, 548932942208392, 3395326330414774, 21109553761623110, 131785019270029876

Offset: 9

Alois P. Heinz, Sep 30 2012

nonn

Also the number of Young tableaux with n cells and 9 rows.

Alois P. Heinz, Table of n, a(n) for n = 9..350

Column k=9 of A047884.

Cf. A007580, A182172, A212915.

a(n) = A182172(n,9)-A182172(n,8) = A212915(n)-A007580(n).

A217322 Number of self-inverse permutations in S_n with longest increasing subsequence of length 10.

Original entry on oeis.org

1, 10, 109, 857, 6798, 48007, 338529, 2267425, 15164662, 98964444, 645978814, 4168541022, 26949303558, 173445855265, 1119737108943, 7224864497439, 46800745943134, 303692912870933, 1979556048016406, 12943419575576650, 85040314513698164, 560910092712436079

Offset: 10

Alois P. Heinz, Sep 30 2012

nonn

Also the number of Young tableaux with n cells and 10 rows.

Alois P. Heinz, Table of n, a(n) for n = 10..350

Column k=10 of A047884.

Cf. A182172, A212915, A212916.

a(n) = A182172(n,10)-A182172(n,9) = A212916(n)-A212915(n).

A217324 Number of self-inverse permutations in S_n with longest increasing subsequence of length 4.

Original entry on oeis.org

1, 4, 19, 69, 265, 929, 3356, 11626, 41117, 142206, 499836, 1734328, 6099193, 21282265, 75125770, 263906332, 936517637, 3313246237, 11827430209, 42139231729, 151339387003, 542857007499, 1961171657524, 7079621540798, 25720257983591, 93396276789196

Offset: 4

Alois P. Heinz, Sep 30 2012

Also the number of Young tableaux with n cells and 4 rows.

			a(4) = 1: 1234.
a(5) = 4: 12354, 12435, 13245, 21345.
a(6) = 19: 123654, 124365, 125436, 125634, 126453, 132465, 132546, 143256, 145236, 153426, 163452, 213465, 213546, 214356, 321456, 341256, 423156, 523416, 623451.

Alois P. Heinz, Table of n, a(n) for n = 4..1000

Column k=4 of A047884.

Cf. A001006, A005817, A182172.

a:= proc(n) option remember; `if`(n<4, 0, `if`(n=4, 1,
      ((2+n)*(30*n^5+199*n^4-374*n^3-1537*n^2-406*n+408)*a(n-1)
       -4*(n-1)*(n-2)*(120*n^4+46*n^3-471*n^2+371*n+204)*a(n-3)
       +(n-1)*(285*n^5-262*n^4-2755*n^3-1520*n^2+820*n-48)*a(n-2)
       -48*(n-1)*(n-3)*(3*n+7)*(5*n+4)*(n-2)^2*a(n-4))/
      ((n-4)*(5*n-1)*(3*n+4)*(n+4)*(n+3)*(n+2))))
    end:
seq(a(n), n=4..40);

h[l_] := With[{n = Length[l]}, Total[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_] := g[n, i, l] = If[n == 0 || i == 1, Function[p, h[p]*x^If[p == {}, 0, p[[1]]]][Join[l, Array[1&, n]]], Sum[g[n - i*j, i - 1, Join[l, Array[i&, j]]], {j, 0, n/i}]];
a[n_] := a[n] = Coefficient[g[n, n, {}], x, 4];
Table[Print[n, " ", a[n]]; a[n], {n, 4, 40}]
(* or: *)
MotzkinNumber = DifferenceRoot[Function[{y, n}, {(-3n-3)*y[n] + (-2n-5)*y[n+1] + (n+4)*y[n+2] == 0, y[0] == 1, y[1] == 1}]];
a[n_] := CatalanNumber[Quotient[n+1, 2]]*CatalanNumber[Quotient[n+2, 2]] - MotzkinNumber[n];
Table[a[n], {n, 4, 40}]
(* Jean-François Alcover, Oct 27 2021, after Alois P. Heinz in A047884 and second formula *)

a(n) = A182172(n,4)-A182172(n,3) = A005817(n)-A001006(n).

cp's OEIS Frontend

A293114 Number of sets of nonempty words with a total of n letters over n-ary alphabet such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293128 Number of standard Young tableaux of 2n cells and height <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A217323 Number of self-inverse permutations in S_n with longest increasing subsequence of length 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A229053 Number of standard Young tableaux of n cells and height <= 11.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A293111 Number of multisets of nonempty words with a total of 2n letters over n-ary alphabet containing the n-th letter such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Views

Author

Keywords

Links

Crossrefs

Formula

A293115 Number of sets of nonempty words with a total of 2n letters over n-ary alphabet containing the n-th letter such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

Views

Author

Keywords

Links

Crossrefs

Formula

A213290 Number of n-length words w over binary alphabet such that for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A217321 Number of self-inverse permutations in S_n with longest increasing subsequence of length 9.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A217322 Number of self-inverse permutations in S_n with longest increasing subsequence of length 10.

Views

Author

Keywords