Journal of Integer Sequences, Vol. 17 (2014), Article 14.3.5

A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers

Milan Janjić and Boris Petković
Department of Mathematics and Informatics
University of Banja Luka
Republic of Srpska, Bosnia and Herzegovina


We define a counting function that is related to the binomial coefficients. For this function, we derive an explicit expression. In some particular cases, we prove simpler explicit formulae. We also derive a formula for the number of (0,1)-matrices, having a fixed number of 1's, and having no zero rows and zero columns. Further, we show that our function satisfies several recurrence relations.

We then examine the relationship of our counting function with different classes of integers. These classes include: some figurate numbers, the number of points on the surface of a square pyramid, the magic constants, the truncated square numbers, the coefficients of the Chebyshev polynomials, the Catalan numbers, the Delannoy numbers, the Sulanke numbers, the numbers of the coordination sequences, and the number of the crystal ball sequences of a cubic lattice.

In the last part of the paper, we count several configurations by our function. Some of these are: the number of spanning subgraphs of the complete bipartite graph, the number of squares contained in a square, the number of colorings of points on a line, the number of divisors of some particular numbers, the number of all parts in the compositions of an integer, the numbers of the weak compositions of integers, and the number of particular lattice paths. We conclude by counting the number of possible moves of the rook, bishop, and queen on a chessboard.

For the most statements in the paper, we provide bijective proofs in terms of insets, which we define in the paper. Hence, using the same method, we count different configurations.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A000217 A000297 A000326 A000327 A000330 A000466 A000567 A000918 A001105 A001655 A001787 A001788 A001789 A001791 A001792 A001844 A001845 A001846 A001847 A001848 A001849 A002002 A002409 A002492 A002694 A003472 A004310 A004311 A004312 A004313 A004314 A004315 A004316 A004317 A004318 A005918 A006003 A006325 A007531 A008288 A008312 A008417 A008419 A008421 A014820 A015237 A017593 A019583 A027417 A027471 A027620 A028347 A028560 A029653 A030622 A030662 A034007 A034428 A034828 A035005 A035006 A035597 A035598 A035599 A035600 A035601 A035602 A035603 A035604 A035605 A039623 A045623 A045891 A045943 A045944 A047010 A047030 A049600 A049611 A050409 A054849 A054851 A058396 A059270 A061927 A062109 A063488 A064861 A069039 A069072 A076301 A080838 A081266 A084485 A084486 A091361 A094952 A099195 A099776 A111297 A116882 A123865 A140325 A140354 A142978 A158920 A159694 A160378 A169792 A169793 A169794 A169795 A169796 A169797 A172242 A191596 A194715 A202804.)

Received January 20 2013; revised version received January 29 2013; October 20 2013; February 15 2014. Published in Journal of Integer Sequences, February 15 2014.

Return to Journal of Integer Sequences home page