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)

0
votes
1answer
50 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
2
votes
1answer
81 views

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+…+|x_{n}| \leq t$ have?

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+...+|x_{n}| \leq t$ have? We know that: $x_{i} \in Z,\ \forall i \ 0\leq i \leq n \ and \ t\geq0.\ $ I know that if we ...
1
vote
1answer
40 views

Geometric distribution example (making kids until couple has a boy and a girl), need explanation

So the condition is following: a man and a woman want to have kids : girl and a boy. They continue to make kids until they get both genders. What is the expected number of kids? As I remember, the ...
1
vote
0answers
31 views

Same problem solved with linearity of expectation and Hypergeometric distribution. Need explanation…

Here is the problem: There is population of size S. Select two independent samples A and B. A size = n B size = m. What is the expected overlap between A and B? $E$[overlap between $A$ and $B$] $=$ ...
3
votes
1answer
106 views

Ways of getting three of a kind in a 52 card deck

This question has probably been asked before, but just to be clear here, I am NOT asking for the answer, I know the answer. What i want to know is why my solution is not equivalent to the actual ...
9
votes
2answers
167 views

Sets $S_i$ such that $|S_i\cap S_j|\geq4$

Let $A=\{1,2,\ldots,1600\}$, and let $S_1,S_2,\ldots,S_{16000}$ be subsets of $A$ such that $|S_i|=80$ for all $i$. Show that for some $i\neq j$, we have $|S_i\cap S_j|\geq4$. I want to suppose for ...
4
votes
1answer
75 views

Number of ways to choose 6 books out of 20 books such that no 2 are adjacent books

I was trying to do the following question: Describe a bijection between ways of choosing 6 books out of 20 books so that no two adjacent books are selected and a 15-bit sequence with exactly 6 ...
1
vote
2answers
145 views

Total $3$-digit odd number combinations from $1,2,3,4,5,6$

How many three digit numbers can be formed from the digits $1,2,3,4,5$ and $6$, if each digit can only be used once? How many of these are odd numbers? How many are greater than $330$? I've ...
1
vote
1answer
30 views

Probability of winning a game similar to bingo

I was trying to do the following question: I have attached the solutions and I am specifically confused about how they got the $${20 \choose 2}$$ the numerator of the first part. I usually post ...
3
votes
1answer
43 views

Combinatorics problem with “at least” condition

I had a regular combinatorcics exercise to solve and I thought it's possible to solve it in two ways but it turned out that only one way is correct. It is: A team of 4 students is to be selected for a ...
1
vote
1answer
32 views

What are the number of possible partitions of a set containing n elements?

This question rises immediately if we try to enumerate the number of possible equivalence relations on a set with n elements.
1
vote
3answers
2k views

The basic of the count

(a) A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are ...
0
votes
1answer
28 views

investing in three stocks with minimum investment

An investor wishes to invest up to ¤12K in three different stocks. Each investment must be made in units of ¤1K. How many different possible investment strategies does he have?
3
votes
1answer
45 views

Combinatorial Problem about putting foxes in a $n\times n$ table

Let $n$ be an integer with $n\geq 2$. $k$ foxes are put into $n \times n$ table, and each $1 \times 1$ square has at most $1$ fox. They are put in such a way that each $2 \times 2$ table has exactly ...
1
vote
1answer
51 views

Find number of pairs satisfying given absolute difference and product

If I'm given absolute difference of two numbers and their product, how can I determine the number of ordered pairs possible? What I have thought is - Total number of pairs possible may be 4, 2 or 0. ...
0
votes
1answer
65 views

Identity of sum of binomial coefficients

I'm struggling to understand the following derivation where $n$ is a positive integer. $$ \sum_{\ell=0}^n {n \choose \ell} 2^\ell \log 2^\ell = n \sum_{\ell=0}^{n-1} {n-1 \choose \ell} 2^{\ell+1}. $$ ...
1
vote
3answers
755 views

What does the “n choose multiple numbers” symbol stands for?

The question is: How many ways can you align 3 red balls, 2 blue balls and 2 yellow balls ...
4
votes
2answers
99 views

How do the answers to combinatorial problems change if instead of 4 different objects we have 4 identical ones?

I think I did the first parts of these correctly, but I really don't know about the last part? Could I just divide all my previous answers by $4!$ If you have $4$ children, $8$ unique fruit, and $8$ ...
0
votes
1answer
36 views

Why is my answer to this multichoose counting problem wrong?

I'm having trouble with the following problem: An ice-cream vendor sells eleven kinds of ice-cream. In how many different ways can I buy six cones, some or even all of which could be the same? I ...
1
vote
1answer
56 views

Prove or disprove this lemma for Catalan Numbers

Prove or disprove that for all non-negative integers $n$ and $r$ with $r+1$ is less than or equal to $n$, $C(n,r+1)=C(n,r)\times\frac{n-r}{r+1}$.
4
votes
2answers
92 views

Probability of having always flipped more $H$ than $T$ in an infinite coin flip sequence

A biased coin has probability $p \in [0,1]$ of landing heads ($H$) and hence probability $1-p$ of landing tails ($T$). We will flip this coin infinitely many times, obtaining a sequence ...
1
vote
2answers
59 views

How many ways are there to place 7 distinct balls into 3 distinct boxes?

How many ways are there to place $7$ distinct balls into $3$ distinct boxes? is the question I'm confused about. The solution shows that the correct answer is $3^7$. I'm just confused why this is. ...
15
votes
1answer
571 views

The 'Unlock All Digits' Game

I challenged myself and thought of a new problem I tried to solve. Here are the rules : The goal is to 'unlock' all the numbers $0,1,2,3,4,5,6,7,8$ and $9$ When you start the game, the only number ...
0
votes
0answers
32 views

Taking independent sets of two numbers of four, two at a time without replacement or repeating integers.

I am using a database that selects unique class schedules for, four selected classes. The sql works by splitting up the query into smaller sets for simplicity. It takes the intersection of classes ...
2
votes
1answer
91 views

Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed. Progress Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1 $ ...
0
votes
0answers
17 views

Can a set of schedules with conflicting times be represented using combinatorics

Suppose I have a set of data from a database that is all class schedules for a given set of four classes that have non-conflicting times. Can I derive an equation that will represent all possible ...
1
vote
1answer
47 views

Number of permutations of m objects taken out of n objects where an object can repeat any number of times.

I'm given $n$ distinct objects. In how many ways can we select and permute $m$ objects out of those $n$ objects. $n$ may be less than $m$ and any object can appear any number of times. For example: ...
2
votes
1answer
115 views

How to prove this Catalan number identity

Catalan number is $\displaystyle C_n= \frac{1}{n+1}\binom{2n}{n}$. How to prove that $$C_{2n-1} = \sum_{k=0}^{n-1}\left(\binom{2n-1}{n-k-1}-\binom{2n-1}{n-k-2}\right)^2$$ for $n\geq 1$. Thank you.
1
vote
0answers
88 views

Induced cycle of odd length in a large graph

I'm trying to prove the following result in order to solve a different problem but I'm stuck; however I'm not sure if it is true, so I'll pose it as a question; Suppose we have a triangle-free ...
6
votes
2answers
965 views

Lights Out Variant: Flipping the whole row and column.

So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so: 1 0 0 00 0 0 00 1 0 0 0 0 1 0 When you selected a ...
4
votes
3answers
149 views

How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?

The following combinatorial identity have been verified via maple, but I can not prove it. Who can prove it without WZ mehtod? $$\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose ...
0
votes
2answers
233 views

There are 14 students: 8 girls and 6 boys. In how many ways can you make a 4-student committee which has at least one boy?

In a group of 14 students there are 8 girls and 6 boys. Determine the number of ways that a committee of 4 students which has at least 1 boy can be chosen from the group. Here is what I have so far: ...
1
vote
3answers
396 views

Find the number of pathways from A to B if you can only travel to the right and down.

I would like to solve the following, using Pascal's Triangle. Since there are shapes withing shapes, I am unsure as to where I should place the values. EDIT 1: Where do I go from here? How do I ...
0
votes
0answers
99 views

What is the sum of the divisors of 14,601,359?

What is the sum of the divisors of 14,601,359? $$14,601,359^2 -1 = 213,204,941,168,520$$ I'm not too sure if my calculation or logic is correct.
3
votes
1answer
116 views

How many different paths can the ball take as it falls from top to bottom?

How many different paths can the ball take as it falls from top to bottom? I've shown my work below; I am wanting to make sure that I've applied Pascal's Triangle to this shape correctly. Honestly, ...
1
vote
2answers
84 views

Sum over product of two binomial distributions

The problem is that of a two-stage "binomial experiment", where first a number $k$ out of $n$ is drawn (each element with probability $p_1$) and later a number $m$ out of those $k$ is drawn (each ...
1
vote
3answers
59 views

Taylor Series of a Complex Function

Consider the function $$ \exp\left(\frac{z}{1-z}\right). $$ Since this is holomorphic for $|z|<1$, then it has a Taylor Series valid for $|z|<1$, i.e., $$ ...
0
votes
2answers
30 views

Length required to get equivalent password security based on available character set

I understand a password of length 12 is very secure if each character is independent of the others and it potentially mixes the 26 lowercase, 26 uppercase, 10 digits, and 32 typeable special ...
1
vote
2answers
70 views

In how many ways can I merge $m$ and $n$ items without disturbing the order in each group?

I have two lists having all distinct elements. One contains $m$ elements and other contains $n$ elements. We need to arrange them such that the order of elements of individual lists is not disturbed. ...
1
vote
1answer
41 views

How many ways are possible to place k items in n spots such that order of k items is not disturbed

I have k items, need to place them in n spots(n>k). In how many ways can this be done? Example - for k=2 and n=4, these are the possibilities assuming items to be like this [1,2] 12-- 1-2- 1--2 -12- ...
0
votes
0answers
34 views

Orbit closure is uncountable, unless there is a periodic element.

Let $a = (a_i)_{i \in \mathbb N}$ be a sequnece over some finite alphabet $\Sigma$. We may define on the space $X = \Sigma^{\mathbb N}$ a shift operation by $(Sx)_i = x_{i+1}$. Let $A$ be the orbit ...
1
vote
1answer
41 views

Calculate number of solutions

Count number of integral solutions of the equations $\sqrt{K-x^2} \geq 0$ where $x$ Is any variable and $K$ is any positive integer?(also the value of $\sqrt{K-x^2}$ should be an integer).
4
votes
1answer
109 views

Proper Bernoulli Function Generating Function [duplicate]

Consider the function $$\frac{t}{e^t - 1} = \sum_{i=0}^{\infty}\frac{B_i}{i!}t^i$$ This has been one of the famous generating functions for the bernoulli numbers. What about the function associated ...
1
vote
1answer
50 views

Number of different normalized inner products?

Let $u,v\in\{0,1\}^n$ be $0-1$ vectors with $n$ components. Let $I=\langle u,v \rangle$. Clearly $I$ can take values in $\{0,1,\dots,n-1,n\}$. How many different values can $$I'=\frac{\langle u,v ...
3
votes
1answer
70 views

Let there be 9 fixed point on the circumference of a circle.

Let there be 9 fixed points on the circumference of a circle. Each of these points is joined to every one of the remaining 8 points by a straight line and the points are positioned on the ...
4
votes
3answers
390 views

pidgeonhole problem need assistance

Suppose you have a sequence 2014, 20142014, 201420142014, . . . Show that there is an element in this sequence such that it is divisible by 2013. This is a problem I had on an exam and I know that ...
1
vote
3answers
7k views

Formula for number of lines you can draw through $n$ points

So I've got a homework question I'm stuck on. It's asking me to develop a formula that when given $n$ points, it gives the number of straight lines that can be drawn through those points. For ...
3
votes
3answers
176 views

AHSME 1981 #22 - Number of lines that pass through four distinct points

How many lines in a three dimensional rectangular coordinate system pass through four distinct points of the form $(i, j, k)$ where $i$, $j$, and $k$ are positive integers not exceeding four? ...
1
vote
2answers
42 views

Unique combinations of strings

If I have the string Delaware and I want to figure out how many unique strings can be made from the letters in this word, I know that the answer is 8!/(2!)(2!) and that the reason we divide by 2! and ...
-1
votes
3answers
45 views

No. of different possible arrangements.

How can I find no. of different possible arrangements with the factor of the term $a^2b^4c^5$ written at full length.