D. Achlioptas, Setting 2 variables at a time yields a new lower bound for random 3-sat, Proceeding of the 32nd ACM Symposium on Theory of ComputingAch01] Dimitris Achlioptas. Lower bounds for random 3-sat via dierential equations, p.2837, 2000.

D. Aldous, B. Flannery, and E. Palacios, Two applications of urn processes the fringe analysis of search trees and the simulation of quasi-stationnary distributions of markov-chains, Probability in the engineering and informational sciences, p.293307, 1988.

K. B. Athreya and S. Karlin, Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems, The Annals of Mathematical Statistics, vol.39, issue.6, p.18011817, 1968.
DOI : 10.1214/aoms/1177698013

K. B. Athreya, E. Peter, and . Ney, Branching processes, 2004.
DOI : 10.1007/978-3-642-65371-1

[. Achlioptas and G. B. Sorkin, Optimal myopic algorithms for random 3-sat, Annual Symposium on Foundations of Computer Science, p.590600, 2000.

. Wilson, The scaling window of the 2-SAT transition. Random Structures Algorithms, p.201256, 2001.

[. Borgs and J. Chayes, Phase transition and nite-size scaling for the integer partitioning problem, Random Structures Algorithms Analysis of algorithms, vol.19, issue.3- 4, p.247288, 2000.

P. Banderier, G. Flajolet, . Schaeffer, . Et-michèle, and . Soria, Random maps, coalescing saddles, singularity analysis, and Airy phenomena Analysis of algorithms, Random Structures Algorithms, vol.19, issue.3-4, 2000.

A. Z. Broder, A. M. Frieze, and E. Upfal, On the satisability and maximum satisability of random 3-CNF formulas, Proceedings of the Fourth Annual ACM- SIAM Symposium on Discrete Algorithms, p.322330, 1993.

P. Billingsley, Probability and measure Wiley Series in Probability and Mathematical Statistics : Probability and Mathematical Statistics, 1986.

A. Bagchi and A. K. , Asymptotic Normality in the Generalized Polya???Eggenberger Urn Model, with an Application to Computer Data Structures, SIAM Journal on Algebraic Discrete Methods, vol.6, issue.3, p.394405, 1985.
DOI : 10.1137/0606041

H. Cartan, Calcul diérentiel, 1967.

M. Chao and J. Franco, Probabilistic analysis of two heuristics for the 3- satisability problem, SIAM Journal on Computing, vol.15, issue.4, p.11061118, 1986.

M. Chao and J. Franco, Probabilistic analysis of a generalization of the unitclause literal selection heuristics for the k-satisability problem, Information Sciences. An International Journal, vol.51, issue.3, p.289314, 1990.

L. Comtet, Advanced combinatorics The art of nite and innite expansions, 1974.

A. Stephen and . Cook, The complexity of theorem proving procedures, Third annual ACM symposium on theory of computing, p.151158, 1971.

V. Chvátal and E. B. Reed, Mick gets some (the odds are on his side), 33rd Annual Symposium on Foundations of Computer Science, p.620627, 1992.

V. Chvatál and E. Szemerédi, Many hard examples for resolution, Journal of the ACM, vol.35, issue.4, p.759768, 1988.
DOI : 10.1145/48014.48016

N. G. De-bruijn, Asymptotic methods in analysis, 1981.

O. Dubois and Y. Boufkhad, A general upper bound for the satisability threshold of random r-SAT formulae, Journal of Algorithms, vol.24, issue.2, p.395420, 1997.

O. Dubois, Y. Boufkhad, M. Drmota, D. Gardy, and E. B. Gittenberger, Length of prime implicants and number of solutions of random CNF formulae A unied presentation of some urn models Average-case analysis of algorithms, Theoret. Comput. Sci. Algorithmica, vol.215, issue.2912, p.130120147, 1998.

O. Dubois and J. Mandler, The 3-xorsat threshold, C. R. Math. Acad. Sci. Paris, vol.335, issue.11, p.963966, 2002.
URL : https://hal.archives-ouvertes.fr/hal-01185801

[. Dubois, J. Mandler, and Y. Boufkhad, Typical 3-sat formulae and the satisability threshold, Electronic Colloquium on computational complexity, 2003.

M. Davis and H. Putnam, A computing procedure for quantication theory, Journal of the association for computing machinery, vol.7, p.201215, 1960.

O. Dubois, Upper bounds on the satisability threshold, Phase transitions in combinatorial problems, p.187197, 1999.

M. Durand, Combinatoire analytique et algorithmique des ensembles de données, Thèse de doctorat, École polytechnique, 2004.

T. [. Ehrenfest and . Ehrenfest, Über zwei bekannte Einwände gegen das Boltzmannsche h-Theorem, Physik, Zs, vol.8, p.311314, 1907.

]. A. Emfdlv95, W. Maftouhi, L. Fernandez-de, and . Vega, On random 3-sat, Combinatorics, Probability and Computing, vol.4, issue.3, p.189195, 1995.

F. Eggenberger and G. Pólya, Über die Statistik verketteter Vorgänge. Zeitschrift für angewandte mathematik und mechanik, p.279289, 1923.

P. Erd®s and A. Rényi, On random graphs. I. Publ, Math. Debrecen, vol.6, p.290297, 1959.

P. Erd®s and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl, vol.5, p.1761, 1960.

W. Feller, An introduction to probability theory and its applications

P. Flajolet, P. J. Grabner, P. Kirschenhofer, and H. Prodinger, On Ramanujan's Q-function, Journal of Computational and Applied Mathematics, vol.58, issue.1, p.103116, 1995.
DOI : 10.1016/0377-0427(93)E0258-N

P. Flajolet, J. Gabarró, and H. Pekari, Analytic urns, The Annals of Probability, vol.33, issue.3, 2004.
DOI : 10.1214/009117905000000026

P. Flajolet and A. Odlyzko, Singularity analysis of generating functions
URL : https://hal.archives-ouvertes.fr/inria-00075725

J. Franco and M. Paull, Probabilistic analysis of the Davis-Putnam procedure for solving the satisability problem, FP05a] Philippe Flajolet et Vincent Puyhaubert. Analytic combinatorics at Ok Corral, p.7787, 1983.

P. Flajolet and V. Puyhaubert, Triangular urns of dimension 2 and 3

J. Franco, Results related to threshold phenomena research in satisability : lower bounds, Phase transitions in combinatorial problems, p.147157, 1999.

A. David and . Freedman, Bernard Friedman's urn, Ann. Math. Statist, vol.36, p.956970, 1965.

B. Friedman, A simple urn model, Communications on Pure and Applied Mathematics, vol.27, issue.1, p.5970, 1949.
DOI : 10.1002/cpa.3160020103

E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem, J

P. Flajolet and R. Sedgewick, Analytic combinatorics. A paraître Une version préliminaire des 9 premiers chapitres est disponible sur le web à l'adresse http
DOI : 10.1017/cbo9780511801655
URL : https://hal.archives-ouvertes.fr/inria-00072739

A. Frieze and S. Suen, Analysis of Two Simple Heuristics on a Random Instance ofk-sat, Journal of Algorithms, vol.20, issue.2, p.312355, 1996.
DOI : 10.1006/jagm.1996.0016

R. Michael, . Garey, S. David, . Johnson, I. W. Computers et al., A guide to the theory of NP-completeness, Series of Books in the Mathematical Sciences, 1979.

R. Gouet, Martingale Functional Central Limit Theorems for a Generalized Polya Urn, The Annals of Probability, vol.21, issue.3, p.16241639, 1993.
DOI : 10.1214/aop/1176989134

H. Hwang, Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques, Thèse de doctorat, École polytechnique, 1994.

H. Hwang, On Convergence Rates in the Central Limit Theorems for Combinatorial Structures, European Journal of Combinatorics, vol.19, issue.3, p.329343, 1998.
DOI : 10.1006/eujc.1997.0179

S. Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process, Appl, vol.110, issue.2, p.177245, 2004.

S. Janson, Limit theorems for triangular urn schemes, Probability Theory and Related Fields, vol.65, issue.3, 2005.
DOI : 10.1007/s00440-005-0442-7

L. Norman, S. Johnson, and . Kotz, Urn models and their application An approach to modern discrete probability theory, 1977.

S. Janson, D. E. Knuth, and . Tomasz, The birth of the giant component. Random Structures Algorithms, p.231358, 1993.

S. Janson, Y. C. Stamatiou, and M. Vamvakari, Bounding the unsatisability threshold of random 3-SAT. Random Structures Algorithms, p.103116, 2000.

J. F. Kingman, Martingales in the Ok Corral, Bulletin of the London Mathematical Society, vol.31, issue.5, pp.601-606, 1999.
DOI : 10.1112/S0024609399006098

M. Lefteris, E. Kirousis, D. Kranakis, . Krizanc, C. Et-yannis et al., Approximating the unsatisability threshold of random formulas. Random Structures and Algorithms, p.253269, 1998.

A. C. Kaporis, L. M. Kirousis, G. Et-efthimios, R. Lalas-möhring, and R. Et-raman, The probabilistic analysis of a greedy satisability algorithm, Lecture Notes in Computer Science, vol.2461, p.574585, 2002.

A. C. Kaporis, L. M. Kirousis, Y. C. Stamatiou, M. Vamvakari, and M. Zito, Coupon collectors, q-binomial coecients and the unsatisability threshold, 7th Italian Conference, volume 2202 de Lecture Notes in Computer Science, p.328338, 2001.

A. Kamath, R. Motwani, K. Palem, and P. Spirakis, Tail bounds for occupancy and the satisability threshold conjecture. Random Structures and Algorithms, p.5980, 1995.

[. Kotz, H. Mahmoud, and P. Robert, On generalized P??lya urn models, Statistics & Probability Letters, vol.49, issue.2, p.163173, 2000.
DOI : 10.1016/S0167-7152(00)00045-6

E. Donald and . Knuth, The art of computer programming Seminumerical Algorithms, 1969.

E. Donald and . Knuth, The art of computer programming

J. F. Kingman and S. E. Volkov, Solution to the OK Corral model via decoupling of Friedman's urn, J. Theoret. Probab, vol.16, issue.1, p.267276, 2003.

H. Mahmoud, Pólya urn models and connections to random trees : A review, 2005.

L. Meunier, Étude des transitions de phases en K-satisfaisabilité, 2000.

C. Olivier, R. Martin, R. Monasson, and . Zecchina, Statistical mechanics methods and phase transitions in optimization problems, Phase transitions in combinatorial problems, p.367, 1999.

J. Nicolas, An integral representation for Eulerian numbers. Dans Sets, graphs and numbers (Budapest, 1991), volume 60 de Colloq, Math. Soc. János Bolyai, p.513527, 1992.

G. Pólya, Sur quelques points de la théorie des probabilités, Annales Institut Poincaré, vol.1, p.118161, 1931.

[. Panholzer and H. Prodinger, An analytic approach for the analysis of rotations in fringe-balanced binary search trees, Annals of Combinatorics, vol.19, issue.2, p.173184, 1998.
DOI : 10.1007/BF01608487

V. Puyhaubert, Generating functions and the satisability threshold, Discrete Mathematics and Theoretical Computer Science, vol.6, issue.2, p.425436, 2004.

J. Simon, J. Carlier, O. Dubois, and E. O. Moulines, étude statistique de l'existence de solutions de problèmes sat, application aux systèmes-experts, p.283286, 1986.

T. J. Schaefer, The complexity of satisability problems, Conference Record of the Tenth Annual ACM Symposium on theory of computing, p.216226

R. T. Smythe, Central limit theorems for urn models. Stochastic Process, Appl, vol.65, issue.1, p.115137, 1996.

R. P. Stanley, de Cambridge Studies in Advanced Mathematics, Enumerative combinatorics, vol.1, issue.49, 1997.

B. L. Van-der-waerden, On the method of saddle points, Applied Scientific Research, Section B, vol.67, issue.1, p.3345, 1951.
DOI : 10.1007/BF02919754

[. Williams and P. Mcilroy, The Ok Corral and the Power of the Law (A Curious Poisson-Kernel Formula for a Parabolic Equation), Bulletin of the London Mathematical Society, vol.30, issue.2, p.166170, 1998.
DOI : 10.1112/S0024609397004062

A. C. and C. Yao, On random 2?3 trees, Acta Informatica, vol.1, issue.2, p.15917078, 1977.
DOI : 10.1007/BF00289075