A138378 Number of embedded coalitions in an n-person game.

1, 3, 10, 37, 151, 674, 3263, 17007, 94828, 562595, 3535027, 23430840, 163254885, 1192059223, 9097183602, 72384727657, 599211936355, 5150665398898, 45891416030315, 423145657921379, 4031845922290572, 39645290116637023, 401806863439720943, 4192631462935194064

Offset: 1

Author

David Yeung (wkyeung(AT)hkbu.edu.hk), May 08 2008

Keywords

• nonn

Comments

Same as A005493, apart from offset. - R. J. Mathar, Sep 23 2011

The strategic behavior of players depends crucially on the coalition structures of a game.

Examples

			a(1) = combination(1,0) = 1,
a(2) = combination(2,1) + combination(2,0)= 3,
a(3) = combination(3,2)* a(1) + combination(3,2) + combination(3,1) + combination(3,0)= 10,
a(4) = combination(4,3)* {a(1) + a(2)} + combination(4,2)* a(1) + combination7(4,3)combination(4,2) + combination(4,1) + combination(4,0)= 37,
a(5) = combination(5,4)* {a(1) + a(2) + a(3)} combination(5,3)* {a(1) + a(2)} + combination(5,2)* a(1) + combination(5,4) + combination(5,3) + combination(5,2) + combination(5,1) + combination(5,0)= 151.
		

References

• J. H. Conway and R. K. Guy, The Book of Numbers, Springer-Verlag, New York, 1995.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..575
• E. T. Bell, Exponential numbers, Amer. Math. Monthly, 41 (1934), 411-419.
• Gábor Czédli, Lattices with lots of congruence energy, arXiv:2205.02294 [math.RA], 2022.
• A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
• David W. K. Yeung, Recursive sequence identifying the number of embedded coalitions, International Game Theory Review 10(2008), 129-136.

Crossrefs

Cf. A000110, A005493, A048993, A138379.

Column k=1 of A283424.

Programs

Magma

[&+[k*StirlingSecond(n, k): k in [1..n]]: n in [1..25]]; // Vincenzo Librandi, May 18 2019

Maple

b:= proc(n, m) option remember;
     `if`(n=0, m, m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..24);  # Alois P. Heinz, Dec 10 2024

Mathematica

a[n_] := Sum[Binomial[n, j] BellB[j], {j, 0, n-1}];
Array[a, 24] (* Jean-François Alcover, Aug 19 2018 *)

Formula

a(1) = combination(1,0) = 1, a(2) = combination(2,1) + combination(2,0)= 3, a(n) = {SUM(i=2 to n-1) combination(n,i)} * {SUM(j=1 to i-1) a(n)} + SUM(i=0 to n-1) combination(n,i), for n > 2.

G.f.: 1/U(0) where U(k)= 1 - x*(k+3) - x^2*(k+1)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2012

G.f.: 1/(U(0)-x) where U(k)= 1 - x - x*(k+1)/(1 - x/U(k+1)); (continued fraction). - Sergei N. Gladkovskii, Oct 12 2012

G.f.: -G(0)/x^2 where G(k) = 1 - 1/(1-k*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 08 2013

G.f.: Q(0)/x^2 -1/x^2, where Q(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 10 2013

a(n) = Bell(n+1)-Bell(n) = Sum_{k=1..n} k*Stirling2(n,k). - Alois P. Heinz, May 11 2017

E.g.f.: (exp(x) - 1) * exp(exp(x) - 1). - Ilya Gutkovskiy, Jan 26 2020