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

Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$ [closed]

Let $r,w \in \mathbb{N}$. Are there some formula for the next sum? $${r \choose 1}+{r \choose 2}\cdots{r \choose w}$$ where $w<r$?
3
votes
3answers
85 views

Combinatorial identity's algebraic proof without induction. [duplicate]

How would you prove this combinatorial idenetity algebraically without induction? $$\sum_{k=0}^n { x+k \choose k} = { x+n+1\choose n }$$ Thanks.
0
votes
2answers
24 views

Formation of Teams in Permutation and Combination

A class has $n$ students , we have to form a team of the students including at least two and also excluding at least two students. The number of ways of forming the team is My Approach : To include ...
1
vote
1answer
33 views

Counting problem: How many triangles?

Sixteen points are on the sides of a $4\times 4$ grid so that the center portion of $2\times 2$ are removed. How many triangles are there in total that have vertices chosen from those remaining points ...
0
votes
2answers
24 views

Colors on sets $S=\{1,2 \cdots ,1000\}$.

To each element of sets $S=\{1,2 \cdots ,1000\}$ a color is assigned. Suppose that for any two elements $a$ and $b$, of $S$,if $15$ divides $a+b$, then they both are assigned with same color. What is ...
-1
votes
2answers
68 views

How many 3 digit numbers that the sum of their digits equals 12?

How many positive 3-digit numbers exist such that the sum if their digits equals 12? A) 54 B) 61 C) 64 D) 65 E) 66 I believe the answer is E. Online problems state that is a stars and bars ...
0
votes
2answers
38 views

How to prove that ${l \choose a_1,…,a_n}\le n^{l-1} $ , when $a_1+…+a_n=l$.

In the proof of (Corollary 8 chap. 3 ) in the book "Sobolev Spaces on Domains" by Burenkov the following inequality is used : given $a_1,...,a_n \in \mathbb{N}$ such that $a_1+...+a_n=l$, then $${l \...
0
votes
1answer
42 views

In how many ways can $5$ Indians, $4$ Chinese, and $3$ Americans be assigned to $12$ stations so that no two Americans serve at consecutive stations?

On a railway route from Delhi to Jaipur there are $12$ stations . A booking clerk is to be deputed for each of these stations out of $12$ candidates of whom $5$ are Indians , $4$ are Chinese and the ...
2
votes
3answers
73 views

Looking for a proof of a combinatorial relation

While working on a problem, I needed to calculate the following sum $$ n!\sum_{n_i\ge1}^{\sum_i n_i=n} \prod_i \frac{x_i^{n_i}}{n_i!} \tag{*} $$ where $i$ runs from 1 to $m$. After some playing ...
-1
votes
4answers
46 views

How many mixed double pairs can be made from 7 married couples provided that no husband and wife plays in a same set?

So for first man there can be 7 possible partners including his wife, for the next man there will be 6 possible partners and so on, therefore for $7$ men and $7$ women, there will be $7!$ possible ...
1
vote
3answers
2k views

Intuitively explaining the difference between a combination and permutation

I'm having a hard time trying to determine when to use combination and when to use permutation with a problem. Can someone offer a clear and concise explanation or general rules to follow so I don't ...
0
votes
1answer
38 views

How to reduce $f(k, n)$ to $\operatorname{fibonacci}(n)$?

Let's define $f(k, n)$ $f(0, n) = f(0, n - 1) + f(1, n - 1)$ $f(1, n) = f(0, n - 1)$ $f(k, 1) = 1$, for every $k$. $k$, $n$ $\subset \mathbb N$, for $0 \le k \le 1, n \ge 1$. I noted that $f(k, ...
0
votes
1answer
27 views

How do I interpret following equations on fibonacii numbers?

I went through an online tutorial (http://codeforces.com/blog/entry/14385) on finding n-th fibonacci number which explains a method as, You are standing at position n in Ox axis. In a step, ...
10
votes
4answers
3k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
10
votes
1answer
2k views

Triangle dissection, no shared edges

It's possible to divide a triangle into smaller triangles such that no edge lengths are shared. Alternately, no two internal triangles share two vertices. The top three are the known simplest ...
3
votes
1answer
2k views

hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem. Suppose that each of $N$ men at a party throws his hat into the center of the room. The hats are first mixed up, ...
3
votes
1answer
17k views

possible combinations of 3-digit

How many possible combinations can a 3-digit safe code have? Because there are 10 digits and we have to choice 3 digits from this, then we may get $10^P3$ but A author used the formula $n^r$, why is ...
2
votes
1answer
386 views

Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
1
vote
1answer
63 views

What is the probability of two-pair poker hand?

To start with, this question has never been asked as how I am going to ask: What is the probability that a five card poker hand will have two pairs (with no additional cards)? Example of two-...
3
votes
2answers
45 views

Material to learn some basic combinatorics?

I realize that I'm pretty weak when It comes to basic combinatorics, even with simple things like n choose k I don't feel confident. Furthermore, I've viewed some combinatorics books and the reasoning ...
2
votes
1answer
46 views

Calculating the number of “birthday days” in the birthday problem

Given 's' students in a room and 'd' days in the calendar year, what is the probability 'P' that there will be 'k' "birthday days"? i.e., 'k = 1' means that everybody's birthday falls on the same day,...
4
votes
1answer
408 views

Number of 'unique' one bit binary functions with N-bit inputs

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ...
4
votes
1answer
25 views

Find an explicit map with certain combinatorial properties

The following combinatorial problem popped up in a totally uncombinatorial context: Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\...
-1
votes
1answer
29 views

Number of solutions of the two equations

Find the number of integral solutions of the equation: $a+b+c=m$ with $0\gt a\gt b\gt c$ And the generalized version: $a_1 + a_2 + \cdots + a_k = m$ with $ 0\gt a_1\gt a_2\gt \cdots \gt a_k$
1
vote
1answer
17 views

Find a map on a power set with certain combinatorial properties

The following combinatorial problem popped up in a totally uncombinatorial context: Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\...
1
vote
2answers
47 views

How many attending puppy school are brown and have long hair but are not small?

Of the 24 dogs attending puppy school -6 are small -12 are brown -15 have long hair -1 is small and brown and has long hair -2 are small and brown but their hair is not long -2 are small and have long ...
10
votes
8answers
544 views

Proving $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially) It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone ...
1
vote
0answers
50 views

Homotopy type of some lattices with top and bottom removed

There was an interesting question on MO which OP removed by some reason. Here is a (more or less) equivalent form. Take a finite cartesian product of finite linear orders, and remove top and bottom. ...
4
votes
3answers
114 views

Books for maths olympiad

I want to prepare for the maths olympiad and I was wondering if you can recommend me some books about combinatorics, number theory and geometry at a beginner and intermediate level. I would appreciate ...
0
votes
1answer
37 views

counting number of steps using permutation-combination

We need to climb 10 stairs. At each support, we can walk one stair or you can jump two stairs. In what number alternative ways we'll climb ten stairs? How to solve this problem easily using less ...
1
vote
0answers
97 views

Counting zeros in a factorial(terminal + zeros in between digits)

The usual questions involving counting zeros in a factorial asks us to count only the terminal zeros. This question asks to count the zeros that are in between digits, for example, 8! (40320, has a ...
6
votes
2answers
115 views

Closed form for sequence A145271

I would like to know if there is a simple formula or method of expanding the expression given by $\left[g(x) \frac{d}{dx}\right]^n g(x)$ where $n$ is a positive integer, without having to resort to ...
1
vote
1answer
396 views

Maximum number of terms of a polynomial of degree n and p indeterminates

I am trying to figure out the maximum number of terms a polynomial have. This polynomial f has p indeterminates, the degree is maximum n and its quotients belong to an arbitrary field K. It would ...
2
votes
2answers
52 views

How many length-$k$ strictly decreasing sequences where sum is $N$?

How many strictly decreasing sequences of length $k$ in positive integers can I find where the sum of elements is $N$? The problem can be described this way too, I have a number $N$ . Now I want ...
2
votes
3answers
59 views

Number of binary strings of length $n$ satisfying specific (ad-hoc) conditions

Count the number of binary strings of length $n$ that satisfy the following additional conditions: a) Two zeroes in a row are not allowed b) Three ones in a row are not allowed c) The ...
1
vote
1answer
41 views

What is the probability that a majority vote gives the correct answer, given that we know the accuracy of each of the voters?

Let's say that we have 7 voters who are voting on a decision. Furthermore, we know that voter A makes the right decision with 10% probability. voter B makes the right decision with 20% probability. ...
7
votes
1answer
234 views

Puzzle: How Many Possibilities Are There Between Connected Points?

Puzzle Jenny drew on her page six points, as shown below: Jenny wants to build a cool match of her points. In a match , divide the six-point into pairs, so that each point has one partner exactly. ...
1
vote
0answers
55 views

Combinatorics problem involving binomial coefficient

I found this interesting problem in a Romanian mathematical magazine while preparing for the USAMO. Let $k$ be a non-zero natural number. Determine $x,y,z \in \Bbb N$ such that $$\binom {z+k}{x+y} - \...
1
vote
2answers
76 views

Is there a closed form for this binomial sum?

I am looking for a closed form of this sum:$\sum\limits_{j=k}^n\binom{j}{k}(-1)^j$ I know that this sum has a closed form: $\sum\limits_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$ I can get this closed ...
2
votes
0answers
23 views

Inclusion-exclusion principle for multisets

Lets say I want to count the number of monic polynomials of degree $d$ in $\mathbb{F}_p[X]$ that have no roots in $\mathbb{F}_p$. Fix a $1 \leq k \leq d$ and choose $k$ distinct elements of $\mathbb{F}...
1
vote
3answers
36 views

How to prove by induction(do not use differential) $(1-x)^{-n}=\sum^{\infty}_{k=0}\binom{n-1+k}{k}x^k$

I would appreciate if somebody could help me with the following problem. Q: How to prove by induction(do not use differential) $$(1-x)^{-n}=\sum^{\infty}_{k=0}\binom{n-1+k}{k}x^k$$ I tried to solve ...
1
vote
2answers
31 views

Distinct digits in a combination of 6 digits

How many 6-digit numbers contain exactly 4 different digits? My approach is: For any 3 digis same and the remaining 3 different(aaabcd) 4*9*8*7*6 For any 2 duplicate digits(aabb) and the remaining ...
2
votes
2answers
66 views

How many 6-digit numbers contain exactly 4 different digits? [duplicate]

my solution is----> NUMBER can be 777210 this i denote by aaabcd ------ this can be done in ---> 10*1*1*9*8*7*[6!/3!] {1 for a thrice} NUMBER can be 772210 this i ...
0
votes
0answers
17 views

Combinations over tree nodes

Assuming to have a generic tree, how can I calculate all the possible combinations of 1,2,3...n nodes (with n that represents the number of nodes at a certain level of the tree) that can be generated ...
1
vote
1answer
42 views

Find number $n(A)$? $A=\{(x,y,z)|x+2y+4z=n, x,y,z\in\{0,1,2,3,4,\cdots\} \}$

I would appreciate if somebody could help me with the following problem. Q: Find number $n(A)$? $$A=\{(x,y,z)|x+2y+4z=n, x,y,z\in\{0,1,2,3,4,\cdots\} \}$$ I tried to solve by $z=0,1,2,3,\cdots$ ...
4
votes
0answers
60 views

How many subsets of $n$ linearly independent binary strings of length $n$?

Let's consider binary words of length $n$ with elements {-1,1}. There are $2^n$ binary words of length $n$. Now let's consider a subset of $n$ such binary words. All possible subsets are $\binom{2^n}{...
2
votes
2answers
92 views

A 3-valued mathematical logic?

Classical propositional logic is consistent and in conformity with human language. A formal statement is true or not true and it is possible to develope rules with which it is possible decide which ...
7
votes
2answers
495 views

Probability question involving sets of cards

I have an infinite deck built out of sets of 10 cards (in other words 10*n cards). The sets are identical so one '2' is identical to another '2'. A player draws 6 cards. If he draws: any '1' AND a '...
1
vote
2answers
47 views

in urn A white balls and B black balls. what would be the probability of taking the 5th ball being white

the problem goes like that "in urn $A$ white balls, $B$ black balls. we take out without returning 5 balls. (we assume $A,B\gt4$) what would be the probability that at the 5th ball removal, there was ...
2
votes
1answer
61 views

Simplify this equation.

Can I simplify or approximate this equation without sigma and combination? \begin{align} \sum_{i = 0}^n (-1)^i {n \choose i} \frac{{d+1}}{d(di + 1)} \end{align}