0,9

T(n,k) is the number of pats on [0,n] with first entry k. Pats are

defined recursively in the Oakley/Wisner reference. Briefly, a one-entry

permutation is a pat and a two-or-more-entry permutation p on any set of integers is a pat

iff (i) there is a unique way to split p as the concatenation of nonempty

permutations p_1 and p_2 such that all entries in p_1 exceed all entries in p_2,

and (ii) reverse(p1) and reverse(p2) are pats. Thus 21 and 43 are pats but 12 is

not and p = 3412 is a pat using p1 = 34 and p2 = 12. Pats on [1,n+1]

(considered by Oakley/Wisner in the definition of flexagons)

correspond to pats on [0,n] by subtracting 1 from each entry.

Also, pats on [0,n] with last entry k correspond to pats with first entry

n-k under the reverse-complement operation on permutations.

C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly 64 (1957), 143-154.

Gf: Sum_{n>=0,k>=0}T(n,k)*x^n*y^k = (1 + x y CatalanGF[x y])/(1 - x^2 y CatalanGF[x] CatalanGF[x y]) where CatalanGF[x] = (1-Sqrt[1-4x])/(2x) is the Gf for the Catalan numbers A000108.

T(4,2)=3 counts 24301, 23140, 21430.

Table begins

1

0...1

0...1...1

0...1...2...2

0...2...3...4...5

0...5...6...7..10..14

0..14..15..15..18..28..42

a[0, 0]=1; a[n_, k_]/; n>=1 && 0<=k<=n := a[n, k] = (* count by splitting point in condition (i) *) Sum[a[i, n-k]CatalanNumber[n-i-1], {i, n-k, n-1}]; Table[a[n, k], {n, 0, 10}, {k, 0, n}]

The Catalan numbers A000108 appear as row sums and in the second column and on the main diagonal.

Sequence in context: A099307 A072738 A165316 this_sequence A102706 A105673 A074823

Adjacent sequences: A141055 A141056 A141057 this_sequence A141059 A141060 A141061

nonn

David Callan (callan(AT)stat.wisc.edu), Aug 01 2008