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)

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
36 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
68 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 ...
-1
votes
3answers
38 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.
11
votes
2answers
103 views

Students who see ears of another student

A student is standing in each cell of an $n\times n$ grid, looking at one of the four directions: up, down, left, right. It turns out that no student is at the border and looking out of the grid, and ...
2
votes
1answer
42 views

Counting permutations of a multiset restricted by nearness condition

I've been scratching the noggin on this for a bit, and have come up blank so far. Given a multiset $S$ with $Z$ zeros and $O$ ones, how many permutations are there where there is at least one pair of ...
2
votes
1answer
98 views

Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair

Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of ...
2
votes
2answers
36 views

Number of winning tern in a deck of cards and other 3 related questions

There is a deck made of $81$ different card. On each card there are $4$ seeds and each seeds can have $3$ different colors, hence generating the $ 3\cdot3\cdot3\cdot3 = 81 $ card in the deck. A tern ...
3
votes
4answers
188 views

Formula for $1! \times 2! \times \cdots \times n!$?

Are there any useful forms for the expression $1!\cdot 2!\cdot 3!\cdot ...\cdot n!$? I'm trying to solve a problem that involves this expression and thought it might help to find a more "workable" ...
1
vote
1answer
16 views

Birthday problem: Let X be number of people needed for a match. Find the PMF of X.

(Introduction to Probability, Blitzstein and Nwang, p.128) People are arriving at a party one at a time. While waiting for more people to arrive they entertain themselves by comparing their ...
0
votes
3answers
36 views

Probability question - arranging 20 pupils in a row - 8 boys and 12 girls

We have 20 pupils in class, 12 girls and 8 boys. We arrange the pupils in a row, and now need to calculate the following probability: a. The probability that Jana, one of the girls, will not stand ...
3
votes
1answer
36 views

Finite abelian groups (application of structure theorem)

Problem Find all finite abelian groups that simultaneously have exactly $7$ elements of order $2$, exactly8 elements of order $3$, exactly $8$ elements of order $4$, at least an element of order ...
3
votes
2answers
63 views

Calculate $\sum_{j=0}^k\binom {2k+1}{2j+1}^2=?$

Knowing that: $${2k\choose k}=\sum_{j=0}^k{k\choose j}^2.$$ calculate the sums: $$\sum_{j=0}^k\binom {2k+1}{2j+1}^2=?$$ Any sugestions please? Thanks in advance.