|
|
A122848
|
|
Exponential Riordan array (1, x(1+x/2)).
|
|
23
|
|
|
1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 3, 6, 1, 0, 0, 0, 15, 10, 1, 0, 0, 0, 15, 45, 15, 1, 0, 0, 0, 0, 105, 105, 21, 1, 0, 0, 0, 0, 105, 420, 210, 28, 1, 0, 0, 0, 0, 0, 945, 1260, 378, 36, 1, 0, 0, 0, 0, 0, 945, 4725, 3150, 630, 45, 1, 0, 0, 0, 0, 0, 0, 10395, 17325, 6930, 990, 55, 1, 0, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
T(n,k) is the number of self-inverse permutations of {1,2,...,n} having exactly k cycles. - Geoffrey Critzer, May 08 2012
Also the inverse Bell transform of the double factorial of odd numbers Product_{k= 0..n-1} (2*k+1) (A001147). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015
|
|
LINKS
|
|
|
FORMULA
|
Number triangle T(n,k) = k!*C(n,k)/((2k-n)!*2^(n-k)).
Triangle equals the matrix product A008275*A039755. Equivalently, the n-th row polynomial R(n,x) is given by the Type B Dobinski formula R(n,x) = exp(-x/2)*Sum_{k>=0} P(n,2*k+1)*(x/2)^k/k!, where P(n,x) = x*(x-1)*...*(x-n+1) denotes the falling factorial polynomial. Cf. A113278. - Peter Bala, Jun 23 2014
E.g.f. for the m-th column: (x^2/2+x)^m/m!.
T(n,k) = T(n-1,k-1) + (n-1)*T(n-2,k-1) for n>1 and k=1..n, T(0,0) = 1. (End)
|
|
EXAMPLE
|
Triangle begins:
1
0 1
0 1 1
0 0 3 1
0 0 3 6 1
0 0 0 15 10 1
0 0 0 15 45 15 1
0 0 0 0 105 105 21 1
0 0 0 0 105 420 210 28 1
0 0 0 0 0 945 1260 378 36 1
As noted above, a(n) is the number of set partitions of {1..n} into k singletons or pairs. This is also the number of set partitions of subsets of {1..n} into n - k pairs. In the first case, row n = 5 counts the following set partitions:
{{1},{2,3},{4,5}} {{1},{2},{3},{4,5}} {{1},{2},{3},{4},{5}}
{{1,2},{3},{4,5}} {{1},{2},{3,4},{5}}
{{1,2},{3,4},{5}} {{1},{2,3},{4},{5}}
{{1,2},{3,5},{4}} {{1,2},{3},{4},{5}}
{{1},{2,4},{3,5}} {{1},{2},{3,5},{4}}
{{1},{2,5},{3,4}} {{1},{2,4},{3},{5}}
{{1,3},{2},{4,5}} {{1},{2,5},{3},{4}}
{{1,3},{2,4},{5}} {{1,3},{2},{4},{5}}
{{1,3},{2,5},{4}} {{1,4},{2},{3},{5}}
{{1,4},{2},{3,5}} {{1,5},{2},{3},{4}}
{{1,4},{2,3},{5}}
{{1,4},{2,5},{3}}
{{1,5},{2},{3,4}}
{{1,5},{2,3},{4}}
{{1,5},{2,4},{3}}
In the second case, we have:
{{1,2},{3,4}} {{1,2}} {}
{{1,2},{3,5}} {{1,3}}
{{1,2},{4,5}} {{1,4}}
{{1,3},{2,4}} {{1,5}}
{{1,3},{2,5}} {{2,3}}
{{1,3},{4,5}} {{2,4}}
{{1,4},{2,3}} {{2,5}}
{{1,4},{2,5}} {{3,4}}
{{1,4},{3,5}} {{3,5}}
{{1,5},{2,3}} {{4,5}}
{{1,5},{2,4}}
{{1,5},{3,4}}
{{2,3},{4,5}}
{{2,4},{3,5}}
{{2,5},{3,4}}
(End)
|
|
MAPLE
|
# The function BellMatrix is defined in A264428.
BellMatrix(n -> `if`(n<2, 1, 0), 9); # Peter Luschny, Jan 27 2016
|
|
MATHEMATICA
|
t[n_, k_] := k!*Binomial[n, k]/((2 k - n)!*2^(n - k)); Table[ t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten
(* Second program: *)
rows = 12;
t = Join[{1, 1}, Table[0, rows]];
T[n_, k_] := BellY[n, k, t];
sbs[{}]:={{}}; sbs[set:{i_, ___}]:=Join@@Function[s, (Prepend[#1, s]&)/@sbs[Complement[set, s]]]/@Cases[Subsets[set], {i}|{i, _}];
Table[Length[Select[sbs[Range[n]], Length[#]==k&]], {n, 0, 6}, {k, 0, n}] (* Gus Wiseman, Jan 12 2021 *)
|
|
PROG
|
(PARI) {T(n, k)=if(2*k<n||k>n, 0, n!/(2*k-n)!/(n-k)!*2^(k-n))} /* Michael Somos, Oct 03 2006 */
(Sage) # uses[inverse_bell_transform from A265605]
multifact_2_1 = lambda n: prod(2*k + 1 for k in (0..n-1))
inverse_bell_matrix(multifact_2_1, 9) # Peter Luschny, Dec 31 2015
|
|
CROSSREFS
|
Same as A049403 but with a first column k = 0.
The same set partitions counted by number of pairs are A100861.
Reversing rows gives A111924 (without column k = 0).
A047884 counts standard Young tableaux by size and greatest row length.
A238123 counts standard Young tableaux by size and least row length.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|