A196776 Triangle T(n,k) gives the number of ordered partitions of an n set into k odd-sized blocks.

1, 0, 2, 1, 0, 6, 0, 8, 0, 24, 1, 0, 60, 0, 120, 0, 32, 0, 480, 0, 720, 1, 0, 546, 0, 4200, 0, 5040, 0, 128, 0, 8064, 0, 40320, 0, 40320, 1, 0, 4920, 0, 115920, 0, 423360, 0, 362880, 0, 512, 0, 130560, 0, 1693440, 0, 4838400, 0, 3628800

Offset: 1

Author

Peter Bala, Oct 06 2011

Keywords

• nonn
• easy
• tabl

Comments

See A136630 for the case of unordered partitions into odd-sized blocks. See A193474 for this triangle in row reverse form (but with an offset of 0).

Examples

			Triangle begins
.n\k.|..1....2....3....4.....5....6.....7
= = = = = = = = = = = = = = = = = = = = =
..1..|..1
..2..|..0....2
..3..|..1....0....6
..4..|..0....8....0...24
..5..|..1....0...60....0...120
..6..|..0...32....0..480.....0..720
..7..|..1....0..546....0..4200....0..5040
...
T(4,2) = 8: The 8 ordered partitions of the set {1,2,3,4} into 2 odd-sized blocks are {1}{2,3,4}, {2,3,4}{1}, {2}{1,3,4}, {1,3,4}{2}, {3}{1,2,4}, {1,2,4}{3}, {4}{1,2,3} and {1,2,3}{4}.
Example of recurrence relation: T(7,3) = 3^2*T(5,3) + 3*(3-1)*T(5,1) = 9*60 + 6*1 = 546.
		

Crossrefs

Cf. A006154 (row sums), A136630, A162590, A193474 (row reverse).

Formula

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

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

E.g.f.: x*sinh(t)/(1-x*sinh(t)) = x*t + 2*x^2*t^2/2! + (x+6*x^3)*t^3/3! + (8*x^2+24*x^4)*t^4/4! + (x+60*x^3+120*x^5)*t^5/5! + ....

O.g.f. for column 2*k: (2*k)!*x^(2*k)/Product {j = 0..k} (1 - (2*j)^2*x^2).

O.g.f. for column 2*k+1: (2*k+1)!*x^(2*k+1)/Product {j = 0..k} (1 - (2*j+1)^2*x^2).

Let P denote Pascal's triangle A070318 and put M = 1/2*(P-P^-1). M is A162590 (see also A131047). Then the first column of (I-t*M)^-1 (apart from the initial 1) lists the row polynomials for the present triangle.

n-th row sum = A006154(n).

Row generating polynomials equal D^n(1/(1-x*t)) evaluated at x = 0, where D is the operator sqrt(1+x^2)*d/dx. Cf. A136630. - Peter Bala, Dec 06 2011