For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
1answer
5k views

Distinguishable/indistinguishable objects and distinguishable/indistinguishable boxes

How many ways are there to distribute 5 balls into 7 boxes if each box must have at most one in it if: a) both the boxes and balls are labeled b) the balls are labeled but the boxes are not c) the ...
0
votes
6answers
2k views

Combinatorial proofs: having a difficult time understanding how to write them out

Can someone explain how combinatorial proofs work? I've included an example questions that's been giving me a hard time. Any insight on the topic would be great. $$\sum_{k=1}^{n}k{n \choose k} = ...
4
votes
1answer
147 views

Showing two generating functions to be equal

Let $\mathcal{A}$ be the set of partitions in which each part may occur 0, 1, 4, or 5 times and let $\mathcal{B}$ be the set of partitions which have no parts congruent to 2mod4, and in which parts ...
1
vote
1answer
608 views

Integer solutions to linear equation – Triangle with set perimeter

We have a triangle with the sides a, b and c where: ...
0
votes
1answer
462 views

Multiple choice questions on relations and some of their properties

I'm confused about these 3 selected problems. I have the solutions for each, if necessary, but I'm much more interested in understanding the material. If anyone can offer a clear, concise, and ...
1
vote
3answers
9k views

Number of subsets of a set having r elements

We have studied the standard way of ascertaining the total number of subsets of a set by using the concept of combinations ( or binomial coeffecients ). I came across an alternate derivation for this ...
2
votes
3answers
49 views

Counting small subsets of a given set

Denote by $P_n$ the set of all subsets of $\lbrace 1,2,3, \ldots ,n \rbrace$. Obviously, the proportion of subsets in $P_n$ of size $\leq \frac{n}{2}$ tends to $\frac{1}{2}$. What about the proportion ...
6
votes
1answer
278 views

Creating generating functions for integer partitions

Say I have a generating function $\Phi_\mathcal{A}$ for the set of partitions $\mathcal{A}$ which have no parts congruent to 2 mod 4, and I have the generating function for $\Phi_\mathcal{B}$ for the ...
3
votes
3answers
53k views

how many ways can the letters in ARRANGEMENT can be arranged [closed]

In how many different ways can the letters in the word ARRANGEMENT be arranged?
1
vote
1answer
111 views

Upcoming exam! Any good sources to learn about counting techniques and discrete probability?

If anyone has a free, online source to contribute for a certain topic/topics, please share! I'm not really looking for an intense theoretical grasp of these topics, just an intuitive understanding of ...
2
votes
3answers
196 views

Are there five complex numbers satisfying the following equalities?

Can anyone help on the following question? Are there five complex numbers $z_{1}$, $z_{2}$ , $z_{3}$ , $z_{4}$ and $z_{5}$ with ...
1
vote
3answers
1k views

Trouble understanding equivalence relations and equivalence classes…anyone care to explain?

What exactly are equivalence relations and equivalence classes? The latter is giving me the most trouble; I've tried to read multiple sources online but it just keeps going over my head. Example ...
1
vote
3answers
424 views

Discrete Math - Counting

Prove that among any 100 integers there are always two whose difference is divisible by 99. How can I prove this?
0
votes
1answer
81 views

Ordered set of integers

$\{x_i\}_{i = 1}^7$ is a set of 7 integers that satisfy $1≤ x_i ≤ 8$. How many such ordered sets of $7$ integers are there, such that $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 - x_1x_2x_3x_4x_5x_6x_7 ...
1
vote
3answers
251 views

Intuitive understanding of relations and their basic properties

Can anyone explain relations and the four basic properties of them (reflexive, symmetric, antisymmetric, transitive)- or direct me to a source that does. Particularly, are these statements ...
1
vote
1answer
111 views

Probability of occurring

The numerial key for a specific safe is four digits long. The digits must be numbers from $1$ to $6$. (an example will be 4321 or 2564) a) I threw a die randomly $4$ times. What will be the ...
7
votes
1answer
2k views

Asymptotics of binomial coefficients and the entropy function

I found a question while I was trying to practice Combinatorics and Probabilistic methods.I tried to solve it with no success.. this is the question: Use the Stirling approximation of the ...
0
votes
3answers
420 views

Sum of combinations

Trying to prove, for all $k$ and $n$, $$\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}.$$ I have tried solving it through induction, but is there a cleaner non-induction based solution to this?
0
votes
2answers
249 views

Count the number of ways to arrange the balls

There are $12$ different boxes which has number from $1$ to $12$ and $8$ same balls. Ask how many way to arrange these $8$ balls to $12$ boxes such that, the sum of balls in box $1;2;3$ is even ...
2
votes
3answers
138 views

Discrete Math HW (Stuck)

I have no idea how to begin the following problem Nautical flags are specially designed flags made up of several colors which can be used to signal from ship to ship, or ship to shore. Suppose there ...
1
vote
1answer
140 views

graphical representation of all combinations

i read the wikipedia article on combinations and saw two drawings there and i am asking myself whats the points of them, does they make something easier to comprehend. Yes there is a pattern, but ...
0
votes
2answers
32 views

Which is the algorithm to calc possible sets?

Example: I have a set {a,b,c}. I want to know how many different sets could I get from these elements. -Ex: {a,b} , {a,c} , {a}, {b} , {c} , {b,c} and {a,b,c} itself Which is the algorithm ? and ...
1
vote
1answer
517 views

Intuition behind Yahtzee probabilities (ie…getting 3 of a kind when rolling 5 dice)

The number of ways of getting three of a kind $(x, x, x, y, z)$ when rolling 5 dice is - $${5 \choose 3}{2 \choose 1}{6 \choose 1}{5 \choose 2}$$ ${5 \choose 3}$ - Ways of choosing dice for the ...
1
vote
0answers
42 views

Combinatorial Proof Method [duplicate]

Possible Duplicate: Proof for formula for sum of sequence $1+2+3+\ldots+n$? I have a question: Show that $$1+2 + \cdots+ n = \binom{n+1}{2}$$ This is a combinatorial proof. Here is my ...
1
vote
1answer
412 views

Integer Partitions Formulas [duplicate]

Possible Duplicate: Identity involving partitions of even and odd parts. How would I go about to show the following: Let $pe(n)$ be the number of partitions of size n with an even number of ...
1
vote
0answers
183 views

Does this hold?

Strayed on the following question. Assume that $x_{1}$,$\ldots$, $x_{d}\ge0$ with $x_{1}+\ldots+x_{d}=1$ and $y_{1},\ldots,y_{d}\in\mathbb{R}$. Does $$ \min_{1\le i\ne j\le ...
2
votes
1answer
320 views

approximation of binomial coefficient sum

I would like to find some approximation or upper & lower bounds on the next simple expression: \begin{align} \sum_{i = 0}^{k} \binom{h}{i} \qquad h \geq k \end{align} But I need this ...
4
votes
2answers
617 views

Generalizing the Catalan Numbers

Preliminaries There are many equivalent definitions of the Catalan Numbers. I'll use this one: A Dyck Word is a string consisting on $n$ X's and $n$ Y's such that no initial segment of the string ...
6
votes
1answer
149 views

Product of binomial coefficient as a basis

I am stuck with the following problem. Every polynomial of degree $d$ can be expressed as $$ p(x) = p_d \binom{x}{d}+ p_{d-1}\binom{x}{d-1} + \cdots + p_0 \binom{x}{0} $$ What is the ...
5
votes
0answers
126 views

divisibility by powers of $2$ of diagonal sums of infinite latin square

This array is formed by placing integers such that each is the smallest such that the rectangle with it and the top left hand corner as opposite corners does not contain the same integer twice in any ...
0
votes
1answer
59 views

About the existence of a partition to a partially ordered set $A$.

Let $A$ be a countable set equipped with a partial order $\prec$. We all know that there are subsets $C\subset A$ with the property that the order $\prec$ in $C$ is total. In other words, any two ...
2
votes
1answer
191 views

Generalized Catalan Numbers

I'm concerned here with Catalan numbers. There are many combinatorial interpretation of these numbers. Here I would focus on the interpretation around words build with 2 symbols, let say [ and ]. The ...
1
vote
1answer
281 views

Setting A Paper on Mathematical Puzzles

I need to set a paper for High School Students on Mathematical Puzzles which make the use of logic, simple combinatorics and algebra. Can people provide new and innovative questions. The questions ...
9
votes
1answer
259 views

(Olympiad) Minimum number of pairs of friends.

I gave up, my approaches didn't work (induction, pigeon-hole, parity; though obviously there's a good chance I didn't use them cleverly): In a group of 12 people, every pair of them has a common ...
1
vote
2answers
219 views

Sum of four numbers less than a particular value

I have four positive numbers $a_1,\dots,a_4$, each less than $45$. How many different ways are there for $a_1+a_2+a_3+a_4<90$? I require different permutations i.e $a_1a_2a_3a_4$ is different from ...
13
votes
1answer
5k views

Odd and even numbers in Pascal's triangle-Sierpinski's triangle

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. I recently learned that when the Pascal's triangle is reduced ...
2
votes
1answer
158 views

Basic Binomial Coefficient Manipulation

Could someone help me manipulate this sum? I need to be able to extract the coefficient of $x^{n-1}$ in the following: $\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{n-1}{i}\binom{n+j-1}{j}x^{i+2j}$. ...
2
votes
3answers
226 views

Extract Coefficients From A Function

So I am trying to determine the average number of nodes with an even amount of children in a plane planted tree with n nodes. I created the generating function, did some manipulation, then applied ...
1
vote
2answers
41 views

Simple linear recursion

$x_n=\frac{x_{n-1}}{a}+\frac{b}{a}$ with $a>1, b>0$ and $x_0>0$ I tried to solve it using the generating function but it does not work because of $\frac{b}{a}$, so may you have an idea.
1
vote
2answers
124 views

Inequalities and binomial coefficients

Does anybody know a proof of the following assertion? The number of solutions to the inequalities $1 \leq x_{1} \leq x_{2} \leq \ldots \leq x_{i} \leq n$ is $\binom{n+i-1}{i}$. I would appreciate ...
0
votes
1answer
121 views

Count the number of group $(x_1;x_2;x_3;…x_c)$

How many groups $(x_1;x_2;x_3;...x_c)$ satisfy that: $$\begin{cases} x_i \in \{1;2;...;m\} \ \forall i \\ x_2 \le x_3 \le x_4 \le ... \le x_c \\ x_2 < x_1 \end{cases}$$ With m,c $\in N (m>c)$
2
votes
3answers
107 views

Number decomposition

Recently I encountered a problem I was not familiar with. So hope someone can help me for this. Here is the problem. Given any odd integer, how many different ways of decomposition into sum of three ...
1
vote
2answers
56 views

Would cartesian product be the best approach for this

Not sure on how to migrate a question yet but over on SO someone said I might get better results here. Also please retag as I'm not allowed to create new and might not know the best tagging. Link to ...
2
votes
1answer
308 views

How many ways are there of coloring the vertices of a regular $n$-gon

How many ways are there of coloring the vertices of a regular $n$-gon with all $p$ colors ($n,p \ge 2$), such that each vertex is given one color, and every color isn't used for two adjacent vertices? ...
1
vote
1answer
103 views

Counting ordered selection with repeats allowed

You are given a sack containing $n$ red balls and $n$ blue balls. You take the balls out of the sack one by one and write down the sequence of reds and blues you get. How many sequences are possible?
2
votes
1answer
171 views

Another Bijective proof for Fibonacci Identities

I'm going through a past exam, and this question popped up: Prove: $3P_n = P_{n-2} + P_{n+2},\,n>2$ Where $\tilde{P}_j = \{\textrm{monomer-dimer pavings on a } 1\times j \textrm{ board}\}$ and ...
1
vote
0answers
41 views

I have N objects and I want to know which one is the heaviest and lightest

Say I only want to know the heaviest. If I have a balancing scale, that will require N-1 balancing scale. If I want to know the lightest. Same. What about if I want to know both the heaviest and ...
2
votes
1answer
245 views

Bijective Proof of a Fibonacci Identity

Prove (Using bijections): $F_{1}+F_{3}+\cdots+F_{2n-1}=F_{2n}$ Where $F_{i}$ is the $i$th Fibonacci number. Apparently you use monomers and dimers to prove this, but I don't really know what to ...
6
votes
2answers
316 views

How many partial order on a n-set?

Let $A$ be a set has $n$ element, my question is how many partial order on it? For $n=0,1$, $N_P(n)=1$ Case $n=2$, $N_P(n)=3$ Case $n=3$, $N_P(n)=19$ Is there a general formula? Update: It seems ...
0
votes
2answers
2k views

How many tries to get at least k successes?

The probability $P'$ of getting at least $k$ successes in $n$ independent tries, given probability of a single success $s$, equals one minus the summed probabilities of getting only $0$ to $k-1$ ...