|
%I #28 Mar 12 2023 14:07:14
%S 1,2,1,4,4,2,8,12,12,6,16,32,48,48,24,32,80,160,240,240,120,64,192,
%T 480,960,1440,1440,720,128,448,1344,3360,6720,10080,10080,5040,256,
%U 1024,3584,10752,26880,53760,80640,80640,40320
%N Triangle read by rows: a(n,k) = number of k-length walks in the Hasse diagram of a Boolean algebra of order n.
%C Row sums = A010842(n); Row sums from column 1 on = A066534(n) = n*A010842(n-1) = A010842(n) - 2^n.
%C a(n,k) = n! = k! = A000142(n) for n = k; a(n,n-1) = 2*n! = A052849(n) for n > 1; a(n,n-2) = 2*n! = A052849(n) for n > 2; a(n,n-3) = (4/3)*n! = A082569(n) for n > 3; a(n,n-1)/a(2,1) = n!/2! = A001710(n) for n > 1; a(n,n-2)/ a(3,1) = n!/3! = A001715(n) for n > 2; a(n,n-3)/a(4,1) = n!/4! = A001720(n) for n > 3.
%C a(2k, k) = A052714(k+1). a(2k-1, k) = A034910(k).
%C a(n,0) = A000079(n); a(n,1) = A001787(n) = row sums of A003506; a(n,2) = A001815(n) = 2!*A001788(n-1); a(n,3) = A052771(n) = 3!*A001789(n); a(n,4) = A052796(n) = 4!*A003472(n); ceiling[a(n,1) / 2] = A057711(n); a(n,5) = 5!*A054849(n).
%C In a class of n students, the number of committees (of any size) that contain an ordered k-sized subcommittee is a(n,k). - _Ross La Haye_, Apr 17 2006
%C Antidiagonal sums [1,2,5,12,30,76,198,528,1448,4080,...] appear to be binomial transform of A000522 interleaved with itself, i.e., 1,1,2,2,5,5,16,16,65,65,... - _Ross La Haye_, Sep 09 2006
%C Let P(A) be the power set of an n-element set A. Then a(n,k) = the number of ways to add k elements of A to each element x of P(A) where the k elements are not elements of x and order of addition is important. - _Ross La Haye_, Nov 19 2007
%C The derivatives of x^n evaluated at x=2. - _T. D. Noe_, Apr 21 2011
%H T. D. Noe, <a href="/A090802/b090802.txt">Rows n = 0..100, flattened</a>
%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
%H Eric Weisstein, <a href="http://mathworld.wolfram.com/Walk.html">Walk</a>
%H Eric Weisstein, <a href="http://mathworld.wolfram.com/BooleanAlgebra.html">Boolean Algebra</a>
%H Eric Weisstein, <a href="http://mathworld.wolfram.com/HasseDiagram.html">Hasse Diagram</a>
%F a(n, k) = 0 for n < k. a(n, k) = k!*C(n, k)*2^(n-k) = P(n, k)*2^(n-k) = (2n)!!/((n-k)!*2^k) = k!*A038207(n, k) = A068424*2^(n-k) = Sum[C(n, m)*P(n-m, k), {m, 0, n-k}] = Sum[C(n, n-m)*P(n-m, k), {m, 0, n-k}] = n!*Sum[1/(m!*(n-m-k)!), {m, 0, n-k}] = k!*Sum[C(n, m)*C(n-m, k), {m, 0, n-k}] = k!*Sum[C(n, n-m)*C(n-m, k), {m, 0, n-k}] = k!*C(n, k)*Sum[C(n-k, n-m-k), {m, 0, n-k}] = k!*C(n, k)*Sum[C(n-k, m), {m, 0, n-k}] for n >= k.
%F a(n, k) = 0 for n < k. a(n, k) = n*a(n-1, k-1) for n >= k >= 1.
%F E.g.f. (by columns): exp(2x)*x^k.
%e {1};
%e {2, 1};
%e {4, 4, 2};
%e {8, 12, 12, 6};
%e {16, 32, 48, 48, 24};
%e {32, 80, 160, 240, 240, 120};
%e {64, 192, 480, 960, 1440, 1440, 720};
%e {128, 448, 1344, 3360, 6720, 10080, 10080, 5040};
%e {256, 1024, 3584, 10752, 26880, 53760, 80640, 80640, 40320}
%e a(5,3) = 240 because P(5,3) = 60, 2^(5-3) = 4 and 60 * 4 = 240.
%t Flatten[Table[n!/(n-k)! * 2^(n-k), {n, 0, 8}, {k, 0, n}]] (* _Ross La Haye_, Feb 10 2004 *)
%Y Cf. A000142, A001710, A001715, A001720, A001787, A001788, A001789, A001815, A003472, A010842, A052771, A052796, A052849, A054849, A057711, A066534, A082569.
%Y Cf. A038207, A007318.
%K easy,nonn,tabl
%O 0,2
%A _Ross La Haye_, Feb 10 2004
%E More terms from _Ray Chandler_, Feb 26 2004
%E Entry revised by _Ross La Haye_, Aug 18 2006
|
