This tag is for basic 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
19 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
25 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
20 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
18 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
42 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
24 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
29 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
590 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 ...
3
votes
3answers
81 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
28 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 ...
0
votes
1answer
55 views

Combinations. x+y+z=12 [closed]

X+y+z=12 x,y,z are all greater or or equal to 0 and are integers No. of combinations of x,y,z are ............. *note-- (12,0,0) and (0,12,0) are treated as same Please solve this by using formulae ...
0
votes
2answers
21 views

Determine the number of integral solutions of the equation

Let ${x_1 + x_2 + x_3 + x_4}$ = 20 which satisfy: 1 $\leq$ $x_1$ $\leq$ 6, 0 $\leq$ $x_2$ $\leq$ 5, 4 $\leq$ $x_3$ $\leq$ 9, 2 $\leq$ $x_4$ $\leq$ 7. Determine the number of integral solutions. I ...
1
vote
1answer
37 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
70 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
27 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. ...
-1
votes
0answers
11 views

Counting problem: 4 members of a committee that must elect a prez and secretary, …? Use Addition Principle [closed]

A committee composed of Mo, Ty, Ma, and Le is to select a president and secretary. How many selections are there in which Ty is president or not an officer? Use the Addition Principle.
15
votes
1answer
556 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
30 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 ...
1
vote
1answer
69 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 $ ...
5
votes
2answers
92 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
0
votes
0answers
15 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
25 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: ...
1
vote
1answer
82 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
27 views

Find the number of combinations to host 4 teams, with restrictions [closed]

Four teams A, B, C, and D should be allocated rooms in a hostel. Each member will have separate room. Each team has K members. It is entrusted that there are 4K side-by-side rooms in one long corridor ...
1
vote
0answers
67 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
685 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
122 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
22 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
67 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
95 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.
-1
votes
3answers
73 views

Understanding combinatorics [closed]

1: There are $3$ distinct groups of $8$ people. How many ways can the groups be divided into triples each consisting of $1$ person from each group? Keep in mind I'm literally taking a stab in the ...
3
votes
1answer
28 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
37 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
52 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., $$ ...
5
votes
0answers
208 views

Minimal number of moves needed to solve a “Lights Out” variant

Lights Out was a popular puzzle in which all lights in some device had to be turned off by pressing on them, which turned off all neighbouring lights as well. We consider instead the same variant ...
0
votes
2answers
25 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
37 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
32 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
19 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
39 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
89 views

Proper Bernoulli Function Generating Function

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
39 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
42 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 ...
1
vote
1answer
380 views

Divide a set of $n$ elements into $k$ subsets having equal sum

Given $n$ ( $n$ <= 20) non-negative numbers. Is there / Can there be an algorithm with acceptable time complexity that determines whether the n numbers can be divided into $k$ ( $k$ <= 10) ...
-1
votes
0answers
31 views

A new proof for Combinatorial Nullstellensatz

Can somebody check the "new" proof? Or has the proof appeared before?
4
votes
3answers
365 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
5k 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
136 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
32 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 ...