A102366 Number of subsets of {1,2,...,n} in which exactly half of the elements are less than or equal to sqrt(n).

1, 1, 2, 3, 6, 10, 15, 21, 28, 84, 120, 165, 220, 286, 364, 455, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 53130, 65780, 80730, 98280, 118755, 142506, 169911, 201376, 237336, 278256, 324632, 1947792, 2324784, 2760681, 3262623, 3838380, 4496388

Offset: 0

Author

Henry Bottomley, Feb 22 2005

Keywords

• nonn

Comments

Also number of subsets of [n] in which exactly half of the elements are squares: a(5) = 10: {}, {1,2}, {1,3}, {1,5}, {2,4}, {3,4}, {4,5}, {1,2,3,4}, {1,2,4,5}, {1,3,4,5}. - Alois P. Heinz, Oct 11 2022

Examples

			a(5) = 10 since the ten subsets of {1,2,3,4,5} are { }, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {1,2, 3,4}, {1,2, 3,5} and {1,2, 4,5}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A011782 for number of subsets with an even number of elements.

Cf. A000290.

Programs

PARI

{a(n)=if(n<0,0,binomial(n, sqrtint(n)))} /* Paul D. Hanna */

PARI

{a(n)=sum(k=0,sqrtint(n),binomial(sqrtint(n), k)*binomial(n-sqrtint(n),k))}

Formula

a(n) = Sum_k C(floor(sqrt(n)),k)*C(n-floor(sqrt(n)),k) = A048093(n) + 1 = a(n-1) + A084919(n-1).

a(n) = binomial(n, floor(sqrt(n))). - Paul D. Hanna, Jun 25 2011