| Displaying 1-7 of 7 results found.
page
1
Number of intersecting families of an n-element set. Also number of n-variable clique Boolean functions.
+10
59
2, 6, 40, 1376, 1314816, 912818962432, 291201248266450683035648, 14704022144627161780744368338695925293142507520, 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328
COMMENTS
Also the number of n-ary Boolean polymorphisms of the binary Boolean relation OR, namely the Boolean functions f(x1,...,xn) with the property that (x1 or y1) and ... and (xn or yn) implies f(x1,...,xn) or f(y1,...,yn). - Don Knuth, Dec 04 2019 These values are necessarily divisible by powers of 2. The sequence of exponents begins 1, 1, 3, 5, 12, 22, 49, 93, ... , 2^(n-1)-C(n-1,floor(n/2)-1), ... (cf. A191391). - Andries E. Brouwer, Aug 07 2012 a(1) = 2^1.
a(2) = 6 = 2^1 * 3
a(3) = 2^3 * 5.
a(4) = 2^5 * 43.
a(5) = 2^12 * 3 * 107.
a(6) = 2^22 * 13 * 16741.
a(7) = 2^49 * 2111 * 245039,
a(8) = 2^93 * 3^2 * 5 * 7211 * 76697 * 59656829,
a(9) = 2^200 * 1823 * 2063 * 576967 * 3600144350906020591.
An intersecting family is a collection of subsets of {1,2,...,n} such that the intersection of every subset with itself or with any other subset in the family is nonempty. The maximum number of subsets in an intersecting family is 2^(n-1). - Geoffrey Critzer, Aug 16 2013
REFERENCES
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
Pogosyan G., Miyakawa M., A. Nozaki, Rosenberg I., The Number of Clique Boolean Functions, IEICE Trans. Fundamentals, Vol. E80-A, No. 8, pp. 1502-1507, 1997/8.
EXAMPLE
a(2) = 6 because we have: {}, {{1}}, {{2}}, {{1, 2}}, {{1}, {1, 2}}, {{2}, {1, 2}}. - Geoffrey Critzer, Aug 16 2013
MATHEMATICA
Table[Length[
Select[Subsets[Subsets[Range[1, n]]],
Apply[And,
Flatten[Table[
Table[Intersection[#[[i]], #[[j]]] != {}, {i, 1,
Length[#]}], {j, 1, Length[#]}]]] &]], {n, 1, 4}] (* Geoffrey Critzer, Aug 16 2013 *)
Number of 6-element families of an n-element set such that every 3 members of the family have a nonempty intersection.
+10
1
0, 0, 0, 0, 112, 40286, 5485032, 534844548, 45066853496, 3538771308282, 267882021563464, 19861835713621616, 1453175611052688600, 105278656040052332838, 7564280930105061931496, 539399446172552069053404
REFERENCES
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
FORMULA
a(n) = (1/6!)*(64^n -20*56^n +90*52^n +30*50^n +25*49^n -420*48^n -180*47^n +450*46^n +60*45^n +615*44^n +1683*43^n -3252*42^n -6030*41^n +8520*40^n +10560*39^n -15849*38^n -13005*37^n +26410*36^n +10655*35^n -50385*34^n +33390*33^n +29480*32^n -82010*31^n +91215*30^n -67380*29^n +36870*28^n -15249*27^n +4380*26^n -1215*25^n +1390*24^n -695*23^n -1574*22^n +3255*21^n -3075*20^n +1800*19^n -675*18^n +150*17^n +70*16^n -340*14^n +510*13^n -340*12^n +85*11^n -225*8^n +225*7^n +274*4^n -274*3^n -120*2^n +120).
Number of 5-element families of an n-element set such that every 3 members of the family have a nonempty intersection.
+10
1
0, 0, 0, 0, 225, 21571, 1174122, 51441824, 2038356243, 76714338477, 2804947403364, 100732231517698, 3572491367063421, 125474030774355263, 4371052010746528926, 151172238539268318372
REFERENCES
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
FORMULA
a(n) = (1/5!)*(32^n - 10*28^n + 30*26^n + 5*25^n - 80*24^n + 45*23^n + 105*22^n - 217*21^n + 205*20^n - 120*19^n + 45*18^n - 10*17^n - 9*16^n + 40*14^n - 60*13^n + 40*12^n - 10*11^n + 35*8^n - 35*7^n - 50*4^n + 50*3^n + 24*2^n - 24).
MATHEMATICA
Table[1/5! (32^n - 10*28^n + 30*26^n + 5*25^n - 80*24^n + 45*23^n + 105*22^n - 217*21^n + 205*20^n - 120*19^n + 45*18^n - 10*17^n - 9*16^n + 40*14^n - 60*13^n + 40*12^n - 10*11^n + 35*8^n - 35*7^n - 50*4^n + 50*3^n + 24*2^n - 24), {n, 0, 50}] (* G. C. Greubel, Oct 08 2017 *)
Number of 4-element families of an n-element set such that every 3 members of the family have a nonempty intersection.
+10
1
0, 0, 0, 3, 275, 8475, 192385, 3831093, 71466675, 1285857975, 22632300245, 392522268633, 6734698919575, 114576024346875, 1935649374363705, 32505459713369373, 543014736097852475, 9029329231317194175, 149522990698790644765, 2466942184607949641313
REFERENCES
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
FORMULA
a(n) = (1/4!)*(16^n - 4*14^n + 6*13^n - 4*12^n + 11^n - 6*8^n + 6*7^n + 11*4^n - 11*3^n - 6*2^n + 6).
G.f.: -x^3*(47062848*x^7 -42816008*x^6 +13976678*x^5 -2170583*x^4 +168932*x^3 -5672*x^2 +2*x +3) / ((x -1)*(2*x -1)*(3*x -1)*(4*x -1)*(7*x -1)*(8*x -1)*(11*x -1)*(12*x -1)*(13*x -1)*(14*x -1)*(16*x -1)). - Colin Barker, Jul 12 2013
MATHEMATICA
Table[1/4! (16^n - 4*14^n + 6*13^n - 4*12^n + 11^n - 6*8^n + 6*7^n + 11*4^n - 11*3^n - 6*2^n + 6), {n, 0, 50}] (* G. C. Greubel, Oct 08 2017 *)
PROG
(PARI) for(n=0, 50, print1((16^n - 4*14^n + 6*13^n - 4*12^n + 11^n - 6*8^n + 6*7^n + 11*4^n - 11*3^n - 6*2^n + 6)/24, ", ")) \\ G. C. Greubel, Oct 08 2017 (Magma) [(16^n - 4*14^n + 6*13^n - 4*12^n + 11^n - 6*8^n + 6*7^n + 11*4^n - 11*3^n - 6*2^n + 6)/24: n in [0..50]]; // G. C. Greubel, Oct 08 2017
Number of 6-element families of an n-element set such that every 4 members of the family have a nonempty intersection.
+10
1
0, 0, 0, 0, 112, 39761, 5318420, 506289623, 41378309308, 3133123494417, 227657567966500, 16152548751321851, 1129224692910819164, 78169242144478858373, 5373159786842137703140, 367368738925063893430959
REFERENCES
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
FORMULA
a(n) = (1/6!)*(64^n - 15*60^n + 60*58^n + 25*57^n - 240*56^n + 45*55^n + 705*54^n - 987*53^n - 351*52^n + 3040*51^n - 5445*50^n + 6105*49^n - 4939*48^n + 2997*47^n - 1365*46^n + 455*45^n - 105*44^n + 15*43^n - 42^n - 15*32^n + 75*30^n - 150*29^n + 150*28^n - 75*27^n + 15*26^n + 85*16^n - 85*15^n - 225*8^n + 225*7^n + 274*4^n - 274*3^n - 120*2^n + 120).
MATHEMATICA
Table[1/6! (64^n - 15*60^n + 60*58^n + 25*57^n - 240*56^n + 45*55^n + 705*54^n - 987*53^n - 351*52^n + 3040*51^n - 5445*50^n + 6105*49^n - 4939*48^n + 2997*47^n - 1365*46^n + 455*45^n - 105*44^n + 15*43^n - 42^n - 15*32^n + 75*30^n - 150*29^n + 150*28^n - 75*27^n + 15*26^n + 85*16^n - 85*15^n - 225*8^n + 225*7^n + 274*4^n - 274*3^n - 120*2^n + 120), {n, 0, 50}] (* G. C. Greubel, Oct 08 2017 *)
Number of 5-element families of an n-element set such that every 4 members of the family have a nonempty intersection.
+10
1
0, 0, 0, 0, 224, 21281, 1144027, 49310674, 1915317642, 70460566827, 2513684751809, 88008877380908, 3043421159408080, 104321464544910613, 3552122530256316471, 120307381384305672102
REFERENCES
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
FORMULA
a(n) = (1/5!)*(32^n - 5*30^n + 10*29^n - 10*28^n + 5*27^n - 26^n - 10*16^n + 10*15^n + 35*8^n - 35*7^n - 50*4^n + 50*3^n + 24*2^n - 24).
MATHEMATICA
Table[(1/5!)*(32^n - 5*30^n + 10*29^n - 10*28^n + 5*27^n - 26^n - 10*16^n + 10*15^n + 35*8^n - 35*7^n - 50*4^n + 50*3^n + 24*2^n - 24), {n, 0, 50}] (* G. C. Greubel, Oct 08 2017 *)
PROG
(PARI) for(n=0, 50, print1((1/5!)*(32^n - 5*30^n + 10*29^n - 10*28^n + 5*27^n - 26^n - 10*16^n + 10*15^n + 35*8^n - 35*7^n - 50*4^n + 50*3^n + 24*2^n - 24), ", ")) \\ G. C. Greubel, Oct 08 2017 (Magma) [(32^n - 5*30^n + 10*29^n - 10*28^n + 5*27^n - 26^n - 10*16^n + 10*15^n + 35*8^n - 35*7^n - 50*4^n + 50*3^n + 24*2^n - 24)/120: n in [0..50]]; // G. C. Greubel, Oct 08 2017
Number of Boolean functions of n variables and rank 8 from the Post class F(5,2).
+10
0
0, 0, 0, 12, 105765, 59046810, 16636450912, 3491313542424, 627725748292995, 102894277877828670, 15867914519581210614, 2343602605748557069356, 335205287948366997151705, 46782266953279485879549090
REFERENCES
E. Post, Two-valued iterative systems, Annals of Mathematics, no 5, Princeton University Press, NY, 1941.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
Search completed in 0.006 seconds
| 