login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 10
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 61-62.

L. Comtet, Advanced Combinatorics, Reidel, 1974, pages 225-226.

LINKS

Table of n, a(n) for n=1..39.

J. Riordan, Letter, Jul 06 1978

FORMULA

Recursion: T(n,1)=1 for 1<=n; T(n,k)=0 for 1<=n<k;

T(n,k) = (2k-1)*T(n-1,k-1) + k^2*T(n-1,k) 1<k<=n.

Generating function for the k-th 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; (2j-1)/(1-j^2*x).

Closed form expression for T(n,k):

T(n,k) = 2/(k!*2^k)*sum {j = 1..k} (-1)^(k-j)*binomial(2*k,k-j)*j^(2*n).

From Peter Bala, Feb 21 2011: (Start)

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*k-1)!!*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*k-1)*T(n-1, k-1) + k^2*T(n-1, 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}]

(* Hartmut F. W. Hoft, Apr 26 2015 *)

CROSSREFS

Diagonal T(n, n) is A001147, subdiagonal T(n+1, n) is A001880.

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

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

Sum of the n-th row is A005046.

Cf. A241171, A257468, A257490, A096162.

Sequence in context: A113378 A178657 A257490 * A095922 A263632 A284861

Adjacent sequences:  A156286 A156287 A156288 * A156290 A156291 A156292

KEYWORD

easy,nonn,tabl

AUTHOR

Hartmut F. W. Hoft, Feb 07 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 04:02 EDT 2019. Contains 323473 sequences. (Running on oeis4.)