|
%I #11 Sep 29 2017 02:46:00
%S 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,0,42,
%T 42,38,40,51,84,132,0,132,126,107,103,115,154,264,429,0,429,396,322,
%U 292,299,350,486,858,1430,0,1430,1287,1014,882,852,915,1110,1584,2860,4862
%N Pats by first entry.
%C 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.
%C Also, pats on [0,n] with last entry k correspond to pats with first entry n-k under the reverse-complement operation on permutations.
%H C. O. Oakley and R. J. Wisner, <a href="http://www.jstor.org/stable/2310544">Flexagons</a>, Amer. Math. Monthly 64 (1957), 143-154.
%F G.f.: 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-4*x))/(2*x) is the g.f. for the Catalan numbers A000108.
%e T(4,2)=3 counts 24301, 23140, 21430.
%e Table begins
%e 1
%e 0...1
%e 0...1...1
%e 0...1...2...2
%e 0...2...3...4...5
%e 0...5...6...7..10..14
%e 0..14..15..15..18..28..42
%t 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}]
%Y The Catalan numbers A000108 appear as row sums and in the second column and on the main diagonal.
%K nonn,tabl
%O 0,9
%A _David Callan_, Aug 01 2008
|
