OFFSET
0,9
COMMENTS
Row sums give A007472.
The recurrence is analogous to that of Stirling numbers of the 2nd kind (A048993), but with a parity constraint. For even columns, T(n+1, 2*k) = 2*k*T(n, 2*k) + T(n, 2*k-1); for odd columns, T(n+1, 2*k+1) = 2*k*T(n, 2*k+1) + T(n, 2*k).
T(n,k) appear as coefficients in the following polynomials (which themselves are coefficients of t^n in the bivariate e.g.f.:
P_0(x) = 1
P_1(x) = 0 + x
P_2(x) = 0 + 0 + x^2
P_3(x) = 0 + 0 + 2x^2 + x^3
P_4(x) = 0 + 0 + 4x^2 + 4x^3 + x^4
P_5(x) = 0 + 0 + 8x^2 + 12x^3 + 8x^4 + x^5
P_6(x) = 0 + 0 + 16x^2 + 32x^3 + 44x^4 + 12x^5 + x^6
P_n(1) gives A007472.
T(n,k) enumerates the number of ways to partition n labeled objects in k compartments of urns with two compartments each with the following constraints:
- you can initially place a marble in any compartment of any urn
- you cannot use the same compartment in an urn again until you've used its other compartment
- you can freely place objects in any compartment of urns where both compartments are already used
- you cannot open a new urn until both compartments of all previously used urns are filled
Examples:
For T(3,2) we have two ways to place the objects in two compartments of a single urn
- {13|2}
- {1|23}
For T(3,3) we have one way to place each object in its own compartment (2 urns, 3 compartments used):
- {1|2}{3|}
For 4 objects we have:
- 4 cases for Z(4,2):
{134|2}
{14|23}
{13|24}
{1|234}
- 4 cases for Z(4,3):
{{13|2},{4|}}
{{1|23},{4|}}
{{14|2},{3|}}
{{1|24},{3|}}
- 1 case for Z(4,4):
{{1|2}, {3|4}}
Then A007472 counts the total number of ways to partition n labeled objects in such nonempty two-compartment urns.
LINKS
FORMULA
T(n, k) = 2*Floor(k/2)*T(n-1, k) + T(n-1, k-1), n > 0; T(0, k) = 0, k > 0; T(0, 0) = 1.
E.g.f.: A[x_, t_] := x*(BesselK[0,x] + BesselK[1,x])*BesselI[0,x*Exp[t]] + x*(BesselI[1,x] - BesselI[0,x])*BesselK[0, x Exp[t]] where T(n,k) are the coefficients of x^k for t^n. The much simpler formula BesselI[0,x*Exp[t]] produces the same coefficients but with carrier alternating BesselI[0,x] and BesselI[1,x] functions at even and odd coefficients.
EXAMPLE
The triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12
0: 1
1: 0 1
2: 0 0 1
3: 0 0 2 1
4: 0 0 4 4 1
5: 0 0 8 12 8 1
6: 0 0 16 32 44 12 1
7: 0 0 32 80 208 92 18 1
8: 0 0 64 192 912 576 200 24 1
9: 0 0 128 448 3840 3216 1776 344 32 1
10: 0 0 256 1024 15808 16704 13872 3840 600 40 1
11: 0 0 512 2304 64256 82624 99936 36912 8640 920 50 1
12: 0 0 1024 5120 259328 394752 682240 321408 106032 16000 1420 60 1
------------------------------------------------------------------------
Recurrence:
S(5,3) = 2*Floor(3/2)*S(4,3) + S(4,2) = 2*4 + 4 = 12.
S(5,4) = 2*Floor(4/2)*S(4,4) + S(4,3) = 4*1 + 4 = 8.
MATHEMATICA
Z[0, 0, m_]=1;
Z[0, k_, m_]:=0/; k>0;
Z[n_, 0, m_]:=0/; n>0;
Z[n_, k_, m_]:=Z[n, k, m]=m*Floor[k/m]*Z[n-1, k, m]+Z[n-1, k-1, m];
Flatten[Table[Z[n, k, 2], {n, 0, 12}, {k, 0, n}]]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Ven Popov, Apr 20 2025
STATUS
approved
