Gender of Boolean functions

Studies of Boolean functions

gender ratio for arities 0...5

A Boolean function shall be called male, iff its root is sharp (i. e. iff its compressed truth table has odd weight).
(Equivalently, it is female, iff after removing all repetitions, the weight of the truth table is still even.)

For positive arities, there are more males than females. The imbalance peaks for arity 2. For higher arities, the ratio is almost balanced.
The ratio is balanced for the infinite set of all Boolean functions. Both sets are countable, so there is a trivial bijection. But is there a meaningful bijection?

	0	1	2	3	4	5
A246537 ♀	1	1	3	97	32199	2147318437
A246418 ♂	1	3	13	159	33337	2147648859

total

This triangle shows the numbers of Boolean functions with arity $n$ and valency $k$. The right diagonal is ${\boldsymbol {p}}$ =  A000371. ${\boldsymbol {p}}(n)$ is the number of non-degenerate $n$-ary Boolean functions. (See root.) This is Pascal's triangle with column $k$ multiplied by ${\boldsymbol {p}}(k)$. The sum of row $n$ is $2^{2^{n}}$.   ( A001146) k n 0 1 2 3 4 5 sums 0 1 · 2 2 2 1 1 · 2 2 1 · 2 2 4 2 1 · 2 2 2 · 2 4 1 · 10 10 16 3 1 · 2 2 3 · 2 6 3 · 10 30 1 · 218 218 256 4 1 · 2 2 4 · 2 8 6 · 10 60 4 · 218 872 1 · 64594 64594 65536 5 1 · 2 2 5 · 2 10 10 · 10 100 10 · 218 2180 5 · 64594 322970 1 · 4294642034 4294642034 4294967296

♀

This triangle shows the numbers of female Boolean functions with arity $n$ and valency $k$. The right diagonal is ${\boldsymbol {d}}={\boldsymbol {p}}-{\boldsymbol {q}}$ = 1, 0, 2, 90, 31826, 2147158386... (compare  A007537) This is Pascal's triangle with column $k$ multiplied by ${\boldsymbol {d}}(k)$. The row sums are  A246537. k n 0 1 2 3 4 5 sums 0 1 · 1 1 1 1 1 · 1 1 1 · 0 0 1 2 1 · 1 1 2 · 0 0 1 · 2 2 3 3 1 · 1 1 3 · 0 0 3 · 2 6 1 · 90 90 97 4 1 · 1 1 4 · 0 0 6 · 2 12 4 · 90 360 1 · 31826 31826 32199 5 1 · 1 1 5 · 0 0 10 · 2 20 10 · 90 900 5 · 31826 159130 1 · 2147158386 2147158386 2147318437

♂

This triangle shows the numbers of male Boolean functions with arity $n$ and valency $k$. The right diagonal is ${\boldsymbol {q}}(n)=2^{(2^{n}-1)}$.   (That is half the number of all $n$-ary Boolean functions.)   (like  A058891, but with offset 0) This is Pascal's triangle with column $k$ multiplied by ${\boldsymbol {q}}(k)$. The row sums are  A246418. k n 0 1 2 3 4 5 sums 0 1 · 1 1 1 1 1 · 1 1 1 · 2 2 3 2 1 · 1 1 2 · 2 4 1 · 8 8 13 3 1 · 1 1 3 · 2 6 3 · 8 24 1 · 128 128 159 4 1 · 1 1 4 · 2 8 6 · 8 48 4 · 128 512 1 · 32768 32768 33337 5 1 · 1 1 5 · 2 10 10 · 8 80 10 · 128 1280 5 · 32768 163840 1 · 2147483648 2147483648 2147648859 from math import factorial def binom(n, k): return factorial(n) // (factorial(k) * factorial(n - k)) for n in range(6): row = [] for k in range(n+1): row.append( binom(n, k) * 2 ** (2 ** k - 1) ) print(n, '-->', row, '-->', sum(row)) illustrated triangles These images show the male functions also seen in the two 8×256 matrices.   (Only a few of the 128 on the right side of the matrix are shown.) They are ordered by adicity (vertical) and valency (horizontal). The numbers sum up to those in the triangle above.   (E.g. 2 + 2 + 2 = 6 and 8 + 16 = 24.) Zhegalkin indices truth tables

roots

A000371 = 2 *  A003465 k n 0 1 2 3 4 5 sums 0 1 · 1 1 1 1 − 0 1 1 · 1 −1 1 · 2 2 1 2 − 1 2 1 · 1 1 2 · 2 −4 1 · 8 8 5 9 − 4 3 1 · 1 −1 3 · 2 6 3 · 8 −24 1 · 128 128 109 134 − 25 4 1 · 1 1 4 · 2 −8 6 · 8 48 4 · 128 −512 1 · 32768 32768 32297 32817 − 520 5 1 · 1 −1 5 · 2 10 10 · 8 −80 10 · 128 1280 5 · 32768 −163840 1 · 2147483648 2147483648 2147321017 2147484938 − 163921 k n 0 1 2 3 4 5 sums 0 1 · 2 2 2 2 − 0 1 1 · 2 −2 1 · 4 4 2 4 − 2 2 1 · 2 2 2 · 4 −8 1 · 16 16 10 18 − 8 3 1 · 2 −2 3 · 4 12 3 · 16 −48 1 · 256 256 218 268 − 50 4 1 · 2 2 4 · 4 −16 6 · 16 96 4 · 256 −1024 1 · 65536 65536 64594 65634 − 1040 5 1 · 2 −2 5 · 4 20 10 · 16 −160 10 · 256 2560 5 · 65536 −327680 1 · 4294967296 4294967296 4294642034 4294969876 − 327842

---

truth tables   (Zhegalkin matrix)
These matrices show the 97 females and 159 males among the first 256 Boolean functions. The matrix above shows the Zhegalkin indices. The Zhegalkin matrix below shows the truth tables. The male truth tables on the left side of the matrix contain repetitions, i.e. their pattern can be described by a shorter truth table.

atomvals   (bitwise OR)
The upper matrix shows the Zhegalkin indices. The one below shows atomvals of the corresponding Boolean functions. This is sequence  A327041, the bitwise ORs of the binary exponents seen above.

---

sequences of Zhegalkin indices

adicity 2adicity ♀ ♂     (not to be confused with  A359527) 0 1 0, 1 1 1, 1 2 0 2 2, 3, 2 4 6, 7, 2 10 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 3 8 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 66, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 82, 83, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 94 146 16, 17, 32, 33, 34, 35, 48, 49, 50, 51, 64, 65, 68, 69, 80, 81, 84, 85, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 4 16 258, 259, 260, 261   ...   32764, 32765, 32766, 32767 32102 32102 256, 257, 512, 513   ...   21840, 21841, 21844, 21845, 32768, 32769, 32770, 32771   ...   65532, 65533, 65534, 65535 females = [0, 6, 7, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 66, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 82, 83, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127] males = [1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 32, 33, 34, 35, 48, 49, 50, 51, 64, 65, 68, 69, 80, 81, 84, 85, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255] 4-ary females on Pastebin