Bijective enumerations of ?-free 0–1 matrices
MTMT : 3341485
Megjelenés dátuma : 2018
Folyóirat címe : Advances in Applied Mathematics
Évfolyam : 96
Oldalszám : 195-215
Dokumentum típusa : folyóiratcikk
Kulcsszó : ?-free matrix, Non-ambiguous forest, Természettudományok, Természettudományok/Matematika- és számítástudományok
Absztrakt :
We construct a new bijection between the set of n × k 0–1 matrices with no three 1’s forming a ? configuration and the set of ( n, k )-Callan sequences, a simple structure counted by poly-Bernoulli numbers. We give two applications of this result: We derive the generating function of ?-free matrices, and we give a new bijective proof for an elegant result of Ava l et al. that states that the number of complete non- ambiguous forests with n leaves is equal to the number of pairs of permutations of { 1 , ..., n } with no common rise.