

A156289


Triangle read by rows: T(n,k) is the number of end rhyme patterns of a poem of an even number of lines (2n) with 1<=k<=n evenly rhymed sounds.


18



1, 1, 3, 1, 15, 15, 1, 63, 210, 105, 1, 255, 2205, 3150, 945, 1, 1023, 21120, 65835, 51975, 10395, 1, 4095, 195195, 1201200, 1891890, 945945, 135135, 1, 16383, 1777230, 20585565, 58108050, 54864810, 18918900, 2027025, 1, 65535, 16076985
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

T(n,k) is the number of partitions of a set of size 2*n into k blocks of even size [Comtet]. For partitions into odd sized blocks see A136630.
See A241171 for the triangle of ordered set partitions of the set {1,2,...,2*n} into k even sized blocks.  Peter Bala, Aug 20 2014
This triangle T(n,k) gives the sum over the M_3 multinomials A036040 for the partitions of 2*n with k even parts, for 1 <= k <= n. See the triangle A257490 with sums over the entries with k parts, and the Hartmut F. W. Hoft program.  Wolfdieter Lang, May 13 2015


REFERENCES

L. Comtet, Analyse Combinatoire, Presses Univ. de France, 1970, Vol. II, pages 6162.
L. Comtet, Advanced Combinatorics, Reidel, 1974, pages 225226.


LINKS



FORMULA

Recursion: T(n,1)=1 for 1<=n; T(n,k)=0 for 1<=n<k;
T(n,k) = (2k1)*T(n1,k1) + k^2*T(n1,k) 1<k<=n.
Generating function for the kth column of the triangle T(i+k,k):
G(k,x) = Sum(i=0,Infinity; T(i+k,k)*x^i) = Product(j=1,k; (2j1)/(1j^2*x).
Closed form expression for T(n,k):
T(n,k) = 2/(k!*2^k)*sum {j = 1..k} (1)^(kj)*binomial(2*k,kj)*j^(2*n).
GENERATING FUNCTION
E.g.f. (including a constant 1):
(1)... F(x,z) = exp(x*(cosh(z)1)
= sum{n>=0} R(n,x)*z^(2*n)/(2*n)!
= 1 + x*z^2/2! + (x + 3*x^2)*z^4/4! + (x + 15*x^2 + 15*x^3)*z^6/6 + ....
ROW POLYNOMIALS
The row polynomials R(n,x) begin
... R(1,x) = x
... R(2,x) = x + 3*x^2
... R(3,x) = x + 15*x^2 + 15*x^3.
The egf F(x,z) satisfies the partial differential equation
(2)... d^2/dz^2(F) = x*F + x*(2*x+1)*F' + x^2*F'',
where ' denotes differentiation with respect to x. Hence the row polynomials satisfy the recurrence relation
(3)... R(n+1,x) = x*{R(n,x) + (2*x+1)*R'(n,x) + x*R''(n,x)}
with R(0,x) = 1. The recurrence relation for T(n,k) given above follows from this.
(4)... T(n,k) = (2*k1)!!*A036969(n,k).
(End)


EXAMPLE

The triangle begins
n\k..1.....2......3......4......5......6
=========================================
.1...1
.2...1.....3
.3...1....15.....15
.4...1....63....210....105
.5...1...255...2205...3150....945
.6...1..1023..21120..65835..51975..10395
..
T(3,3) = 15. The 15 partitions of the set [6] into three even blocks are:
(12)(34)(56), (12)(35)(46), (12)(36)(45),
(13)(24)(56), (13)(25)(46), (13)(26)(45),
(14)(23)(56), (14)(25)(36), (14)(26)(35),
(15)(23)(46), (15)(24)(36), (15)(26)(34),
(16)(23)(45), (16)(24)(35), (16)(25)(34).
Examples of recurrence relation
T(4,3) = 5*T(3,2) + 9*T(3,3) = 5*15 + 9*15 = 210;
T(6,5) = 9*T(5,4) + 25*T(5,5) = 9*3150 + 25*945 = 51975.
T(4,2) = 28 + 35 = 63 (M_3 multinomials A036040 for partitions of 8 with 3 even parts, namely (2,6) and (4^2)).  Wolfdieter Lang, May 13 2015


MAPLE

T := proc(n, k) option remember; `if`(k = 0 and n = 0, 1, `if`(n < 0, 0,
(2*k1)*T(n1, k1) + k^2*T(n1, k))) end:
for n from 1 to 8 do seq(T(n, k), k=1..n) od; # Peter Luschny, Sep 04 2017


MATHEMATICA

T[n_, k_] := Which[n < k, 0, n == 1, 1, True, 2/Factorial2[2 k] Sum[(1)^(k + j) Binomial[2 k, k + j] j^(2 n), {j, 1, k}]]
(* alternate computation with function triangle[] defined in A257490 *)
a[n_]:=Map[Apply[Plus, #]&, triangle[n], {2}]


CROSSREFS

2nd column variant T(n, 2)/3, for 2<=n, is A002450.
3rd column variant T(n, 3)/15, for 3<=n, is A002451.


KEYWORD



AUTHOR



STATUS

approved



